C++標(biāo)準(zhǔn)模板庫STL容器
容器都是類模板，它們實(shí)例化后就成為容器類。用容器類定義的對象稱為容器對象。對象或變量插入容器時，實(shí)際插入的是對象或變量的一個復(fù)制品。
容器分類
順序容器
1、元素在容器中的位置同元素的值無關(guān)，即容器不是排序的。
2、順序容器包括：vector、deque、list。
關(guān)聯(lián)容器
1、關(guān)聯(lián)容器內(nèi)的元素是有規(guī)則排列的（排序或加入哈希桶），插入元素時，容器會按一定的排序規(guī)則將元素放在適當(dāng)?shù)奈恢蒙?。因?yàn)榘匆?guī)則排列，關(guān)聯(lián)容器在查找時具有非常好的性能。
2、關(guān)聯(lián)容器包括：set、multiset、map、multimap、unordered_set、unordered_multiset、unordered_map、std::unordered_multimap等。
3、不能修改關(guān)聯(lián)容器中key的值，因?yàn)樵匦薷暮笕萜鞑⒉粫詣又匦屡判?。正確的做法的是， 先刪除該元素，再插入新元素。
容器適配器
1、STL在兩類容器的基礎(chǔ)上屏蔽一部分功能，突出或增加另一部分功能，實(shí)現(xiàn)了容器適配器。
2、STL中容器適配器有stack、queue、priority_queue三種，它們都是在順序容器的基礎(chǔ)上實(shí)現(xiàn)的。
容器通用接口
所有容器
int size( ) 返回容器對象中元素的個數(shù)
bool empty( ) 判斷容器對象是否為空
順序容器
front() 返回容器中第一個元素的引用
back() 返回容器中最后一個元素的引用
push_back() 在容器末尾增加新元素
pop_back() 刪除容器末尾的元素
insert() 插入一個或多個元素
順序容器和關(guān)聯(lián)容器
begin( ) 返回指向容器中第一個元素的迭代器
end( ) 返回指向容器中最后一個元素后面的位置的迭代器
rbegin( ) 返回指向容器中最后一個元素的反向迭代器
rend( ) 返回指向容器中第一個元素前面的位置的反響迭代器
erase( ) 從容器中刪除一個或幾個元素
clear( ) 從容器中刪除所有的元素
如果一個容器為空，則begin()和end()的返回值相等，rbegin()和rend()的返回值也相等
容器適配器
push：添加一個元素
top：返回頂部或?qū)︻^的元素的引用
pop：刪除一個元素
順序容器
vector
1、動態(tài)數(shù)組，也叫可變長數(shù)組，在堆中分配內(nèi)存，元素存放在連續(xù)的內(nèi)存空間，支持下標(biāo)隨機(jī)訪問，元素可重復(fù)，且是無序存放。
2、在頭部或中間進(jìn)行插入和刪除操作時，會造成內(nèi)存塊的拷貝；對尾部進(jìn)行插入和刪除時一般不會拷貝內(nèi)存；擴(kuò)容時會內(nèi)存拷貝。
擴(kuò)容方式
開辟二倍的內(nèi)存；舊的數(shù)據(jù)拷貝到新的內(nèi)存；釋放舊內(nèi)存；重新指向新內(nèi)存。
時間復(fù)雜度
1、[ ]或at()下標(biāo)訪問任意元素，時間復(fù)雜度是O(1)。
2、push_back尾部插入、pop_back尾部刪除，時間復(fù)雜度O(1)。
3、insert插入、erase刪除時間復(fù)雜度O(n)。
#include <vector>
std::vector<int> _v;
_v.push_back(20);//尾部添加元素
_v.push_back(10);
_v.push_back(10);//{20,10,10}
printf("_v.front=%d\n",_v.front());//隊(duì)首元素，_v.front=20
printf("_v.back=%d\n",_v.back());//隊(duì)尾元素，_v.back=10
_v.pop_back();//移除尾部元素，{20,10}
_v.insert(_v.begin() + 1, 30); //在指定的位置插入元素10的拷貝，{20,30,10}
_v.erase(_v.begin() + 2);//刪除指定位置的元素，{20,30}
//遍歷，可以使用下標(biāo)遍歷，也可以使用迭代器遍歷
auto iter = _v.begin();
while(iter != _v.end())
{
printf("value=%d\n",*iter);
iter++;
}
printf("_v[0]=%d,_v.at(1)=%d\n",_v[0],_v.at(1));//下標(biāo)訪問，越界crash，at拋出異常
打印
_v.front=20
_v.back=10
value=20
value=30
_v[0]=20,_v.at(1)=30
list
1、雙向鏈表，存放在堆中，內(nèi)存空間是不連續(xù)的，每個元素都存放在一塊內(nèi)存中，通過指針指向上一個元素和下一個元素。元素可重復(fù)，且是無序存放。
2、不需要擴(kuò)容，添加元素時分配內(nèi)存，刪除元素時回收內(nèi)存。
3、在任何位置添加和刪除元素效率都很高，無需內(nèi)存拷貝。
4、不能下標(biāo)隨機(jī)訪問，訪問任意元素效率低。
時間復(fù)雜度
1、訪問首部和尾部是O(1)，訪問其他元素是O(n)。
2、push_back、push_front、insert插入是O(1)，pop_front、pop_back、erase刪除是O(1)。
#include <list>
std::list<int> _l;
_l.push_back(20);//尾部添加元素
_l.push_back(30);
_l.push_back(40);
_l.push_front(10);//頭部添加元素{10,20,30,40}
printf("_l.front=%d\n",_l.front());//訪問隊(duì)首元素，_l.front=10
printf("_l.back=%d\n",_l.back());//訪問隊(duì)尾元素，_l.back=40
_l.pop_back();//移除尾部元素，{10,20,30}
_l.pop_front();//移除頭部元素，{20,30}
//list迭代器只能++/--，不能+i隨機(jī)訪問
_l.erase(_l.begin());//刪除指定位置的元素，{30}
_l.insert(++_l.begin(), 50); //在指定的位置插入元素10的拷貝，{30,50}
//使用迭代器遍歷,不能使用下標(biāo)訪問
auto iter = _l.begin();
while(iter != _l.end())
{
printf("value=%d\n",*iter);
iter++;
}
打印
_l.front=10
_l.back=40
value=30
value=50
deque
1、雙端隊(duì)列，deque類似于一個二維數(shù)組，由多個連續(xù)小空間拼接而成，引入map管理分段空間；map是一塊連續(xù)的空間，map的每個元素是指向緩存區(qū)buffer的指針，每個緩存區(qū)buffer存儲多個元素。
2、deque底層是假象的連續(xù)空間，實(shí)際上是分段連續(xù)的，為了“整體連續(xù)”和下標(biāo)隨機(jī)訪問，deque定義了復(fù)雜的迭代器，實(shí)現(xiàn)隨機(jī)訪問。
3、deque結(jié)合了vector和list的優(yōu)缺點(diǎn)，在隊(duì)首和隊(duì)尾進(jìn)行插入和刪除操作時效率高，遍歷和排序效率低，中間插入和刪除元素仍然存在內(nèi)存拷貝，隨機(jī)訪問時需要計(jì)算數(shù)據(jù)在哪個buffer的第幾個數(shù)據(jù)，效率低于vector。
4、deque功能全面，但效率普遍較低，實(shí)際應(yīng)用時很少使用，通常作為stack和queue的底層默認(rèn)容器（stack和queue不需要遍歷，只需要在固定的一端或者兩端進(jìn)行操作，且deque擴(kuò)容時不需要內(nèi)存拷貝）。
時間復(fù)雜度
1、訪問首部和尾部是O(1)，下標(biāo)訪問其他元素時接近O(1)。
2、push_back、push_front插入是O(1)，pop_front、pop_back刪除是O(1)。
3、insert插入、erase刪除時間復(fù)雜度O(n)。
支持首尾添加元素/訪問元素/移除元素，支持下標(biāo)訪問和迭代器隨機(jī)訪問，幾乎支持vector和list的所有功能。
#include <deque>
std::deque<int> _d;
_d.push_back(20);//尾部添加元素
_d.push_back(30);
_d.push_back(40);
_d.push_front(10);//頭部添加元素{10,20,30,40}
printf("_d.front=%d\n",_d.front());//訪問隊(duì)首元素，_d.front=10
printf("_d.back=%d\n",_d.back());//訪問隊(duì)尾元素，_d.back=40
_d.pop_back();//移除尾部元素，{10,20,30}
_d.pop_front();//移除頭部元素，{20,30}
_d.erase(_d.begin());//刪除指定位置的元素，{30}
_d.insert(_d.begin() + 1, 80); //在指定的位置插入元素，{30,80}
//使用迭代器遍歷
auto iter = _d.begin();
while(iter != _d.end())
{
printf("value=%d\n",*iter);
iter++;
}
printf("_d[0]=%d,_d.at(1)=%d\n",_d[0],_d.at(1));//下標(biāo)訪問，越界crash，at拋出異常
打印
_d.front=10
_d.back=40
value=30
value=80
_d[0]=30,_d.at(1)=80
容器適配器
queue
1、隊(duì)列，先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，只支持在隊(duì)尾添加元素，在隊(duì)首刪除元素。
2、queue可以指定底層容器（例如std::queue<int, std::list> q1），可以是基于數(shù)組的隊(duì)列，也可以是基于鏈表的隊(duì)列，即順序隊(duì)列和鏈表隊(duì)列。
3、queue不提供迭代器訪問，不能使用下標(biāo)訪問。
時間復(fù)雜度
1、插入push和刪除pop是O(1)。
2、front和back訪問是O(1)。
#include <queue>
std::queue<int> _q;
_q.push(10);//尾部添加元素
_q.push(20);
_q.push(30);
_q.push(40);//{10,20,30,40}
printf("_q.front=%d\n",_q.front());//訪問隊(duì)首元素，_q.front=10
printf("_q.back=%d\n",_q.back());//訪問隊(duì)尾元素，_q.back=40
_q.pop();//移除隊(duì)首元素，{20,30,40}
//不能使用下標(biāo)和迭代器訪問
打印
_q.front=10
_q.back=40
stack
1、數(shù)據(jù)棧，先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，單端口進(jìn)出，數(shù)據(jù)入棧只能加入棧頂，數(shù)據(jù)出棧也只能取棧頂?shù)脑亍?br> 2、stack和queue數(shù)據(jù)結(jié)構(gòu)類似，可以指定底層容器，默認(rèn)是deque，分?jǐn)?shù)組棧和鏈表?xiàng)！?br> 3、stack不提供迭代器訪問，不能使用下標(biāo)訪問。
時間復(fù)雜度
1、入棧push和出棧pop是O(1)。
2、top訪問是O(1)。
#include <stack>
std::stack<int> _s;
_s.push(10);//頂部添加元素
_s.push(20);
_s.push(30);
_s.push(40);//{10,20,30,40}
printf("_s.top=%d\n",_s.top());//訪問頂部元素，_s.top=40
_s.pop();//移除頂部元素，{10,20,30}
priority_queue
1、優(yōu)先級隊(duì)列 priority_queue，常用來對數(shù)據(jù)進(jìn)行優(yōu)先級處理，比如優(yōu)先級高的值在前面，常用堆（Heap）來實(shí)現(xiàn)，底層是以vector數(shù)組存儲的完全二叉樹。
2、優(yōu)先級隊(duì)列是一個擁有權(quán)值的queue，其內(nèi)部元素按照元素的權(quán)值排列。權(quán)值較高者排在最前優(yōu)先出隊(duì)。
3、priority_queue不提供迭代器訪問，不能使用下標(biāo)訪問。
堆是一種特殊的樹，只要滿足以下兩個條件，就可以稱這棵樹為堆：
1、堆是一顆完全二叉樹（完全二叉樹要求，除了最后一層，其他節(jié)點(diǎn)個數(shù)都是滿的，最后一層的節(jié)點(diǎn)都靠左排列）。
2、堆中的每一個節(jié)點(diǎn)都必須大于等于(或者小于等于)其子樹中每個節(jié)點(diǎn)的值。
時間復(fù)雜度
1、使用vector數(shù)組構(gòu)造priority_queue是O(n)。
2、插入元素push和移除堆頂pop是O(log(n))。
3、訪問堆頂top是O(1)。
以下面程序舉例，數(shù)據(jù)結(jié)構(gòu)如下
#include <queue>
std::vector<int> v{ 1,2,3,4,5,6,7,8,9,10 };
std::priority_queue<int> p1(v.begin(), v.end());//使用vector數(shù)組構(gòu)造大頂堆
printf("p1.top=%d\n",p1.top());//訪問頂部元素，.top=10
// std::priority_queue <int,std::vector<int>,std::greater<int> > _p2;//小頂堆
std::priority_queue<int> _p;//默認(rèn)大頂堆
_p.push(56);//添加一個元素，自動排序
_p.push(15);
_p.push(70);
_p.push(30);
_p.push(10);
_p.push(25);//{70,30,56,15,10,25}
printf("_p.top=%d\n",_p.top());//訪問頂部元素，_p.top=70
_p.pop();//移除頂部元素，重新排序，{56,30,25,15,10}
打印
p1.top=10
_p.top=70
關(guān)聯(lián)容器：紅黑樹
set
1、set是排序的、不重復(fù)的數(shù)據(jù)集合。
2、set元素類型是pair，存儲鍵值對，且key和value必須相等。
3、set中的元素不能直接改變，可以先刪除再添加。
4、set底層是以紅黑樹數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，節(jié)點(diǎn)存儲值key。
5、set在內(nèi)存中表現(xiàn)為一個排序的數(shù)組。
6、不支持下標(biāo)訪問。
時間復(fù)雜度
1、插入、刪除、查找，都是嚴(yán)格在O(logn)時間內(nèi)完成。
#include <set>
std::set<int> s1;//定義一個空set
std::set<int>::iterator it;//s1的迭代器類型
std::pair<std::set<int>::iterator,bool> ret;//插入數(shù)據(jù)的返回值類型,first是指向插入數(shù)據(jù)的迭代器，second標(biāo)識是否插入成功
// 單個數(shù)據(jù)插入
for (int i=1; i<=5; ++i)
s1.insert(i*10); // {10,20,30,40,50}
ret = s1.insert(20); // 重復(fù)插入時失敗，返回的迭代器指向容器中已存在的值，bool為false
if (ret.second==false)
it=ret.first; // "it" now points to element 20
s1.erase(50);// 通過值刪除元素，{10,20,30,40}
s1.insert (it,25);//通過迭代器插入，{10,20,25,30,40}
//區(qū)間插入
int myints[]= {5,10,15};
s1.insert (myints,myints+3);
//迭代器遍歷訪問
for (it=s1.begin(); it!=s1.end(); ++it)
printf("*it=%d ",*it);
printf("\n");
auto iter = s1.find(20);//find查詢元素是否在set集合中
if(iter != s1.end())
{
printf("found 20\n");
}
打印
*it=5 *it=10 *it=15 *it=20 *it=25 *it=30 *it=40
found 20
multiset
multiset類似與set，區(qū)別在于multiset支持插入重復(fù)的元素，insert函數(shù)沒有返回值，有重復(fù)元素時count函數(shù)返回值大于1。
map
1、map中存儲的是鍵值對<key,value>，根據(jù)key有序排列，且key唯一。
2、map底層是以紅黑樹數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。
3、使用迭代器可以對value進(jìn)行修改，但不能修改key，若要修改key，可以先刪除再添加。
4、可以通過[key]或at(key)下標(biāo)訪問，若map中沒有該key，則[ ]會向map中添加鍵值對，at()拋出異?；騝rash。
5、map在內(nèi)存中表現(xiàn)為根據(jù)key排序的一組鍵值對。
時間復(fù)雜度
1、插入、刪除、查找，都是嚴(yán)格在O(logn)時間內(nèi)完成。
#include <map>
std::map<int,std::string> map1;//定義一個空map
std::map<int,std::string>::iterator it;//map1的迭代器類型
//插入數(shù)據(jù)的返回值類型,first是指向插入數(shù)據(jù)的迭代器，second標(biāo)識是否插入成功
std::pair<std::map<int,std::string>::iterator,bool> ret;
//1.通過pair<int, string>(1,"lilei") 構(gòu)造pair元素
map1.insert(std::pair<int, std::string>(1,"lilei"));
//2.通過make_pair構(gòu)造pair元素
map1.insert(std::make_pair(2,"hmm"));
//3.通過value_type構(gòu)造pair元素
map1.insert(std::map<int, std::string>::value_type(3,"zsan"));
//4.[ ]下標(biāo)插入
map1[4] = "zsi";
//5.emplace插入
map1.emplace(5,"chw");
ret = map1.emplace(2,"hmei");
if(ret.second == false)//插入失敗，返回false
printf("ret.first=%s\n",ret.first->second.c_str());
bool ret2 = map1.erase(1);//通過key刪除元素，成功返回true，失敗返回false
printf("erase ret2=%d\n",ret2);
//find查找key
auto iter_find = map1.find(3);
if(iter_find != map1.end())
{
printf("find key=%d,value=%s\n",iter_find->first,iter_find->second.c_str());
}
//迭代器安全刪除
std::map<int,std::string>::iterator ite_es = map1.begin();
while(ite_es != map1.end())
{
if(ite_es->first == 3)
{
ite_es = map1.erase(ite_es);
}
else
++ite_es;
}
//迭代器遍歷
auto iter_bl = map1.begin();
while(iter_bl != map1.end())
{
printf("key=%d,value=%s\n",iter_bl->first,iter_bl->second.c_str());
++iter_bl;
}
打印
ret.first=hmm
erase ret2=1
find key=3,value=zsan
key=2,value=hmm
key=4,value=zsi
key=5,value=chw
multimap
multimap類似與map，區(qū)別在于multimap支持插入重復(fù)的元素，insert和emplace函數(shù)沒有返回值，有重復(fù)元素時count函數(shù)返回值大于1。multimap不能使用[ ]下標(biāo)插入。
關(guān)聯(lián)容器：哈希表
unordered_set和unordered_multiset
1、這兩個容器的操作集類似于set和multiset，區(qū)別在于unordered_set和unordered_multiset的底層數(shù)據(jù)結(jié)構(gòu)是哈希表。
2、哈希表是通過把key進(jìn)行哈希運(yùn)算，分配到哈希桶，哈希桶內(nèi)使用鏈表法解決哈希沖突。通過key就可以快速找到哈希桶的位置，因此查找效率高。
時間復(fù)雜度
1、在沒有哈希沖突的情況下，查找是O(1)。
unordered_map和unordered_multimap
1、這兩個容器的操作集類似于map和multimap，區(qū)別在于unordered_map和unordered_multimap的底層數(shù)據(jù)結(jié)構(gòu)是哈希表。
2、哈希表是通過把key進(jìn)行哈希運(yùn)算，分配到哈希桶，哈希桶內(nèi)使用鏈表法解決哈希沖突。通過key就可以快速找到哈希桶的位置，因此查找效率高。
時間復(fù)雜度
1、在沒有哈希沖突的情況下，查找是O(1)。
unordered_map用法參考這里：https://blog.csdn.net/weixin_40355471/article/details/131803322?spm=1001.2014.3001.5502。
附1：紅黑樹數(shù)據(jù)結(jié)構(gòu)
紅黑樹并不是嚴(yán)格的平衡二叉樹，它要求從根到葉子的最長路徑不多于最短路徑的兩倍長，為了滿足這個特性，紅黑樹設(shè)置了五大規(guī)則：
1、節(jié)點(diǎn)是紅色或者黑色
2、根節(jié)點(diǎn)是黑色
3、每個葉子的節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)
4、每個紅色節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色的
5、從任意節(jié)點(diǎn)到其葉子節(jié)點(diǎn)的每條路徑都包含相同個數(shù)的黑色節(jié)點(diǎn)
紅黑樹的高度近似logn，是近似平衡的二叉樹，插入、刪除、查找的時間復(fù)雜度都是O(logn)，性能非常穩(wěn)定，在實(shí)際工作中，凡是動態(tài)插入、刪除、查找數(shù)據(jù)的場景都可以用它。
附2：哈希表數(shù)據(jù)結(jié)構(gòu)
哈希表也叫散列表（Hash table），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
下圖是一個典型應(yīng)用，key經(jīng)過哈希函數(shù)計(jì)算得到哈希值，哈希值對一個常數(shù)n取模得到下標(biāo)，通過下標(biāo)可以直接訪問哈希桶，哈希桶內(nèi)存放<key,value>，如果有哈希沖突，在哈希桶內(nèi)使用鏈表存儲。
附3：reserve和resize
這兩個函數(shù)常用于STL容器容量操作。
1、reserve，只分配空間，不創(chuàng)建對象，不可訪問，用于大量成員創(chuàng)建，一次性分配空間，push_back時就不用再分配，提高執(zhí)行效率。
2、resize，分配空間的同時還創(chuàng)建對象，并給對象賦初始值，可訪問。文章來源：http://www.zghlxwxcb.cn/news/detail-683224.html
std::vector<int> v1;
v1.resize(5);//分配空間并初始化對象為0，此時元素個數(shù)是5
v1.push_back(10);
for(int index=0;index<v1.size();index++)
printf("v1[%d]=%d ",index,v1[index]);
printf("\n");
std::vector<int> v2;
v2.reserve(5);//只分配空間，不創(chuàng)建對象，此時元素個數(shù)是0
v2.push_back(20);
for(int index=0;index<v2.size();index++)
printf("v2[%d]=%d ",index,v2[index]);
printf("\n");
打印文章來源地址http://www.zghlxwxcb.cn/news/detail-683224.html
v1[0]=0 v1[1]=0 v1[2]=0 v1[3]=0 v1[4]=0 v1[5]=10
v2[0]=20
到了這里，關(guān)于C++標(biāo)準(zhǔn)庫STL容器詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
