順序容器類型

string和vector將元素保存在連續的內存空間中，因此支持快速隨機訪問，但是在這兩種容器的中間位置添加或刪除元素會非常耗時，因為需要移動插入/ 刪除位置之后的所有元素，來保持連續存儲。而且添加一個元素有時可能還需要分配額外的存儲空間，這種情況下，每個元素都必須移動到新的存儲空間中。
list和forward_list兩個容器添加和刪除操作快速，但不支持元素的隨機訪問，為了訪問一個元素只能遍歷整個容器，其存儲的內存空間不連續。
deque支持快速隨機訪問，中間位置添加或刪除元素非常耗時，但是在deque的兩端添加或刪除元素很快。

確定使用哪種順序容器

通常，使用vector是最好的選擇，除非你有很好的理由選擇其他容器。

容器庫概覽

一般來說，每個容器都定義在一個頭文件中，文件名與類型名相同，即deque定義在頭文件deque中，list定義在頭文件list中，以此類推。容器均定義為模板類，例如對vector，我們必須提供額外信息來生成特定的容器類型。對大多數，但不是所有容器，我們還需要額外提供元素類型信息：

list<Sales_data> 保存Sales_data對象的list
deque<double> 保存double的deque

順序容器幾乎可以保存任意類型的元素。特別是，我們可以定義一個容器，其元素的類型是另一個容器。這種容器的定義與任何其他容器類型完全一樣：

vector<vector<string>> lines; 此處lines是一個vector，其元素類型是string的vector

容器操作

迭代器

迭代器支持的所有操作

forward_list迭代器不支持遞減運算符

迭代器支持的所有運算

這些運算只適用于string、vector、deque和array的迭代器，我們不能將它們用于其他任何容器類型的迭代器。

例如，list的迭代器不支持<運算，只支持遞增、遞減、==以及!=運算，原因在于list是將元素以鏈表方式存儲，在內存中不連續，兩個指針的大小關系與它們指向的元素的前后關系并不一定是吻合的，實現<運算將會非常困難和低效。

迭代器范圍

一個迭代器范圍由一對迭代器表示，兩個迭代器分別指向同一個容器中的元素或者是尾元素之后的位置。這兩個迭代器通常被稱為begin和end

對構成范圍的迭代器的要求

如果滿足如下條件，兩個迭代器begin和end構成一個迭代器范圍：
它們指向同一個容器中的元素，或者是容器最后一個元素之后的位置，且我們可以通過反復遞增begin來到達end。換句話說，end不在begin之前。

標準庫迭代器范圍左閉右開的三種性質

假定begin和end構成一個合法的迭代器范圍，則

• 如果begin與end相等，則范圍為空
• 如果begin與end不相等，則范圍至少包含一個元素，且begin指向該范圍中的第一個元素
• 我們可以對begin遞增若干次，使得begin==end

容器定義和初始化

每個容器類型都定義了一個默認構造函數。除array之外，其他容器的默認構造函數都會創建一個指定類型的空容器，且都可以接受指定容器大小和元素初始值的參數。

將一個新容器創建為另一個容器的拷貝

為了創建一個容器為另一個容器的拷貝，兩個容器的類型及其元素類型必須匹配。不過，當傳遞迭代器參數來拷貝一個范圍時，就不要求容器類型是相同的了，而且新容器和原容器中的元素類型也可以不同，只要能將要拷貝的元素轉換為要初始化的容器的元素類型即可。

將array拷貝到vector中的代碼

int ia[] = { 0,1,1,2,3,5,8,13,21,55,89 };
vector<int>vect;
vect.assign(ia,ia+11);

與順序容器大小相關的構造函數

如果元素類型是內置類型或者是具有默認構造函數的類類型，可以只為構造函數提供一個容器大小參數。如果元素類型沒有默認構造函數，除了大小參數外，還必須指定一個顯式的元素初始值。
只有順序容器的構造函數才接受大小參數，關聯容器并不支持。

標準庫array具有固定大小

與內置數組一樣，標準庫array的大小也是類型的一部分。當定義一個array時，除了指定元素類型，還要指定容器大小，例如array<int,42>
與其他容器不同，一個默認構造的array是非空的：它包含了與其大小一樣多的元素。這些元素都被默認初始化。如果我們對array進行列表初始化，則初始值的數目必須等于或小于array的大小。如果初始值數目小于array的大小，則它們被用來初始化array中靠前的元素，所有剩余元素都會進行值初始化。在這兩種情況下，如果元素類型是一個類類型，那么該類必須有一個默認構造函數，以使值初始化能夠進行。

我們不能對內置數組類型進行拷貝或對象賦值操作，但array并無此限制：

賦值和swap

與內置數組不同，標準庫array類型允許賦值，賦值后左右兩邊的運算對象需具有相同的類型：

array<int, 10>a1 = {0,1,2,3,4,5,6,7,8,9};
array<int, 10>a2 = { 0 };
a1 = a2;//此時a1中的元素為10個0

除array外，swap不對任何元素進行拷貝、刪除或插入操作，因此可以保證在常數時間內完成。
除string外， 指向容器的迭代器、引用和指針在swap操作之后都不會失效，它們仍指向swap操作之前所指向的那些元素，但是在swap之后，這些元素已經屬于不同的容器了，詳情可見對vector進行測試的代碼。與其他容器不同，swap兩個array會真正交換它們的元素，因此，對于array，在swap操作之后，指針、引用和迭代器所綁定的元素保持不變，但元素值已經與另一個array中對應元素的值進行了交換，詳情可見對array進行測試的代碼。

測試swap的代碼

對array進行測試的代碼

int main() {array<int, 10>a1 = {1};array<int, 10>a2 = {0};auto beg1 = a1.begin();auto beg2 = a2.begin();cout << "swap之前：" << endl;cout << "a1元素：";for (auto a : a1) {cout << a << " ";}cout << endl;cout << "a2元素：";for (auto a : a2) {cout << a << " ";}cout << endl;cout << "a1.begin:"<< *beg1 << endl;cout << "a2.begin:" << *beg2 << endl;swap(a1,a2);cout << "swap之后："<<endl;cout << "a1元素：";for (auto a : a1) {cout << a << " ";}cout << endl;cout << "a2元素：";for (auto a:a2) {cout << a << " ";}cout << endl;cout << "a1.begin:" << *beg1 << endl;cout << "a2.begin:" << *beg2 << endl;system("pause");return 0;
}

測試結果：

swap之前：
a1元素：1 0 0 0 0 0 0 0 0 0
a2元素：0 0 0 0 0 0 0 0 0 0
a1.begin:1
a2.begin:0
swap之后：
a1元素：0 0 0 0 0 0 0 0 0 0
a2元素：1 0 0 0 0 0 0 0 0 0
a1.begin:0
a2.begin:1

對vector進行測試的代碼：

int main() {vector<int>a1 = {1};vector<int>a2 = {0};auto beg1 = a1.begin();auto beg2 = a2.begin();cout << "swap之前：" << endl;cout << "a1元素：";for (auto a : a1) {cout << a << " ";}cout << endl;cout << "a2元素：";for (auto a : a2) {cout << a << " ";}cout << endl;cout << "a1.begin:"<< *beg1 << endl;cout << "a2.begin:" << *beg2 << endl;swap(a1,a2);cout << "swap之后："<<endl;cout << "a1元素：";for (auto a : a1) {cout << a << " ";}cout << endl;cout << "a2元素：";for (auto a:a2) {cout << a << " ";}cout << endl;cout << "a1.begin:" << *beg1 << endl;cout << "a2.begin:" << *beg2 << endl;system("pause");return 0;
}

測試結果：

swap之前：
a1元素：1
a2元素：0
a1.begin:1
a2.begin:0
swap之后：
a1元素：0
a2元素：1
a1.begin:1
a2.begin:0

關系運算符

每個容器都支持相等運算符（==和 !=），除了無序關聯容器外的所有容器都支持關系運算符（>,>=,<,<=），關系運算符左右兩邊的運算對象必須是相同類型的容器，且必須保存相同類型的元素。
比較兩個容器實際上是進行元素的逐對比較：

• 如果兩個容器具有相同大小且所有元素都兩兩對應相等，則這兩個容器相等；否則兩個容器不等
• 如果兩個容器大小不同，但較小容器中每個元素都等于較大容器中的對應元素，則較小容器小于較大容器
• 如果兩個容器都不是另一個容器的前綴子序列，則它們的比較結果取決于第一個不相等的元素的比較結果

順序容器的特有操作

向順序容器添加元素

除array外，所有標準庫容器都提供靈活的內存管理，在運行時可以動態添加或刪除元素來改變容器大小。

容器元素是拷貝

當我們用一個對象來初始化容器時，或將一個對象插入到容器中時，實際上放入到容器中的是對象值的一個拷貝，而不是對象本身。容器中的元素與提供值的對象之間沒有任何關聯，隨后對容器中元素的任何改變都不會影響到原始對象，反之亦然。

在容器中特定位置添加元素：insert

在新標準下，接受元素個數或范圍的insert版本返回指向第一個新加入元素的迭代器，如果范圍為空，不插入任何元素，insert操作會將第一個參數返回。
通過使用insert的返回值，可以在容器中一個特定位置反復插入元素。

s.iinsert(iter,"hello")       將"hello"添加到iter之前的位置
s.iinsert(iter,10，"hello")    將10個"hello"添加到iter之前的位置
s.insert(s.begin(),s2.begin(),s2.end())  將指定范圍中的元素插入到給定迭代器位置之前
s.insert(s.begin(),{"the","haha","heihei"}) 將初始化列表中的元素插入到給定位置之前
s.insert(s.begin(),s.begin(),s.end())  此句錯誤，拷貝的范圍不能指向與目的位置相同的容器

emplace操作

訪問元素

訪問成員函數返回的是引用

在容器中訪問元素的成員函數（即，front、back、下標和at）返回的都是引用。如果容器是一個const對象，則返回值是const的引用。如果容器不是const的，則返回值是普通引用，我們可以用來改變元素的值：

刪除元素

特殊的forward_list操作

改變容器大小

示例代碼如下：

容器操作可能使迭代器失效

向容器中添加元素和從容器中刪除元素的操作可能會使指向容器元素的指針、引用或迭代器失效。一個失效的指針、引用或迭代器將不再表示任何元素。使用失效的指針、引用或迭代器是一種嚴重的程序設計錯誤，很可能會引起與使用未初始化指針一樣的問題。

如果在一個循環中插入/刪除deque、string或vector中的元素，不要緩存end返回的迭代器，必須在每次操作后重新調用end()，而不能在循環開始前保存它返回的迭代器。

vector對象是如何增長的

reserve并不改變容器中元素的數量，它僅影響vector預先分配多大的內存空間。

capacity和size

容器的size是指它已經保存的元素的數目；而capacity則是在不分配新的內存空間的前提下它最多可以保存多少元素。

額外的string操作

除了順序容器共同的操作之外，string類型還提供了一些額外的操作，這些操作中的大部分要么是提供string類和c風格字符數組之間的相互轉換，要么是增加了運行我們用下標代替迭代器的版本。

構造string的其他方法

代碼示例：

substr操作

從一個vector <char> 初始化一個string

vector提供了一個data成員函數，返回其內存空間的首地址

vector<char>vi{ 'a','b' ,'c','d'};
string s(vi.begin(),vi.end());
string s2(vi.data(),vi.size());

改變string的其他方法

string的下標版本的insert和erase版本

string類型支持順序容器的賦值運算符以及assign、insert和erase操作，除此之外，它還定義了下標版本的insert和erase版本：

	string s="0123456789";s.insert(5, 3, 'A'); //此時s是01234AAA56789，即在s[5]之前插入3個‘A’string s1 = "0123456789";s1.erase(5, 3);//此時s1是0123489，即刪除s[5]之后的3個元素，包括s[5]

string的c風格字符數組版本的insert和erase版本

	const char *cp = "0123456789";string s;s.assign(cp,5);  //s=="01234"s.insert(s.size(),cp+7);s=="01234789"

	string s = "some string";string s2 = "some other string ";s.insert(0,s2);//s=="some other string some string"// 在s[0]之前插入s2中s2[0]開始的s2.size()個字符s.insert(0,s2,0,s2.size());//s=="some other string some other string some string"

append和replace函數

string s="some ";
s.append("things"); //s=="some things"
s.replace(5,3,"hhhh");//s=="some hhhhngs"即從s[5]開始將3個元素，替換為“hhhh”

string搜索操作

string搜索操作，每個操作都返回一個string::size_type值，表示匹配位置的下標。如果搜索失敗，則返回一個名為string::npos的static成員。

string find

find查找參數指定的字符串，若找到，則返回第一個匹配位置的下標，否則返回npos

string name("AnnaBelleAnnaBelle");
auto pos1=name.find("Anna");//pos1==0
auto pos2 = name.find("Anna",1);//pos2==9 此處是從name[1]處開始查找"Anna"，返回第一個匹配位置的下標

string find_first_of

	string numbers("0123456789");string name("n1inin4n");auto pos1 = name.find_first_of(numbers,2);//pos1==6auto pos1 = name.find_first_of(numbers);//pos1==1

string compare函數

根據s是等于、大于還是小于參數指定的字符串，s.compare返回0、正數或負數。

數值轉換

	int i = 42;string s = to_string(i);//將整數i轉換為字符“42”double num = stod(s);// 將字符“42”轉換為浮點數42

	s = "00110011";int num = stoi(s,0,2);// 將s轉換為二進制，num==51

容器適配器

除了順序容器外，標準庫還定義了三個順序容器適配器：stack、queue和priority_queue。
默認情況下，stack和queue是基于deque實現的，priority_queue是在vector之上實現的。
適配器是標準庫中的一個通用概念，容器、迭代器和函數都有適配器。本質上，一個適配器是一種機制，能使某種事物的行為看起來像另外一種事物一樣。一個容器適配器接受一種已有的容器類型，使其行為看起來像一種不同的類型。

所有容器適配器都支持的操作和類型

棧適配器

stack定義在stack頭文件中，先進后出

隊列適配器

queue和priority_queue定義在queue頭文件中。
queue，先進先出
priority_queue，允許我們為隊列中的元素建立優先級，新加入的元素會排在所有優先級比它低的已有元素之前。默認情況下，標準庫在元素類型上使用<運算符來確定相對優先級。