組成：容器宴咧，迭代器，算法

各種容器的元素在內(nèi)存中的儲(chǔ)存方式

1档桃、vector（向量）：相當(dāng)于數(shù)組，但其大小可以不預(yù)先指定堪嫂，并且自動(dòng)擴(kuò)展。它可以像數(shù)組一樣被操作木柬，由于它的特性我們完全可以將vector 看作動(dòng)態(tài)數(shù)組皆串。在創(chuàng)建一個(gè)vector 后，它會(huì)自動(dòng)在內(nèi)存中分配一塊連續(xù)的眉枕。內(nèi)存空間進(jìn)行數(shù)據(jù)存儲(chǔ)恶复，初始的空間大小可以預(yù)先指定也可以由vector 默認(rèn)指定，這個(gè)大小即capacity （）函數(shù)的返回值速挑。當(dāng)存儲(chǔ)的數(shù)據(jù)超過分配的空間時(shí)vector 會(huì)重新分配一塊內(nèi)存塊谤牡，但這樣的分配是很耗時(shí)的，效率非常低姥宝。
2翅萤、deque（隊(duì)列）：它不像vector 把所有的對象保存在一塊連續(xù)的內(nèi)存塊，而是采用多個(gè)連續(xù)的存儲(chǔ)塊腊满，并且在一個(gè)映射結(jié)構(gòu)中保存對這些塊及其順序的跟蹤套么。向deque 兩端添加或刪除元素的開銷很小，它不需要重新分配空間糜烹。
3违诗、list（列表）：是一個(gè)線性鏈表結(jié)構(gòu)，它的數(shù)據(jù)由若干個(gè)節(jié)點(diǎn)構(gòu)成疮蹦，每一個(gè)節(jié)點(diǎn)都包括一個(gè)信息塊（即實(shí)際存儲(chǔ)的數(shù)據(jù)）、一個(gè)前驅(qū)指針和一個(gè)后驅(qū)指針茸炒。它無需分配指定的內(nèi)存大小且可以任意伸縮愕乎，這是因?yàn)樗鎯?chǔ)在非連續(xù)的內(nèi)存空間中，并且由指針將有序的元素鏈接起來壁公。
4感论、set, multiset, map, multimap 是一種非線性的樹結(jié)構(gòu)，具體的說采用的是一種比較高效的特殊的平衡檢索二叉樹—— 紅黑樹結(jié)構(gòu)紊册。

hashset與set相比較比肄，它里面的元素不一定是經(jīng)過排序的快耿，而是按照所用的hash函數(shù)分派的，它能提供更快的搜索速度（當(dāng)然跟hash函數(shù)有關(guān)）
Stl容器的參數(shù)allocate是用來做什么的芳绩？這是一個(gè)函數(shù)對象掀亥，用來指定小于運(yùn)算過程。Map的Key有什么要求妥色？開始我答不能重復(fù)搪花，他繼續(xù)問，答必須重載<運(yùn)算符嘹害，OK
1.C++ STL 之所以得到廣泛的贊譽(yù)撮竿，也被很多人使用，不只是提供了像vector, string, list等方便的容器笔呀，更重要的是STL封裝了許多復(fù)雜的數(shù)據(jù)結(jié)構(gòu)算法和大量常用數(shù)據(jù)結(jié)構(gòu)操作幢踏。vector封裝數(shù)組，list封裝了鏈表许师，map和set封裝了二叉樹等
2.標(biāo)準(zhǔn)關(guān)聯(lián)容器set, multiset, map, multimap內(nèi)部采用的就是一種非常高效的平衡檢索二叉樹：紅黑樹房蝉，也成為RB樹(Red-BlackTree)。RB樹的統(tǒng)計(jì)性能要好于一般的 平衡二叉樹
3.STL map和set的使用雖不復(fù)雜枯跑，但也有一些不易理解的地方惨驶，如：
map: type pair <constKey, T> ，很多不同的 const Key 對應(yīng)的 T 對象的一個(gè)集合敛助，所有的記錄集中只要 const Key 不一樣就可以粗卜， T 無關(guān)！ set: type const Key. 只存單一的對 const Key 纳击，沒有 map 的 T 對像续扔！可以看成 map 的一個(gè)特例

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

答：因?yàn)閷τ陉P(guān)聯(lián)容器來說纱昧，不需要做內(nèi)存拷貝和內(nèi)存移動(dòng)。說對了堡赔，確實(shí)如此识脆。map和set容器內(nèi)所有元素都是以節(jié)點(diǎn)的方式來存儲(chǔ)，其節(jié)點(diǎn)結(jié)構(gòu)和鏈表差不多善已，指向父節(jié)點(diǎn)和子節(jié)點(diǎn)

（2）為何每次insert之后灼捂，以前保存的iterator不會(huì)失效？

答：iterator這里就相當(dāng)于指向節(jié)點(diǎn)的指針换团，內(nèi)存沒有變悉稠，指向內(nèi)存的指針怎么會(huì)失效呢(當(dāng)然被刪除的那個(gè)元素本身已經(jīng)失效了)。相對于vector來說艘包，每一次刪除和插入的猛，指針都有可能失效耀盗，調(diào)用push_back在尾部插入也是如此。因?yàn)闉榱吮ＷC內(nèi)部數(shù)據(jù)的連續(xù)存放卦尊，iterator指向的那塊內(nèi)存在刪除和插入過程中可能已經(jīng)被其他內(nèi)存覆蓋或者內(nèi)存已經(jīng)被釋放了叛拷。即使時(shí)push_back的時(shí)候，容器內(nèi)部空間可能不夠猫牡，需要一塊新的更大的內(nèi)存胡诗，只有把以前的內(nèi)存釋放，申請新的更大的內(nèi)存淌友，復(fù)制已有的數(shù)據(jù)元素到新的內(nèi)存煌恢，最后把需要插入的元素放到最后，那么以前的內(nèi)存指針自然就不可用了震庭。特別時(shí)在和find等算法在一起使用的時(shí)候瑰抵，牢記這個(gè)原則：不要使用過期的iterator。

（3）為何map和set不能像vector一樣有個(gè)reserve函數(shù)來預(yù)分配數(shù)據(jù)器联？

答：我以前也這么問二汛，究其原理來說時(shí)，引起它的原因在于在map和set內(nèi)部存儲(chǔ)的已經(jīng)不是元素本身了拨拓，而是包含元素的節(jié)點(diǎn)肴颊。也就是說map內(nèi)部使用的Alloc并不是map<Key, Data, Compare, Alloc>聲明的時(shí)候從參數(shù)中傳入的Alloc。例如：

4.set, multiset

set和multiset會(huì)根據(jù)特定的排序準(zhǔn)則自動(dòng)將元素排序渣磷，set中元素不允許重復(fù)婿着，multiset可以重復(fù)。
因?yàn)槭桥判虻拇捉纾詓et中的元素不能被修改竟宋，只能刪除后再添加。
向set中添加的元素類型必須重載<操作符用來排序形纺。排序滿足以下準(zhǔn)則：
1丘侠、非對稱，若A<B為真逐样，則B<A為假蜗字。
2、可傳遞脂新，若A<B,B<C秽澳，則A<C。
3戏羽、A<A永遠(yuǎn)為假。
set中判斷元素是否相等：
if(!(A<B || B<A))楼吃，當(dāng)A<B和B<A都為假時(shí)始花，它們相等妄讯。

5.map，multimap

map和multimap將key和value組成的pair作為元素酷宵，根據(jù)key的排序準(zhǔn)則自動(dòng)將元素排序亥贸，map中元素的key不允許重復(fù)，multimap可以重復(fù)浇垦。
map<key,value>
因?yàn)槭桥判虻目恢茫詍ap中元素的key不能被修改，只能刪除后再添加男韧。key對應(yīng)的value可以修改朴摊。
向map中添加的元素的key類型必須重載<操作符用來排序。排序與set規(guī)則一致此虑。

6. List的功能方法

實(shí)際上有兩種List: 一種是基本的ArrayList,其優(yōu)點(diǎn)在于隨機(jī)訪問元素甚纲，另一種是更強(qiáng)大的LinkedList,它并不是為快速隨機(jī)訪問設(shè)計(jì)的，而是具有一套更通用的方法朦前。
List : 次序是List最重要的特點(diǎn)：它保證維護(hù)元素特定的順序介杆。List為Collection添加了許多方法，使得能夠向List中間插入與移除元素(這只推薦LinkedList使用韭寸。)一個(gè)List可以生成ListIterator,使用它可以從兩個(gè)方向遍歷List,也可以從List中間插入和移除元素春哨。
ArrayList : 由數(shù)組實(shí)現(xiàn)的List。允許對元素進(jìn)行快速隨機(jī)訪問恩伺，但是向List中間插入與移除元素的速度很慢赴背。ListIterator只應(yīng)該用來由后向前遍歷ArrayList,而不是用來插入和移除元素。因?yàn)槟潜萀inkedList開銷要大很多莫其。
LinkedList : 對順序訪問進(jìn)行了優(yōu)化癞尚，向List中間插入與刪除的開銷并不大。隨機(jī)訪問則相對較慢乱陡。(使用ArrayList代替浇揩。)還具有下列方法：addFirst(), addLast(), getFirst(),getLast(), removeFirst() 和 removeLast(), 這些方法 (沒有在任何接口或基類中定義過)使得LinkedList可以當(dāng)作堆棧、隊(duì)列和雙向隊(duì)列使用

7..1 hash_map和map的區(qū)別在哪里憨颠？

構(gòu)造函數(shù)胳徽。hash_map需要hash函數(shù)，等于函數(shù)爽彤；map只需要比較函數(shù)(小于函數(shù)).
存儲(chǔ)結(jié)構(gòu)养盗。hash_map采用hash表存儲(chǔ)，map一般采用 紅黑樹(RB Tree) 實(shí)現(xiàn)适篙。因此其memory數(shù)據(jù)結(jié)構(gòu)是不一樣的往核。

7.2 什么時(shí)候需要用hash_map，什么時(shí)候需要用map?

總體來說嚷节，hash_map 查找速度會(huì)比map快聂儒，而且查找速度基本和數(shù)據(jù)數(shù)據(jù)量大小虎锚，屬于常數(shù)級別;而map的查找速度是log(n)級別。并不一定常數(shù)就比log(n)小衩婚，hash還有hash函數(shù)的耗時(shí)窜护，如果你考慮效率，特別是在元素達(dá)到一定數(shù)量級時(shí)非春，考慮考慮hash_map柱徙。但若你對內(nèi)存使用特別嚴(yán)格，希望程序盡可能少消耗內(nèi)存奇昙，那么一定要小心护侮，hash_map可能會(huì)讓你陷入尷尬，特別是當(dāng)你的hash_map對象特別多時(shí)敬矩，你就更無法控制了概行，而且hash_map的構(gòu)造速度較慢。
權(quán)衡三個(gè)因素: 查找速度, 數(shù)據(jù)量, 內(nèi)存使用弧岳。
8.一些使用上的建議：
Level 1 - 僅僅作為Map使用：采用靜態(tài)數(shù)組
Level 2 - 保存定長數(shù)據(jù)凳忙，使用時(shí)也是全部遍歷：采用動(dòng)態(tài)數(shù)組（長度一開始就固定的話靜態(tài)數(shù)組也行）
Level 3 - 保存不定長數(shù)組，需要?jiǎng)討B(tài)增加的能力禽炬，側(cè)重于尋找數(shù)據(jù)的速度：采用vector
Level 3 - 保存不定長數(shù)組涧卵，需要?jiǎng)討B(tài)增加的能力，側(cè)重于增加刪除數(shù)據(jù)的速度：采用list
Level 4 - 對數(shù)據(jù)有復(fù)雜操作腹尖，即需要前后增刪數(shù)據(jù)的能力柳恐，又要良好的數(shù)據(jù)訪問速度：采用deque
Level 5 - 對數(shù)據(jù)中間的增刪操作比較多：采用list，建議在排序的基礎(chǔ)上热幔，批量進(jìn)行增刪可以對運(yùn)行效率提供最大的保證
Level 6 - 上述中找不到適合的：組合STL容器或者自己建立特殊的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)

(1).vector - 會(huì)自動(dòng)增長的數(shù)組
vector<int>vec(10) //一個(gè)有10個(gè)int元素的容器
vector<float> vec(10, 0.5)//一個(gè)有10個(gè)float元素的容器乐设，并且他們得值都是0.5
vector<int>::iterator iter;
for(iter = vec.begin(); iter != vec.end(); iter++)
{
//. . . . . . .
}
vector由于數(shù)組的增長只能向前，所以也只提供了后端插入和后端刪除绎巨，
也就是push_back和pop_back近尚。當(dāng)然在前端和中間要操作數(shù)據(jù)也是可以的，
用insert和erase场勤，但是前端和中間對數(shù)據(jù)進(jìn)行操作必然會(huì)引起數(shù)據(jù)塊的移動(dòng)戈锻，
這對性能影響是非常大的。
最大的優(yōu)勢就是隨機(jī)訪問的能力和媳。
vector<T1>::iterator相關(guān)的方法有：
begin()：用來獲得一個(gè)指向vector第一個(gè)元素的指針
end()：用來獲得一個(gè)指向vector最后一個(gè)元素之后的那個(gè)位置的指針格遭，注意不是指向最后一個(gè)元素。
erase(vector<T1>::iterator)：用來刪除作為參數(shù)所傳入的那個(gè)iterator所指向的那個(gè)元素留瞳。
(2).list - 擅長插入刪除的鏈表
list<string>Milkshakes; list<int> Scores;
push_back, pop_backpush_front. pop_front
list是一個(gè)雙向鏈表的實(shí)現(xiàn)拒迅。
為了提供雙向遍歷的能力，list要比一般的數(shù)據(jù)單元多出兩個(gè)指向前后的指針
一個(gè)使用iterator來刪除元素的例子
list<string> stringList;
list<string>::iterator iter;
advance(iter, 5); //將iterator指向stringList的第五個(gè)元素
stringList.erase(iterator);//刪除
那么刪除操作進(jìn)行以后，傳入erase()方法的iterator指向哪里了呢坪它？它指向了刪除操作前所指向的那個(gè)元素的后一個(gè)元素骤竹。
(3).deque - 擁有vector和list兩者優(yōu)點(diǎn)的雙端隊(duì)列
(4)．這三個(gè)模板的總結(jié) 比較和一般使用準(zhǔn)則
這三個(gè)模板都屬于序列類模板，可以看到他們有一些通用方法
size():得到容器大小
begin():得到指向容器內(nèi)第一個(gè)元素的指針（這個(gè)指針的類型依容器的不同而不同）
end():得到指向容器內(nèi)最后一個(gè)元素之后一個(gè)位置的指針
erase():刪除傳入指針指向的那個(gè)元素
clear():清除所有的元素
＝＝運(yùn)算符：判斷兩個(gè)容器是否相等
＝運(yùn)算符：用來給容器賦值
上面的三個(gè)模板有各自的特點(diǎn)
vector模板的數(shù)據(jù)在內(nèi)存中連續(xù)的排列往毡，所以隨機(jī)存取元素（即通過[]運(yùn)算符存取）的速度最快靶溜，這一點(diǎn)和數(shù)組是一致的开瞭。同樣由于它的連續(xù)排列，所以它在除尾部以外的位置刪除或添加元素的速度很慢罩息，在使用vector時(shí)嗤详，要避免這種操作。
list模板的數(shù)據(jù)是鏈?zhǔn)酱鎯?chǔ)瓷炮，所以不能隨機(jī)存取元素葱色。它的優(yōu)勢在于任意位置添加 刪除元素的速度。
deque模板是通過鏈接若干片連續(xù)的數(shù)據(jù)實(shí)現(xiàn)的娘香，所以均衡了以上兩個(gè)容器的特點(diǎn)