C++中的容器大致可以分為兩個大類：順序容器和關聯容器。順序容器中有包含有順序容器適配器。
順序容器：將單一類型元素聚集起來成為容器，然後根據位置來存儲和訪問這些元素。主要有vector、list、deque雙端隊列）。順序容器適配器：stack、queue和priority_queue。
關聯容器：支持通過鍵來高效地查找和讀取元素。主要有：pair、set、map、multiset和multimap。
接下來依次對於各種容器做詳細的介紹。
一、順序容器
1、順序容器定義
為了定義一個容器類型的對象，必須先包含相關的頭文件：
定義vector：#include <vector>
定義list：#include <list>
定義deque：#include <deque>
定義示例
vector<int> vi; list<int> li; deque<int> di;
2、順序容器初始化
函數模板意義C<T> c;
創建一個名為c的空容器。C是容器類型名，如vector，T是元素類型，如int或
string適用於所有容器。
C c(c2);
創建容器c2的副本c；c和c2必須具有相同的容器類型，並存放相同類型的元素。適用於所有容器。
C c(b,e);
創建c，其元素是迭代器b和e標示的范圍內元素的副本。
適用於所有容器。
C c(n,t);
用n個值為t的元素創建容器c，其中值t必須是容器類型C的元素類型的值，或者是可轉換為該類型的值。
只適用於順序容器
C c(n);創建有 n 個值初始化元素的容器 c。
只適用於順序容器
初始化示例：
//初始化為一個容器的副本
vector<int> vi;
vector<int> vi2(vi); //利用vi來初始化vi2
//初始化為一段元素的副本
char*words[] = {"stately", "plump", "buck", "mulligan"};
size_twords_size = sizeof(words)/sizeof(char*);
list<string> words2(words, words + words_size);
//分配和初始化指定數目的元素
constlist<int>::size_type list_size = 64;
list<string> slist(list_size, "a"); // 64 strings, each is a3、順序容器支持的指針運算
①所有順序都支持的指針運行
表達式意義*iter返回迭代器 iter 所指向的元素的引用
iter->mem對iter進行解引用，獲取指定元素中名為mem的成員。等效於(*iter).mem
++iter
iter++
給 iter 加 1，使其指向容器裡的下一個元素
--iter
iter--
給 iter 減 1，使其指向容器裡的前一個元素
iter==iter2
iter1!=iter2
比較兩個迭代器是否相等或不等）。當兩個迭代器指向同一個
容器中的同一個元素，或者當它們都指向同一個容器的超出末端
的下一位置時，兩個迭代器相等
②vector 和 deque 容器的迭代器提供額外的運算
表達式意義iter + n
iter - n
在迭代器上加減）整數值 n，將產生指向容器中前面後面）第 n
個元素的迭代器。新計算出來的迭代器必須指向容器中的元素或超出
容器末端的下一位置
iter1+=iter2
iter1-=iter2
這裡迭代器加減法的復合賦值運算：將 iter1 加上或減去 iter2 的
運算結果賦給 iter1
iter1 -
iter2
兩個迭代器的減法，其運算結果加上右邊的迭代器即得左邊的迭代
器。這兩個迭代器必須指向同一個容器中的元素或超出容器末端的下
一位置
>, >=,
<, <=
迭代器的關系操作符。當一個迭代器指向的元素在容器中位於另一個
迭代器指向的元素之前，則前一個迭代器小於後一個迭代器。關系操
作符的兩個迭代器必須指向同一個容器中的元素或超出容器末端的
下一位置
③迭代器失效：一些容器操作會修改容器的內在狀態或移動容器內的元素。這樣的操作使所有指向被移動的元素的迭代器失效，也可能同時使其他迭代器失效。使用無效迭代器是沒有定義的，可能會導致與懸垂指針相同的問題。
④begin和end成員：begin和end操作產生指向容器內第一個元素和最後一個元素的下一位置的迭代器。
函數名意義c.begin()返回一個迭代器，它指向容器 c 的第一個元素
c.end()返回一個迭代器，它指向容器 c 的最後一個元素的下一位置c.rbegin()返回一個逆序迭代器，它指向容器 c 的最後一個元素c.rend() 返回一個逆序迭代器，它指向容器 c 的第一個元素前面的位置3、順序容器操作
①添加元素
函數名意義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 容器
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; //越界錯誤 cout<<vi.at(10)<<endl;//越界錯誤
④刪除元素
函數名意義c.erase(p)刪除迭代器p所指向的元素。返回一個迭代器，它指向被刪除元素後面的元素。如果p指向容器內的最後一個元素，則返回的迭代器指向容器超出末端的下一位置。如果p本身就是指向超出末端的下一位置的迭代器，則該函數未定義
c.erase(b,e)刪除迭代器b和e所標記的范圍內所有的元素。返回一個迭代器，它指向被刪除元素段後面的元素。如果e本身就是指向超出末端的下一位置的迭代器，則返回的迭代器也指向容器的超出末端的下一位置
c.clear()刪除容器c內的所有元素。返回voidc.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的元素賦值assign示例：
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被重新賦值，擁有十個元素，都為Aswap示例：
vector<string> vs1(3); // vs1有3個元素 vector<string> vs(5); // vs2有5個元素 vs1.swap(vs2);//執行後,vs1中5個元素，而vs2則存3個元素。
⑥vector的自增長：capacity 和 reserve 成員
為了提高vector的效率，不用每次添加元素都重新分配空間。vector會在分配空間時候預分配大於需要的空間。vector 類提供了兩個成員函數：capacity 和reserve 使程序員可與 vector 容器內存分配的實現部分交互工作。
capacity操作：獲取在容器需要分配更多的存儲空間之前能夠存儲的元素總數
reserve操作：告訴vector容器應該預留多少個元素的存儲空間
capacity容量）與size長度）的區別：size指容器當前擁有的元素個數，而capacity則指容器在必須分配新存儲空間之前可以存儲的元素總數。capacity是比size大的一般情況下。
示例：
vector<int> ivec; cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;//都為0 for (vector<int>::size_type ix = 0; ix != 24; ++ix)ivec.push_back(ix); cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;//capacity大於size
可以通過函數reserve()來操作預留空間
//在之前一段代碼的基礎上 ivec.reserveivec.capacity()+50）;//為ivec增加了50的預留空間
另外：如果不手動操作來預留空間，每當 vector 容器不得不分配新的存儲空間時，以加倍當前容量的分配策略實現重新分配。
4、容器的選用
選擇容器類型的常規法則：
①如果程序要求隨機訪問元素，則應使用 vector 或 deque 容器。
②如果程序必須在容器的中間位置插入或刪除元素，則應采用 list 容器。
③如果程序不是在容器的中間位置，而是在容器首部或尾部插入或刪除元素，則應采用 deque 容器。
④如果只需在讀取輸入時在容器的中間位置插入元素，然後需要隨機訪問元素，則可考慮在輸入時將元素讀入到一個 list 容器，接著對此容器重新排序，使其適合順序訪問，然後將排序後的 list 容器復制到一個 vector容器。
如果程序既需要隨機訪問又必須在容器的中間位置插入或刪除元素，選擇何種容器取決於下面兩種操作付出的相對代價：隨機訪問 list 容器元素的代價，以及在 vector 或 deque 容器中插入／刪除元素時復制元素的代價。通常來說，應用中占優勢的操作程序中更多使用的是訪問操作還是插入／刪除操作）將決定應該什麼類型的容器。
5、容器適配器
①適配器通用的操作和類型
名稱意義size_type一種類型，足以存儲此適配器類型最大對象的長度
value_type 元素類型container_type基礎容器的類型，適配器在此容器類型上實現A a; 創建一個新空適配器，命名為 aA a(c); 創建一個名為 a 的新適配器，初始化為容器 c 的副本關系操作符所有適配器都支持全部關系操作符：==、 !=、 <、 <=、 >、>=
②適配器的初始化
所有適配器都定義了兩個構造函數：默認構造函數用於創建空對象，而帶一個容器參數的構造函數將參數容器的副本作為其基礎值。
默認的stack和queue都基於deque容器實現，而priority_queue則在vector容器上實現。
示例：
vector<int> vi; deque<int> deq; stack<int> stk(deq); //用deq初始化stk stack<int> stk1(vi); //報錯
③適配器的操作
棧適配器：
函數名意義s.empty()如果棧為空，則返回true，否則返回stack
s.size() 返回棧中元素的個數s.pop()刪除棧頂元素的值，但不返回其值s.top()返回棧頂元素的值，但不刪除該元素s.push(item)在棧頂壓入新元素隊列和優先級隊列：
函數名意義q.empty()如果隊列為空，則返回true，否則返回false
q.size()返回隊列中元素的個數q.pop() 刪除隊首元素，但不返回其值q.front()返回隊首元素的值，但不刪除該元素
該操作只適用於隊列
q.back()返回隊尾元素的值，但不刪除該元素
該操作只適用於隊列
q.top()返回具有最高優先級的元素值，但不刪除該元素
該操作只適用於優先級隊列
q.push(item)對於queue，在隊尾壓入一個新元素，對於priority_quue，在基於優先級的適當位置插入新元素
二、關聯容器
1、pair
①pairs類型提供的操作
操作名pair<T1, T2>p1
創建一個空的pair對象，它的兩個元素分別是T1和T2類型，采用值初始化
pair<T1, T2>
p1(v1, v2)
創建一個pair對象，它的兩個元素分別是T1和T2，其中first成員初始化為v1，而second成員初始化為v2
make_pair(v1,v2)
以v1和v2值創建一個新pair對象，其元素類型分別是v1和v2的類型
p1 < p2兩個pair對象之間的小於運算，其定義遵循字典次序：如果 p1.first< p2.first或者!(p2.first<p1.first)&&p1.second<p2.second，則返回true
p1 == p2如果兩個pair對象的first和second成員依次相等，則這兩個對象相等。該運算使用其元素的==操作符
p.first 返回p中名為first的公有）數據成員p.second返回p的名為second的公有）數據成員②pairs類型定義和初始化
pair<string, string> test("A", "B");③pairs其他操作
//pairs對象的操作
string firstBook;
if (author.first == "James" && author.second == "Joyce")firstBook = "Stephen Hero";
//生成新的pair對象
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 是鍵－值對的集合。map 類型通常可理解為關聯數組：可使用鍵作為下標來獲取一個值，正如內置數組類型一樣。而關聯的本質在於元素的值與某個特定的鍵相關聯，而並非通過元素在數組中的位置來獲取。
①map對象的定義
map<string, int> word_count;
這個語句定義了一個名為 word_count 的 map 對象，由 string 類型的鍵索引，關聯的值則int型。
map訪問：對迭代器進行解引用時，將獲得一個引用，指向容器中一個pair<const string,int>類
型的值。通過pair類型的訪問方式進行訪問。
②map的構造函數
函數名意義map<k, v>m
創建一個名為m的空map對象，其鍵和值的類型分別為k和v
map<k, v>
m(m2)
創建m2的副本m，m與m2必須有相同的鍵類型和值類型
map<k, v>
m(b, e)
創建map類型的對象m，存儲迭代器b和e標記的范圍內所有元素的副本。元素的類型必須能轉換為pair<const k, v>
③鍵類型的約束
在使用關聯容器時，它的鍵不但有一個類型，而且還有一個相關的比較函數。所用的比較函數必須在鍵類型上定義嚴格弱排序strict weak ordering）：可理解為鍵類型數據上的“小於”關系，雖然實際上可以選擇將比較函數設計得更復雜。
對於鍵類型，唯一的約束就是必須支持 < 操作符，至於是否支持其他的關系或相等運算，則不作要求。
④map類定義的類型
類型意義map<K,V>::key_type
在 map 容器中，用做索引的鍵的類型
map<K,V>::mapped_type
在 map 容器中，鍵所關聯的值的類型map<K,V>::value_type
一個pair類型，它的first元素具有const map<K,V>::key_type類型，而second元素則為map<K,V>::mapped_type 類型
value_type是存儲元素的鍵以及值的pair類型，而且鍵為const。例如，word_count 數組的value_type 為pair<const string,int> 類型。value_type 是 pair 類型，它的值成員可以修改，但鍵成員不能修改。
⑤map添加元素
添加元素有兩種方法：1、先用下標操作符獲取元素，然後給獲取的元素賦值 2、使用insert成員函數實現
下標操作添加元素：如果該鍵已在容器中，則 map 的下標運算與 vector 的下標運算行為相同：返回該鍵所關聯的值。只有在所查找的鍵不存在時，map 容器才為該鍵創建一個新的元素，並將它插入到此 map 對象中。此時，所關聯的值采用值初始化：類類型的元素用默認構造函數初始化，而內置類型的元素初始化為 0。
insert 操作：
函數名意義m.insert(e)e是一個用在m上的value_type 類型的值。如果鍵e.first不在m中，則插入一個值為e.second 的新元素；如果該鍵在m中已存在，則保持m不變。該函數返回一個pair類型對象，包含指向鍵為e.first的元素的map迭代器，以及一個 bool 類型的對象，表示是否插入了該元素
m.insert
(beg,end)
beg和end是標記元素范圍的迭代器，其中的元素必須為m.value_type 類型的鍵－值對。對於該范圍內的所有元素，如果它的鍵在 m 中不存在，則將該鍵及其關聯的值插入到 m。返回 void 類型
m.insert
(iter,e)
e是一個用在m上的 value_type 類型的值。如果鍵e.first）不在m中，則創建新元素，並以迭代器iter為起點搜索新元素存儲的位置。返回一個迭代器，指向m中具有給定鍵的元素
示例：
word_count.insert(map<string, int>::value_type("Anna", 1));
word_count.insert(make_pair("Anna", 1));insert的返回值：包含一個迭代器和一個bool值的pair對象，其中迭代器指向map中具有相應鍵的元素，而bool值則表示是否插入了該元素。如果該鍵已在容器中，則其關聯的值保持不變，返回的bool值為true。在這兩種情況下，迭代器都將指向具有給定鍵的元素。
pair<map<string, int>::iterator, bool> ret = word_count.insert(make_pair(word, 1));
ret存儲insert函數返回的pair對象。該pair的first成員是一個map迭代器，指向插入的鍵。ret.first從insert返回的pair對象中獲取 map 迭代器；ret.second從insert返回是否插入了該元素。
⑥查找並讀取map中的元素
map中使用下標存在一個很危險的副作用：如果該鍵不在 map 容器中，那麼下標操作會插入一個具有該鍵的新元素。所以map 容器提供了兩個操作：count 和 find，用於檢查某個鍵是否存在而不會插入該鍵。
函數名意義m.count(k)返回 m 中 k 的出現次數
m.find(k)如果m容器中存在按k索引的元素，則返回指向該元素的迭代器。如果不存在，則返回超出末端迭代器。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對象中刪除元素
函數名意義m.erase(k)刪除m中鍵為k的元素。返回size_type類型的值，表示刪除的元素個數
m.erase(p)從m中刪除迭代器p所指向的元素。p必須指向m中確實存在的元素，而且不能等於m.end()。返回void
m.erase(b,
e)
從m中刪除一段范圍內的元素，該范圍由迭代器對b和e標記。b和e必須標記m中的一段有效范圍：即b和e都必須指向m中的元素或最後一個元素的下一個位置。而且，b和e要麼相等此時刪除的范圍為空），要麼b所指向的元素必須出在e所
指向的元素之前。返回 void 類型
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 容器的每個鍵都只能對應一個元素。以一段范圍的元素初始化set對象，或在set對象中插入一組元素時，對於每個鍵，事實上都只添加了一個元素。
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個
cout << iset.size() << endl; // 10個②在set中添加元素
set<string> set1;
set1.insert("the"); //第一種方法：直接添加
set<int> iset2;
iset2.insert(ivec.begin(), ivec.end());//第二中方法：通過指針迭代器③從set中獲取元素
set 容器不提供下標操作符。為了通過鍵從 set 中獲取元素，可使用 find運算。如果只需簡單地判斷某個元素是否存在，同樣可以使用 count 運算，返回 set 中該鍵對應的元素個數。當然，對於 set 容器，count 的返回值只能是1該元素存在）或 0該元素不存在）
set<int> iset; for(int i = 0; i<10; i++)iset.insert(i); iset.find(1) // 返回指向元素內容為1的指針 iset.find(11) // 返回指針iset.end() iset.count(1) // 存在，返回1 iset.count(11) // 不存在，返回0
3、multimap 和 multiset
關聯容器 map 和 set 的元素是按順序存儲的。而 multimap 和multset 也一樣。因此，在multimap和multiset容器中，如果某個鍵對應多個實例，則這些實例在容器中將相鄰存放。迭代遍歷multimap或multiset容器時，可保證依次返回特定鍵所關聯的所有元素。
①迭代器的關聯容器操作
函數名意義m.lower_bound(k)返回一個迭代器，指向鍵不小於 k 的第一個元素
m.upper_bound(k)返回一個迭代器，指向鍵大於 k 的第一個元素m.equal_range(k)返回一個迭代器的 pair 對象。它的 first 成員等價於 m.lower_bound(k)。而 second 成員則等價於 m.upper_bound(k)
本文出自 “我的學習筆記” 博客，請務必保留此出處http://6924918.blog.51cto.com/6914918/1275726
