一、容器的定義

? ? ? ?在數(shù)據(jù)存儲(chǔ)上，有一種對(duì)象類(lèi)型，它可以持有其它對(duì)象或指向其它對(duì)像的指針，這種對(duì)象類(lèi)型就叫做容器。很簡(jiǎn)單，容器就是保存其它對(duì)象的對(duì)象，當(dāng)然這是一個(gè)樸素的理解，這種“對(duì)象”還包含了一系列處理“其它對(duì)象”的方法。

二、容器的種類(lèi)

????????1、順序容器：是一種各元素之間有順序關(guān)系的線性表，是一種線性結(jié)構(gòu)的可序群集。順序性容器中的每個(gè)元素均有固定的位置，除非用刪除或插入的操作改變這個(gè)位置。順序容器的元素排列次序與元素值無(wú)關(guān)，而是由元素添加到容器里的次序決定。順序容器包括：vector(向量)、list（列表）、deque（隊(duì)列）。
????????2、關(guān)聯(lián)容器：關(guān)聯(lián)式容器是非線性的樹(shù)結(jié)構(gòu)，更準(zhǔn)確的說(shuō)是二叉樹(shù)結(jié)構(gòu)。各元素之間沒(méi)有嚴(yán)格的物理上的順序關(guān)系，也就是說(shuō)元素在容器中并沒(méi)有保存元素置入容器時(shí)的邏輯順序。但是關(guān)聯(lián)式容器提供了另一種根據(jù)元素特點(diǎn)排序的功能，這樣迭代器就能根據(jù)元素的特點(diǎn)“順序地”獲取元素。元素是有序的集合，默認(rèn)在插入的時(shí)候按升序排列。關(guān)聯(lián)容器包括：map（集合）、set（映射）、multimap（多重集合）、multiset（多重映射）。
????????3、容器適配器：本質(zhì)上，適配器是使一種不同的行為類(lèi)似于另一事物的行為的一種機(jī)制。容器適配器讓一種已存在的容器類(lèi)型采用另一種不同的抽象類(lèi)型的工作方式實(shí)現(xiàn)。適配器是容器的接口，它本身不能直接保存元素，它保存元素的機(jī)制是調(diào)用另一種順序容器去實(shí)現(xiàn)，即可以把適配器看作“它保存一個(gè)容器，這個(gè)容器再保存所有元素”。STL 中包含三種適配器：棧stack 、隊(duì)列queue 和優(yōu)先級(jí)隊(duì)列priority_queue 。

????????4、容器類(lèi)自動(dòng)申請(qǐng)和釋放內(nèi)存，因此無(wú)需new和delete操作。

? ? ? ?

三、不同容器的使用方法

? 1、vector

? ? ? ?①定義與初始化(需要導(dǎo)入頭文件#include <vector>)

? ? ? ? ? ??如果沒(méi)有指定元素的初始化式，那么標(biāo)準(zhǔn)庫(kù)將自行提供一個(gè)元素初始值進(jìn)行，具體值為何，取決于存儲(chǔ)在vector 中元素的數(shù)據(jù)類(lèi)型；如果為int型數(shù)據(jù)，那么標(biāo)準(zhǔn)庫(kù)將用 0 值創(chuàng)建元素初始化式；如果 vector 保存的是含有構(gòu)造函數(shù)的類(lèi)類(lèi)型（如 string）的元素，標(biāo)準(zhǔn)庫(kù)將用該類(lèi)型的默認(rèn)構(gòu)造函數(shù)創(chuàng)建元素初始化式；元素類(lèi)型可能是沒(méi)有定義任何構(gòu)造函數(shù)的類(lèi)類(lèi)型。這種情況下，標(biāo)準(zhǔn)庫(kù)仍產(chǎn)生一個(gè)帶初始值的對(duì)象，這個(gè)對(duì)象的每個(gè)成員進(jìn)行了值初始化。

vector<int> vec1; //默認(rèn)初始化，vec1為空vector<int> vec2(vec1); //使用vec1初始化vec2vector<int> vec3(vec1.begin(),vec1.end());//使用vec1初始化vec2vector<int> vec4(10); //10個(gè)值為0的元素vector<int> vec5(10,4); //10個(gè)值為4的元素vector<string> vec6(10,"null"); //10個(gè)值為null的元素vector<string> vec7(10,"hello"); //10個(gè)值為hello的元素

? ? ? ②常用的操作方法

vec1.push_back(100); //添加元素int size = vec1.size(); //元素個(gè)數(shù)bool isEmpty = vec1.empty(); //判斷是否為空cout<<vec1[0]<<endl; //取得第一個(gè)元素vec1.insert(vec1.end(),5,3); //從vec1.back位置插入5個(gè)值為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類(lèi)型迭代器vec1.clear(); //清空元素

????????③遍歷方法

// 下標(biāo)法(vector的特有訪問(wèn)方法，一般容器只能通過(guò)迭代器訪問(wèn))int length = vec1.size();for ( int i=0;i<length;i++){cout<<vec1[i];}cout<<endl<<endl;// 迭代器法vector< int >::const_iterator iterator = vec1.begin();for (;iterator != vec1.end();iterator++){cout<<*iterator；}

2、list

?????? ①定義與初始化(需要導(dǎo)入頭文件#include <list>)

list<int> lst1; //創(chuàng)建空l(shuí)istlist<int> lst2(3); //創(chuàng)建含有三個(gè)元素的listlist<int> lst3(3,2); //創(chuàng)建含有三個(gè)元素的值為2的listlist<int> lst4(lst2); //使用lst2初始化lst4list<int> lst5(lst2.begin(),lst2.end()); //同lst4

?????? ②常用的操作方法

lst1.assign(lst2.begin(),lst2.end()); //分配值lst1.push_back(10); //添加值lst1.pop_back(); //刪除末尾值lst1.begin(); //返回首值的迭代器lst1.end(); //返回尾值的迭代器lst1.clear(); //清空值bool isEmpty1 = lst1.empty(); //判斷為空l(shuí)st1.erase(lst1.begin(),lst1.end()); //刪除元素lst1.front(); //返回第一個(gè)元素的引用lst1.back(); //返回最后一個(gè)元素的引用lst1.insert(lst1.begin(),3,2); //從指定位置插入3個(gè)值為2的元素lst1.rbegin(); //返回第一個(gè)元素的前向指針lst1.remove(2); //相同的元素全部刪除lst1.reverse(); //反轉(zhuǎn)lst1.size(); //含有元素個(gè)數(shù)lst1.sort(); //排序lst1.unique(); //刪除相鄰重復(fù)元素

?????? ③遍歷方法

//迭代器法for(list<int>::const_iterator iter = lst1.begin();iter != lst1.end();iter++) {cout<<*iter; } cout<<endl;

? 3、deque

?????? deque容器類(lèi)與vector類(lèi)似，支持隨機(jī)訪問(wèn)和快速插入刪除，它在容器中某一位置上的操作所花費(fèi)的是線性時(shí)間。與vector不同的是，deque還支持從開(kāi)始端插入數(shù)據(jù)：push_front()。其余類(lèi)似vector操作方法的使用。(需要導(dǎo)入頭文件#include <deque>)

4、順序容器使用方法小結(jié)

?????? ①添加元素

函數(shù)名 意義 c.push_back(t) 在容器c的尾部添加值為t的元素。返回void 類(lèi)型c.push_front(t) 在容器c的前端添加值為t的元素。返回void 類(lèi)型只適用于list和deque容器類(lèi)型。c.insert(p,t) 在迭代器p所指向的元素前面插入值為t的新元素。返回指向新添加元素的迭代器。c.insert(p,n,t) 在迭代器p所指向的元素前面插入n個(gè)值為t的新元素。返回void 類(lèi)型c.insert(p,b,e) 在迭代器p所指向的元素前面插入由迭代器b和e標(biāo)記的范圍內(nèi)的元素。返回 void 類(lèi)型//在容器首部或者尾部添加數(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è)元素都是A list<string>::iterator slist_iter = slist.begin(); slist.insert(slist_iter, sarray+2, sarray+4);//指針?lè)秶砑?

??????? ②容器大小的操作

函數(shù)名 意義 c.size() 返回容器c中元素個(gè)數(shù)。返回類(lèi)型為 c::size_typec.max_size() 返回容器c可容納的最多元素個(gè)數(shù)，返回類(lèi)型為c::size_typec.empty() 返回標(biāo)記容器大小是否為0的布爾值c.resize(n) 調(diào)整容器c的長(zhǎng)度大小，使其能容納n個(gè)元素，如果n<c.size()，則刪除多出來(lái)的元素；否則，添加采用值初始化的新元素c.resize(n,t) 調(diào)整容器c的長(zhǎng)度大小，使其能容納n個(gè)元素。所有新添加的元素值都為tlist<int> ilist(10, 1); ilist.resize(15); // 尾部添加五個(gè)元素，值都為0 ilist.resize(25, -1); // 再在尾部添加十個(gè)元素，元素為-1 ilist.resize(5); // 從尾部刪除20個(gè)元素

????????③訪問(wèn)元素

函數(shù)名 意義 c.back() 返回容器 c 的最后一個(gè)元素的引用。如果 c 為空，則該操作未定義c.front() 返回容器 c 的第一個(gè)元素的引用。如果 c 為空，則該操作未定義 c[n] 返回下標(biāo)為 n 的元素的引用。如果 n <0 或 n >= c.size()，則該操作未定義只適用于 vector 和 deque 容器c.at(n) 返回下標(biāo)為 n 的元素的引用。如果下標(biāo)越界，則該操作未定義只適用于 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; //越界錯(cuò)誤 cout<<vi.at(10)<<endl;//越界錯(cuò)誤

????????④ 刪除元素

函數(shù)名 意義 c.erase(p) 刪除迭代器p所指向的元素。返回一個(gè)迭代器，它指向被刪除元素后面的元素。如果p指向容器內(nèi)的最后一個(gè)元素，則返回的迭代器指向容器超出末端的下一位置。如果p本身就是指向超出末端的下一位置的迭代器，則該函數(shù)未定義c.erase(b,e) 刪除迭代器b和e所標(biāo)記的范圍內(nèi)所有的元素。返回一個(gè)迭代器，它指向被刪除元素段后面的元素。如果e本身就是指向超出末端的下一位置的迭代器，則返回的迭代器也指向容器的超出末端的下一位置c.clear() 刪除容器c內(nèi)的所有元素。返回void c.pop_back() 刪除容器c的最后一個(gè)元素。返回void。如果c為空容器，則該函數(shù)未定義c.pop_front() 刪除容器c的第一個(gè)元素。返回void。如果c為空容器，則該函數(shù)未定義只適用于 list 或 deque 容器//刪除第一個(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

函數(shù)名 意義 c1 = c2 刪除容器c1的所有元素，然后將c2的元素復(fù)制給c1。c1和c2的類(lèi)型（包括容器類(lèi)型和元素類(lèi)型）必須相同c1.swap(c2) 交換內(nèi)容：調(diào)用完該函數(shù)后，c1中存放的是 c2 原來(lái)的元素，c2中存放的則是c1原來(lái)的元素。c1和c2的類(lèi)型必須相同。該函數(shù)的執(zhí)行速度通常要比將c2復(fù)制到c1的操作快c.assign(b,e) 重新設(shè)置c的元素：將迭代器b和e標(biāo)記的范圍內(nèi)所有的元素復(fù)制到c中。b和e必須不是指向c中元素的迭代器c.assign(n,t) 將容器c重新設(shè)置為存儲(chǔ)n個(gè)值為t的元素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è)元素都為a sl1.assign(10, "A"); //s1被重新賦值，擁有十個(gè)元素，都為Avector<string> vs1(3); // vs1有3個(gè)元素 vector<string> vs(5); // vs2有5個(gè)元素 vs1.swap(vs2);//執(zhí)行后,vs1中5個(gè)元素，而vs2則存3個(gè)元素。

5、map

????????(需要導(dǎo)入頭文件#include <map>)
?????? C++中map容器提供一個(gè)鍵值對(duì)（key/value）容器，map與multimap差別僅僅在于multiple允許一個(gè)鍵對(duì)應(yīng)多個(gè)值。對(duì)于迭代器來(lái)說(shuō)，可以修改實(shí)值，而不能修改key。Map會(huì)根據(jù)key自動(dòng)排序。??? ?
??????? map 是鍵－值對(duì)的集合。map 類(lèi)型通常可理解為關(guān)聯(lián)數(shù)組：可使用鍵作為下標(biāo)來(lái)獲取一個(gè)值，正如內(nèi)置數(shù)組類(lèi)型一樣。而關(guān)聯(lián)的本質(zhì)在于元素的值與某個(gè)特定的鍵相關(guān)聯(lián)，而并非通過(guò)元素在數(shù)組中的位置來(lái)獲取。

?????? ①定義與初始化

map<int,string> map1; //空map函數(shù)名 意義 map<k, v>m創(chuàng)建一個(gè)名為m的空map對(duì)象，其鍵和值的類(lèi)型分別為k和vmap<k, v>m(m2)創(chuàng)建m2的副本m，m與m2必須有相同的鍵類(lèi)型和值類(lèi)型map<k, v>m(b, e)創(chuàng)建map類(lèi)型的對(duì)象m，存儲(chǔ)迭代器b和e標(biāo)記的范圍內(nèi)所有元素的副本。元素的類(lèi)型必須能轉(zhuǎn)換為pair<const k, v>

?????? 在使用關(guān)聯(lián)容器時(shí)，它的鍵不但有一個(gè)類(lèi)型，而且還有一個(gè)相關(guān)的比較函數(shù)。所用的比較函數(shù)必須在鍵類(lèi)型上定義嚴(yán)格弱排序（strict weak ordering）：可理解為鍵類(lèi)型數(shù)據(jù)上的“小于”關(guān)系，雖然實(shí)際上可以選擇將比較函數(shù)設(shè)計(jì)得更復(fù)雜。
?????? 對(duì)于鍵類(lèi)型，唯一的約束就是必須支持 < 操作符，至于是否支持其他的關(guān)系或相等運(yùn)算，則不作要求。

?????? ②常用的操作方法

?????? 添加元素有兩種方法：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)的值采用值初始化：類(lèi)類(lèi)型的元素用默認(rèn)構(gòu)造函數(shù)初始化，而內(nèi)置類(lèi)型的元素初始化為 0。

insert 操作：函數(shù)名 意義 m.insert(e) e是一個(gè)用在m上的value_type 類(lèi)型的值。如果鍵（e.first不在m中，則插入一個(gè)值為e.second 的新元素；如果該鍵在m中已存在，則保持m不變。該函數(shù)返回一個(gè)pair類(lèi)型對(duì)象，包含指向鍵為e.first的元素的map迭代器，以及一個(gè) bool 類(lèi)型的對(duì)象，表示是否插入了該元素m.insert(beg,end)beg和end是標(biāo)記元素范圍的迭代器，其中的元素必須為m.value_type 類(lèi)型的鍵－值對(duì)。對(duì)于該范圍內(nèi)的所有元素，如果它的鍵在 m 中不存在，則將該鍵及其關(guān)聯(lián)的值插入到 m。返回 void 類(lèi)型m.insert(iter,e) e是一個(gè)用在m上的 value_type 類(lèi)型的值。如果鍵（e.first）不在m中，則創(chuàng)建新元素，并以迭代器iter為起點(diǎn)搜索新元素存儲(chǔ)的位置。返回一個(gè)迭代器，指向m中具有給定鍵的元素例1：word_count.insert(map<string, int >::value_type( "Anna" , 1)); word_count.insert(make_pair( "Anna" , 2));//返回false，且鍵值仍為1. word_count["Anna"] = 2;//鍵值變?yōu)?insert的返回值：包含一個(gè)迭代器和一個(gè)bool值的pair對(duì)象，其中迭代器指向map中具有相應(yīng)鍵的元素， 而bool值則表示是否插入了該元素。 如果該鍵已在容器中，則其關(guān)聯(lián)的值保持不變，返回的bool值為false。 在這兩種情況下，迭代器都將指向具有給定鍵的元素。例2： 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返回是否插入了該元素。例3：map1[3] = "Saniya"; //添加元素map1.insert(map<int,string>::value_type(2,"Diyabi"));//插入元素map1.insert(pair<int,string>(1,"Siqinsini"));map1.insert(make_pair<int,string>(4,"V5"));string str = map1[3]; //根據(jù)key取得value，key不能修改map<int,string>::iterator iter_map = map1.begin();//取得迭代器首地址int key = iter_map->first; //取得keystring value = iter_map->second; //取得valuemap1.erase(iter_map); //刪除迭代器數(shù)據(jù)map1.erase(3); //根據(jù)key刪除valuemap1.size(); //元素個(gè)數(shù)map1.empty(); //判斷空map1.clear(); //清空所有元素

????????③遍歷

??? map中使用下標(biāo)存在一個(gè)很危險(xiǎn)的副作用：如果該鍵不在 map 容器中，那么下標(biāo)操作會(huì)插入一個(gè)具有該鍵的新元素。所以map 容器提供了兩個(gè)操作：count 和 find，用于檢查某個(gè)鍵是否存在而不會(huì)插入該鍵。

函數(shù)名 意義 m.count(k) 返回 m 中 k 的出現(xiàn)次數(shù)m.find(k) 如果m容器中存在按k索引的元素，則返回指向該元素的迭代器。如果不存在，則返回超出末端迭器。 例1： 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;例2： for(map<int,string>::iterator iter = map1.begin();iter!=map1.end();iter++){int keyk = iter->first;string valuev = iter->second;}

????????④從map對(duì)象中刪除元素

函數(shù)名 意義 m.erase(k) 刪除m中鍵為k的元素。返回size_type類(lèi)型的值，表示刪除的元素個(gè)數(shù) m.erase(p) 從m中刪除迭代器p所指向的元素。p必須指向m中確實(shí)存在的元素，而且不能等于m.end()。返回void m.erase(b,e) 從m中刪除一段范圍內(nèi)的元素，該范圍由迭代器對(duì)b和e標(biāo)記。b和e必須標(biāo)記m中的一段有效范圍：即b和e都必須指向m中的元素或最后一個(gè)元素的下一個(gè)位置。而且，b和e要么相等（此時(shí)刪除的范圍為空），要么b所指向的元素必須出在e所指向的元素之前。返回 void 類(lèi)型 string removal_word = "a"; if (word_count.erase(removal_word)) cout << "ok: " << removal_word << " removed\n"; else cout << "oops: " << removal_word << " not found!\n";

6、set

?????? set的含義是集合，它是一個(gè)有序的容器，里面的元素都是排序好的，支持插入，刪除，查找等操作，就像一個(gè)集合一樣。所有的操作的都是嚴(yán)格在logn時(shí)間之內(nèi)完成，效率非常高。set和multiset的區(qū)別是：set插入的元素不能相同，但是multiset可以相同。Set默認(rèn)自動(dòng)排序。使用方法類(lèi)似list。(需要導(dǎo)入頭文件#include <set>)

?????? ①set容器的定義和使用

?????????? set 容器的每個(gè)鍵都只能對(duì)應(yīng)一個(gè)元素。以一段范圍的元素初始化set對(duì)象，或在set對(duì)象中插入一組元素時(shí)，對(duì)于每個(gè)鍵，事實(shí)上都只添加了一個(gè)元素。

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中添加元素

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（該元素不存在）。

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) // 不存在，返回0set<int>::iterator it=iset.begin() *it就是當(dāng)前迭代器指向的值set默認(rèn)是從小到大排列值，定義時(shí)set<int,greater<int>> iset;則此時(shí)默認(rèn)是從大到小排列值。

????????④迭代器的關(guān)聯(lián)容器操作

函數(shù)名 意義 m.lower_bound(k) 返回一個(gè)迭代器，指向鍵不小于 k 的第一個(gè)元素m.upper_bound(k) 返回一個(gè)迭代器，指向鍵大于 k 的第一個(gè)元素 m.equal_range(k) 返回一個(gè)迭代器的 pair 對(duì)象。它的 first 成員等價(jià)于 m.lower_bound(k)。而 second 成員則等價(jià)于 m.upper_bound(k)

四、各種容器的元素在內(nèi)存中的儲(chǔ)存方式

????????1、vector（向量）：相當(dāng)于數(shù)組，但其大小可以不預(yù)先指定，并且自動(dòng)擴(kuò)展。它可以像數(shù)組一樣被操作，由于它的特性我們完全可以將vector 看作動(dòng)態(tài)數(shù)組。在創(chuàng)建一個(gè)vector 后，它會(huì)自動(dòng)在內(nèi)存中分配一塊連續(xù)的內(nèi)存空間進(jìn)行數(shù)據(jù)存儲(chǔ)，初始的空間大小可以預(yù)先指定也可以由vector 默認(rèn)指定，這個(gè)大小即capacity （）函數(shù)的返回值。當(dāng)存儲(chǔ)的數(shù)據(jù)超過(guò)分配的空間時(shí)vector 會(huì)重新分配一塊內(nèi)存塊，但這樣的分配是很耗時(shí)的，效率非常低。

????????2、deque（隊(duì)列）：它不像vector 把所有的對(duì)象保存在一塊連續(xù)的內(nèi)存塊，而是采用多個(gè)連續(xù)的存儲(chǔ)塊，并且在一個(gè)映射結(jié)構(gòu)中保存對(duì)這些塊及其順序的跟蹤。向deque 兩端添加或刪除元素的開(kāi)銷(xiāo)很小，它不需要重新分配空間。

????????3、list（列表）：是一個(gè)線性鏈表結(jié)構(gòu)，它的數(shù)據(jù)由若干個(gè)節(jié)點(diǎn)構(gòu)成，每一個(gè)節(jié)點(diǎn)都包括一個(gè)信息塊（即實(shí)際存儲(chǔ)的數(shù)據(jù)）、一個(gè)前驅(qū)指針和一個(gè)后驅(qū)指針。它無(wú)需分配指定的內(nèi)存大小且可以任意伸縮，這是因?yàn)樗鎯?chǔ)在非連續(xù)的內(nèi)存空間中，并且由指針將有序的元素鏈接起來(lái)。

????????4、set, multiset, map, multimap 是一種非線性的樹(shù)結(jié)構(gòu)，具體的說(shuō)采用的是一種比較高效的特殊的平衡檢索二叉樹(shù)—— 紅黑樹(shù)結(jié)構(gòu)。

五、各種容器優(yōu)劣分析

1、Vector：

??????? 優(yōu)點(diǎn)：
????????? A、支持隨機(jī)訪問(wèn)，訪問(wèn)效率高和方便，它像數(shù)組一樣被訪問(wèn)，即支持[ ] 操作符和vector.at()。
????????? B、節(jié)省空間，因?yàn)樗沁B續(xù)存儲(chǔ)，在存儲(chǔ)數(shù)據(jù)的區(qū)域都是沒(méi)有被浪費(fèi)的，但是要明確一點(diǎn)vector 大多情況下并不是滿存的，在未存儲(chǔ)的區(qū)域?qū)嶋H是浪費(fèi)的。
????????缺點(diǎn)：
????????? A、在內(nèi)部進(jìn)行插入、刪除操作效率非常低。
????????? B、只能在vector 的最后進(jìn)行push 和pop ，不能在vector 的頭進(jìn)行push 和pop 。
????????? C、 當(dāng)動(dòng)態(tài)添加的數(shù)據(jù)超過(guò)vector 默認(rèn)分配的大小時(shí)要進(jìn)行內(nèi)存的重新分配、拷貝與釋放，這個(gè)操作非常消耗能。

2、List：

????????優(yōu)點(diǎn)：
? ??????? A、不使用連續(xù)的內(nèi)存空間這樣可以隨意地進(jìn)行動(dòng)態(tài)操作，插入、刪除操作效率高；
????????缺點(diǎn)：
? ????????A、不能進(jìn)行內(nèi)部的隨機(jī)訪問(wèn)，即不支持[ ] 操作符和vector.at()，訪問(wèn)效率低。
? ????????B、相對(duì)于verctor 占用更多的內(nèi)存。

3、Deque：

????????優(yōu)點(diǎn)：
? ????????A、支持隨機(jī)訪問(wèn)，方便，即支持[ ] 操作符和vector.at() ，但性能沒(méi)有vector 好；
? ????????B、可以在兩端進(jìn)行push 、pop 。
????????缺點(diǎn)：
? ??????? A、在內(nèi)部進(jìn)行插入、刪除操作效率低。

綜合：

????????vector 的查詢性能最好，并且在末端增加數(shù)據(jù)也很好，除非它重新申請(qǐng)內(nèi)存段；適合高效地隨機(jī)存儲(chǔ)。
????????list 是一個(gè)鏈表，任何一個(gè)元素都可以是不連續(xù)的，但它都有兩個(gè)指向上一元素和下一元素的指針。所以它對(duì)插入、刪除元素性能是最好的，而查詢性能非常差；適合 大量地插入和刪除操作而不關(guān)心隨機(jī)存取的需求。
????????deque 是介于兩者之間，它兼顧了數(shù)組和鏈表的優(yōu)點(diǎn)，它是分塊的鏈表和多個(gè)數(shù)組的聯(lián)合。所以它有被list 好的查詢性能，有被vector 好的插入、刪除性能。 如果你需要隨即存取又關(guān)心兩端數(shù)據(jù)的插入和刪除，那么deque 是最佳之選。關(guān)聯(lián)容器的特點(diǎn)是明顯的，相對(duì)于順序容器，有以下幾個(gè)主要特點(diǎn)：
????????A， 其內(nèi)部實(shí)現(xiàn)是采用非線性的二叉樹(shù)結(jié)構(gòu)，具體的說(shuō)是紅黑樹(shù)的結(jié)構(gòu)原理實(shí)現(xiàn)的；
????????B， set 和map 保證了元素的唯一性，mulset 和mulmap 擴(kuò)展了這一屬性，可以允許元素不唯一；
????????C， 元素是有序的集合，默認(rèn)在插入的時(shí)候按升序排列。

基于以上分析

??????? A， 關(guān)聯(lián)容器對(duì)元素的插入和刪除操作比vector 要快，因?yàn)関ector 是順序存儲(chǔ)，而關(guān)聯(lián)容器是鏈?zhǔn)酱鎯?chǔ)；比list 要慢，是因?yàn)榧词顾鼈兺擎準(zhǔn)浇Y(jié)構(gòu)，但list 是線性的，而關(guān)聯(lián)容器是二叉樹(shù)結(jié)構(gòu)，其改變一個(gè)元素涉及到其它元素的變動(dòng)比list 要多，并且它是排序的，每次插入和刪除都需要對(duì)元素重新排序；

????????B， 關(guān)聯(lián)容器對(duì)元素的檢索操作比vector 慢，但是比list 要快很多。vector 是順序的連續(xù)存儲(chǔ)，當(dāng)然是比不上的，但相對(duì)鏈?zhǔn)降膌ist 要快很多是因?yàn)閘ist 是逐個(gè)搜索，它搜索的時(shí)間是跟容器的大小成正比，而關(guān)聯(lián)容器 查找的復(fù)雜度基本是Log(N) ，比如如果有1000 個(gè)記錄，最多查找10 次，1,000,000 個(gè)記錄，最多查找20 次。容器越大，關(guān)聯(lián)容器相對(duì)list 的優(yōu)越性就越能體現(xiàn)；

????????C， 在使用上set 區(qū)別于vector,deque,list 的最大特點(diǎn)就是set 是內(nèi)部排序的，這在查詢上雖然遜色于vector ，但是卻大大的強(qiáng)于list 。

????????D， 在使用上map 的功能是不可取代的，它保存了“鍵- 值”關(guān)系的數(shù)據(jù)，而這種鍵值關(guān)系采用了類(lèi)數(shù)組的方式。數(shù)組是用數(shù)字類(lèi)型的下標(biāo)來(lái)索引元素的位置，而map 是用字符型關(guān)鍵字來(lái)索引元素的位置。在使用上map 也提供了一種類(lèi)數(shù)組操作的方式，即它可以通過(guò)下標(biāo)來(lái)檢索數(shù)據(jù)，這是其他容器做不到的，當(dāng)然也包括set 。（STL 中只有vector 和map 可以通過(guò)類(lèi)數(shù)組的方式操作元素，即如同ele[1] 方式）。

六、關(guān)于容器的相關(guān)的問(wèn)題

1、sizeof、size()、capacity問(wèn)題

vector<int> ivec;cout<<sizeof(ivec)<<endl; // 12cout<<ivec.size()<<endl; // 0cout<<ivec.capacity()<<endl; // 0for(int i=0;i<10;i++)ivec.push_back(1);cout<<sizeof(ivec)<<endl; // 12Cout<<ivec.size()<<endl; // 10cout<<ivec.capacity()<<endl; // 16

總結(jié)

以上是生活随笔為你收集整理的C++容器亲自总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。