STL 就是所謂的標(biāo)準(zhǔn)模板庫（Standard Template Library）矾利，這可能是C++程序員的一大利器尤揣。
總的來說业筏，STL包括幾個部分：容器捻悯，算法（泛型算法）箩朴，迭代器三個主要部分（當(dāng)然還包含仿函數(shù)，適配器等其他部分）秋度，下圖說明了三個主要部分之間的關(guān)系（網(wǎng)圖，侵刪）钱床。
要是詳細(xì)的總結(jié)荚斯，這肯定是一本類似于《C++ Primer》的大書。本篇文章主要是對于STL中的常用容器的底層數(shù)據(jù)結(jié)構(gòu)進(jìn)行總結(jié)整理。
I事期、vector
1.1 vector底層數(shù)據(jù)結(jié)構(gòu)
vector是我們用到最多的數(shù)據(jù)結(jié)構(gòu)滥壕，其底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，由于數(shù)組的特點兽泣，vector也具有以下特性：
1绎橘、O(1)時間的快速訪問；
2唠倦、順序存儲称鳞，所以插入到非尾結(jié)點位置所需時間復(fù)雜度為O(n)，刪除也一樣稠鼻；
3冈止、擴(kuò)容規(guī)則：
當(dāng)我們新建一個vector的時候，會首先分配給他一片連續(xù)的內(nèi)存空間候齿，如std::vector<int> vec熙暴，當(dāng)通過push_back向其中增加元素時，如果初始分配空間已滿慌盯，就會引起vector擴(kuò)容周霉，其擴(kuò)容規(guī)則在gcc下以2倍方式完成：
首先重新申請一個2倍大的內(nèi)存空間；
然后將原空間的內(nèi)容拷貝過來亚皂；
最后將原空間內(nèi)容進(jìn)行釋放俱箱，將內(nèi)存交還給操作系統(tǒng)；
測試代碼如下：
#include<iostream>
#include<vector>
using namespace std;
void mycapacity(const vector<int>& vec)
{
cout << "分配總空間大小為：" << vec.capacity() << endl;
}
void mysize(const vector<int>& vec)
{
cout << "已用空間大小為：" << vec.size() << endl;
}
void myprint(const vector<int>& vec)
{
for (int i = 0; i < vec.size(); ++i)
cout << vec[i] << ",";
cout << endl;
}
int main()
{
vector<int> vec;
cout << "起始狀態(tài)：" << endl;
mycapacity(vec);
mysize(vec);
cout << "========================" << endl;
for (int i = 0; i < 10; ++i) {
vec.push_back(i);
cout << "壓入第" << i+1 << "個元素之后：" << endl;
myprint(vec);
mycapacity(vec);
mysize(vec);
cout << "========================" << endl;
}
return 0;
}
從輸出結(jié)果中的三個紅色箭頭可以看出vector的擴(kuò)容規(guī)則孕讳。
4匠楚、注意事項：
根據(jù)vector的插入和刪除特性，以及擴(kuò)容規(guī)則厂财，我們在使用vector的時候要注意芋簿，在插入位置和刪除位置之后的所有迭代器和指針引用都會失效，同理璃饱，擴(kuò)容之后的所有迭代器指針和引用也都會失效与斤。
II、map & multimap & unordered_map & unordered_multimap
2.1 map與multimap底層數(shù)據(jù)結(jié)構(gòu)
map與multimap是STL中的關(guān)聯(lián)容器荚恶、提供一對一key-value的數(shù)據(jù)處理能力撩穿； map與multimap的區(qū)別在于，multimap允許關(guān)鍵字重復(fù)谒撼，而map不允許重復(fù)食寡。
這兩個關(guān)聯(lián)容器的底層數(shù)據(jù)結(jié)構(gòu)均為紅黑樹，關(guān)于紅黑樹的理解可以參考教你透徹了解紅黑樹一文廓潜。
根據(jù)紅黑樹的原理抵皱，map與multimap可以實現(xiàn)O(lgn)的查找善榛，插入和刪除。
2.2 unordered_map 與unordered_multimap底層數(shù)據(jù)結(jié)構(gòu)
unordered_map與unordered_multimap 對比2.1中的兩種map在于其2.1中的兩個容器實現(xiàn)了以key為序排列呻畸，也就是說map與multimap為有序的移盆。
而unordered_map與unordered_multimap中key為無序排列，其底層實現(xiàn)為hash table伤为，因此其查找時間復(fù)雜度理論上達(dá)到了O(n)咒循，之所以說理論上是因為在理想無碰撞的情況下，而真實情況未必如此绞愚。
III叙甸、set & multiset & unordered_set & unordered_multiset
以上四種容器也都是關(guān)聯(lián)容器，set系與map系的區(qū)別在于map中存儲的是<key-value>爽醋，而set可以理解為關(guān)鍵字即值蚁署，即只保存關(guān)鍵字的容器。
3.1 set & multiset底層數(shù)據(jù)結(jié)構(gòu)
set與multiset有序存儲元素蚂四，這兩種容器的底層實現(xiàn)與map一樣都是紅黑樹光戈，所以能實現(xiàn)O(lgn)的查找，插入遂赠，刪除操作久妆。
set與multiset的區(qū)別在于是否允許重復(fù)；
3.2 unordered_set & unordered_multiset
與unordered_map & unordered_multimap相同跷睦，其底層實現(xiàn)為hash table筷弦；
IV、 priority_queue
4.1 priority_queue
優(yōu)先級隊列相當(dāng)于一個有權(quán)值的單向隊列queue抑诸，在這個隊列中烂琴，所有元素是按照優(yōu)先級排列的。
priority_queue根據(jù)堆的處理規(guī)則來調(diào)整元素之間的位置蜕乡，關(guān)于堆的原理奸绷，可以參考堆；
根據(jù)堆的特性层玲，優(yōu)先級隊列實現(xiàn)了取出最大最小元素時間復(fù)雜度為O(1),對于插入和刪除号醉，其最壞情況為O(lgn)。
V辛块、 其他數(shù)據(jù)結(jié)構(gòu)
list的底層數(shù)據(jù)結(jié)構(gòu)為雙向鏈表畔派，特點是支持快速的增刪。
queue為單向隊列润绵，為先入先出原則线椰。
deque為雙向隊列，其對比queue可以實現(xiàn)在頭尾兩端高效的插入和刪除操作尘盼。
歡迎轉(zhuǎn)載憨愉，轉(zhuǎn)載請注明出處wenmingxing 你好呀 C++
