所謂的順序容器即元素在順序容器中的順序與其加入容器時的位置相對應(yīng)。標(biāo)準(zhǔn)庫還定義了幾種關(guān)聯(lián)容器，關(guān)聯(lián)容器中元素的位置由元素相關(guān)聯(lián)的關(guān)鍵字值決定。所有的容器類都共享公共的接口，不同容器按不同方式對其進(jìn)行擴展。
- 標(biāo)準(zhǔn)庫中的順序容器常用的有以下這些：
- vector：可變大小數(shù)組，支持快速隨機訪問。非尾部插入刪除很慢
- deque：雙端隊列，支持快速隨機訪問，在頭尾插入/刪除速度很快
- list：雙向鏈表，只支持雙向順序訪問，任何位置插入/刪除都很快
- forward_list：單向鏈表，只支持單向順序訪問，任何位置插入/刪除都很快
- array：固定大小數(shù)組，支持快速隨機訪問，不能添加或刪除元素
- string：與vector相似的容器，但專門用于保存字符
- 現(xiàn)代C++程序應(yīng)該使用標(biāo)準(zhǔn)庫容器，而不是更原始的數(shù)據(jù)結(jié)構(gòu)，如內(nèi)置數(shù)組。一般來說，使用vector是最好的選擇，除非你有很好的理由選擇其他容器。
- 容器類型上的操作形成了一種層次：
- 某些操作是所有容器類型都提供的
- 另外一些操作僅針對順序容器，關(guān)聯(lián)容器或無序容器
- 一般來說，每個容器都定義在一個頭文件中，文件名與類型名相同。容器均定義為模板類，我們必須提供額外信息來生成特定的容器類型。
- 順序容器幾乎可以保存任意類型的元素，但某些容器操作對元素類型有其自己的特殊要求。
-
常用容器操作（通用）
容器操作
反向容器額外操作 - 一個迭代器范圍（iterator range）由一對迭代器表示，兩個迭代器分別指向同一個容器中的元素或者尾后位置。這兩個迭代器通常被稱為begin和end。這種元素范圍被稱為左閉合區(qū)間，其標(biāo)準(zhǔn)數(shù)學(xué)描述為：
[begin, end)
begin和end必須指向相同的容器，end可以和begin指向同樣的位置，但不能指向begin之前的位置。
- 之所以規(guī)定左閉合范圍是因為我們可以安全方便地處理元素，如下：
while(begin!=end){
*begin=val;
++begin;
}
- 通過容器內(nèi)置的類型別名，我們可以在不了解容器中元素類型的情況下使用它（通過value_type）。如果需要元素類型的一個引用，可以使用reference或const_reference。
- 當(dāng)auto與begin或end結(jié)合使用時，獲得的迭代器版本依賴于容器類型（因為實際上begin被重載過），但以c開頭的版本一定會獲得const_iterator。當(dāng)不需要寫訪問時，應(yīng)該使用cbegin和cend。
- 每個容器類型都定義了一個默認(rèn)構(gòu)造函數(shù)。除array之外，其他容器的默認(rèn)構(gòu)造函數(shù)都會創(chuàng)建一個指定類型的空容器。
- 為了創(chuàng)建一個容器為另一個容器的拷貝，兩個容器的類型及元素類型必須匹配。不過如果傳遞迭代器參數(shù)來拷貝一個范圍，就不要求容器類型是相同的了。
- 新標(biāo)準(zhǔn)中，我們可以對一個容器進(jìn)行列表初始化，這樣我們顯式指定了每個元素的值，還隱含了容器的大小。
- 與內(nèi)置數(shù)組一樣，標(biāo)準(zhǔn)庫array的大小也是類型的一部分。定義一個array時，除了指定元素類型，還要指定容器大?。?/li>
array<int,42>;
array<string,10>;
- 由于大小是array的一部分，array不支持普通的容器構(gòu)造函數(shù)，這些構(gòu)造函數(shù)或顯式或隱式地確定了容器的大小。
- 與其他容器不同，一個默認(rèn)構(gòu)造的array是非空的：它包含與其大小一樣多的元素，這些元素都被默認(rèn)初始化，就像一個內(nèi)置數(shù)組一樣。如果我們對array進(jìn)行列表初始化，初始值數(shù)目必須等于或小于array的大小，如果小于，則剩余靠后的元素都會進(jìn)行值初始化。這種情況下，如果元素是類類型，則必須要有一個默認(rèn)構(gòu)造函數(shù)。
- 值得注意的是，雖然我們不能對內(nèi)置數(shù)組進(jìn)行拷貝或?qū)ο筚x值操作，但array并無此限制。array要求容器類型，元素類型和大小都一樣，因為大小也是array類型的一部分。
- 賦值運算符將其左邊容器中的全部元素替換成右邊容器中元素的拷貝，要求左邊和右邊具有相同的類型
- 順序容器（除了array）還定義了一個名為assign的成員，允許我們從一個不同但相容的類型賦值，或者從容器的一個子序列賦值。
- swap操作交換兩個相同類型容器的內(nèi)容，除了array外，swap只是交換了兩個容器的內(nèi)部數(shù)據(jù)結(jié)構(gòu)。所以迭代器，引用和指針仍指向之前所指的元素，但是這些元素已經(jīng)去到另外一個容器了。swap兩個array則會真正交換它們的元素。
- 新標(biāo)準(zhǔn)庫中，容器既提供成員函數(shù)版本的swap，也提供非成員版本的swap，由于非成員版本的swap在泛型編程中很重要，所以統(tǒng)一使用非成員版本的swap是好習(xí)慣。
- 每個容器類型都支持相等運算符；除了無序關(guān)聯(lián)容器外所有容器都支持關(guān)系運算符，關(guān)系運算符左右兩邊的運算對象必須是相同類型的容器，且必須保存相同類型的元素。比較兩個容器實際上是元素的逐對比較，與string的字典序比較類似。
- 如果元素類型不支持所需的運算符（比如==和>），那么保存這種元素的容器就不能使用相應(yīng)的關(guān)系運算。
- 容器提供的操作與它組織元素的方式有密切關(guān)系（實際上就是內(nèi)部數(shù)據(jù)結(jié)構(gòu)），也與它的語義有關(guān)（比如array不支持改變大小的操作）
-
向順序容器添加元素：
向順序容器添加元素 -
訪問順序容器的元素：
訪問元素 -
刪除順序容器的元素：
刪除元素 - forward_list本質(zhì)上一個單向鏈表，刪除或添加某個元素會影響前驅(qū)節(jié)點的后繼，但是單向鏈表并沒有簡單的方法來獲取一個元素的前驅(qū)。所以一個forward_list中添加或刪除元素的操作時通過改變給定元素之后的元素來完成的。所以從forward_list添加或刪除元素的時候，我們往往關(guān)注兩個迭代器，如下：
forward_list<int> flst={0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin();
auto curr = flst.begin();
while(curr!=flst.end()){
if(*curr%2)
curr=flst.erase_after(prev);
else{
prev=curr++;
}
}
在forward_list中插入或刪除元素
- 在容器中添加元素和從容器中刪除元素的操作可能會使指向容器元素的指針，引用或迭代器失效，仍舊使用失效的它們是一種嚴(yán)重的程序設(shè)計錯誤。具體的失效情況可以通過分析容器的底層數(shù)據(jù)結(jié)構(gòu)并將迭代器假想為指針大致得出，此處不再贅述。特別是如果在使用迭代器的循環(huán)中具有添加/刪除的操作，一定要注意迭代器的更新，保證其正確性。
- 當(dāng)vector和string不得不獲取新的內(nèi)存空間時，通常會分配比新的空間需求更大的內(nèi)存空間作為備用。但vector只有迫不得已的時候才分配新的內(nèi)存空間。
-
vector和string提供了一些成員函數(shù)，允許我們與它的實現(xiàn)中內(nèi)存分配部分互動：
容器大小管理操作 - 除了順序容器共同的操作之外，string類型還提供了一些額外的操作。這些操作中大部分要么是提供了string類和C風(fēng)格字符數(shù)組之間的相互轉(zhuǎn)換，要么是增加了允許我們用下標(biāo)代替迭代器的版本。
- string類型提供了非常多的成員函數(shù)，總的來說，包括多種構(gòu)造函數(shù)，返回子串函數(shù)，多種修改函數(shù)，多種搜索字符函數(shù)，多種比較函數(shù)，以及多種string和數(shù)值之間的轉(zhuǎn)換函數(shù)，此處不一一贅述，需要時再查閱資料即可。
- 除了順序容器外，標(biāo)準(zhǔn)庫還定義了三個順序容器適配器：stack，queue和priority_queue。適配器（adaptor）是標(biāo)準(zhǔn)庫的一個通用概念。本質(zhì)上，一個適配器是一種機制，能使某種事物的行為看起來像另外一種事物一樣。一個容器適配器接受一種已有的容器類型，使其行為看起來像一種不同的類型。例如，stack適配器接受一個順序容器，使其操作看起來像一個stack一樣。
所有容器適配器都支持的操作和類型 - 默認(rèn)情況下，stack和queue是基于deque實現(xiàn)的，priority_queue是在vector之上實現(xiàn)的。我們可以在創(chuàng)建一個適配器時將一個命名的順序容器作為第二個類型參數(shù)，來重載默認(rèn)容器類型。
//在vector上實現(xiàn)的空棧
stack<string,vector<string>> str_stk;
對于給定的適配器，可以使用哪些容器是有限制的，具體的規(guī)則可以結(jié)合適配器以及容器的接口來分析，要求適配器接口一定能通過容器的接口直接或簡單間接實現(xiàn)，就不一一贅述了。
棧的接口
隊列和優(yōu)先隊列接口(1)
隊列和優(yōu)先隊列接口(2)
值得注意的是：這里關(guān)于pop的用法寫錯了，pop返回的是void，這是因為如果pop要彈出元素，則必須返回元素的值而不是引用。然而接收值的時候有可能發(fā)生異常（比如通過這個值來初始化一個類類型），這時丟失的元素就再也找不回來了。所以往往pop和top搭配使用。
