一、STL的概念

1、STL的定義

STL是惠普實驗室開發的一系列標準化組件的統稱。STL的一個基本理念就是將數據和操作分離，數據由容器加以管理，操作則由可定制的算法完成，迭代器在兩者之間充當“黏合劑”。

2、STL的組成

STL主要由六個部分組成：分配器（allocator）、配接器（adapters）、容器（containers）、迭代器（Iterator）、仿函數（functors）、算法（algorithm）。

分配器給容器分配存儲空間，算法通過迭代器獲取容器中的內容，仿函數可以協助算法完成各種操作，配接器用來套接適配仿函數。

二、容器

1、容器的定義及作用

容器是存儲其他對象的對象，它存儲的對象可以是自定義數據類型的對象，也可以是內置數據類型的對象。這些被存儲的對象必須是同一種數據類型，它們歸容器所有，稱為容器的元素。當容器失效時，容器中的元素也會失效。容器本身包含了處理這些數據的方法。另外，容器最重要的優點就是它可以擴展自身的大小。
從實現角度來看，STL容器是一種類模板（class template）。
STL容器是將運用最廣泛的一些數據結構實現出來，數組（array）、鏈表（list）、樹（tree）、棧（stack）、隊列（queue）、集合（set）、映射表（map），根據數據在容器中的排列特性，分為序列式容器和關聯式容器。

序列式容器：容器元素在容器中的位置是由元素進入容器的時間和地點來決定。有：vector容器、deque容器、list容器、stack容器、queue容器。

關聯式容器：是指容器已經有了一定的規則，容器元素在容器中的位置由我的規則來決定。是可以存儲鍵-值對的容器，使用鍵來快速檢索值，里面存儲的是<key, value>結構的鍵值對，在數據檢索時比序列式容器的效率高，有：set/multiset容器、map/multimap容器。

2、string類（非容器）

string類與STL容器有很多相似的操作，C++中的string類相當于是字符數組，但是其更方便于我們的操作，不需要在輸入之前初始化字符數組的容量，節省了空間。

3、vector容器

vector是變長數組（vector內部使用動態內存分配，可以根據需要動態增加或減少其占用的內存空間，這樣可以在運行時接喊個空間，因為vector只會使用實際需要的內存空間），在堆上分配空間，支持隨機訪問（由于vector內部使用數組來存儲元素，因此可以通過索引直接訪問任意位置的元素），不支持在任意位置O(1)插入。為了保證效率，元素的增刪都應該在末尾進行（在中間或者開頭進行插入操作是O(n)的，因為涉及到元素的移動和內存的重新分配）。

vector的用法舉例：

#include<vector>/*vector 生成*/
vector<int> vct(3);//數組中有3個元素，不指定的情況下默認為0
vector<int>vct(3,5);//數組中有3個元素，全是5
vector<int>vct{1，2，3};//數組中的元素為1，2，3/*vector 頭尾*/
vector.front();//第一個元素
vector.back();//最后一個元素/*vector 迭代器*/
vector<int>::iterator iter //一個vector的迭代器
vct.begin()//指向vct中第一個元素位置的迭代器
vct.end()//指向vct中最后一個元素位置的迭代器/*vector 插入*/
vct.push_back(1);//在尾部插入一個1
vct.insert(vct.begin(),1);//在指定位置前面插入一個元素1/*vector 刪除*/
vct.pop_back();//刪除vct中最后一個元素
vct.erase(vct.begin());//刪除指定位置的元素
vct.erase(vct.begin()+1, vct.end()-2);//刪除vct中第二個元素到倒數第三個元素中的所有元素（包括第二個和倒數第三個）/*vector 容量*/
vct.size()/*vector 遍歷*/
for(int i = 0;i<vct.size();i++)//索引遍歷
for(vector<int>::iterator iter = vct.begin(); iter != vct.end();iter++)//迭代器遍歷
for(auto &x :vct)//迭代器的另一種便捷遍歷方法/*vector 排序*/
sort(vct.begin(),vct.end());/*vector 查找*/
vct.find(2);//從前往后，找元素2，若找到，則返回指向該處的迭代器，若沒找到，則返回vct.end()/*vector 某元素的個數*/
vct.count(2);//返回容器中2的個數/*vector 判空*/
vct.empty()//返回布爾值/*vector 清空*/
vct.clear();

4、set容器

頭文件主要包括set和multiset兩個容器，分別是“有序集合”和“有序多重集合”，即前者的元素不能重復，而后者可以包含若跟個相等的元素，兩者都會將其容器內的元素按照從小到大自動排序。set內部使用二叉搜索樹（紅黑樹，RB Tree）數據結構來存儲元素，并根據元素的鍵值進行自動排序。

set的用法如下：

#incude<set>/*set生成*/
set<int> st;/*set 迭代器*/
set<int>::iterator iter
st.begin()
st.end()/*set 插入*/
set.insert(2);//插入一個為值為2的元素/*set 刪除*/
st.erase(st.begin());//刪除迭代器指向元素
st.erase(2);//刪除所有為2的元素/*set 容量*/
st.size();/*set 查找*/
st.find(2);//從前往后找為2的元素，若找到，返回指向該處的迭代器，反之，返回迭代器st.end()
st.lower_bound(x);//二分查找大于等于x的元素中最小的一個，并返回指向該元素的迭代器
st.upper_bound(x);//二分查找大于等于x的元素中最大的一個，并返回指向該元素的迭代器、/*set 某元素的個數*/
st.count(2);//返回容器里2的個數/*set 判空*/
st.empty();//返回布爾值/*set 清空*/
st.clear();

5、queue容器

頭文件queue主要包括循環隊列queue和優先隊列priority_queue兩個容器，其中queue容器相當于隊列，滿足先進先出的原則，即隊尾進、隊首出。

queue的用法舉例：

#include<queue>/*queue 生成*/
queue<int> q;/*queue 頭尾*/
q.front();
q.back();/*queue 插入*/
q.push();//在隊首插入一個元素/*queue 刪除*/
q.pop();//在隊首刪除一個元素/*queue 容量*/
q.size();/*queue 判空*/
q.empty()

6、priority_queue容器

priority_queue容器相當于大根堆（或者小根堆），大根堆每次堆項是最大元素，小根堆每次堆項是最小元素。

priority_queue用法舉例：

#include<queue>/*priority_queue 生成*/
priority_queue<int> pq;//大根堆
priority_queue<int,vector<int>,greater<int>> pq;//小根堆/*priority_queue 插入*/
pq.push(2);//把元素2插入堆/*priority_queue 刪除*/
pq.pop();//刪除堆頂的元素/*priority_queue 堆項*/
pq.top();//返回堆頂元素/*priority_queue 容量*/
pq.size();/*priority_queue 判空*/
pq.empty()

7、stack容器

stack容器相當于棧，滿足先進后出的原則，即插入和刪除都只能在棧頂操作。

stack用法舉例：

#include<stack>/*stack 生成*/
stack<int> sk;/*stack 插入*/
sk.push(1);//把元素1放入棧頂/*stack 刪除*/
sk.pop();//刪除棧頂元素/*stack 棧頂*/
sk.top();//返回棧頂元素/*stack 容量*/
sk.size();/*stack 判空*/
sk.empty()

8、deque容器

雙端隊列deaue容器是一個支持在兩端高效插入或刪除元素的連續性存儲空間，它就像是vector和queue的結合。與vector相比，deque在頭部增刪元素僅需要O(1)的時間，與queue相比，deque像數組一樣支持隨機訪問。

deque的用法舉例：

#include<deque>/*deque 生成*/
deque<int> dq;/*deque 迭代器*/
deque<int>::iterator iter
dq.begin()
dq.end()/*deque 插入*/
dq.push_front(1);//在頭部插入元素1
dq.push_back(1);//在尾部插入元素1/*deque 刪除*/
dq.pop_front();//刪除頭部元素
dq.pop_back();//刪除尾部元素/*deque 容量*/
dq.size();/*deque 判空*/
dq.empty()/*deque 頭尾*/
dq.front();
dq.back();/*deque 清空*/
dq.clear();

9、map容器

map容器是一個鍵值對key-value的映射，其內部實現是一顆以key為關鍵碼的紅黑樹。map的key和value可以是任意類型。unordered_map的底層結構是哈希表。

map的用法舉例：

#include<map>/*map 生成*/
map<key_type, value_type> name;
map<int, int> mp;/*map 迭代器*/
map<int, int>::iterator iter
mp.begin()
mp.end()/*map 鍵值*/
iter->first//key
iter->second//value/*map 插入*/
mp[2] = 5;//2是key，5是value
mp.insert(pair<int, int>(2,5));//insert一個pair/*map 刪除*/
mp.erase(iter);//刪除迭代器所指的鍵值對/*map 容量*/
mp.size()/*map 查找*/
mp.find(2);//從前往后，找元素2，若找到，則返回指向該處的迭代器，反之，返回迭代器mp.end()/*map 某元素的個數*/
mp.count(2);/*map 判空*/
mp.empty()/*map 清空*/
mp.clear();

10、pair容器

pair容器相當于將兩份數據打包為一對，兩份數據的數據類型任意，多與其他容器混合使用，單獨使用的情況比較少。
pair的用法舉例：

#include<utility>/*pair 生成*/
pair<int,int> pr = make_pair(0,1);/*pair 兩個值*/
pr.first
pr.second/*pair 多與其他容器混合使用*/
set<pair<int,int>> st;
vector<pair<int,int>> vct(mp.begin(), mp.end());

11、bitset容器

bitset容器相當于是0/1數組，其方便之處是可以直接按位進行位運算，但是要注意下標從小到大依次存低位到高位，是逆序的。

#include<bitset>/*bitset 生成*/
bitset<4> bt;//生成4位二進制數，初始化為0000
bitset<8> bt(12);//生成8位二進制數，且將十進制數12轉化為二進制數存入其中，12的二進制數為：0000 1100
bitset<8> bt(str);//str可以是只有0/1的字符串或字符數組/*bitset 位相關運算*/
bt1 |= bt2;//按位或
bt1 &= bt2;//按位與
bt1 ^= bt2;//按位異或
bt1 =~ bt2;//按位取反
bt1 <<= x;//左移x位bt.test(x)//判斷第x個位置是0還是1，也就是輸出第x個位置，注意逆序bt.flip();//將二進制每一位取反
bt.flip(x);//將二進制第x位取反
bt.set();//將二進制每一個位置都置為1
bt.set(x);//將二進制第x個位置1
bt.reset();//將二進制每一個位置都置0
bt.reset(x);//將二進制第x個位置置0/*bitset 容量*/
bt.size()//二進制數組的長度，也就是生成時定義的長度/*bitset 某元素的個數*/
bt.count();//查詢二進制數組中1的個數/*bitset 轉化字符串*/
string str = bt.to_string();//將二進制數組轉化為字符串

12、map和set的區別

1. map中的元素是key-value（關鍵字-值）對：關鍵字起到索引的作用，值則表示與索引相關聯的數據；set與之相對的就是關鍵字的簡單集合，set中每個元素只包含一個關鍵字；
2. set的迭代器是const的，不允許修改元素的值；map允許修改value，但不允許修改key。其原因是map和set是根據關鍵字排序來保證其有序性的，如果允許修改key的話，那么首先需要刪除該鍵，然后調節平衡，再插入修改后的鍵值，調節平衡，如此一來，嚴重破壞了map和set的結構，導致iterator失效，不知道應該指向改變前的位置還是改變后的位置，所以STL中將set的迭代器設置為const，不允許修改迭代器的值；而map的迭代器則不允許修改key的值，允許修改value的值。
3. map支持下標操作，set不支持下標操作。map可以用key做下標，map的下標運算符[]將關鍵碼作為下標去執行查找，如果關鍵碼不存在，則插入一個具有該關鍵碼和mapped_type類型默認值的元素到map容器中，因此下標運算符[]在map中應謹慎使用，在const_map中不能用，只希望確定某一個關健值是否存在而不希望插入元素時也不能用，mapped_type類型沒有默認值也不應該使用。如果find能解決需求，盡量使用find。

13、vector和list的區別

1、vector
連續存儲的數組、動態數組、在堆上分配空間
底層實現：數組
兩倍容量增長
vector增加（插入）新元素時，如果未超過當時的容量，還有剩余的空間，則直接添加到最后（插入指定位置），然后調整迭代器；若沒有剩余空間，則會重新配置原有元素個數的兩倍空間，然后將原空間元素通過復制的方式初始化新空間，再向新空間增加元素，最后析構并釋放原空間，之前的迭代器會失效。
性能：
訪問：O(1)
插入：在最后插入（空間夠）：很快
在最后插入（空間不夠）：需要內存申請和釋放，以及對之前數據進行拷貝
在中間插入（空間夠）：內存拷貝
在中間插入（空間不夠）：需要內存申請和釋放，以及對之前數據進行拷貝
刪除：刪除末尾：很快
在中間刪除：內存拷貝
適用場景：經常隨機訪問，且不經常對非尾節點進行插入刪除
2、list
動態鏈表、在堆上分配空間、每插入一個元素都會分配空間，每刪除一個元素都會釋放空間
底層：雙向鏈表
性能：
訪問：隨機訪問性能很差，只能快速訪問頭尾節點
插入：很快，一般是常數開銷
刪除：很快，一般是常數開銷
適用場景：經常插入刪除大量數據
3、區別

1. vector底層實現是數組，list是雙向鏈表；
2. vector支持隨機訪問，list不支持；
3. vector是順序內存，list不是；
4. vector在中間進行插入刪除需要進行內存拷貝，list不需要；
5. vector一次性分配好內存，不夠時才進行兩倍擴容；list每次插入新節點都會進行內存申請；
6. vector隨機訪問性好，插入刪除性能差；list隨機訪問性差，插入刪除性能好。
7. 適用場景不同，vector適用于需要高效進行隨機訪問而不在乎插入和刪除的效率的場景；list適用于需要高效進行插入和刪除而不關心隨機訪問效率的場景。

三、分配器（allocaotr）

STL的空間適配器用于封裝STL容器在內存管理上的底層細節。在C++中，其內存配置和釋放如下：

new運算分為兩個階段：（1）調用::operator new配置內存（2）調用對象構造函數構造對象內容
delete運算分為兩個階段：（1）調用對象析構函數（2）調用::operator delete釋放內存

為了精密分工，STL allocaotr將兩個階段操作區分開來，內存配置由alloc::allocate()負責，內存釋放由alloc::deallocate()負責；對象構造由::construct()負責，對象析構由::destroy()負責。

同時為了提升內存管理的效率，減少申請小內存造成的內存碎片化的問題，SGI STL采用了兩級配置器，當分配的空間大小超過128B時，會使用第一級空間配置器；當配置的空間大小小于128B時，將使用第二級空間配置器。第一級空間配置器直接使用malloc()、realloc()、free()函數進行內存的分配和釋放，而第二級空間適配器則采用了內存池技術，通過空閑鏈表來管理內存。

四、迭代器（iterator）

1、迭代器的概念

iterator模式又稱為custor（游標）模式，用于提供一種方法順序訪問一個聚合對象中各個元素，而又不需要暴露該對象的內部表示。換個更容易理解的說法：iterator模式是運用于聚合對象的一種模式，通過運用該模式，我們可以在不知道對象內部表示的情況下，按照一定的順序（由iterator提供的方法）訪問聚合對象中的各個元素。

由于iterator模式的以上特性：與聚合對象耦合，在一定程度上限制了它的廣泛運用，一般僅用于底層聚合支持類，如STL的list、vector、stack等容器類及ostream_iterator等擴展iterator。

2、迭代器和指針的區別

迭代器不是指針，是類模版，表現得像指針。它只是模擬了指針的一些功能，通過重載了指針的一些操作符->、、++、–等迭代器封裝了指針，是一個“可遍歷的STL（Standard Template Library）容器內全部或部分元素”的對象，本質是封裝了原生指針，是指針概念的一種提升（lift），提供了比指針更高級的行為，相當于一種只能指針，它可以根據不同類型的數據結構來實現不同的++，–等操作。
迭代器返回的是對象引用而不是對象的值，所以cout只能輸出迭代器使用取值后的值，而不能直接輸出其自身。

3、迭代器產生的原因

iterator類的訪問方式就是把不同集合類的訪問邏輯抽象出來，使得不用暴露集合內部的結構而達到循環遍歷集合的效果。