STL的各個容器？

序列式容器

vecor，動态數組模型，它維護的是一個連續線性空間。

vector的擴容：并不是在原空間之後接着開辟新空間（因為無法保證之後有可供配置的空間），而是每次再配置設定原大小兩倍的記憶體空間，這是一個配置新空間（malloc），拷貝移動資料（memcpy），釋放舊空間（free）的大工程，時間成本很高。是以，對vector的任何操作，一旦引起控件重新配置，指向原vector的所有疊代器就都失效了。

vector維護的是一個連續線性空間，是以vector疊代器具備普通指針的功能，支援随機存取。

list

相對于vector的連續線性空間，list，與向量(vector)相比, 它允許快速的插入和删除，且每次插入或删除一個元素，就配置或釋放一個元素空間。

list不再能夠像vector那樣以普通指針作為疊代器，因為其節點不保證在儲存空間中連續存在。list疊代器必須有能力指向list的節點，并有能力進行正确的遞增、遞減、取值、成員存取等操作。

list是一個帶有頭結點循環雙向連結清單。是以它隻需要一個指針，便可以完整實作整個連結清單。疊代器必須具備前移、後移的能力，是以list提供的是雙向疊代器

deque

可以在頭尾兩端分别做元素的插入和删除操作，它是動态地以分段連續空間組合而成。

deque是由一段一段的連續空間構成。一旦有必要在deque的前端或尾端增加新空間，便配置一段定量的連續空間，串接在整個deque的頭端或尾端。deque的最大任務，便是在這些分段的定量連續空間上，維護其整體連續的假象，并提供随機存取的接口。避開了“重新配置、複制、釋放”的輪回，代價則是複雜的疊代器架構。

關聯式容器

每項資料（元素）包含一個鍵值（key）和一個實值（value），标準的STL關聯式容器分為set（集合）和map（映射類）兩大類，以及這兩大類的衍生體multiset（多鍵集合）和multimap（多鍵映射表）。這些容器的底層機制均以RB-tree完成（紅黑樹）。

set和mutilset

set：其鍵值對的鍵和值相同，那麼set更像普通的二叉樹即結點是鍵值和實值。

set的鍵值不允許相同，是以set的value值也沒有相同的。而這也是mutilset和set唯一的不同，mutilset可以有相同的鍵值。

set是基于紅黑樹的是以其中的元素會自動排序。

思考：

（1）為何map和set的插入删除效率比用其他序列容器高？

因為對于關聯容器來說，不需要做記憶體拷貝和記憶體移動。set容器内所有元素都是以節點的方式來存儲，其節點結構和連結清單差不多，指向父節點和子節點。（用節點表示二叉樹結構）

是以插入的時候隻需要稍做變換，把節點的指針指向新的節點就可以了。删除的時候類似，稍做變換後把指向删除節點的指針指向其他節點也OK了。這裡的一切操作就是指針換來換去，和記憶體移動沒有關系。

（2）對set進行增删操作後，疊代器iterator如何變化？

set的疊代器本質上是const_iterator，這是因為RB-tree的結構依賴于資料的組織，如果允許通過iterator改變set元素值，會嚴重破壞RB-tree結構。

iterator這裡就相當于指向節點的指針，記憶體沒有變，指針就沒有失效，隻是指向的内容變化了。進行增删操作後，隻影響本身的疊代器，對其它疊代器無影響。

map和mutilmap

map是映射之意，即用鍵值(key)映射實值資料(value)。

對比set，map的關聯特效更加明顯，但類似set，map也不允許有相同的鍵值，要想有相同鍵值可用mutilmap。

容器擴充卡

基于deque的順序容器擴充卡stack、queue、priority_queue。

stack

是一種後進先出（First In Last Out，FILO）的資料結構，它隻有一個出口。stack允許新增元素、移除元素、取得最頂端元素，不允許随機通路。底層結構為deque，對deque封閉頭端開口。

STL的各個容器？