作者：melonstreet
連結：https://www.cnblogs.com/QG-whz/p/5152963.html
閱讀目錄0、前言本文簡單地總結了STL的順序容器的知識點。文中並不涉及具體的實現技巧，對於細節的東西也沒有提及。一來不同的標準庫有著不同的實現，二來關於具體實現《STL源碼剖析》已經展示得全面細緻。所以本文僅僅是對容器基礎知識的歸納。至於容器提供的接口與使用實例，建議查取官方文檔。文章難免有錯漏，希望指出。
1、容器概論容器，置物之所也。像桶可裝水，碗可盛湯，C++的容器，可以存儲對象。容器有多種，用來處理不同的元素操作訴求。按照元素存儲到容器中以及訪問方式的差異，容器分為順序容器與關聯容器。順序容器也稱為序列式容器。序列式容器按元素插入的順序存儲元素，這些元素可以進行排序，但未必是有序的。C++本身內置了一個序列式容器array（數組），STL另外提供了vector,list,forward_list,deque,stack,queue,priority-queue，string等等序列式容器。所有的容器都是基於模板實現的，因為容器必須保證能裝得下各種各樣的類型。其中，stack，queue都是基於deque來實現的，priority-queue基於heap來實現，從技術上來說它們屬於容器適配器（adapter）。其中array與forward_list是C++11添加的新容器類型。
2、std::array2.1.底層數據結構array的底層數據結構是固定數組。與C-style的數組類似，它的大小在定義後就不能被改變。由於array具有固定的大小，它不支持添加和刪除元素或改變容器大小等其他容器擁有的操作。在定義一個array容器的時候必須指定大小：
Defined in header <array>
template<
class T,
std::size_t N
> struct array;
在內存分配策略上，array也與C-style數組類似。編譯器在哪裡為array分配內存，取決於array定義的位置和方式。
若作為函數的局部對象，則將從棧上獲得內存，與之對比是的vector，vector底層數據結構是動態數組，從自由存儲區上分配內存：
若使用new操作符分配內存，則是在自由存儲區上分配內存。
若作為全局變量或局部靜態變量，則是在全局/靜態存儲區上分配的內存。
例如，在函數定義的array局部對象在棧上分配內存，與此對比的是vector，它底層數據結構為動態數組，因此在自由存儲區上分配內存：
#include <array>
#include <vector>
#include <iostream>
using namespace std;
int main() {
int stack_var;
array<int, 5> a;
vector<int> b(5);
cout << "stack area: 0x" << hex << (uintptr_t)&stack_var << endl;
cout << "a[3] address: 0x" << hex << (uintptr_t)&a[3] << endl;
cout << "b[3] address: 0x" << hex << (uintptr_t)&b[3] << endl;
getchar();
return 0;
}
結果：
2.3.array的優勢在哪
array比數組更安全。它提供了opeartor[]與at()成員函數，後者將進行數組越界檢查。
與其他容器相似，array也有自己的迭代器，因此array能夠更好地與標準算法庫結合起來。
通過array::swap函數，可以實現線性時間內的兩個數組內容的交換。
另外，不像C-style數組，array容器類型的名稱不會自動轉換為指針。對於C++程式設計師來說，array要比C-style數組更好用。
3、forward_list3.1.底層數據結構forward_list的底層數據結構為單向鍊表。如C++標準所講，forward_list容器支持前向遍曆元素序列，允許常數時間內在任意位置的插入或刪除操作並進行自動的內存管理。與list的主要區別是forward_list沒有反方向的迭代器，不過也正因如此，forward_list的每個節點都節省了迭代器大小的開銷，在元素眾多的時候，將比list消耗少得多的內存。
受單向鍊表這種特殊結構的影響，forward_list在很多地方表現得和其他容器不同：
3.2.forward_list特殊之一：forward_list不提供返回其大小的操作。在所有已知的STL容器中，forward_list是唯一一個不提供size()的容器。不提供的原因在於計算一個forward_list的長度需要線性的時間，庫用戶有時無法忍受這樣的時間開銷。其他容器提供的size()操作皆可以在常數時間內完成（在C++98時，list也是線性時間）。為了節省內存，forward_list甚至不跟蹤序列的長度，要想獲得某個forward_list對象的長度，用戶需要通過distance()來計算。這帶來了一些不便，但使得用戶遠離了size()帶來的高消耗。每個容器類型都有三個與大小相關的操作：
max_size(),empty(),size(),而forward_list只提供了前兩個。
int main()
{
forward_list<int> flist;
for (int i = 0; i < 10; i++)
{
flist.push_front(i);
}
std::cout << std::distance(flist.begin(), flist.end());
getchar();
}
為此，forward_list提供了如下的插入接口：
insert_after在給定位置之後插入新元素emplace_after在給定位置之後構造新元素erase_after刪除給定位置之後的元素splice_after將另一個forward_list的元素移動到本forward_list的指定位置之後其他所有STL容器都是在指定位置之前插入元素（除了std::array，它不允許插入）。forward_list的這種特殊處理，還是出於效率的考慮。對於單鍊表我們應該很熟悉，為了在某個指定節點之前插入插入節點，我們必須改變插入位置的前一個節點的指向。換句話說，為了在指定節點之前插入新元素，我們必須要先獲得插入位置前一個位置的節點，為了獲取前面這個節點，需要線性的操作時間。
而如果我們是在指定位置之後插入新元素，則無需線性時間的查找操作，這樣可實現常數時間的插入：
同樣的，處於性能的考慮，forward_list沒有提供在尾部進行操作的接口，包括push_back(),pop_back()和emplace_back(),這些操作對單列表來說都至少要花費O(n)來完成。
3.4.迭代器失效問題指向被刪除元素的迭代器，在刪除之後失效。
4、list4.1.底層數據結構list同樣是一個模板類，它底層數據結構為雙向循環鍊表。因此，它支持任意位置常數時間的插入/刪除操作，不支持快速隨機訪問。
4.2、迭代器類型list的迭代器具備前移、後移的能力，所以list提供的是Bidirectional iterator(雙向迭代器)。由於採用的是雙向迭代器，自然也很方便在指定元素之前插入新節點，所以list很正常地提供了insert()操作與push_back()/pop_back()操作。在C++11中，list新增了三個接口，以支持在指定位置構造對象後插入容器中:
emplace在指定位置之前插入新構造的元素emplace_front在鍊表頭插入新構造的元素emplace_back在鍊表尾插入新構造的元素4.3.內存分配策略list的空間配置策略，自然是像我們普通雙向鍊表那樣，有多少元素申請多少內存。它不像vactor那樣需要預留空間供新元素的分配，也不會因找不到連續的空間而引起整個容器的內存遷移。
4.4.迭代器失效問題list 有一個重要性質：插入操作（insert）與接合操作（splice）都不會造成原有的list迭代器失效。這在vector是不成立的，因為vactor的插入可能引起空間的重新配置，導致原來的迭代器全部失效。list的迭代器失效，只會出現在刪除的時候，指向刪除元素的那個迭代器在刪除後失效。
通常來說，forward_list在使用靈活度上比不上list，因為它只能單向迭代元素，且提供的接口沒有list多。然而，在內存的使用上，它是比list佔優勢的。當對內存的要求佔首要位置時，應該選擇forward_list。
5、vector5.1.底層數據結構vector的底層數據結構是動態數組，因此，vector的數據安排以及操作方式與std::array十很相似，它們間的唯一差別在於對空間的運用靈活性上。array為靜態數組，有著靜態數組最大的缺點：每次只能分配一定大小的存儲空間，當有新元素插入時，要經歷 「找到更大的內存空間」->「把數據複製到新空間」 ->「銷毀舊空間」 三部曲， 對於std::array而言，這種空間管理的任務壓在使用它的用戶身上，用戶必須把握好數據的數量，儘量在第一次分配時就給數據分配合理的空間（這有時很難做到），以防止「三部曲」帶來的代價，而數據溢出也是靜態數組使用者需要注意的問題。而vector用戶不需要親自處理空間運用問題。vector是動態空間，隨著新元素的插入，舊存儲空間不夠用時，vector內部機制會自行擴充空間以容納新元素，當然，這種空間擴充大部分情況下（幾乎是）也逃脫不了「三部曲」，只是不需要用戶自己處理，而且vector處理得更加安全高效。vector的實現技術關鍵就在於對其大小的控制以及重新配置時數據移動效率。
5.2.迭代器類型對於C_style數組，我們使用普通指針就可以對數組進行各種操作。vector維護的是一個連續線性空間，與數組一樣，所以無論其元素型別為何，普通指針都可以作為vector的迭代器而滿足所有必要的條件。vector所需要的迭代器操作，包括operator*,operator->,operator++,operator--,operator+=,operator-=等，普通指針都具有。因此，普通指針即可滿足vector對迭代器的需求。所以，vector提供了Random Access Iterators。
5.3.內存分配策略標準庫的實現者使用了這樣的內存分配策略：以最小的代價連續存儲元素。為了使vector容器實現快速的內存分配，其實際分配的容量要比當前所需的空間多一些(預留空間)，vector容器預留了這些額外的存儲區用於存放添加的新元素，於是不必為每個新元素進行一次內存分配。當繼續向容器中加入元素導致備用空間被用光（超過了容量 capacity），此時再加入元素時vector的內存管理機制便會擴充容量至兩倍，如果兩倍容量仍不足，就擴張至足夠大的容量。容量擴張必須經歷「重新配置、元素移動、釋放原空間」這個浩大的工程。按照《STL源碼剖析》中提供的vector源碼，vector的內存配置原則為：
當然，vector的每種實現都可以自由地選擇自己的內存分配策略，分配多少內存取決於其實現方式，不同的庫採用不同的分配策略。
5.4.迭代器失效問題1、vector管理的是連續的內存空間，在容器中插入（或刪除）元素時，插入（或刪除）點後面的所有元素都需要向後（或向前）移動一個位置，指向發生移動的元素的迭代器都失效。這裡以插入操作示例：
2、隨著元素的插入，原來分配的連續內存空間已經不夠且無法在原地拓展新的內存空間，整個容器會被copy到另外一塊內存上，此時指向原來容器元素的所有迭代器通通失效。
3、刪除元素後，指向被刪除元素的迭代器失效，這是顯而易見的。
6、deque6.1.底層數據結構vector是單向開口的線性連續空間，deque則是一種雙向開口的連續數據空間。所謂的雙向開口，意思是可以在頭尾兩端分別做元素的插入和刪除操作。當然vector也可以在頭尾兩端進行操作，但是其頭部操作效果奇差，所以標準庫沒有為vector提供push_front或pop_front操作。與vector類似，deque支持元素的快速隨機訪問。deque的示意圖如下：
現在問題來了：如果deque以數組來實現，如何做到在頭部的常數時間插入？如果是採用鍊表來實現，又如何做到快速隨機訪問？deque的內部數據結構到底如何？想必你已經猜到了，要實現如上需求，需要由一段一段的連續空間連結起來的數據結構才能滿足。
6.2.內存分配策略接著上面講。deque由一段一段的連續空間所連結而成，一旦需要在deque的前端或尾端增加新空間，便配置一段定量的連續空間，並將該空間串接在deque的頭部或尾部。deque複雜的迭代器架構，構建出了所有分段連續空間」整體連續「的假象。
既然deque是由一段一段定長的連續空間所構成，就需要有結構來管理這些連續空間。deque採用一塊map（非STL中的map）作為主控，map是一塊小的連續空間，其中每個元素都是指針，指向一塊較大的線性連續空間，稱為緩衝區。而緩衝區才是存儲deque元素的空間主體。示例圖：
map本身也是一塊固定大小的連續空間，當緩衝區數量增多，map容不下更多的指針時，deque會尋找一塊新的空間來作為map。
6.3.deque的迭代器為了使得這些分段的連續空間看起來像是一個整體，deque的迭代器必須有這樣的能力：它必須能夠指出分段連續空間在哪裡，判斷自己所指的位置是否位於某一個緩衝區的邊緣，如果位於邊緣，則執行operator-- 或operator++時要能夠自動跳到下一個緩衝區。因此，儘管deque的迭代器也是Ramdon Access Iterator 迭代器，但它的實現要比vector的複雜太多。SGI版本的STL deque實現思路可以看侯捷的《STL源碼剖析》。
6.4.迭代器失效問題在deque容器首部或者尾部插入元素不會使得任何迭代器失效。
在其首部或尾部刪除元素則只會使指向被刪除元素的迭代器失效。
在deque容器的任何其他位置的插入和刪除操作將使指向該容器元素的所有迭代器失效。
7、容器適配器stack，也稱為棧，是一種先進後出的數據結構。STL中的statck是一種容器適配器。所謂的容器適配器，是以某種容器作為底部容器，在底部容器之上修改接口，形成另一種風貌。stack默認以雙端隊列deque作為底部容器。stack沒有提供迭代器，通過push/pop接口對棧頂元素進行操作。
queue，也稱為隊列，是一種先進先出的數據結構，它同樣也是一種容器適配器。它的底部容器默認為deque。同樣，queue也沒有提供迭代器，通過push向隊尾壓入元素，pop從隊首彈出元素。
priority-queue，優先隊列，是一種擁有權值觀念的隊列，例如在以整數大小作為衡量的權值定義下，priority-queue總是彈出最大的數。priority-queue的底部數據結構默認是max-heap，大頂堆。
8、總結array固定大小的數組支持快速隨機訪問不能添加或刪除元素通常不會發生迭代器失效，除非對象已經被銷毀，則原來的迭代器全部失效vector可動態增長的數組支持快速隨機訪問尾部可高效插入/刪除元素若插入操作引起內存重新分配，則全部迭代器失效；否則插入點/刪除點之後的迭代器失效;list雙向鍊表只支持元素的雙向順序訪問在list的任何位置可高效插入/刪除元素插入操作後指向容器的迭代器有效；刪除操作指向其他位置的迭代器有效deque雙端隊列支持快速隨機訪問首尾可高效插入/刪除元素情況較多，見上面分析forward_list單向鍊表只支持元素的單向順序訪問在鍊表的任何位置可高效插入/刪除元素插入操作後指向容器的迭代器有效；刪除操作指向其他位置的迭代器有效string只存儲字符元素的動態數組支持快速隨機訪問尾部可高效插入/刪除元素若插入操作引起內存重新分配，則全部迭代器失效；否則插入點/刪除點之後的迭代器失效;stack默認deque先進後出，只能訪問棧頂元素----沒有迭代器queue默認deque先進先出，只能訪問隊首元素----沒有迭代器priority-queue默認max-heap先進先出，只能訪問隊首元素----沒有迭代器注意：
「尾部可高效插入/刪除元素」，意味著在除了尾部之外的其他位置插入/刪除元素是較低效的。
「順序訪問」意味著要訪問某一個元素，必須遍歷其他元素。
迭代器失效意味著指針、引用在同樣的情況下也會失效。
9、一些參考連結http://en.cppreference.com/w/cpp/container/array●編號584，輸入編號直達本文
●輸入m獲取文章目錄
分享C/C++技術文章