腳本之家

你與百萬開發(fā)者在一起

作者 |?focuscode出品 | 腳本之家(ID：jb51net)

公司有位C++標(biāo)準(zhǔn)委員會(huì)的顧問大佬，一年會(huì)有幾次視頻講座，分享一些編程要點(diǎn)或者經(jīng)驗(yàn)。很多時(shí)候都是C++很基礎(chǔ)的方面，但是他的講解視頻真的很深入淺出，有時(shí)候會(huì)“打破”一些理所應(yīng)當(dāng)?shù)挠^點(diǎn)，這篇文章就是讓我覺得很有趣，并且意想不到的地方，在這里分享一下。

1. 非關(guān)聯(lián)容器

在我們看到的眾多數(shù)據(jù)結(jié)構(gòu)書籍中，最開始介紹過時(shí)間復(fù)雜度和空間復(fù)雜度后，接下來由簡入難，分別是數(shù)組，鏈表和樹。很多程序語言都提供了自己的標(biāo)準(zhǔn)實(shí)現(xiàn)，這里我們以C++為例。在C++標(biāo)準(zhǔn)庫(STL)中，有兩個(gè)基于堆分配的容器，分別對應(yīng)數(shù)組和雙向鏈表，std::vector和std::list。在后續(xù)的說明中，所有的實(shí)驗(yàn)都是基于這兩個(gè)容器，但是其適用于任何基于節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，不只是C++標(biāo)準(zhǔn)庫中的。開始之前，都知道這兩種數(shù)據(jù)結(jié)構(gòu)在內(nèi)存的中的存儲(chǔ)形式是不同的，數(shù)組在內(nèi)存中地址是連續(xù)的，鏈表的內(nèi)存地址是非連續(xù)的(如下圖)。

插入元素比較?

在數(shù)組中插入一個(gè)元素，需要將插入位置后面的元素向后移動(dòng)，時(shí)間復(fù)雜度是O(N)；但是向雙向鏈表中插入一個(gè)元素需要分配一個(gè)節(jié)點(diǎn)，并設(shè)置4個(gè)指針，時(shí)間復(fù)雜度是O(1)。自然，對于很大的常數(shù)N，在鏈表中插入要快速的多。

讀取元素比較

對于這兩種容器，按順序讀取所有元素的時(shí)間復(fù)雜度是O(N)。但是，數(shù)組的讀取速度仍舊比鏈表快。緩存(cache)和預(yù)取(prefetch)機(jī)制對數(shù)組讀取是有利的，但是對鏈表的讀取沒有任何幫助。

從理論上來說，以上的說法是正確的，但在現(xiàn)代計(jì)算機(jī)上，真正的性能是如何的？我們可以通過實(shí)驗(yàn)來驗(yàn)證，通過不停地修改N的值，該程序可以得到在數(shù)組和雙向鏈表的中間值右邊插入數(shù)值0所消耗的時(shí)間。所用機(jī)器配置如下圖:

#include#include#include#include#include#includeusingnamespace std;constsize_t N = 50000;int main(){doublestart_t, end_t; std::vector vec(N); std::list lst(N);//The vector and list has same N elementsfor(size_t i = 0; i < vec.size(); ++i){ vec[i] = i + 1; lst.push_back(i + 1);}//insert 100 right before the the first occurence of 3start_t= clock(); vec.insert(std::find(vec.begin(), vec.end(), 3), 100); //Tvend_t= clock(); std::cout << "vector cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl;start_t= clock(); lst.insert(std::find(lst.begin(), lst.end(), 3), 100); // Tlend_t= clock(); std::cout << "list cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl;return0;}

很明顯，這樣的線性搜索對于兩種容器來說都是O(N),正如我們已經(jīng)看到的，向vector插入一個(gè)元素是一個(gè)O(N)操作，向list插入一個(gè)元素是O(1)操作。向數(shù)組插入元素時(shí)，把少量的元素向右移動(dòng)代價(jià)是很小的，毫無疑問應(yīng)該期待Tv < Tl；但是當(dāng)N是多少時(shí)，移動(dòng)元素的代價(jià)會(huì)使Tl < Tv? 應(yīng)該存在這樣的一個(gè)臨界值N。下面的表格是插入元素的實(shí)驗(yàn)結(jié)果：

Sizestd::vectorstd::listlist/vector

10000	0ns	0ns	null
50000	0ns	1e+06ns	null
100000	0ns	2e+06ns	null
1000000	6e+06ns	2.1e+07ns	3.5
10000000	5.5e+07ns	2.03e+08ns	3.69
100000000	5.79e+08ns	2.169e+09ns	3.746
500000000	3.6342e+10ns	2.7049e+11ns	5.638

我們發(fā)現(xiàn)，沒有這樣的一個(gè)臨界值N，使得在雙向鏈表中插入元素比數(shù)組快。線性內(nèi)存訪問模式會(huì)使用CPU的pre-fetcher，其作為一個(gè)無限大小的LN+1緩存。但是指針節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)沒有這點(diǎn)好處，所以總是更慢一點(diǎn)。所以，如果你的關(guān)心迭代速度，就不要使用基于節(jié)點(diǎn)的容器，大多數(shù)情況下，程序更關(guān)注迭代速度。實(shí)際上，不管是插入或者刪除操作，當(dāng)你試圖去尋找正確的位置，這時(shí)程序就需要迭代。所以，一般不要使用鏈表。

但是，在寫程序時(shí)，總是會(huì)有適合鏈表的時(shí)刻(雖然很少)：

1.用分離鏈表法去解決hash沖突的時(shí)候，對于相同的hash key值，使用鏈表來存儲(chǔ)，將新的節(jié)點(diǎn)插入鏈表的頭部；2.如果需要引用穩(wěn)定性，則可能需要一個(gè)鏈表，因?yàn)楣?jié)點(diǎn)不會(huì)移動(dòng)。如果指向一個(gè)節(jié)點(diǎn)，并對除了所指向的節(jié)點(diǎn)之外的任何內(nèi)容執(zhí)行插入或擦除操作，該指針將保持有效。3.實(shí)現(xiàn)一個(gè)軟件LRU或MRU緩存，通常使用鏈表，并有指針指向緩存的所有元素。當(dāng)使用其中一個(gè)時(shí)，將其從鏈表中拉出，并將其放在開頭或結(jié)尾。

別的一般情況下，相比std::list，更傾向于選擇std::array和std::vector。

2. 關(guān)聯(lián)容器

“關(guān)聯(lián)容器”是一個(gè)來自c++標(biāo)準(zhǔn)的術(shù)語。關(guān)聯(lián)容器通常稱為映射或字典。它們將一組鍵一對一地關(guān)聯(lián)到一組值上。換句話說，您可以將一個(gè)鍵及其關(guān)聯(lián)值插入到容器中，然后通過傳遞該鍵請求該值。在C++ STL中，包括std::map和std::set。這兩個(gè)容器都以紅黑樹的方式實(shí)現(xiàn)，因此可以按照鍵排序的順序遍歷元素。

std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.

從c++ 11開始，還有散列關(guān)聯(lián)容器std::unordered_map和std::unordered_set。顧名思義，這些元素沒有按順序排列。

這里，我們討論有序的，其底層結(jié)構(gòu)是紅黑樹的容器，內(nèi)存存儲(chǔ)結(jié)構(gòu)如下圖：

在有序數(shù)組和樹中，查找一個(gè)特定值的時(shí)間復(fù)雜度是O(log(N))，并且由于在任何二叉搜索中都要在內(nèi)存中跳躍，所以數(shù)組的速度并沒有加快。

將一個(gè)元素插入到已排序的數(shù)組中需要先進(jìn)行搜索，然后再進(jìn)行插入(包括將后面的所有元素后移)，時(shí)間消耗為O(log(N) + N)或者說O(N)。插入到樹中需要搜索、分配，可能還需要重新平衡樹，時(shí)間復(fù)雜度是O (log (N))。對于較大的N，在樹中插入自然要快得多。

需要注意的是，由于插入時(shí)間的xx性，填充一個(gè)排序數(shù)組是O(N * N)，填充紅黑樹是O(N * log(N))。對于兩個(gè)容器，按順序讀取所有元素的時(shí)間是O(N)。同樣，讀取數(shù)組中的值要快得多。事實(shí)上，樹中的迭代速度甚至比鏈表中的還要慢。下面的測試代碼是基于vector_vs_map稍作改動(dòng)。

#include#include#include#include#includeconstsize_t N = 1000000;volatilesize_t acc = 0;typedef std::vector<:pair>size_t, size_t>> vecss;typedef std::map<size_t, size_t> mapss;struct firstPairComp{booloperator()(const vecss::value_type& lhs, const vecss::value_type& rhs){return lhs.first < rhs.first;}};void insert_in_vec(const std::vector& orderVec){ vecss vals; vals.reserve(N);doublestart_t, end_t;start_t= clock();for(size_t i = 0; i < N; ++i){ vecss::value_type val(orderVec[i], rand()); std::pair<:iterator vecss::iterator> res = std::equal_range(vals.begin(), vals.end(), val, firstPairComp()); vals.insert(res.second, val);}end_t= clock(); std::cout << "vector insert cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl;}void find_in_vec(const std::vector& orderVec){ vecss vals; vals.reserve(N);for(size_t i = 0; i < N; ++i){ vecss::value_type val(orderVec[i], rand()); std::pair<:iterator vecss::iterator> res = std::equal_range(vals.begin(), vals.end(), val, firstPairComp()); vals.insert(res.second, val);}doublestart_t, end_t;start_t= clock();for(size_t i = 0; i < N; ++i){ vecss::value_type val(orderVec[i], 0); std::pair<:iterator vecss::iterator> res = std::equal_range(vals.begin(), vals.end(), val, firstPairComp()); acc += res.first->second;}end_t= clock(); std::cout << "vector find cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl;}void insert_in_map(const std::vector& orderVec){ mapss vals;doublestart_t, end_t;start_t= clock();for(size_t i = 0; i < N; ++i){ mapss::value_type val(orderVec[i], rand()); vals.insert(val);}end_t= clock(); std::cout << "map insert cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl;}void find_in_map(const std::vector& orderVec){ mapss vals;for(size_t i = 0; i < N; ++i){ mapss::value_type val(orderVec[i], rand()); vals.insert(val);}doublestart_t, end_t;start_t= clock();for(size_t i = 0; i < N; ++i){ mapss::iterator it = vals.find(orderVec[i]); acc += it->second;}end_t= clock(); std::cout << "map insert cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl;}void iter_vec(){ vecss vals; vals.reserve(N);for(size_t i = 0; i < N; ++i) vals.push_back(vecss::value_type(i, rand())); vecss::value_type *begin= &vals[0];doublestart_t, end_t;start_t= clock();for(size_t i = 0; i < N; ++i) acc += begin[i].second;end_t= clock(); std::cout << "vector iterator cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl;}void iter_map(){ mapss vals;for(size_t i = 0; i < N; ++i) vals.insert(mapss::value_type(i, rand()));doublestart_t, end_t;start_t= clock(); mapss::const_iterator end= vals.end();for(mapss::const_iterator it = vals.begin(); it != end; ++it) acc += it->second;end_t= clock(); std::cout << "map iterator cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl;}int main(){ std::vector orderVec(N);for(size_t i = 0; i < N; i++){ orderVec[i] = i + 1;} insert_in_vec(orderVec); insert_in_map(orderVec); find_in_vec(orderVec); find_in_map(orderVec); iter_vec(); iter_map(); system("pause");return0;}

測試結(jié)果在下面的表格(注意：這里的vector是有序的),單位是納秒(ns)：

SizeInsert ComparisonFind ComparisonIterator Comparison

Vector	Map	Map/Vector	Vector	Map	Map/Vector	Vector	Map	Map/Vector
10000	1e+06	2e+06	2	1e+06	1e+06	1	0	0	null
50000	4e+06	7e+06	1.75	3e+06	3e+06	1	0	1e+06	null
100000	8e+06	1.5e+07	1.875	7e+06	7e+06	1	0	2e+06	null
1000000	9.6e+07	1.74e+08	1.813	7.2e+07	7.2e+07	1	2e+06	2.1e+07	10.5
10000000	1.097e+09	1.908e+09	1.74	8.23e+08	7.9e+08	0.96	1.5e+07	2.2e+08	14.67
100000000	1.3488e+10	2.3679e+10	1.76	7.83e+09	8.888e+09	1.13	1.84e+08	2.117e+09	11.51

從上面可以看出，對于迭代，沒有比線性內(nèi)存訪問更好的方法了，并且插入操作，map也沒有比有序數(shù)組更好。如果只關(guān)心快速插入、刪除和查找怎么辦?使用散列表，如std::unordered_map或std::unordered_set。這些操作平攤了O(1)的運(yùn)行時(shí)間，比O(log(N))要好。當(dāng)你決定使用樹的時(shí)候，記住:

?對于關(guān)聯(lián)數(shù)據(jù)結(jié)構(gòu)的插入、擦除和查找操作，哈希幾乎總是優(yōu)于樹。?對于相當(dāng)小的工作集，排序數(shù)組具有無與倫比的迭代速度，但代價(jià)昂貴的插入和擦除。

因此，如果您關(guān)心迭代速度或插入、刪除和查找的性能，就不要使用基于樹的數(shù)據(jù)結(jié)構(gòu)。同樣，可能會(huì)發(fā)現(xiàn)少數(shù)場景下需要考慮穩(wěn)定性。

3. 總結(jié)

避免使用鏈表，除非:

?你需要參考穩(wěn)定性；?你正在實(shí)現(xiàn)一個(gè)軟件MRU/LRU緩存。

使用數(shù)組來代替。std::vector生成一個(gè)良好的堆分配數(shù)組，而std::array生成一個(gè)適合堆棧的固定大小的良好數(shù)組。

避免使用樹結(jié)構(gòu),除非:

?需要參考穩(wěn)定性；?操作的成本并不依賴于樹中的元素?cái)?shù)量(如trie)。

對于小的N值，使用排序數(shù)組(boost::container::flat_map構(gòu)造了一個(gè)良好排序的數(shù)組，就像一個(gè)有序的std::vector一樣)。

flat_map is similar to std::map but it's implemented by as an?ordered sequence container. The underlying sequence container is by default vector but it can also work user-provided vector-like SequenceContainers (like static_vector or small_vector).

對于大的N值，使用哈希表(std::unordered_map和std::unordered_set)。

本文作者：focuscode，16年控制工程畢業(yè)，不慎誤入C/C++懷抱，希望有一天可以給簡歷的精通C++加上雙引號~。

聲明：本文為 腳本之家專欄作者 投稿，未經(jīng)允許請勿轉(zhuǎn)載。

- END -

●??腳本之家粉絲福利，請查看?

●??人人都欠微軟一個(gè)正版？?

●??什么是RSA算法

●?加密算法的前世今生

●?HTTPS 到底加密了什么？

總結(jié)

以上是生活随笔為你收集整理的boost::unorder_map如何插入元素_链表和有序二叉树插入元素时真的比数组快吗？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。