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

list

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

vector

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

map

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

set

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

Hash_Map

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

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

vector

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

vector對象的創(chuàng)建

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

vector常用操作

vector.size();        //返回容器中元素的個數(shù)
vector.empty();   //判斷容器是否為空
vector.resize(num);   //重新指定容器的長度為num
vector.push_back(1);  //在容器尾部加入一個元素
vector.pop_back();    //移除容器中最后一個元素
vector.clear(); //移除容器的所有數(shù)據(jù)
vector.erase(beg,end); //刪除[beg,end)區(qū)間的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置。
vector.erase(pos);  //刪除pos位置的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置。
vector.insert(pos,elem);  //在pos位置插入一個elem元素的拷貝，返回新數(shù)據(jù)的位置。
vector.insert(pos,n,elem);  //在pos位置插入n個elem數(shù)據(jù)，無返回值。
vector.insert(pos,beg,end);  //在pos位置插入[beg,end)區(qū)間的數(shù)據(jù)，無返回值 
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)  //注意，小括號內(nèi)仍是++rit
{
    int iItem = *rit;
        cout << iItem; //或直接使用cout << *rit;
}
//直接用vector[i]的方式訪問第i個元素
for(int i = 0;i<5;i++)
{
 cout << vector[i] << " " ;
}
//for_each進行遍歷
for_each(vector.begin(),vector.end(),print);

支持隨機訪問，即支持[]運算符和vector.at()

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

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

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

問題解決方法

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

list

list是一個雙向鏈表容器，可高效地進行插入刪除操作

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

list常用操作

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

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

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

deque

deque在功能上合并vector和list

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

stack

stack堆棧容器，是一種“先進后出”的容器

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

queue

queue隊列容器，是一種“先進先出”的容器

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

其他操作同deque容器。

priority_queue

• priority_queue優(yōu)先級隊列，背后是堆的思想。
• 用來開發(fā)一些特殊的應(yīng)用，可以對STL類庫進行擴展

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

最大值優(yōu)先級隊列、最小值優(yōu)先級隊列

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

set和multiset容器

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

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

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

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

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

multiset與set的區(qū)別：set支持唯一鍵值，每個元素值只能出現(xiàn)一次；而multiset中同一值可以出現(xiàn)多次。
不可以直接修改set或multiset容器中的元素值，因為該類容器是自動排序的。如果希望修改一個元素值，必須先刪除原有的元素，再插入新的元素。

基本操作

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

pair的使用

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

以下操作返回一個pair

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

map和multimap容器

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

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

基本操作

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

一、通過pair的方式插入對象
mapStu.insert( pair<int,string>(3,"小張") );
二、通過pair的方式插入對象
mapStu.inset(make_pair(-1, “校長-1”));
三、通過value_type的方式插入對象
mapStu.insert( map<int,string>::value_type(1,"小李") );
四、通過數(shù)組的方式插入值
mapStu[3] = “小劉";
map.begin(); //返回容器中第一個數(shù)據(jù)的迭代器。
map.end(); //返回容器中最后一個數(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ù)對象，默認(rèn)采用less<T1>函數(shù)對象。
map<T1,T2,greater<T1>> mapB;  //該容器是按鍵的降序方式排列元素。

總結(jié)

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

vector與deque的比較：

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

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

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

最新評論