下一篇：C++ 關聯容器(map、multimap 、set、multiset)詳解
一、容器的定義
在資料存儲上，有一種對象類型，它可以持有其它對象或指向其它對像的指針，這種對象類型就叫做容器。很簡單，容器就是儲存其它對象的對象，當然這是一個樸素的了解，這種“對象”還包含了一系列處理“其它對象”的方法。
二、容器的種類
1. 順序容器：
是一種各元素之間有順序關系的線性表，是一種線性結構的可序群集。順序性容器中的每個元素均有固定的位置，除非用删除或插入的操作改變這個位置。順序容器的元素排列次序與元素值無關，而是由元素添加到容器裡的次序決定。順序容器包括：vector(向量)、list（清單）、deque（隊列）、array(數組)、forward_list。
2. 關聯容器：
關聯式容器是非線性的樹結構，更準确的說是二叉樹結構。各元素之間沒有嚴格的實體上的順序關系，也就是說元素在容器中并沒有儲存元素置入容器時的邏輯順序。但是關聯式容器提供了另一種根據元素特點排序的功能，這樣疊代器就能根據元素的特點“順序地”擷取元素。元素是有序的集合，預設在插入的時候按升序排列。關聯容器包括：map（集合）、set（映射）、multimap（多重集合）、multiset（多重映射）。
3.容器擴充卡：
本質上，擴充卡是使一種不同的行為類似于另一事物的行為的一種機制。容器擴充卡讓一種已存在的容器類型采用另一種不同的抽象類型的工作方式實作。擴充卡是容器的接口，它本身不能直接儲存元素，它儲存元素的機制是調用另一種順序容器去實作，即可以把擴充卡看作“它儲存一個容器，這個容器再儲存所有元素”。STL 中包含三種擴充卡：棧stack 、隊列queue 和優先級隊列priority_queue 。
容器類自動申請和釋放記憶體，是以無需new和delete操作。
三、不同順序容器使用方法
1、array(數組)
是個順序容器，其實是個數組，記憶體空間連續，大小固定。剛開始申請記憶體多大，就是多大，不能再增加其容量。
1、詳細用法
參考部落格：c++ array模闆類使用
2、vector(需要導入頭檔案#include )
1. 定義與初始化
如果沒有指定元素的初始化式，那麼标準庫将自行提供一個元素初始值進行，具體值為何，取決于存儲在vector 中元素的資料類型；如果為int型資料，那麼标準庫将用 0 值建立元素初始化式；如果 vector 儲存的是含有構造函數的類類型（如 string）的元素，标準庫将用該類型的預設構造函數建立元素初始化式；元素類型可能是沒有定義任何構造函數的類類型。這種情況下，标準庫仍産生一個帶初始值的對象，這個對象的每個成員進行了值初始化。
vector<int> vec1; //預設初始化，vec1為空
vector<int> vec2(vec1); //使用vec1初始化vec2
vector<int> vec3(vec1.begin(),vec1.end());//使用vec1初始化vec2
vector<int> vec4(10); //10個值為0的元素
vector<int> vec5(10,4); //10個值為4的元素
vector<string> vec6(10,"null"); //10個值為null的元素
vector<string> vec7(10,"hello"); //10個值為hello的元素
2. 常用的操作方法
vec1.push_back(100); //末尾添加元素
int size = vec1.size(); //元素個數
bool isEmpty = vec1.empty(); //判斷是否為空
cout<<vec1[0]<<endl; //取得第一個元素
vec1.insert(vec1.end(),5,3); //從vec1.back位置插入5個值為3的元素
vec1.pop_back(); //删除末尾元素
vec1.erase(vec1.begin(),vec1.end());//删除之間的元素，其他元素前移(傳回指向下一個元素的疊代器)
//元素個數相同，且對應的元素值也要相同
cout<<(vec1==vec2)?true:false; //判斷是否相等==、！=、>=、<=...
vector<int>::iterator iter = vec1.begin(); //擷取疊代器首位址
vector<int>::const_iterator c_iter = vec1.begin(); //擷取const類型疊代器
vector<int>::reverse_iterator iter = vec.rbegin();//擷取一個反向疊代器
vec1.clear(); //清空元素
vec1.front(); //擷取第一個元素
vec1.back(); //擷取最後一個元素
vec1.max_size(); //向量最大容量
vec1.resize(); //更改向量大小
vec1.capacity(); //向量真實大小
vec1.swap(); //交換兩個向量的元素
注意：
- vector::iterator iter = vec.end();疊代器指針時指向最後一個元素的下一個位置，故不能通過疊代器指針直接通路，直接通路會造成程式崩潰。
- C++11引入的兩個新函數 cbegin()，cend()。和 begin()，end()類似，但是傳回的是常量疊代器。
3. 周遊方法
- 下标法(vector的特有通路方法，一般容器隻能通過疊代器通路)
int length = vec1.size();
for(int i=0;i<length;i++)
{
cout<<vec1[i];
}
cout<<endl<<endl;
-
疊代器法
vector::iterator iter = vec.begin(); //正向疊代器
vector::reverse_iterator iter = vec.begin(); //反向疊代器
vector::const_iterator iter = vec.begin(); //const 疊代器
注意：如果容器用const修飾，則疊代器通路時，必須使用 const 疊代器
vector<int>::const_iterator iterator = vec1.begin(); //const 疊代器，表示不能通過該疊代器指針修改内容。
for(;iterator != vec1.end();iterator++)
{
cout<<*iterator；
}
vector<Student> vec;
Student stu;
stu.name = "小王";
stu.age = 25;
vec.push_back(stu);
if (!vec.empty())
{
vector<Student>::iterator iter = vec.begin();
cout << (*iter).name << endl; //輸出首元素對象的名字
cout << iter->name << endl; //注意此用法
cout << vec.front().name << endl;
}
防止疊代器失效的方法：
vector<int> vec{ 10,15,25,56 };
auto iter = vec.begin();
int count = 0;
while (iter != vec.end()) //每次更新end,防止疊代器失效
{
iter = vec.insert(iter, 85);
count++;
if (count > 10)
{
break;
}
iter++;
}
for (const auto& it : vec)
{
cout << it << endl;
}
vector<int> vec{ 10,15,25,56 };
auto iter = vec.begin();
while (iter != vec.end())
{
iter = vec.erase(iter); //移除iter位置上的元素，傳回下一個元素的位置
}
vector<int> vec{ 10,15,25,56 };
while (!vec.empty())
{
auto iter = vec.begin(); //移除iter位置上的元素，傳回下一個元素的位置
vec.erase(iter);
}
3、list(需要導入頭檔案#include )
注意：雙向連結清單，不需要各個元素之間的記憶體連續，查找效率不突出，但是能快速的插入和删除。
1. 定義與初始化
list<int> lst1; //建立空list
list<int> lst2(3); //建立含有三個元素的list
list<int> lst3(3,2); //建立含有三個元素的值為2的list
list<int> lst4(lst2); //使用lst2初始化lst4
list<int> lst5(lst2.begin(),lst2.end()); //同lst4
2.常用的操作方法
lst1.assign(lst2.begin(),lst2.end()); //配置設定值
lst1.push_back(10); //添加值
lst1.pop_back(); //删除末尾值
lst1.begin(); //傳回首值的疊代器
lst1.end(); //傳回尾值的疊代器
lst1.clear(); //清空值
bool isEmpty1 = lst1.empty(); //判斷為空
lst1.erase(lst1.begin(),lst1.end()); //删除元素
lst1.front(); //傳回第一個元素的引用
lst1.back(); //傳回最後一個元素的引用
lst1.insert(lst1.begin(),3,2); //從指定位置插入3個值為2的元素
lst1.rbegin(); //傳回第一個元素的前向指針
lst1.remove(2); //相同的元素全部删除
lst1.reverse(); //反轉
lst1.size(); //含有元素個數
lst1.sort(); //排序
lst1.unique(); //删除相鄰重複元素
3. 周遊方法
- 疊代器法
for(list<int>::const_iterator iter = lst1.begin();iter != lst1.end();iter++)
{
cout<<*iter;
}
cout<<endl;
4、deque(雙端隊列)
(需要導入頭檔案#include )
deque容器類與vector類似，支援随機通路和快速插入删除，它在容器中某一位置上的操作所花費的是線性時間。與vector不同的是，deque還支援從開始端插入資料：push_front()。其餘類似vector操作方法的使用。
注意：它允許較為快速地随機通路但它不像vector一樣把所有對象儲存在一個連續的記憶體塊，而是多個連續的記憶體塊
詳細使用：參考部落格C++deque介紹
5、stack(棧容器)
詳細用法：C++ stack(STL stack)用法詳解
6、queue(普通隊列)
先進先出，比較基本的資料結構。
詳細使用：參考部落格：C++ queue(STL queue)用法詳解
7、forward_list(單向連結清單)
C++11新增的，單向連結清單（受限list）,但節省了記憶體
詳細使用：參考部落格：C++ forward_list用法詳解
8、順序容器使用方法小結（操作的共同點）
- 添加元素
| 函數名 | 意義 |
|---|---|
| c.push_back(t) | 在容器c的尾部添加值為t的元素。傳回void 類型 |
| c.push_front(t) | 在容器c的前端添加值為t的元素。傳回void 類型，隻适用于list和deque容器類型。 |
| c.insert(p,t) | 在疊代器p所指向的元素前面插入值為t的新元素。傳回指向新添加元素的疊代器。 |
| c.insert(p,n,t) | 在疊代器p所指向的元素前面插入n個值為t的新元素。傳回void 類型 |
| c.insert(p,b,e) | 在疊代器p所指向的元素前面插入由疊代器b和e标記的範圍内的元素。傳回 void 類型 |
//在容器首部或者尾部添加資料
list<int> ilist;
ilist.push_back(ix);//尾部添加
ilist.push_front(ix);//首部添加
//在容器中指定位置添加元素
list<string> lst;
list<string>::iterator iter = lst.begin();
while (cin >> word)
iter = lst.insert(iter, word); // 和push_front意義一樣
//插入一段元素
list<string> slist;
string sarray[4] = {"quasi", "simba", "frollo", "scar"};
slist.insert(slist.end(), 10, "A");//尾部前添加十個元素都是A
list<string>::iterator slist_iter = slist.begin();
slist.insert(slist_iter, sarray+2, sarray+4);//指針範圍添加
- 器大小的操作
| 函數名 | 意義 |
|---|---|
| c.size() | 傳回容器c中元素個數。傳回類型為 c::size_type |
| c.max_size() | 傳回容器c可容納的最多元素個數，傳回類型為c::size_type |
| c.empty() | 傳回标記容器大小是否為0的布爾值 |
| c.resize(n) | 調整容器c的長度大小，使其能容納n個元素，如果n<c.size()，則删除多出來的元素；否則，添加采用值初始化的新元素 |
| c.resize(n,t) | 調整容器c的長度大小，使其能容納n個元素。所有新添加的元素值都為t |
list<int> ilist(10, 1);
ilist.resize(15); // 尾部添加五個元素，值都為0
ilist.resize(25, -1); // 再在尾部添加十個元素，元素為-1
ilist.resize(5); // 從尾部删除20個元素
- 通路元素
| 函數名 | 意義 |
|---|---|
| c.back() | 傳回容器 c 的最後一個元素的引用。如果 c 為空，則該操作未定 |
| c.front() | 傳回容器 c 的第一個元素的引用。如果 c 為空，則該操作未定義 |
| c[n] | 傳回下标為 n 的元素的引用。如果 n <0 或 n >= c.size()，則該操作未定義，隻适用于 vector 和 deque 容器 |
| c.at(n) | 傳回下标為 n 的元素的引用。如果下标越界，則該操作未定義，隻适用于 vector 和 deque 容器 |
vector<int> vi;
for(int i=0;i<10;i++)vi.push_back(i);
cout<<vi[0]<<endl;
cout<<vi.at(0)<<endl;
cout<<vi[10]<<endl; //越界錯誤
cout<<vi.at(10)<<endl;//越界錯誤
- 删除元素
| 函數名 | 意義 |
|---|---|
| c.erase§ | 删除疊代器p所指向的元素。傳回一個疊代器，它指向被删除元素後面的元素。如果p指向容器内的最後一個元素，則傳回的疊代器指向容器超出末端的下一位置。如果p本身就是指向超出末端的下一位置的疊代器，則該函數未定義 |
| c.erase(b,e) | 删除疊代器b和e所标記的範圍内所有的元素。傳回一個疊代器，它指向被删除元素段後面的元素。如果e本身就是指向超出末端的下一位置的疊代器，則傳回的疊代器也指向容器的超出末端的下一位置 |
| c.clear() | 删除容器c内的所有元素。傳回void |
| c.pop_back() | 删除容器c的最後一個元素。傳回void。如果c為空容器，則該函數未定義 |
| c.pop_front() | 删除容器c的第一個元素。傳回void。如果c為空容器，則該函數未定義，隻适用于 list 或 deque 容器 |
//删除第一個或最後一個元素
list<int> li;
for(int i=0;i<10;i++)list.push_back(i);
li.pop_front();//删除第一個元素
li.pop_back(); //删除最後一個元素
//删除容器内的一個元素
list<int>::iterator iter =li.begin();
if(iter!= li.end())li.erase(iter);
//删除容器内所有元素
li.clear();
- 指派與swap
| 函數名 | 意義 |
|---|---|
| c1 = c2 | 删除容器c1的所有元素，然後将c2的元素複制給c1。c1和c2的類型（包括容器類型和元素類型）必須相同 |
| c1.swap(c2) | 交換内容：調用完該函數後，c1中存放的是 c2 原來的元素，c2中存放的則是c1原來的元素。c1和c2的類型必須相同。該函數的執行速度通常要比将c2複制到c1的操作快 |
| c.assign(b,e) | 重新設定c的元素：将疊代器b和e标記的範圍内所有的元素複制到c中。b和e必須不是指向c中元素的疊代器 |
| c.assign(n,t) | 将容器c重新設定為存儲n個值為t的元素 |
list<string> sl1,sl2;
for(int i=0;i<10;i++)sl2.push_back("a");
sl1.assign(sl2.begin(),sl2.end());//用sl2的指針範圍指派，sl1中十個元素都為a
sl1.assign(10, "A"); //s1被重新指派，擁有十個元素，都為A
vector<string> vs1(3); // vs1有3個元素
vector<string> vs(5); // vs2有5個元素
vs1.swap(vs2);//執行後,vs1中5個元素，而vs2則存3個元素。
注意：vector和list的差別
1. vector類似于數組，記憶體空間是連續的；list是雙向連結清單，記憶體空間并不連續。
2. vector從中間或者開頭插入元素效率比較低；但是list插入元素效率非常高。
3. vector當記憶體不夠時，會動态配置設定記憶體，對原來的對象做析構，在新棧的記憶體中重新建構對象。
4. vector能夠高效的随機存取，而list随機存取比較慢。
![C語言第四章自述2第四章 選擇結構程式設計[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)