c++容器list、vector、map、set區別
list
封裝鏈表，以鏈表形式實現，不支持[]運算符。
對隨機訪問的速度很慢(需要遍歷整個鏈表)，插入數據很快(不需要拷貝和移動數據，只需改變指針的指向)。
新添加的元素，list可以任意加入。
vector
封裝數組，使用連續內存存儲，支持[]運算符。
對隨機訪問的速度很快，對頭插元素速度很慢，尾插元素速度很快
新添加的元素，vector有一套算法。
map
採用平衡檢索二叉樹:紅黑樹
存儲結構為鍵值對
set
採用平衡檢索二叉樹:紅黑樹
set中不包含重複的數據
Hash_Map
採用hash算法加快查找過程，但需要更多內存存放hash桶元素，是一種採用空間換取時間的策略。
c++容器list、vector、map、set用法
vector
在內存中分配一塊連續的存儲空間進行存儲，支持不指定vector大小的存儲。即將元素置於一個動態數組中加以管理的容器。
vector對象的創建
vector vector容器名稱 vectorvecInt; //一個存放int的vector容器。 vectorvecFloat; //一個存放float的vector容器。 vectorvecString; //一個存放string的vector容器。
vector常用操作
vector.size(); //返回容器中元素的個數 vector.empty(); //判斷容器是否為空 vector.resize(num); //重新指定容器的長度為num vector.push_back(1); //在容器尾部加入一個元素 vector.pop_back(); //移除容器中最後一個元素 vector.clear(); //移除容器的所有數據 vector.erase(beg,end); //刪除[beg,end)區間的數據，返回下一個數據的位置。 vector.erase(pos); //刪除pos位置的數據，返回下一個數據的位置。 vector.insert(pos,elem); //在pos位置插入一個elem元素的拷貝，返回新數據的位置。 vector.insert(pos,n,elem); //在pos位置插入n個elem數據，無返回值。 vector.insert(pos,beg,end); //在pos位置插入[beg,end)區間的數據，無返回值 vector::iterator iter = find(vector.begin(),vector.end(),3);//查找元素3是否存在vector中。若存在返回元素,否則返回vector.end()。find()函數加上頭文件**#include**
vector的正向遍歷和反向遍歷
//正向遍歷 for(vector::iterator it=vecInt.begin(); it!=vecInt.end(); ++it) { int iItem = *it; cout << iItem; //或直接使用 cout << *it; } //反向遍歷 for(vector::reverse_iterator rit=vecInt.rbegin(); rit!=vecInt.rend(); ++rit) //注意，小括號內仍是++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所指的數據，如果idx越界，拋出out_of_range異常。 vector[idx]; //返回索引idx所指的數據，越界時，運行直接報錯
只能從尾部進行插入和刪除，不能從頭部進行插入和刪除。中間進行插入和刪除操作需要把插入位置後媽的元素後移或前移，效率低。
vector的內存管理與效率
當元素需要插入且容器的容量不足時會發生重新分配。
問題這會導致vector的原始內存分配和回收、對象的拷貝和析構和迭代器、指針和引用的失效。
問題產生的原因:vector容器分配的是一塊連續的內存空間，每次容器的增長，並不是在原有連續的內存空間後再進行簡單的疊加，而是重新申請一塊更大的新內存(一般是當前大小的1.5~2倍的新內存區)，並把現有容器中的元素逐個複製過去，同時銷燬舊的內存。
問題解決方法
提前使用reserve()函數設定容器大小，在vector操作的末尾添加vector
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(); //反轉鏈表，
不支持內部的隨機訪問，即不支持[]操作符和vector.at()
deque
deque在功能上合併vector和list
deque是雙端數組，vector是單端，所以這兩個容器在操作上很多地方是一樣的。添加刪除操作和list一樣，其他操作同上。
支持內部的隨機訪問，即不支持[]操作符和vector.at()
可在內部方便的進行插入和刪除操作，兩端都可進行push和pop
stack
stack堆棧容器，是一種“先進後出”的容器
stack.push(elem); //往棧頭添加元素 stack.pop(); //從棧頭移除第一個元素 stack.top(); //返回最後一個壓入棧元素，即返回棧頂元素
queue
queue隊列容器，是一種“先進先出”的容器
stack.push(elem); //往隊尾添加元素 stack.pop(); //從隊頭移除第一個元素
其他操作同deque容器。
priority_queue
priority_queue優先級隊列，背後是堆的思想。
用來開發一些特殊的應用，可以對STL類庫進行擴展
priority_queue<int, deque> pq; priority_queue<int, vector> pq;
最大值優先級隊列、最小值優先級隊列
priority_queuep1; //默認是 最大值優先級隊列 大頂堆，隊頭元素最大 //priority_queue<int, vector, less> p1; //相當於這樣寫 priority_queue<int, vector, greater> p2; //最小值優先級隊列
set和multiset容器
這兩個容器屬於關聯式容器(元素的值與某個特定的鍵相關聯)，對應同一個頭文件#include
set是一個集合容器，其中所包含的元素是唯一的，集合中的元素按一定順序排列，元素插入過程是按排序規則插入，所有不能指定插入位置。
set採用紅黑樹變體的數據結構實現，紅黑樹屬於平衡二叉樹，在插入和刪除操作上比vector快。
原因set容器本質是二叉樹，不需要做內存拷貝和移動。set容器內所有元素都是以節點的方式來存儲，其節點的結構和鏈表類似，如圖所示。在插入時只需把節點的指針指向新的節點即可，刪除類似把指向刪除節點的指針指向其他節點即可。
set容器中每次insert後，以前保存的iterator不會失效。因為iterator相當於指向節點的指針，內存不變，指向內存的指針就不會變。
set不支持內部的隨機訪問，即不支持[]操作符和vector.at()。但是set中查找使用二分查找，即使數據元素增多，插入和搜索的速度也不會變即log2。
multiset與set的區別：set支持唯一鍵值，每個元素值只能出現一次；而multiset中同一值可以出現多次。
不可以直接修改set或multiset容器中的元素值，因為該類容器是自動排序的。如果希望修改一個元素值，必須先刪除原有的元素，再插入新的元素。
基本操作
set<int,less> setIntA; //該容器是按升序方式排列元素。 set<int,greater> setIntB; //該容器是按降序方式排列元素。 set相當於 set<int,less>。
pair的使用
pair譯為對組，可以將兩個值視為一個單元。
pair
以下操作返回一個pair
set.find(elem); //查找elem元素，返回指向elem元素的迭代器。 set.count(elem); //返回容器中值為elem的元素個數。對set來說，要麼是0，要麼是1。對multiset來說，值可能大於1。 set.lower_bound(elem); //返回第一個>=elem元素的迭代器。 set.upper_bound(elem); // 返回第一個>elem元素的迭代器。 set.equal_range(elem); //返回容器中與elem相等的上下限的兩個迭代器。上限是閉區間，下限是開區間，如[beg,end)。
map和multimap容器
這兩個容器屬於關聯式容器，對應同一個頭文件#include
map是一個鍵值對序列，即(key,value)對，其中key是唯一的，集合中的元素按一定順序排列，元素插入過程是按排序規則插入，所有不能指定插入位置。
map採用紅黑樹變體平衡二叉樹的數據結構實現，在插入和刪除操作上比vector快。
map可以直接存取key所對應的value，支持[]操作符，如map[key]=value。
multimap與map的區別：map支持唯一鍵值，每個鍵只能出現一次；而multimap中相同鍵可以出現多次。multimap不支持[]操作符。
基本操作
插入元素四種方式，前三種返回值為pair
一、通過pair的方式插入對象 mapStu.insert( pair(3,"小張") ); 二、通過pair的方式插入對象 mapStu.inset(make_pair(-1, “校長-1”)); 三、通過value_type的方式插入對象 mapStu.insert( map::value_type(1,"小李") ); 四、通過數組的方式插入值 mapStu[3] = “小劉"; map.begin(); //返回容器中第一個數據的迭代器。 map.end(); //返回容器中最後一個數據之後的迭代器。
迭代器遍歷
//前向遍歷和反向遍歷同上 for (map::iterator it=mapA.begin(); it!=mapA.end(); ++it) { cout <first << " " << it->second << endl; } //數組方式遍歷 for(int i = 1;i<=mapStu.size();++i) { cout << i << " " << mapStu[i] << endl; }
map的排序
map<T1,T2,less> mapA; //該容器是按鍵的升序方式排列元素。未指定函數對象，默認採用less函數對象。 map<T1,T2,greater> mapB; //該容器是按鍵的降序方式排列元素。
總結
deque的使用場景：比如排隊購票系統，對排隊者的存儲可以採用deque，支持頭端的快速移除，尾端的快速添加。如果採用vector，則頭端移除時，會移動大量的數據，速度慢。
vector與deque的比較：
vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的開始位置卻是不固定的。
如果有大量釋放操作的話，vector花的時間更少，這跟二者的內部實現有關。
deque支持頭部的快速插入與快速移除，這是deque的優點。
list的使用場景：比如公交車乘客的存儲，隨時可能有乘客下車，支持頻繁的不確實位置元素的移除插入。
set的使用場景：比如對手機遊戲的個人得分記錄的存儲，存儲要求從高分到低分的順序排列。
map的使用場景：比如按ID號存儲十萬個用戶，想要快速要通過ID查找對應的用戶。二叉樹的查找效率，這時就體現出來了。如果是vector容器，最壞的情況下可能要遍歷完整個容器才能找到該用戶。
[qp18502452 ] c++容器list、vector、map、set區別與用法詳解已經有258次圍觀