STL 就是所謂的標(biāo)準(zhǔn)模板庫(kù)（Standard Template Library），這可能是C++程序員的一大利器。
總的來說，STL包括幾個(gè)部分：容器，算法（泛型算法），迭代器三個(gè)主要部分（當(dāng)然還包含仿函數(shù)，適配器等其他部分），下圖說明了三個(gè)主要部分之間的關(guān)系（網(wǎng)圖，侵刪）。
要是詳細(xì)的總結(jié)，這肯定是一本類似于《C++ Primer》的大書。本篇文章主要是對(duì)于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ù)組的特點(diǎn)，vector也具有以下特性：
1、O(1)時(shí)間的快速訪問；
2、順序存儲(chǔ)，所以插入到非尾結(jié)點(diǎn)位置所需時(shí)間復(fù)雜度為O(n)，刪除也一樣；
3、擴(kuò)容規(guī)則：
當(dāng)我們新建一個(gè)vector的時(shí)候，會(huì)首先分配給他一片連續(xù)的內(nèi)存空間，如std::vector<int> vec，當(dāng)通過push_back向其中增加元素時(shí)，如果初始分配空間已滿，就會(huì)引起vector擴(kuò)容，其擴(kuò)容規(guī)則在gcc下以2倍方式完成：
首先重新申請(qǐng)一個(gè)2倍大的內(nèi)存空間；
然后將原空間的內(nèi)容拷貝過來；
最后將原空間內(nèi)容進(jìn)行釋放，將內(nèi)存交還給操作系統(tǒng)；
測(cè)試代碼如下：
#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 << "個(gè)元素之后：" << endl;
myprint(vec);
mycapacity(vec);
mysize(vec);
cout << "========================" << endl;
}
return 0;
}
從輸出結(jié)果中的三個(gè)紅色箭頭可以看出vector的擴(kuò)容規(guī)則。
4、注意事項(xiàng)：
根據(jù)vector的插入和刪除特性，以及擴(kuò)容規(guī)則，我們?cè)谑褂胿ector的時(shí)候要注意，在插入位置和刪除位置之后的所有迭代器和指針引用都會(huì)失效，同理，擴(kuò)容之后的所有迭代器指針和引用也都會(huì)失效。
II、map & multimap & unordered_map & unordered_multimap
2.1 map與multimap底層數(shù)據(jù)結(jié)構(gòu)
map與multimap是STL中的關(guān)聯(lián)容器、提供一對(duì)一key-value的數(shù)據(jù)處理能力； map與multimap的區(qū)別在于，multimap允許關(guān)鍵字重復(fù)，而map不允許重復(fù)。
這兩個(gè)關(guān)聯(lián)容器的底層數(shù)據(jù)結(jié)構(gòu)均為紅黑樹，關(guān)于紅黑樹的理解可以參考教你透徹了解紅黑樹一文。
根據(jù)紅黑樹的原理，map與multimap可以實(shí)現(xiàn)O(lgn)的查找，插入和刪除。
2.2 unordered_map 與unordered_multimap底層數(shù)據(jù)結(jié)構(gòu)
unordered_map與unordered_multimap 對(duì)比2.1中的兩種map在于其2.1中的兩個(gè)容器實(shí)現(xiàn)了以key為序排列，也就是說map與multimap為有序的。
而unordered_map與unordered_multimap中key為無序排列，其底層實(shí)現(xiàn)為hash table，因此其查找時(shí)間復(fù)雜度理論上達(dá)到了O(n)，之所以說理論上是因?yàn)樵诶硐霟o碰撞的情況下，而真實(shí)情況未必如此。
III、set & multiset & unordered_set & unordered_multiset
以上四種容器也都是關(guān)聯(lián)容器，set系與map系的區(qū)別在于map中存儲(chǔ)的是<key-value>，而set可以理解為關(guān)鍵字即值，即只保存關(guān)鍵字的容器。
3.1 set & multiset底層數(shù)據(jù)結(jié)構(gòu)
set與multiset有序存儲(chǔ)元素，這兩種容器的底層實(shí)現(xiàn)與map一樣都是紅黑樹，所以能實(shí)現(xiàn)O(lgn)的查找，插入，刪除操作。
set與multiset的區(qū)別在于是否允許重復(fù)；
3.2 unordered_set & unordered_multiset
與unordered_map & unordered_multimap相同，其底層實(shí)現(xiàn)為hash table；
IV、 priority_queue
4.1 priority_queue
優(yōu)先級(jí)隊(duì)列相當(dāng)于一個(gè)有權(quán)值的單向隊(duì)列queue，在這個(gè)隊(duì)列中，所有元素是按照優(yōu)先級(jí)排列的。
priority_queue根據(jù)堆的處理規(guī)則來調(diào)整元素之間的位置，關(guān)于堆的原理，可以參考堆；
根據(jù)堆的特性，優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)了取出最大最小元素時(shí)間復(fù)雜度為O(1),對(duì)于插入和刪除，其最壞情況為O(lgn)。
V、 其他數(shù)據(jù)結(jié)構(gòu)
list的底層數(shù)據(jù)結(jié)構(gòu)為雙向鏈表，特點(diǎn)是支持快速的增刪。
queue為單向隊(duì)列，為先入先出原則。
deque為雙向隊(duì)列，其對(duì)比queue可以實(shí)現(xiàn)在頭尾兩端高效的插入和刪除操作。
歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)注明出處wenmingxing 你好呀 C++
