十八.STL庫
主要包括三大組件：容器、算法、迭代器。
容器：序列式容器：vector、deque、list；關聯(lián)式容器：set、multiset、map、multimap；
1.vector：相當于動態(tài)數(shù)組
用法：push_back、pop_back、begin、end（得到數(shù)組的最后一個單元+1的指針）、capacity（當前vector分配的大小，每次擴充當前1.5-2倍的容量）、size（當前使用數(shù)據(jù)的大?。esize、reserve、reverse(vec.begin(),vec.end())（元素翻轉(zhuǎn)）、erase、clear、empty、swap、rbegin（原來的end-1）、rend（原來的begin-1）、insert（在指定位置loc前插入值為val的元素,返回指向這個元素的迭代器, 在指定位置loc前插入num個值為val的元素 在指定位置loc前插入?yún)^(qū)間[start, end)的所有元素）；
實現(xiàn)：動態(tài)數(shù)組，里面有一個指針指向一片連續(xù)的內(nèi)存空間，當空間裝不下的時候會自動申請一片更大的空間（空間配置器）將原來的數(shù)據(jù)拷貝到新的空間，然后就會釋放舊的空間。當刪除的時候空間并不會被釋放只是清空了里面的數(shù)據(jù)。
優(yōu)點：方便的進行隨機存取，可以不用定義大小；
缺點：內(nèi)存連續(xù)，在中間插入或刪除元素時需要復制移動現(xiàn)有的元素；只能在一端進行push和pop；若插入內(nèi)存空間不夠時，需要重新申請一塊足夠大的內(nèi)存并進行拷貝，若對象比較大則執(zhí)行效率比較低；
reserve和resize的區(qū)別：reserve: 分配空間，更改capacity但不改變size；resize: 分配空間，更改capacity也改變size
2.list：循環(huán)雙向鏈表
用法：begin()和end()、push_back()和push_front()、pop_back和pop_front()、front()和back()、empty()、resize()、clear()、reverse()（逆置）、swap()、insert()、erase()、merge()(合并兩個有序鏈表并使之有序)、sort()、unique()（容器內(nèi)相鄰元素若有重復的，則僅保留一個）
實現(xiàn)： 底層數(shù)據(jù)結(jié)構(gòu)為雙向鏈表，內(nèi)存空間是不連續(xù)的，通過指針來進行數(shù)據(jù)的訪問；
優(yōu)點：內(nèi)存不連續(xù)，在內(nèi)部方便進行插入和刪除操作，可在兩端進行push和pop；
缺點：不能進行內(nèi)部的隨機訪問，相對vector占用內(nèi)存較多；
3.deque
用法：begin()和end()、push_back()和push_front()、pop_back和pop_front()、front()和back()、empty()、resize()、clear()、swap()、insert()、erase()、at();
實現(xiàn)：是一個雙端隊列
優(yōu)點：隨機訪問方便，在內(nèi)部方便的進行插入和刪除操作，可在兩端進行push、pop；
缺點：占用內(nèi)存多；
vector、list、deque使用對比：
? ? 1 如果你需要高效的隨即存取，而不在乎插入和刪除的效率，使用vector
? ? 2 如果你需要大量的插入和刪除，而不關心隨即存取，則應使用list
? ? 3 如果你需要隨即存取，而且關心兩端數(shù)據(jù)的插入和刪除，則應使用deque
4.set
用法：count()-返回某個值元素的個數(shù)（set中最多為1）、find()-返回一個指向被查找到元素的迭代器、equal_range()-返回集合中與給定值相等的上下限的兩個迭代器、
實現(xiàn)：紅黑樹；
特點：元素不允許有重復，在默認情況下會對元素進行自動排序，數(shù)據(jù)被組織成一棵紅黑樹，查找的速度非常快（二分），時間復雜度是O(logN)，set中的元素不能被修改，只能刪除后再添加。
缺點：set不能存儲無法比較大小的數(shù)據(jù)，不可以通過set的迭代器改變set的元素值，會破壞排序規(guī)則
5.map：建立Key－value的對應
用法：數(shù)據(jù)插入（1、用insert函數(shù)插入pair數(shù)據(jù)，如：a.insert(pair(1, "student_one"))；2、用insert函數(shù)插入value_type數(shù)據(jù)，如：insert(map::value_type (1, "student_one"))；3、用數(shù)組方式插入數(shù)據(jù)，如：a[1]="student_one"）;元素查找（find()函數(shù)返回一個迭代器指向鍵值為key的元素，如果沒找到就返回指向map尾部的迭代器）；元素刪除（iterator erase（iterator it);//通過一個條目對象刪除，size_type erase(const Key&key);//通過關鍵字刪除）；swap()（map中的swap不是一個容器中的元素交換，而是兩個容器所有元素的交換。）；
實現(xiàn)：按照key值組織成一棵紅黑樹
特點：自動建立Key－value的對應，key的類型必須支持<操作符，key值排序且不重復，根據(jù)key值快速查找記錄（二分），查找的復雜度基本是Log(N)，增加和刪除節(jié)點對迭代器的影響很小，除了操作節(jié)點，對其他的節(jié)點都沒有什么影響。對于迭代器來說，不可以修改鍵值，只能修改其對應的實值。
6.hash_map與map的區(qū)別？什么時候用hash_map，什么時候用map？
構(gòu)造函數(shù)：hash_map需要hash function和等于函數(shù)，而map需要比較函數(shù)（大于或小于）。
存儲結(jié)構(gòu)：hash_map以hashtable為底層，而map以RB-TREE為底層。
總的說來，hash_map查找速度比map快，而且查找速度基本和數(shù)據(jù)量大小無關，屬于常數(shù)級別。而map的查找速度是logn級別。但不一定常數(shù)就比log小，而且hash_map還有hash function耗時。
如果考慮效率，特別當元素達到一定數(shù)量級時，用hash_map。
考慮內(nèi)存，或者元素數(shù)量較少時，用map。
7.map和set的3個問題
1）為何map和set的插入刪除效率比其他序列容器高。
因為不需要內(nèi)存拷貝和內(nèi)存移動
2）為何map和set每次Insert之后，以前保存的iterator不會失效？
因為插入操作只是結(jié)點指針換來換去，結(jié)點內(nèi)存沒有改變。而iterator就像指向結(jié)點的指針，內(nèi)存沒變，指向內(nèi)存的指針也不會變。
3）當數(shù)據(jù)元素增多時（從10000到20000），map的set的查找速度會怎樣變化？
RB-TREE用二分查找法，時間復雜度為logn，所以從10000增到20000時，查找次數(shù)從log10000=14次到log20000=15次，多了1次而已。
8.STL的底層數(shù)據(jù)結(jié)構(gòu)實現(xiàn)
1）vector：底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組，支持快速隨機訪問。
2）list：底層數(shù)據(jù)結(jié)構(gòu)為雙向鏈表，支持快速增刪。
3）deque：底層數(shù)據(jù)結(jié)構(gòu)為一個中央控制器和多個緩沖區(qū)，支持首尾（中間不能）快速增刪，支持隨機訪問。
4）stack：底層用deque或者list實現(xiàn)，不用vector的原因是擴容耗時。
5）queue：底層用deque或者list實現(xiàn)，不用vector的原因是擴容耗時。
6）priority_queue：底層數(shù)據(jù)結(jié)構(gòu)一般以vector為底層容器，heap為處理規(guī)則來管理底層容器實現(xiàn)。
7）set：底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹，有序，不重復。
8）multiset：底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹，有序，可重復。
9）map：底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹，有序，不重復。
10）multimap：底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹，有序，可重復。
11）hash_set：底層數(shù)據(jù)結(jié)構(gòu)為hash表，無序，不重復。
12）hash_map：底層數(shù)據(jù)結(jié)構(gòu)為hash表，無序，不重復。
13）hashtable：底層數(shù)據(jù)結(jié)構(gòu)是vector。
迭代器：
迭代器提供了一種方法，使它能夠按照順序訪問某個容器所含的各個元素，但無需暴露該容器的內(nèi)部結(jié)構(gòu)1.vector::const_iterator 和 const vector::iterator的區(qū)別
前者不能修改容器中的元素，如：*newiter=11 屬于錯誤，可以修改迭代器自身，如：newiter++正確；后者可以修改指向容器的元素，如：*newiter=11正確，迭代器本身不能被修改，如：newiter++錯誤；
2.迭代器的刪除操作
vector、list、map、deque用erase（it）后，迭代器的變化。
vector和deque是序列式容器，其內(nèi)存分別是連續(xù)空間和分段連續(xù)空間，刪除迭代器it后，其后面的迭代器都失效了，此時it及其后面的迭代器會自動加1，使it指向被刪除元素的下一個元素。
list刪除迭代器it時，其后面的迭代器都不會失效，將前面和后面連接起來即可。
map也是只能使當前刪除的迭代器失效，其后面的迭代器依然有效。
在迭代容器的時候刪除元素，可能導致迭代器失效，解決方法：
? ? ? ? for (it != my_container.end(); ) {
? ? ? ? ? ? if (*it % 2 == 1) {
? ? ? ? ? ? ? ? it = my_container.erase(it);? ? ? //讓erase() 返回一個新的迭代器，指向被刪除元素的后面的元素
? ? ? ? ? ? }
? ? ? ? ? ? else{
? ? ? ? ? ? ? ? ? it++;
? ? ? ? ? ? }
? ? ? ? }
? ? 或者 for( it = List.begin(); it != List.end(); )
? ? ? ? ? {
? ? ? ? ? ? ? ? if( WillDelete( *it) )
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? List.erase( it++);? ? ? ? ? ? ? ? //使迭代器在刪除前自加
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? it++;
? ? ? ? ? }
算法：
std::sort()
1.stl set map 使用紅黑樹 avl樹作為底層數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，不支持隨機迭代器，所以不能使用sort來排序,能用std::sort()的有vector, deque, string；
2.排序是通過多次內(nèi)存的copy來實現(xiàn)的，所以鏈表不能使用stl算法sort來對其排序(next指針修改問題)，list自帶排序算法list::sort()；
