C++中的容器大致可以分為兩個(gè)大類：順序容器和關(guān)聯(lián)容器。順序容器中有包含有順序容器適配器。
順序容器：將單一類型元素聚集起來(lái)成為容器，然后根據(jù)位置來(lái)存儲(chǔ)和訪問(wèn)這些元素。主要有vector、list、deque（雙端隊(duì)列）。順序容器適配器：stack、queue和priority_queue。
關(guān)聯(lián)容器：支持通過(guò)鍵來(lái)高效地查找和讀取元素。主要有：pair、set、map、multiset和multimap。
接下來(lái)依次對(duì)于各種容器做詳細(xì)的介紹。
一、順序容器
1、順序容器定義
為了定義一個(gè)容器類型的對(duì)象，必須先包含相關(guān)的頭文件：
定義vector：#include <vector>
定義list：#include <list>
定義deque：#include <deque>
定義示例
|
1
2
3
|
vector<int> vi;list<int> li;deque<int> di; |
2、順序容器初始化
初始化示例：
|
1
2
3
4
5
6
7
8
9
10
|
//初始化為一個(gè)容器的副本vector<int> vi;vector<int> vi2(vi); //利用vi來(lái)初始化vi2//初始化為一段元素的副本char*words[] = {"stately", "plump", "buck", "mulligan"};size_twords_size = sizeof(words)/sizeof(char*);list<string> words2(words, words + words_size);//分配和初始化指定數(shù)目的元素constlist<int>::size_type list_size = 64;list<string> slist(list_size, "a"); // 64 strings, each is a |
3、順序容器支持的指針運(yùn)算
①所有順序都支持的指針運(yùn)行
②vector 和 deque 容器的迭代器提供額外的運(yùn)算
③迭代器失效：一些容器操作會(huì)修改容器的內(nèi)在狀態(tài)或移動(dòng)容器內(nèi)的元素。這樣的操作使所有指向被移動(dòng)的元素的迭代器失效，也可能同時(shí)使其他迭代器失效。使用無(wú)效迭代器是沒(méi)有定義的，可能會(huì)導(dǎo)致與懸垂指針相同的問(wèn)題。
④begin和end成員：begin和end操作產(chǎn)生指向容器內(nèi)第一個(gè)元素和最后一個(gè)元素的下一位置的迭代器。
3、順序容器操作
①添加元素
添加元素示例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
//在容器首部或者尾部添加數(shù)據(jù)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");//尾部前添加十個(gè)元素都是Alist<string>::iterator slist_iter = slist.begin();slist.insert(slist_iter, sarray+2, sarray+4);//指針?lè)秶砑?/code> |
②容器大小的操作
示例：
|
1
2
3
4
|
list<int> ilist(10, 1);ilist.resize(15); // 尾部添加五個(gè)元素，值都為0ilist.resize(25, -1); // 再在尾部添加十個(gè)元素，元素為-1ilist.resize(5); // 從尾部刪除20個(gè)元素 |
③訪問(wèn)元素
|
1
2
3
4
5
6
|
int 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; //越界錯(cuò)誤cout<<vi.at(10)<<endl;//越界錯(cuò)誤 |
④刪除元素
示例：
|
1
2
3
4
5
6
7
8
9
10
|
//刪除第一個(gè)或最后一個(gè)元素list<int> li;for(int i=0;i<10;i++)list.push_back(i);li.pop_front();//刪除第一個(gè)元素li.pop_back(); //刪除最后一個(gè)元素//刪除容器內(nèi)的一個(gè)元素list<int>::iterator iter =li.begin();if(iter!= li.end())li.erase(iter);//刪除容器內(nèi)所有元素li.clear(); |
⑤賦值與swap
|
1
2
3
4
|
list<string> sl1,sl2;for(int i=0;i<10;i++)sl2.push_back("a");sl1.assign(sl2.begin(),sl2.end());//用sl2的指針?lè)秶x值，sl1中十個(gè)元素都為asl1.assign(10, "A"); //s1被重新賦值，擁有十個(gè)元素，都為A |
swap示例：
vector<string> vs1(3); // vs1有3個(gè)元素
vector<string> vs(5); // vs2有5個(gè)元素
vs1.swap(vs2);//執(zhí)行后,vs1中5個(gè)元素，而vs2則存3個(gè)元素。
⑥vector的自增長(zhǎng)：capacity 和 reserve 成員
為了提高vector的效率，不用每次添加元素都重新分配空間。vector會(huì)在分配空間時(shí)候預(yù)分配大于需要的空間。vector 類提供了兩個(gè)成員函數(shù)：capacity 和reserve 使程序員可與 vector 容器內(nèi)存分配的實(shí)現(xiàn)部分交互工作。
capacity操作：獲取在容器需要分配更多的存儲(chǔ)空間之前能夠存儲(chǔ)的元素總數(shù)
reserve操作：告訴vector容器應(yīng)該預(yù)留多少個(gè)元素的存儲(chǔ)空間
capacity（容量）與size（長(zhǎng)度）的區(qū)別：size指容器當(dāng)前擁有的元素個(gè)數(shù)，而capacity則指容器在必須分配新存儲(chǔ)空間之前可以存儲(chǔ)的元素總數(shù)。capacity是比size大的一般情況下。
示例：
|
1
2
3
4
5
6
|
vector<int> ivec;cout << "ivec: size: " << ivec.size()<< " capacity: " << ivec.capacity() << endl;//都為0for (vector<int>::size_type ix = 0; ix != 24; ++ix)ivec.push_back(ix);cout << "ivec: size: " << ivec.size()<< " capacity: " << ivec.capacity() << endl;//capacity大于size |
可以通過(guò)函數(shù)reserve()來(lái)操作預(yù)留空間
//在之前一段代碼的基礎(chǔ)上
ivec.reserve（ivec.capacity()+50）;//為ivec增加了50的預(yù)留空間
另外：如果不手動(dòng)操作來(lái)預(yù)留空間，每當(dāng) vector 容器不得不分配新的存儲(chǔ)空間時(shí)，以加倍當(dāng)前容量的分配策略實(shí)現(xiàn)重新分配。
4、容器的選用
選擇容器類型的常規(guī)法則：
①如果程序要求隨機(jī)訪問(wèn)元素，則應(yīng)使用 vector 或 deque 容器。
②如果程序必須在容器的中間位置插入或刪除元素，則應(yīng)采用 list 容器。
③如果程序不是在容器的中間位置，而是在容器首部或尾部插入或刪除元素，則應(yīng)采用 deque 容器。
④如果只需在讀取輸入時(shí)在容器的中間位置插入元素，然后需要隨機(jī)訪問(wèn)元素，則可考慮在輸入時(shí)將元素讀入到一個(gè) list 容器，接著對(duì)此容器重新排序，使其適合順序訪問(wèn)，然后將排序后的 list 容器復(fù)制到一個(gè) vector容器。
如果程序既需要隨機(jī)訪問(wèn)又必須在容器的中間位置插入或刪除元素，選擇何種容器取決于下面兩種操作付出的相對(duì)代價(jià)：隨機(jī)訪問(wèn) list 容器元素的代價(jià)，以及在 vector 或 deque 容器中插入／刪除元素時(shí)復(fù)制元素的代價(jià)。通常來(lái)說(shuō)，應(yīng)用中占優(yōu)勢(shì)的操作（程序中更多使用的是訪問(wèn)操作還是插入／刪除操作）將決定應(yīng)該什么類型的容器。
5、容器適配器
①適配器通用的操作和類型
②適配器的初始化
所有適配器都定義了兩個(gè)構(gòu)造函數(shù)：默認(rèn)構(gòu)造函數(shù)用于創(chuàng)建空對(duì)象，而帶一個(gè)容器參數(shù)的構(gòu)造函數(shù)將參數(shù)容器的副本作為其基礎(chǔ)值。
默認(rèn)的stack和queue都基于deque容器實(shí)現(xiàn)，而priority_queue則在vector容器上實(shí)現(xiàn)。
示例：
|
1
2
3
4
|
vector<int> vi;deque<int> deq;stack<int> stk(deq); //用deq初始化stkstack<int> stk1(vi); //報(bào)錯(cuò) |
③適配器的操作
棧適配器：
隊(duì)列和優(yōu)先級(jí)隊(duì)列：
二、關(guān)聯(lián)容器
1、pair
①pairs類型提供的操作
②pairs類型定義和初始化
pair<string, string> test("A", "B");
③pairs其他操作
|
1
2
3
4
5
6
7
8
|
//pairs對(duì)象的操作string firstBook;if (author.first == "James" && author.second == "Joyce")firstBook = "Stephen Hero";//生成新的pair對(duì)象pair<string, string> next_auth;next_auth = make_pair("A","B");//第一種方法next_auth = pair<string, string>("A","B"); //第二種方法cin>>next_auth.first>>next_auth.second;//第三種方法 |
2、map
map 是鍵－值對(duì)的集合。map 類型通常可理解為關(guān)聯(lián)數(shù)組：可使用鍵作為下標(biāo)來(lái)獲取一個(gè)值，正如內(nèi)置數(shù)組類型一樣。而關(guān)聯(lián)的本質(zhì)在于元素的值與某個(gè)特定的鍵相關(guān)聯(lián)，而并非通過(guò)元素在數(shù)組中的位置來(lái)獲取。
①map對(duì)象的定義
map<string, int> word_count;
這個(gè)語(yǔ)句定義了一個(gè)名為 word_count 的 map 對(duì)象，由 string 類型的鍵索引，關(guān)聯(lián)的值則int型。
map訪問(wèn)：對(duì)迭代器進(jìn)行解引用時(shí)，將獲得一個(gè)引用，指向容器中一個(gè)pair<const string,int>類
型的值。通過(guò)pair類型的訪問(wèn)方式進(jìn)行訪問(wèn)。
②map的構(gòu)造函數(shù)
③鍵類型的約束
在使用關(guān)聯(lián)容器時(shí)，它的鍵不但有一個(gè)類型，而且還有一個(gè)相關(guān)的比較函數(shù)。所用的比較函數(shù)必須在鍵類型上定義嚴(yán)格弱排序（strict weak ordering）：可理解為鍵類型數(shù)據(jù)上的“小于”關(guān)系，雖然實(shí)際上可以選擇將比較函數(shù)設(shè)計(jì)得更復(fù)雜。
對(duì)于鍵類型，唯一的約束就是必須支持 < 操作符，至于是否支持其他的關(guān)系或相等運(yùn)算，則不作要求。
④map類定義的類型
value_type是存儲(chǔ)元素的鍵以及值的pair類型，而且鍵為const。例如，word_count 數(shù)組的value_type 為pair<const string,int> 類型。value_type 是 pair 類型，它的值成員可以修改，但鍵成員不能修改。
⑤map添加元素
添加元素有兩種方法：1、先用下標(biāo)操作符獲取元素，然后給獲取的元素賦值 2、使用insert成員函數(shù)實(shí)現(xiàn)
下標(biāo)操作添加元素：如果該鍵已在容器中，則 map 的下標(biāo)運(yùn)算與 vector 的下標(biāo)運(yùn)算行為相同：返回該鍵所關(guān)聯(lián)的值。只有在所查找的鍵不存在時(shí)，map 容器才為該鍵創(chuàng)建一個(gè)新的元素，并將它插入到此 map 對(duì)象中。此時(shí)，所關(guān)聯(lián)的值采用值初始化：類類型的元素用默認(rèn)構(gòu)造函數(shù)初始化，而內(nèi)置類型的元素初始化為 0。
insert 操作：
示例：
|
1
2
|
word_count.insert(map<string, int>::value_type("Anna", 1));word_count.insert(make_pair("Anna", 1)); |
insert的返回值：包含一個(gè)迭代器和一個(gè)bool值的pair對(duì)象，其中迭代器指向map中具有相應(yīng)鍵的元素，而bool值則表示是否插入了該元素。如果該鍵已在容器中，則其關(guān)聯(lián)的值保持不變，返回的bool值為true。在這兩種情況下，迭代器都將指向具有給定鍵的元素。
pair<map<string, int>::iterator, bool> ret =
word_count.insert(make_pair(word, 1));
ret存儲(chǔ)insert函數(shù)返回的pair對(duì)象。該pair的first成員是一個(gè)map迭代器，指向插入的鍵。ret.first從insert返回的pair對(duì)象中獲取 map 迭代器；ret.second從insert返回是否插入了該元素。
⑥查找并讀取map中的元素
map中使用下標(biāo)存在一個(gè)很危險(xiǎn)的副作用：如果該鍵不在 map 容器中，那么下標(biāo)操作會(huì)插入一個(gè)具有該鍵的新元素。所以map 容器提供了兩個(gè)操作：count 和 find，用于檢查某個(gè)鍵是否存在而不會(huì)插入該鍵。
|
1
2
3
4
|
int occurs = 0;if (word_count.count("foobar"))occurs = word_count["foobar"];map<string,int>::iterator it = word_count.find("foobar");if (it != word_count.end())occurs = it->second; |
⑦從map對(duì)象中刪除元素
|
1
2
3
4
|
string removal_word = "a";if (word_count.erase(removal_word))cout << "ok: " << removal_word << " removed\n";else cout << "oops: " << removal_word << " not found!\n"; |
3、set
①set容器的定義和使用
set 容器的每個(gè)鍵都只能對(duì)應(yīng)一個(gè)元素。以一段范圍的元素初始化set對(duì)象，或在set對(duì)象中插入一組元素時(shí)，對(duì)于每個(gè)鍵，事實(shí)上都只添加了一個(gè)元素。
|
1
2
3
4
5
6
7
8
|
vector<int> ivec;for (vector<int>::size_type i = 0; i != 10; ++i) {ivec.push_back(i);ivec.push_back(i);}set<int> iset(ivec.begin(), ivec.end());cout << ivec.size() << endl; //20個(gè)cout << iset.size() << endl; // 10個(gè) |
②在set中添加元素
|
1
2
3
4
|
set<string> set1;set1.insert("the"); //第一種方法：直接添加set<int> iset2;iset2.insert(ivec.begin(), ivec.end());//第二中方法：通過(guò)指針迭代器 |
③從set中獲取元素
set 容器不提供下標(biāo)操作符。為了通過(guò)鍵從 set 中獲取元素，可使用 find運(yùn)算。如果只需簡(jiǎn)單地判斷某個(gè)元素是否存在，同樣可以使用 count 運(yùn)算，返回 set 中該鍵對(duì)應(yīng)的元素個(gè)數(shù)。當(dāng)然，對(duì)于 set 容器，count 的返回值只能是1（該元素存在）或 0（該元素不存在）
|
1
2
3
4
5
6
|
set<int> iset;for(int i = 0; i<10; i++)iset.insert(i);iset.find(1) // 返回指向元素內(nèi)容為1的指針iset.find(11) // 返回指針iset.end()iset.count(1) // 存在，返回1iset.count(11) // 不存在，返回0 |
3、multimap 和 multiset
關(guān)聯(lián)容器 map 和 set 的元素是按順序存儲(chǔ)的。而 multimap 和multset 也一樣。因此，在multimap和multiset容器中，如果某個(gè)鍵對(duì)應(yīng)多個(gè)實(shí)例，則這些實(shí)例在容器中將相鄰存放。迭代遍歷multimap或multiset容器時(shí)，可保證依次返回特定鍵所關(guān)聯(lián)的所有元素。
①迭代器的關(guān)聯(lián)容器操作
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助。
