c++容器list、vector、map、set區(qū)別

list

• 封裝鏈表，以鏈表形式實(shí)現(xiàn)，不支持[]運(yùn)算符。
• 對(duì)隨機(jī)訪問的速度很慢(需要遍歷整個(gè)鏈表)，插入數(shù)據(jù)很快(不需要拷貝和移動(dòng)數(shù)據(jù)，只需改變指針的指向)。
• 新添加的元素，list可以任意加入。

vector

• 封裝數(shù)組，使用連續(xù)內(nèi)存存儲(chǔ)，支持[]運(yùn)算符。
• 對(duì)隨機(jī)訪問的速度很快，對(duì)頭插元素速度很慢，尾插元素速度很快
• 新添加的元素，vector有一套算法。

map

• 采用平衡檢索二叉樹:紅黑樹
• 存儲(chǔ)結(jié)構(gòu)為鍵值對(duì)<key,value>

set

• 采用平衡檢索二叉樹:紅黑樹
• set中不包含重復(fù)的數(shù)據(jù)

Hash_Map

• 采用hash算法加快查找過程，但需要更多內(nèi)存存放hash桶元素，是一種采用空間換取時(shí)間的策略。
  

c++容器list、vector、map、set用法

vector

在內(nèi)存中分配一塊連續(xù)的存儲(chǔ)空間進(jìn)行存儲(chǔ)，支持不指定vector大小的存儲(chǔ)。即將元素置于一個(gè)動(dòng)態(tài)數(shù)組中加以管理的容器。

vector對(duì)象的創(chuàng)建

vector<數(shù)據(jù)類型> vector容器名稱
vector<int> vecInt;     //一個(gè)存放int的vector容器。
vector<float> vecFloat;     //一個(gè)存放float的vector容器。
vector<string> vecString;    //一個(gè)存放string的vector容器。

vector常用操作

vector.size();        //返回容器中元素的個(gè)數(shù)
vector.empty();   //判斷容器是否為空
vector.resize(num);   //重新指定容器的長(zhǎng)度為num
vector.push_back(1);  //在容器尾部加入一個(gè)元素
vector.pop_back();    //移除容器中最后一個(gè)元素
vector.clear(); //移除容器的所有數(shù)據(jù)
vector.erase(beg,end); //刪除[beg,end)區(qū)間的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。
vector.erase(pos);  //刪除pos位置的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。
vector.insert(pos,elem);  //在pos位置插入一個(gè)elem元素的拷貝，返回新數(shù)據(jù)的位置。
vector.insert(pos,n,elem);  //在pos位置插入n個(gè)elem數(shù)據(jù)，無(wú)返回值。
vector.insert(pos,beg,end);  //在pos位置插入[beg,end)區(qū)間的數(shù)據(jù)，無(wú)返回值 
vector<int>::iterator iter = find(vector.begin(),vector.end(),3);//查找元素3是否存在vector中。若存在返回元素,否則返回vector.end()。find()函數(shù)加上頭文件**#include<algorithm>**

vector的正向遍歷和反向遍歷

//正向遍歷
for(vector<int>::iterator it=vecInt.begin(); it!=vecInt.end(); ++it)
{
   int iItem = *it; 
   cout << iItem;  //或直接使用 cout << *it;
}
//反向遍歷
for(vector<int>::reverse_iterator rit=vecInt.rbegin(); rit!=vecInt.rend(); ++rit)  //注意，小括號(hào)內(nèi)仍是++rit
{
    int iItem = *rit;
        cout << iItem; //或直接使用cout << *rit;
}
//直接用vector[i]的方式訪問第i個(gè)元素
for(int i = 0;i<5;i++)
{
 cout << vector[i] << " " ;
}
//for_each進(jìn)行遍歷
for_each(vector.begin(),vector.end(),print);

支持隨機(jī)訪問，即支持[]運(yùn)算符和vector.at()

vector.at(idx);   //返回索引idx所指的數(shù)據(jù)，如果idx越界，拋出out_of_range異常。
vector[idx];  //返回索引idx所指的數(shù)據(jù)，越界時(shí)，運(yùn)行直接報(bào)錯(cuò)

只能從尾部進(jìn)行插入和刪除，不能從頭部進(jìn)行插入和刪除。中間進(jìn)行插入和刪除操作需要把插入位置后媽的元素后移或前移，效率低。

vector的內(nèi)存管理與效率
當(dāng)元素需要插入且容器的容量不足時(shí)會(huì)發(fā)生重新分配。
問題這會(huì)導(dǎo)致vector的原始內(nèi)存分配和回收、對(duì)象的拷貝和析構(gòu)和迭代器、指針和引用的失效。
問題產(chǎn)生的原因:vector容器分配的是一塊連續(xù)的內(nèi)存空間，每次容器的增長(zhǎng)，并不是在原有連續(xù)的內(nèi)存空間后再進(jìn)行簡(jiǎn)單的疊加，而是重新申請(qǐng)一塊更大的新內(nèi)存(一般是當(dāng)前大小的1.5~2倍的新內(nèi)存區(qū))，并把現(xiàn)有容器中的元素逐個(gè)復(fù)制過去，同時(shí)銷毀舊的內(nèi)存。

問題解決方法

提前使用reserve()函數(shù)設(shè)定容器大小，在vector操作的末尾添加vector<int>().swap(v)來(lái)修正過剩的空間或內(nèi)存。

list

list是一個(gè)雙向鏈表容器，可高效地進(jìn)行插入刪除操作

list.push_back(elem);   //在容器尾部加入一個(gè)元素
list.pop_back();         //刪除容器中最后一個(gè)元素
list.push_front(elem);     //在容器開頭插入一個(gè)元素
list.pop_front();         //從容器開頭移除第一個(gè)元素

list常用操作

list的大小size()之類的和插入刪除操作以及遍歷操作同vector

list.front();            //返回第一個(gè)元素。
list.back();            //返回最后一個(gè)元素。
list.begin();           //返回容器中第一個(gè)元素的迭代器。
list.end();            //返回容器中最后一個(gè)元素之后的迭代器。
list.reverse();         //反轉(zhuǎn)鏈表，

不支持內(nèi)部的隨機(jī)訪問，即不支持[]操作符和vector.at()

deque

deque在功能上合并vector和list

• deque是雙端數(shù)組，vector是單端，所以這兩個(gè)容器在操作上很多地方是一樣的。添加刪除操作和list一樣，其他操作同上。
• 支持內(nèi)部的隨機(jī)訪問，即不支持[]操作符和vector.at()
• 可在內(nèi)部方便的進(jìn)行插入和刪除操作，兩端都可進(jìn)行push和pop

stack

stack堆棧容器，是一種“先進(jìn)后出”的容器

stack.push(elem);  //往棧頭添加元素
stack.pop();       //從棧頭移除第一個(gè)元素
stack.top();      //返回最后一個(gè)壓入棧元素，即返回棧頂元素

queue

queue隊(duì)列容器，是一種“先進(jìn)先出”的容器

stack.push(elem);  //往隊(duì)尾添加元素
stack.pop();       //從隊(duì)頭移除第一個(gè)元素

其他操作同deque容器。

priority_queue

• priority_queue優(yōu)先級(jí)隊(duì)列，背后是堆的思想。
• 用來(lái)開發(fā)一些特殊的應(yīng)用，可以對(duì)STL類庫(kù)進(jìn)行擴(kuò)展

priority_queue<int, deque<int>>   pq;
priority_queue<int, vector<int>>  pq;

最大值優(yōu)先級(jí)隊(duì)列、最小值優(yōu)先級(jí)隊(duì)列

priority_queue<int> p1; //默認(rèn)是 最大值優(yōu)先級(jí)隊(duì)列 大頂堆，隊(duì)頭元素最大
//priority_queue<int, vector<int>, less<int> > p1; //相當(dāng)于這樣寫
priority_queue<int, vector<int>, greater<int>> p2; //最小值優(yōu)先級(jí)隊(duì)列

set和multiset容器

這兩個(gè)容器屬于關(guān)聯(lián)式容器(元素的值與某個(gè)特定的鍵相關(guān)聯(lián))，對(duì)應(yīng)同一個(gè)頭文件#include<set>

• set是一個(gè)集合容器，其中所包含的元素是唯一的，集合中的元素按一定順序排列，元素插入過程是按排序規(guī)則插入，所有不能指定插入位置。
• set采用紅黑樹變體的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，紅黑樹屬于平衡二叉樹，在插入和刪除操作上比vector快。

原因set容器本質(zhì)是二叉樹，不需要做內(nèi)存拷貝和移動(dòng)。set容器內(nèi)所有元素都是以節(jié)點(diǎn)的方式來(lái)存儲(chǔ)，其節(jié)點(diǎn)的結(jié)構(gòu)和鏈表類似，如圖所示。在插入時(shí)只需把節(jié)點(diǎn)的指針指向新的節(jié)點(diǎn)即可，刪除類似把指向刪除節(jié)點(diǎn)的指針指向其他節(jié)點(diǎn)即可。

set容器中每次insert后，以前保存的iterator不會(huì)失效。因?yàn)閕terator相當(dāng)于指向節(jié)點(diǎn)的指針，內(nèi)存不變，指向內(nèi)存的指針就不會(huì)變。

set不支持內(nèi)部的隨機(jī)訪問，即不支持[]操作符和vector.at()。但是set中查找使用二分查找，即使數(shù)據(jù)元素增多，插入和搜索的速度也不會(huì)變即log2。

multiset與set的區(qū)別：set支持唯一鍵值，每個(gè)元素值只能出現(xiàn)一次；而multiset中同一值可以出現(xiàn)多次。
不可以直接修改set或multiset容器中的元素值，因?yàn)樵擃惾萜魇亲詣?dòng)排序的。如果希望修改一個(gè)元素值，必須先刪除原有的元素，再插入新的元素。

基本操作

set<int,less<int> > setIntA; //該容器是按升序方式排列元素。
set<int,greater<int>> setIntB;  //該容器是按降序方式排列元素。
set<int> 相當(dāng)于 set<int,less<int>>。

pair的使用

pair譯為對(duì)組，可以將兩個(gè)值視為一個(gè)單元。
pair<T1,T2>存放的兩個(gè)值的類型，可以不一樣，如T1為int，T2為float。T1,T2也可以是自定義類型。

以下操作返回一個(gè)pair

set.find(elem);   //查找elem元素，返回指向elem元素的迭代器。
set.count(elem);    //返回容器中值為elem的元素個(gè)數(shù)。對(duì)set來(lái)說(shuō)，要么是0，要么是1。對(duì)multiset來(lái)說(shuō)，值可能大于1。
set.lower_bound(elem);   //返回第一個(gè)>=elem元素的迭代器。
set.upper_bound(elem);   // 返回第一個(gè)>elem元素的迭代器。
set.equal_range(elem);   //返回容器中與elem相等的上下限的兩個(gè)迭代器。上限是閉區(qū)間，下限是開區(qū)間，如[beg,end)。

map和multimap容器

這兩個(gè)容器屬于關(guān)聯(lián)式容器，對(duì)應(yīng)同一個(gè)頭文件#include<map>，查找的時(shí)間復(fù)雜度為logn

• map是一個(gè)鍵值對(duì)序列，即(key,value)對(duì)，其中key是唯一的，集合中的元素按一定順序排列，元素插入過程是按排序規(guī)則插入，所有不能指定插入位置。
• map采用紅黑樹變體平衡二叉樹的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，在插入和刪除操作上比vector快。
• map可以直接存取key所對(duì)應(yīng)的value，支持[]操作符，如map[key]=value。
• multimap與map的區(qū)別：map支持唯一鍵值，每個(gè)鍵只能出現(xiàn)一次；而multimap中相同鍵可以出現(xiàn)多次。multimap不支持[]操作符。

基本操作

插入元素四種方式，前三種返回值為pair<iterator,bool>。其他操作同set容器。

一、通過pair的方式插入對(duì)象
mapStu.insert( pair<int,string>(3,"小張") );
二、通過pair的方式插入對(duì)象
mapStu.inset(make_pair(-1, “校長(zhǎng)-1”));
三、通過value_type的方式插入對(duì)象
mapStu.insert( map<int,string>::value_type(1,"小李") );
四、通過數(shù)組的方式插入值
mapStu[3] = “小劉";
map.begin(); //返回容器中第一個(gè)數(shù)據(jù)的迭代器。
map.end(); //返回容器中最后一個(gè)數(shù)據(jù)之后的迭代器。

迭代器遍歷

//前向遍歷和反向遍歷同上
for (map<int,string>::iterator it=mapA.begin(); it!=mapA.end(); ++it)
{
  cout <<it->first << " " << it->second << endl;
}
//數(shù)組方式遍歷
for(int i = 1;i<=mapStu.size();++i)
{
   cout << i << " " << mapStu[i] << endl;
}

map的排序

map<T1,T2,less<T1> > mapA; //該容器是按鍵的升序方式排列元素。未指定函數(shù)對(duì)象，默認(rèn)采用less<T1>函數(shù)對(duì)象。
map<T1,T2,greater<T1>> mapB;  //該容器是按鍵的降序方式排列元素。

總結(jié)

deque的使用場(chǎng)景：比如排隊(duì)購(gòu)票系統(tǒng)，對(duì)排隊(duì)者的存儲(chǔ)可以采用deque，支持頭端的快速移除，尾端的快速添加。如果采用vector，則頭端移除時(shí)，會(huì)移動(dòng)大量的數(shù)據(jù)，速度慢。

vector與deque的比較：

vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的開始位置卻是不固定的。
如果有大量釋放操作的話，vector花的時(shí)間更少，這跟二者的內(nèi)部實(shí)現(xiàn)有關(guān)。
deque支持頭部的快速插入與快速移除，這是deque的優(yōu)點(diǎn)。
list的使用場(chǎng)景：比如公交車乘客的存儲(chǔ)，隨時(shí)可能有乘客下車，支持頻繁的不確實(shí)位置元素的移除插入。
set的使用場(chǎng)景：比如對(duì)手機(jī)游戲的個(gè)人得分記錄的存儲(chǔ)，存儲(chǔ)要求從高分到低分的順序排列。
map的使用場(chǎng)景：比如按ID號(hào)存儲(chǔ)十萬(wàn)個(gè)用戶，想要快速要通過ID查找對(duì)應(yīng)的用戶。二叉樹的查找效率，這時(shí)就體現(xiàn)出來(lái)了。如果是vector容器，最壞的情況下可能要遍歷完整個(gè)容器才能找到該用戶。

參考
《傳智播客c++基礎(chǔ)和進(jìn)階課堂講義》
《后臺(tái)開發(fā) 核心技術(shù)與應(yīng)用實(shí)踐》---第三章

到此這篇關(guān)于c++容器list、vector、map、set區(qū)別與用法詳解的文章就介紹到這了,更多相關(guān)c++ list、vector、map、set內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！