十八.STL庫(kù)

主要包括三大組件：容器、算法贩耐、迭代器弧腥。

容器：序列式容器：vector、deque潮太、list管搪；關(guān)聯(lián)式容器：set虾攻、multiset、map更鲁、multimap霎箍；

1.vector：相當(dāng)于動(dòng)態(tài)數(shù)組

用法：push_back、pop_back澡为、begin漂坏、end（得到數(shù)組的最后一個(gè)單元+1的指針）、capacity（當(dāng)前vector分配的大小缀壤，每次擴(kuò)充當(dāng)前1.5-2倍的容量）樊拓、size（當(dāng)前使用數(shù)據(jù)的大小）塘慕、resize筋夏、reserve、reverse(vec.begin(),vec.end())（元素翻轉(zhuǎn)）图呢、erase条篷、clear、empty蛤织、swap赴叹、rbegin（原來(lái)的end-1）、rend（原來(lái)的begin-1）指蚜、insert（在指定位置loc前插入值為val的元素,返回指向這個(gè)元素的迭代器, 在指定位置loc前插入num個(gè)值為val的元素 在指定位置loc前插入?yún)^(qū)間[start, end)的所有元素）乞巧；

實(shí)現(xiàn)：動(dòng)態(tài)數(shù)組，里面有一個(gè)指針指向一片連續(xù)的內(nèi)存空間摊鸡，當(dāng)空間裝不下的時(shí)候會(huì)自動(dòng)申請(qǐng)一片更大的空間（空間配置器）將原來(lái)的數(shù)據(jù)拷貝到新的空間绽媒，然后就會(huì)釋放舊的空間。當(dāng)刪除的時(shí)候空間并不會(huì)被釋放只是清空了里面的數(shù)據(jù)免猾。

優(yōu)點(diǎn)：方便的進(jìn)行隨機(jī)存取是辕，可以不用定義大小猎提；

缺點(diǎn)：內(nèi)存連續(xù)获三，在中間插入或刪除元素時(shí)需要復(fù)制移動(dòng)現(xiàn)有的元素；只能在一端進(jìn)行push和pop锨苏；若插入內(nèi)存空間不夠時(shí)疙教，需要重新申請(qǐng)一塊足夠大的內(nèi)存并進(jìn)行拷貝，若對(duì)象比較大則執(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()(合并兩個(gè)有序鏈表并使之有序)李根、sort()槽奕、unique()（容器內(nèi)相鄰元素若有重復(fù)的，則僅保留一個(gè)）

實(shí)現(xiàn)： 底層數(shù)據(jù)結(jié)構(gòu)為雙向鏈表房轿，內(nèi)存空間是不連續(xù)的粤攒，通過(guò)指針來(lái)進(jìn)行數(shù)據(jù)的訪問(wèn)；

優(yōu)點(diǎn)：內(nèi)存不連續(xù)囱持，在內(nèi)部方便進(jìn)行插入和刪除操作夯接，可在兩端進(jìn)行push和pop；

缺點(diǎn)：不能進(jìn)行內(nèi)部的隨機(jī)訪問(wèn)纷妆，相對(duì)vector占用內(nèi)存較多盔几；

3.deque

用法：begin()和end()、push_back()和push_front()掩幢、pop_back和pop_front()逊拍、front()和back()、empty()粒蜈、resize()顺献、clear()、swap()枯怖、insert()注整、erase()、at();

實(shí)現(xiàn)：是一個(gè)雙端隊(duì)列

優(yōu)點(diǎn)：隨機(jī)訪問(wèn)方便度硝，在內(nèi)部方便的進(jìn)行插入和刪除操作肿轨，可在兩端進(jìn)行push、pop蕊程；

缺點(diǎn)：占用內(nèi)存多椒袍；

vector、list藻茂、deque使用對(duì)比：

? ? 1 如果你需要高效的隨即存取驹暑，而不在乎插入和刪除的效率玫恳，使用vector

? ? 2 如果你需要大量的插入和刪除，而不關(guān)心隨即存取优俘，則應(yīng)使用list

? ? 3 如果你需要隨即存取京办，而且關(guān)心兩端數(shù)據(jù)的插入和刪除，則應(yīng)使用deque

4.set

用法：count()-返回某個(gè)值元素的個(gè)數(shù)（set中最多為1）帆焕、find()-返回一個(gè)指向被查找到元素的迭代器惭婿、equal_range()-返回集合中與給定值相等的上下限的兩個(gè)迭代器、

實(shí)現(xiàn)：紅黑樹(shù)叶雹；

特點(diǎn)：元素不允許有重復(fù)财饥，在默認(rèn)情況下會(huì)對(duì)元素進(jìn)行自動(dòng)排序，數(shù)據(jù)被組織成一棵紅黑樹(shù)折晦，查找的速度非吃啃牵快（二分），時(shí)間復(fù)雜度是O(logN)筋遭，set中的元素不能被修改打颤，只能刪除后再添加。

缺點(diǎn)：set不能存儲(chǔ)無(wú)法比較大小的數(shù)據(jù)漓滔，不可以通過(guò)set的迭代器改變set的元素值编饺，會(huì)破壞排序規(guī)則

5.map：建立Key－value的對(duì)應(yīng)

用法：數(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ù)返回一個(gè)迭代器指向鍵值為key的元素锅论，如果沒(méi)找到就返回指向map尾部的迭代器）；元素刪除（iterator erase（iterator it);//通過(guò)一個(gè)條目對(duì)象刪除楣号，size_type erase(const Key&key);//通過(guò)關(guān)鍵字刪除）最易；swap()（map中的swap不是一個(gè)容器中的元素交換，而是兩個(gè)容器所有元素的交換炫狱。）藻懒；

實(shí)現(xiàn)：按照key值組織成一棵紅黑樹(shù)

特點(diǎn)：自動(dòng)建立Key－value的對(duì)應(yīng)，key的類型必須支持<操作符视译，key值排序且不重復(fù)嬉荆，根據(jù)key值快速查找記錄（二分），查找的復(fù)雜度基本是Log(N)酷含，增加和刪除節(jié)點(diǎn)對(duì)迭代器的影響很小鄙早，除了操作節(jié)點(diǎn)汪茧，對(duì)其他的節(jié)點(diǎn)都沒(méi)有什么影響。對(duì)于迭代器來(lái)說(shuō)蝶锋，不可以修改鍵值陆爽，只能修改其對(duì)應(yīng)的實(shí)值什往。

6.hash_map與map的區(qū)別扳缕？什么時(shí)候用hash_map，什么時(shí)候用map别威？

構(gòu)造函數(shù)：hash_map需要hash function和等于函數(shù)躯舔，而map需要比較函數(shù)（大于或小于）。

存儲(chǔ)結(jié)構(gòu)：hash_map以hashtable為底層省古，而map以RB-TREE為底層粥庄。

總的說(shuō)來(lái)，hash_map查找速度比map快豺妓，而且查找速度基本和數(shù)據(jù)量大小無(wú)關(guān)惜互，屬于常數(shù)級(jí)別。而map的查找速度是logn級(jí)別琳拭。但不一定常數(shù)就比log小训堆，而且hash_map還有hash function耗時(shí)。

如果考慮效率白嘁，特別當(dāng)元素達(dá)到一定數(shù)量級(jí)時(shí)坑鱼，用hash_map。

考慮內(nèi)存絮缅，或者元素?cái)?shù)量較少時(shí)鲁沥，用map。

7.map和set的3個(gè)問(wèn)題

1）為何map和set的插入刪除效率比其他序列容器高耕魄。

因?yàn)椴恍枰獌?nèi)存拷貝和內(nèi)存移動(dòng)

2）為何map和set每次Insert之后画恰，以前保存的iterator不會(huì)失效？

因?yàn)椴迦氩僮髦皇墙Y(jié)點(diǎn)指針換來(lái)?yè)Q去吸奴，結(jié)點(diǎn)內(nèi)存沒(méi)有改變允扇。而iterator就像指向結(jié)點(diǎn)的指針，內(nèi)存沒(méi)變奄抽，指向內(nèi)存的指針也不會(huì)變蔼两。

3）當(dāng)數(shù)據(jù)元素增多時(shí)（從10000到20000），map的set的查找速度會(huì)怎樣變化逞度？

RB-TREE用二分查找法额划，時(shí)間復(fù)雜度為logn，所以從10000增到20000時(shí)档泽，查找次數(shù)從log10000=14次到log20000=15次俊戳，多了1次而已揖赴。

8.STL的底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)

1）vector：底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組，支持快速隨機(jī)訪問(wèn)抑胎。

2）list：底層數(shù)據(jù)結(jié)構(gòu)為雙向鏈表燥滑，支持快速增刪。

3）deque：底層數(shù)據(jù)結(jié)構(gòu)為一個(gè)中央控制器和多個(gè)緩沖區(qū)阿逃，支持首尾（中間不能）快速增刪铭拧，支持隨機(jī)訪問(wèn)。

4）stack：底層用deque或者list實(shí)現(xiàn)恃锉，不用vector的原因是擴(kuò)容耗時(shí)搀菩。

5）queue：底層用deque或者list實(shí)現(xiàn)，不用vector的原因是擴(kuò)容耗時(shí)破托。

6）priority_queue：底層數(shù)據(jù)結(jié)構(gòu)一般以vector為底層容器肪跋，heap為處理規(guī)則來(lái)管理底層容器實(shí)現(xiàn)。

7）set：底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹(shù)土砂，有序州既，不重復(fù)。

8）multiset：底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹(shù)萝映，有序吴叶，可重復(fù)。

9）map：底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹(shù)锌俱，有序晤郑，不重復(fù)。

10）multimap：底層數(shù)據(jù)結(jié)構(gòu)為紅黑樹(shù)贸宏，有序造寝，可重復(fù)。

11）hash_set：底層數(shù)據(jù)結(jié)構(gòu)為hash表吭练，無(wú)序诫龙，不重復(fù)。

12）hash_map：底層數(shù)據(jù)結(jié)構(gòu)為hash表鲫咽，無(wú)序签赃，不重復(fù)。

13）hashtable：底層數(shù)據(jù)結(jié)構(gòu)是vector分尸。

迭代器：

迭代器提供了一種方法锦聊，使它能夠按照順序訪問(wèn)某個(gè)容器所含的各個(gè)元素，但無(wú)需暴露該容器的內(nèi)部結(jié)構(gòu)1.vector::const_iterator 和 const vector::iterator的區(qū)別

前者不能修改容器中的元素箩绍，如：*newiter=11 屬于錯(cuò)誤孔庭，可以修改迭代器自身，如：newiter++正確；后者可以修改指向容器的元素圆到，如：*newiter=11正確怎抛，迭代器本身不能被修改，如：newiter++錯(cuò)誤芽淡；

2.迭代器的刪除操作

vector马绝、list、map挣菲、deque用erase（it）后富稻，迭代器的變化。

vector和deque是序列式容器己单，其內(nèi)存分別是連續(xù)空間和分段連續(xù)空間唉窃，刪除迭代器it后，其后面的迭代器都失效了纹笼，此時(shí)it及其后面的迭代器會(huì)自動(dòng)加1，使it指向被刪除元素的下一個(gè)元素苟跪。

list刪除迭代器it時(shí)廷痘，其后面的迭代器都不會(huì)失效，將前面和后面連接起來(lái)即可件已。

map也是只能使當(dāng)前刪除的迭代器失效笋额，其后面的迭代器依然有效。

在迭代容器的時(shí)候刪除元素篷扩，可能導(dǎo)致迭代器失效兄猩，解決方法：

　　? ? ? ? for (it != my_container.end(); ) {

? ? ? ? ? ? if (*it % 2 == 1) {

　　? ? ? ? ? ? ? ? it = my_container.erase(it);? ? ? //讓erase() 返回一個(gè)新的迭代器，指向被刪除元素的后面的元素

　　? ? ? ? ? ? }

　　? ? ? ? ? ? else{

　　? ? ? ? ? ? ? ? ? it++;

　　? ? ? ? ? ? }

　　? ? ? ? }

? ? 或者 for( it = List.begin(); it != List.end(); )

? ? ? ? ? {

? ? ? ? ? ? ? ? if( WillDelete( *it) )

? ? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? List.erase( it++);? ? ? ? ? ? ? ? //使迭代器在刪除前自加

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? else

? ? ? ? ? ? ? ? ? it++;

? ? ? ? ? }

算法：

std::sort()

1.stl set map 使用紅黑樹(shù) avl樹(shù)作為底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)鉴未，不支持隨機(jī)迭代器枢冤，所以不能使用sort來(lái)排序,能用std::sort()的有vector, deque, string；

2.排序是通過(guò)多次內(nèi)存的copy來(lái)實(shí)現(xiàn)的铜秆，所以鏈表不能使用stl算法sort來(lái)對(duì)其排序(next指針修改問(wèn)題)淹真，list自帶排序算法list::sort()；