簡介
STL是Standard Template Library的簡稱城侧，中文名標準模板庫。其提供了許多計算機科學的基礎算法和數(shù)據(jù)結(jié)構。下面主要是收集一些網(wǎng)上以及自己在使用過程中關于STL的一些注意事項以及問題答疑總結(jié)
STL組成部分
1.容器：
容器是容納疏之、包含一組元素或元素集合的對象,主要分為兩大類序列式容器和關聯(lián)式容器
序列式容器：容器提供順序訪問州弟、隨機訪問其中的元素
| 名稱 | 說明 |
|---|---|
array |
c++內(nèi)建 |
vector |
|
heap |
以算法形式呈現(xiàn) |
priority_queue |
|
list |
|
slist |
非標準 |
deque |
|
stack |
配接器 |
queue |
配接器 |
關聯(lián)式容器：通過優(yōu)化關鍵值訪問
| 名稱 | 說明 |
|---|---|
RB-tree |
非公開 |
set |
|
map |
|
multiset |
|
multimap |
|
hashtable |
非標準 |
hash_set |
非標準 |
hash_map |
非標準 |
hash_multiset |
非標準 |
hash_multimap |
非標準 |
2.算法：
算法Algorithms，用來處理群集內(nèi)的元素,它們可以出于不同的目的而搜尋嘿悬、排序实柠、修改、使用那些元素善涨。通過迭代器的協(xié)助窒盐，我們可以只需編寫一次算法草则，就可以將它應用于任意容器，這是因為所有的容器迭代器都提供一致的接口,常見算法如sort/search/copy/erase/next_permutation/partion等
3.迭代器：
扮演容器與算法之間的膠合劑蟹漓，用來在一個對象群集的元素上進行遍歷炕横。這個對象群集或許是個容器，或許是容器的一部分葡粒。迭代器的主要好處是看锉，為所有容器提供了一組很小的公共接口,每種容器都提供了自己的迭代器，而這些迭代器能夠了解容器內(nèi)部的數(shù)據(jù)結(jié)構
4. 容器配接器：
一種用來修飾容器或者仿函數(shù)或迭代器接口的東西塔鳍。比如queue和stack伯铣，看著像容器，其實就是deque包了一層封裝
5.仿函數(shù)：
行為類似函數(shù)轮纫，可作為算法的某種策略（Policy）,從實現(xiàn)的角度來看腔寡，仿函數(shù)是一種重載了Operator()的Class 或 Class Template。一般函數(shù)指針可視為狹義的仿函數(shù)
6.空間配置器：
負責空間配置與管理,是一個實現(xiàn)了動態(tài)空間配置掌唾、空間管理放前、空間釋放的class template
STL使用總結(jié)與注意事項
vector的底層機制
vector就是一個動態(tài)數(shù)組,里面有一個指針指向一片連續(xù)的內(nèi)存空間,當空間不夠裝下數(shù)據(jù)時,會自動申請一份雙倍于當前容量的空間,然后把原來的數(shù)據(jù)拷貝過去,接著釋放原來的那片空間,當釋放或者刪除里面的數(shù)據(jù)時,其存儲空間不釋放,僅僅是清空了里面的數(shù)據(jù)。對vector的任何操作,一旦硬氣空間重新配置,指向原vector的所有迭代器都失效
list的底層機制
以節(jié)點為單位存儲數(shù)據(jù),結(jié)點的地址在內(nèi)存中不一定連續(xù),每次插入或者刪除一個元素,就配置或者釋放一個元素空間
什么情況下用vector,什么情況下使用list
vector可以隨機存儲元素,但是非尾部插入刪除數(shù)據(jù)時效率很低,適合對象簡單糯彬、對象數(shù)量變化不大凭语、隨機訪問頻繁的場景
list不支持隨機存儲訪問,適用于對象大、對象數(shù)量變化頻繁撩扒、插入和刪除頻繁的場景
list自帶排序函數(shù)排序原理
將前2個元素合并,再將后2個元素合并,然后合并這2個子序列成為4個元素序列的子序列,重復這一過程,得到8個似扔，16個....子序列，最后得到的就是排序后的序列搓谆。時間復雜度O(logn)
deque的底層機制
deque動態(tài)地以分段連續(xù)空間組合而成炒辉，隨時可以增加一段新的連續(xù)空間并鏈接起來，不提供空間保留功能(底層數(shù)據(jù)結(jié)構為一個中央控制器和多個緩沖區(qū))
注意:
1.除非必要泉手，我們盡可能選擇使用vector而非deque黔寇，因為deque的迭代器比vector迭代器復雜很多。對duque的排序斩萌，為了提高效率缝裤，可先將deque復制到一個vector上排序，然后再復制到deque
2.deque采用一塊map(不是STL的map容器)作為主控颊郎，其為一小塊連續(xù)空間憋飞，其中每個元素都是指針，指向另一段較大的連續(xù)空間(緩沖區(qū))
3.包含四個內(nèi)容：
??cur：迭代器當前所指元素
??first：此迭代器所指的緩沖區(qū)的頭
??last：緩沖區(qū)尾
??node：指向管控中心
deque與vector的區(qū)別
1.vector是單向開口的連續(xù)空間,deque是雙向開口的連續(xù)線性空間
2.deque沒有提供空間保留功能,vector則提供空間保留功能
3.deque也提供隨機訪問迭代器,但是deque迭代器比vector要復雜
map底層機制袭艺、查找時間復雜度搀崭、能否邊遍歷邊插入
紅黑樹叨粘、O(logN)猾编、不可以,它在容器進行erase操作后不會返回后一個元素的迭代器
hashtable如何避免地址沖突
1.hash函數(shù)計算某個元素的插入位置后瘤睹，如果該位置的空間已經(jīng)被占用，則繼續(xù)向下尋找答倡，直到找到一個可用空間為止
2.二次探測：如果計算的位置被占用轰传，就依次嘗試H+12,H+22 等
3.開鏈：每一個表格元素中維護一個list，在那個list中執(zhí)行插入瘪撇、刪除
hash_set與set的區(qū)別
hash_set以hashtable為底層获茬，不具有排序功能，能快速查找倔既，其鍵值就是實值
set以紅黑樹為底層恕曲，具有排序功能
hash_map與map區(qū)別
構造函數(shù)：hash_map需要hash function 和等于函數(shù)，而 map需要比較函數(shù)（大小或小于）
存儲結(jié)構：hash_map以hashtable為底層渤涌，而map以紅黑樹為底層
hash_map與map選擇性
查找角度:hash_map查找速度比map快佩谣，而且查找速度基本和數(shù)據(jù)量大小無關，屬于常數(shù)級別实蓬。而map的查找速度是logN級別,但不一定常數(shù)就比log小茸俭，而且hash_map還有hash function耗時,如果考慮效率，特別當元素達到一定數(shù)量級時安皱，用hash_map调鬓。選用map還是hash_map，關鍵是看關鍵字查詢操作次數(shù)酌伊，以及你所需要保證的是查詢總體時間還是單個查詢的時間腾窝。如果是要很多次操作，要求其整體效率居砖，那么使用hash_map燕锥，平均處理時間短。如果是少數(shù)次的操作悯蝉，使用 hash_map可能造成不確定的O(N)归形，那么使用平均處理時間相對較慢、單次處理時間恒定的map鼻由，考慮整體穩(wěn)定性應該要高于整體效率暇榴，因為前提在操作次數(shù)較少。如果在一次流程中蕉世，使用hash_map的少數(shù)操作產(chǎn)生一個最壞情況O(N)蔼紧，那么hash_map的優(yōu)勢也因此喪盡了
map和set的插入效率為啥必其他序列容器高
不需要內(nèi)存拷貝和移動
map和set每次insert之后,之前保存的iterator會不會失效
因為插入操作只是結(jié)點指針換來換去，結(jié)點內(nèi)存沒有改變狠轻，而iterator就像指向結(jié)點的指針奸例，內(nèi)存沒變，指向內(nèi)存的指針也不會變
當元素增多時例如從10000到20000,map和set查找速度會有怎樣的變化
紅黑樹用二分查找法，時間復雜度為logN查吊，所以查找次數(shù)從log100000=14變?yōu)閘og20000=15,多了1次而已
auto_ptr是否可以做vector的元素
不能,因為STL的標準容器規(guī)定它所容納的元素必須是可以拷貝構造和可被轉(zhuǎn)移賦值的,而auto_ptr不能谐区，可以用shared_ptr智能指針代替
不允許遍歷行為(不提供迭代器)的容器有哪些
queue：除了頭部外，沒有其他方法存取deque的其他元素
stack：(底層以deque實現(xiàn)),除了最頂端外逻卖，沒有任何方法可以存取stack的其他元素
heap：所有元素都必須遵循特別的排序規(guī)則宋列，不提供遍歷功能
vector、list评也、map炼杖、deque用erase（it）后，迭代器的變化
vector和deque是序列式容器盗迟，其內(nèi)存分別是連續(xù)空間和分段連續(xù)空間坤邪，刪除迭代器it后，其后面的迭代器都失效了罚缕，此時it及其后面的迭代器會自動加1罩扇，使it指向被刪除元素的下一個元素
list刪除迭代器it時，其后面的迭代器都不會失效怕磨，將前面和后面連接起來即可
map也是只能使當前刪除的迭代器失效喂饥，其后面的迭代器依然有效
為何map和set不能像vector一樣有個reserve函數(shù)來預分配數(shù)據(jù)
引起它的原因在于在map和set內(nèi)部存儲的已經(jīng)不是元素本身了，而是包含元素的節(jié)點肠鲫。也就是說map內(nèi)部使用的Alloc并不是map<Key, Data, Compare, Alloc>聲明的時候從參數(shù)中傳入的Alloc
set, multiset區(qū)別
1.set和multiset會根據(jù)特定的排序準則自動將元素排序员帮，set中元素不允許重復，multiset可以重復
2.因為是排序的导饲，所以set中的元素不能被修改捞高，只能
map，multimap區(qū)別
1.map和multimap將key和value組成的pair作為元素渣锦，根據(jù)key的排序準則自動將元素排序硝岗，map中元素的key不允許重復，multimap可以重復
2.因為是排序的袋毙，所以map中元素的key不能被修改型檀，只能刪除后再添加。key對應的value可以修改
3.向map中添加的元素的key類型必須重載<操作符用來排序
