STL容器由于各自用途的不同，底層實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)也有所不同。

具體來講，容器的主要用途就是對其中存儲的數(shù)據(jù)進行“增刪改查”。那么不同的數(shù)據(jù)結(jié)構(gòu)的設計，增刪改查的效率是不一樣的。

下面是《The C++ Standard Library 2nd》的一個截圖，

我們可以看到，STL容器的類型可以分為兩種：序列容器和關聯(lián)容器。

關聯(lián)容器中又包括不定序容器。不定序容器是指元素在容器中的位置是不確定的，也就是減少了關聯(lián)容器的排序的過程，對于不需要排序的數(shù)據(jù)來講，效率會更高一些。

下面分別討論下。

std::array

從圖中可以看出來，stl中的array是固定大小容器，底層實現(xiàn)是C-Style array。

這個容器和vector和C類型數(shù)組的功能類似，那么它的優(yōu)勢在哪？

1、和std::vector相比，std::array是靜態(tài)數(shù)組實現(xiàn)，在編譯時就可以確定大小，所以沒有vector的容量動態(tài)擴充時的消耗。當然也就沒有vector靈活。

2、和C-Style array相比，

　　std::array保持了和一般STL容器的一致的接口函數(shù)，迭代器，這樣可以更好的利用STL的算法，在使用上也更為靈活。

　　std::array不會隱式轉(zhuǎn)成指針，在作為參數(shù)傳遞時，也不會丟失大小信息。

std::vector

底層也是數(shù)組，和array不同的是可以動態(tài)改變大小。

內(nèi)存連續(xù)。所以可以通過迭代器，指針和偏移量來隨機訪問。

容量動態(tài)擴充。當插入新的元素時，如果空間不足，會重新申請一塊2倍于當前容量的內(nèi)存，并和當前內(nèi)存空間做交換。原來的指針和引用會失效。

std::deque

雙端隊列。從上面這個圖可以看出來，deque可以實現(xiàn)兩端的插入和刪除，同時又支持隨機訪問。但其實底層實現(xiàn)比上面這張圖實現(xiàn)的更復雜。

以下這個圖很好的闡明了底層的實現(xiàn)，轉(zhuǎn)自知乎

1. deque是由多塊不連續(xù)的內(nèi)存chunk組成的，再用一個表來存儲索引每一個chunk，數(shù)據(jù)存儲在chunk中，每個chunk的大小是相同的。

這樣設計最重要的原因是：

同時保證在兩端的插入刪除和隨機訪問可以在常量時間內(nèi)完成。

　 這其實兼容了vector的隨機訪問和后面要提到的list常量時間插入刪除的優(yōu)點。

2. deque可以做到動態(tài)大小。但是又不像vector需要重新申請內(nèi)存和內(nèi)存交換。

3. deque的隨機訪問需要做兩次定位。先查詢索引表，再查詢chunk中的偏移。

std::queue和std::stack是對deque的封裝。

std::list,std::forward_list

前者雙向鏈表，后者單向鏈表。

由于是鏈表，所以兩個容器都可以實現(xiàn)O(1)的任意位置的插入和移除。但都不支持隨機訪問。

前者提供雙向迭代器，同時在空間上占用的更多。

后者只提供在頭部插入和刪除，空間占用比list更高效，如果只需要在一端操作，forward_list更適合。

std::set， std::map， std::multiset， std::multimap

關聯(lián)型容器底層實現(xiàn)都是紅黑樹。

為什么要使用紅黑樹呢？因為關聯(lián)型容器對查詢的效率要求很高。而紅黑樹是一種自平衡二叉搜索樹（屬于二叉搜索樹 BST）。

我們知道在BST中，左子樹小于父節(jié)點，右子樹大于父節(jié)點。所以查詢就是遍歷節(jié)點的過程。如果樹的結(jié)構(gòu)是平衡二叉樹，也就是節(jié)點的高度之間不會大于2，那么查詢的復雜度就是O(logn)，這還不僅是平均時間復雜度，在最壞的情況下也是如此，因為平衡。

紅黑樹通過一些規(guī)則限制，保證節(jié)點在創(chuàng)建，插入和刪除后，依然能保持平衡。

所以這些關聯(lián)型容器的插入，查詢，刪除的時間復雜度都是O(logn)

后面我要總結(jié)一篇紅黑樹的文章。

std::unordered_set,std::unordered_map

這兩個也是關聯(lián)型容器，不同的是內(nèi)部存儲的數(shù)據(jù)并不按照一定的順序排列。

為了實現(xiàn)平均時間復雜度O(1)的搜索，插入和刪除，底層的實現(xiàn)采用哈希表的方式。

鏈地址法：HashTable由多個bucket組成，bucket以hashkey為索引，bucket里面存儲的是相同hashkey的元素。

總結(jié)

以上是生活随笔為你收集整理的STL容器之数据结构图解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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