STL部分
1.STL為什么廣泛被使用
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)部采用數(shù)據(jù)結(jié)構(gòu)是什么？簡要介紹一下谎僻。
（1）都是一種非常高效的平衡檢索二叉樹:紅黑樹娄柳，也稱為為RB樹(Red-BlackTree)。RB樹的統(tǒng)計(jì)性能要好于一般的平衡二叉樹戈稿，
（2）紅黑樹的簡要介紹：紅黑樹(一)之 原理和算法詳細(xì)介紹 - 如果天空不死 - 博客園
3.STL map和set的相關(guān)問題:?
(1)為何map和set的插入刪除效率比用其他序列容器高?西土，樹
答:因?yàn)閷τ陉P(guān)聯(lián)容器來說，不需要做內(nèi)存拷貝和內(nèi)存移動鞍盗。說對了需了，確實(shí)如此。map和set容器內(nèi)所有元素都是以節(jié)點(diǎn)的方式來存儲般甲，其節(jié)點(diǎn)結(jié)構(gòu)和鏈表差不多肋乍，指向父節(jié)點(diǎn)和子節(jié)點(diǎn)
(2)為何每次insert之后，以前保存的iterator不會失效?
答:iterator這里就相當(dāng)于指向節(jié)點(diǎn)的指針敷存，內(nèi)存沒有變墓造，指向內(nèi)存的指針怎么會失效呢(當(dāng)然被刪除的那個元素本身已經(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)被釋放了。即使是push_back的時候彻亲，容器內(nèi)部空間可能不夠孕锄，需要一塊新的更大的內(nèi)存，只有把以前的內(nèi)存釋放苞尝，申請新的更大的內(nèi)存畸肆，復(fù)制已有的數(shù)據(jù)元素到新的內(nèi)存，最后把需要插入的元素放到最后宙址，那么以前的內(nèi)存指針自然就不可用了轴脐。特別時在和find等算法在一起使用的時候，牢記這個原則:不要使用過期的iterator。
(3)為何map和set不能像vector一樣有個reserve函數(shù)來預(yù)分配數(shù)據(jù)?
答:我以前也這么問豁辉，究其原理來說時令野，引起它的原因在于在map和set內(nèi)部存儲的已經(jīng)不是元素本身了，而是包含元素的節(jié)點(diǎn)徽级。也就是說map內(nèi)部使用的Alloc并不是map聲明的時候從參數(shù)中傳入的Alloc气破。例如:
4.? set 與 multiset
set和multiset會根據(jù)特定的排序準(zhǔn)則自動將元素排序，set中元素不允許重復(fù)餐抢，multiset可以重復(fù)现使。
因?yàn)槭桥判虻模詓et中的元素不能被修改旷痕，只能刪除后再添加碳锈。
set與multiset有序存儲元素，這兩種容器的底層實(shí)現(xiàn)與map一樣都是紅黑樹欺抗，所以能實(shí)現(xiàn)O(lgn)的查找售碳，插入，刪除操作绞呈。
5.? map與multimap底層數(shù)據(jù)結(jié)構(gòu)
map與multimap是STL中的關(guān)聯(lián)容器贸人、提供一對一key-value的數(shù)據(jù)處理能力； map與multimap的區(qū)別在于佃声，multimap允許關(guān)鍵字重復(fù)艺智，而map不允許重復(fù)。
這兩個關(guān)聯(lián)容器的底層數(shù)據(jù)結(jié)構(gòu)均為紅黑樹圾亏，關(guān)于紅黑樹的理解可以參考教你透徹了解紅黑樹一文十拣。
根據(jù)紅黑樹的原理，map與multimap可以實(shí)現(xiàn)O(lgn)的查找志鹃，插入和刪除夭问。
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使用)一個List可以生成ListIterator,使用它可以從兩個方向遍歷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ì)列使用
List常用操作函數(shù)：
Lst1.assign() 給list賦值 韧骗； ? Lst1.back() 返回最后一個元素嘉抒； ? Lst1.begin() 返回指向第一個元素的迭代器
Lst1.clear() 刪除所有元素； Lst1.empty() 如果list是空的則返回true袍暴； ? Lst1.end() 返回末尾的迭代器
Lst1.erase() 刪除一個元素些侍；? Lst1.front() 返回第一個元素； ?? Lst1.get_allocator() 返回list的配置器
Lst1.insert() 插入一個元素到list中政模；（Lst1.insert(iter, 100)//在迭代器iter指的元素后面加入元素100
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? Lst1.insert(iter岗宣，2, 100)? //在迭代器iter指的元素后面加如2個100）
? Lst1.max_size() 返回list能容納的最大元素?cái)?shù)量
Lst1.merge() 合并兩個list淋样； ? ? ? Lst1.pop_back() 刪除最后一個元素； ?? Lst1.pop_front() 刪除第一個元素
Lst1.push_back() 在list的末尾添加一個元素刊咳；Lst1.push_front() 在list的頭部添加一個元素
Lst1.rbegin() 返回指向第一個元素的逆向迭代器躲叼； Lst1.remove() 從list刪除元素；
Lst1.remove_if() 按指定條件刪除元素枫慷；? Lst1.rend() 指向list末尾的逆向迭代器； Lst1.resize() 改變list的大小
Lst1.reverse() 把list的元素倒轉(zhuǎn)探孝； Lst1.size() 返回list中的元素個數(shù)；? Lst1.sort() 給list排序
Lst1.splice() 合并兩個list誉裆； Lst1.swap() 交換兩個list顿颅；? Lst1.unique() 刪除list中重復(fù)的元素
7.? hash_map和map的區(qū)別在哪里?
構(gòu)造函數(shù)：hash_map需要hash函數(shù)（等于函數(shù)）; ? ?? map只需要比較函數(shù)(小于函數(shù)).
存儲結(jié)構(gòu)：hash_map采用hash表存儲，map一般采用紅黑樹(RBTree)實(shí)現(xiàn)足丢。因此其memory數(shù)據(jù)結(jié)構(gòu)是不一樣的粱腻。
8 .什么時候需要用hash_map，什么時候需要用map?
總體來說斩跌，hash_map 查找速度會比map快绍些，而且查找速度基本和數(shù)據(jù)數(shù)據(jù)量大小無關(guān)，屬于常數(shù)級別;而map的查找速度是log(n)級別耀鸦。并不一定常數(shù)就比log(n)小柬批，hash還有hash函數(shù)的耗時啸澡，明白了吧，如果你考慮效率氮帐，特別是在元素達(dá)到一定數(shù)量級時嗅虏，考慮考慮hash_map。但若你對內(nèi)存使用特別嚴(yán)格上沐，希望程序盡可能少消耗內(nèi)存皮服，那么一定要小心，hash_map可能會讓你陷入尷尬奄容，特別是當(dāng)你的hash_map對象特別多時冰更，你就更無法控制了，而且hash_map的構(gòu)造速度較慢昂勒。
現(xiàn)在知道如何選擇了嗎?權(quán)衡三個因素: 查找速度, 數(shù)據(jù)量, 內(nèi)存使用蜀细。
9.?一些容器使用上的建議（應(yīng)用場景）
Level 1 - 僅僅作為Map使用:采用靜態(tài)數(shù)組
Level 2 - 保存定長數(shù)據(jù)奠衔，使用時也是全部遍歷:采用動態(tài)數(shù)組(長度一開始就固定的話靜態(tài)數(shù)組也行)
Level 3 - 保存不定長數(shù)組，需要動態(tài)增加的能力脏里，側(cè)重于尋找數(shù)據(jù)的速度:采用vector
Level 3 - 保存不定長數(shù)組迫横，需要動態(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)
10 vector, list, deque 三者比較分析
(1).vector ----- 會自動增長的數(shù)組
vector由于數(shù)組的增長只能向前十厢，所以也只提供了后端插入和后端刪除缩抡，也就是push_back和pop_back瞻想。當(dāng)然在前端和中間要操作數(shù)據(jù)也是可以的，用insert和erase佃迄，但是前端和中間對數(shù)據(jù)進(jìn)行操作必然會引起數(shù)據(jù)塊的移動呵俏，
這對性能影響是非常大的。最大的優(yōu)勢就是隨機(jī)訪問的能力麻车。
(2).list -------- 擅長插入刪除的鏈表
list 的常用操作：?push_back（）, pop_back（）绪氛，push_front（）， pop_front（）
list是一個雙向鏈表的實(shí)現(xiàn)：
為了提供雙向遍歷的能力序目，list要比一般的數(shù)據(jù)單元多出兩個指向前后的指針猿涨，一個使用iterator來刪除元素的例子
list stringList;
list::iterator iter;
advance(iter, 5); //將iterator指向stringList的第五個元素
stringList.erase(iterator);//刪除
那么刪除操作進(jìn)行以后澡绩，傳入erase()方法的iterator指向哪里了呢?它指向了刪除操作前所指向的那個元素的后一個元素肥卡。
(3).deque ------? 擁有vector和list兩者優(yōu)點(diǎn)的雙端隊(duì)列
這三個模板的總結(jié) 比較和一般使用準(zhǔn)則
這三個模板都屬于序列類模板，可以看到他們有一些通用方法
size():得到容器大小
begin():得到指向容器內(nèi)第一個元素的指針(這個指針的類型依容器的不同而不同)
end():得到指向容器內(nèi)最后一個元素之后一個位置的指針
erase():刪除傳入指針指向的那個元素
clear():清除所有的元素
==運(yùn)算符:判斷兩個容器是否相等
=運(yùn)算符:用來給容器賦值
上面的三個模板有各自的特點(diǎn)
vector模板的數(shù)據(jù)在內(nèi)存中連續(xù)的排列镰矿，所以隨機(jī)存取元素(即通過[]運(yùn)算符存取)的速度最快，這一點(diǎn)和數(shù)組是一致的障般。同樣由于它的連續(xù)排列挽荡，所以它在除尾部以外的位置刪除或添加元素的速度很慢，在使用vector時青自，要避免這種操作延窜。
list模板的數(shù)據(jù)是鏈?zhǔn)酱鎯δ嫒穑圆荒茈S機(jī)存取元素获高。它的優(yōu)勢在于任意位置添加 刪除元素的速度。
deque模板是通過鏈接若干片連續(xù)的數(shù)據(jù)實(shí)現(xiàn)的摊趾，所以均衡了以上兩個容器的特點(diǎn)
11.說說vector的底層（存儲）機(jī)制
?vector就是一個動態(tài)數(shù)組砾层，里面有一個指針指向一片連續(xù)的內(nèi)存空間，當(dāng)空間不夠裝下數(shù)據(jù)時铸董，會自動申請另一片更大的空間（一般是增加當(dāng)前容量的50%或100%）粟害，然后把原來的數(shù)據(jù)拷貝過去，接著釋放原來的那片空間站蝠；當(dāng)釋放或者刪除當(dāng)前vector里面的數(shù)據(jù)時留荔，當(dāng)前vector的存儲空間不釋放，僅僅是清空了里面的數(shù)據(jù)藻治。
12.vector的自增長機(jī)制
當(dāng)已經(jīng)分配的空間不夠裝下數(shù)據(jù)時验靡，分配雙倍于當(dāng)前容量的存儲區(qū)晴叨，把當(dāng)前的值拷貝到新分配的內(nèi)存中，并釋放原來的內(nèi)存孙技。
13.說說list的底層（存儲）機(jī)制
以結(jié)點(diǎn)為單位存放數(shù)據(jù)亚情，結(jié)點(diǎn)的地址在內(nèi)存中不一定連續(xù)楞件，每次插入或刪除一個元素土浸，就配置或釋放一個元素空間
14. unordeded_map和unordeded_set的底層實(shí)現(xiàn)
? ?? 在STL函數(shù)庫里邊有關(guān)map和set的總共有8個函數(shù)。
? map还最； set拓轻；multimap悦即；multiset；unordered_map作瞄；unordered_set宗挥；unordered_multiset；unordered_multimap
?簡單的做以區(qū)分：
map: ? K/V （鍵/值）結(jié)構(gòu)搪桂。 ? ? ? ? ? set: ? K（鍵）結(jié)構(gòu)酗电。
multi: ? 可以冗余，如沒有這個關(guān)鍵字嫩与，則是防冗余版本。
unordered: ? 底層由哈希表（哈希桶算法）來實(shí)現(xiàn)，如無該關(guān)鍵字都许，則底層是由紅黑樹來實(shí)現(xiàn)。
unordered_map和unordered_set ? &? unordered_multiset 和 unordered_multimap中key為無序排列睛低，其底層實(shí)現(xiàn)為hash table，因此其查找時間復(fù)雜度理論上達(dá)到了O(n)
15.什么情況下用vector吹零，什么情況下用list
vector可以隨機(jī)存儲元素（即可以通過公式直接計(jì)算出元素地址灿椅，而不需要挨個查找）操刀，但在非尾部插入刪除數(shù)據(jù)時骨坑，效率很低静稻，適合對象簡單，對象數(shù)量變化不大押搪，隨機(jī)訪問頻繁大州。
list不支持隨機(jī)存儲，適用于對象大垂谢，對象數(shù)量變化頻繁厦画，插入和刪除頻繁。
16. list自帶排序函數(shù)的排序原理
將前兩個元素合并滥朱，再將后兩個元素合并根暑，然后合并這兩個子序列成4個元素的子序列，重復(fù)這一過程徙邻，得到8個颇象，16個耍贾，...，子序列，最后得到的就是排序后的序列砂竖。
時間復(fù)雜度：O(nlgn)
17.說說deque的底層機(jī)制 ? STL之deque容器的實(shí)現(xiàn)框架 - CSDN博客
深入剖析deque容器實(shí)現(xiàn) - 綜合編程類其他綜合 - 紅黑聯(lián)盟
deque動態(tài)地以分段連續(xù)空間組合而成，隨時可以增加一段新的連續(xù)空間并鏈接起來脏款。不提供空間保留功能腺占。
注意：除非必要，我們盡可能選擇使用vector而非deque，因?yàn)閐eque的迭代器比vector迭代器復(fù)雜很多闰靴。對deque排序捆交，為了提高效率，可先將deque復(fù)制到一個vector上排序鲫趁，然后再復(fù)制回deque。
deque采用一塊map（不是STL的map容器）這個_Map是一個指針，指向一塊特殊的內(nèi)存地址役电，這里保存著指向deque動態(tài)申請的所有512字節(jié)內(nèi)存空間的首地址。作為中控器/ 中央控制器 /主控，其為一小塊連續(xù)空間，其中每個元素都是指針，指向另一段較大的連續(xù)空間（緩沖區(qū)）。
deque先用一段小的連續(xù)空間順序存放了一個一個指針砂吞，然后這些順序存放的指針再各自指向用來真正存放數(shù)據(jù)的512字節(jié)連續(xù)性空間。當(dāng)_Map指向的這塊空間不夠存放內(nèi)存指針的時候，就會另覓一塊更大的連續(xù)性空間（是map空間重新尋找胶惰，而不是緩沖區(qū)重新尋找），然后把指針一個一個復(fù)制過去尿赚，并銷毀舊的空間（銷毀的是原來的map空間）皿渗。利用這種數(shù)據(jù)結(jié)構(gòu)挤土，deque就能方便地模擬自身的存儲區(qū)是連續(xù)性空間的假象懦尝，并且可以實(shí)現(xiàn)雙向插入刪除的功能
deque 的迭代器
??讓我們思考一下甥绿，deque的迭代器應(yīng)該具備什么結(jié)構(gòu)字币，首先，它必須能夠指出分段連續(xù)空間（亦即緩沖區(qū)）在哪里共缕，其次它必須能夠判斷自己是否已經(jīng)處于其所在緩沖區(qū)的邊緣洗出，如果是，一旦前進(jìn)或后退就必須跳躍至下一個或上一個緩沖區(qū)图谷。為了能夠正確跳躍翩活，deque必須隨時掌握管控中心（map）。所以在迭代器中需要定義：當(dāng)前元素的指針cur便贵，當(dāng)前元素所在緩沖區(qū)的起始指針first菠镇，當(dāng)前元素所在緩沖區(qū)的尾指針last，指向map中指向所在緩區(qū)地址的指針node承璃， ?? 分別為cur, first, last, node辟犀。
deque的迭代器包含4個內(nèi)容：
1）cur：迭代器當(dāng)前所指元素
2）first：此迭代器所指的緩沖區(qū)的頭。
3）last：緩沖區(qū)尾绸硕。
4）node：指向管控中心堂竟。
deque迭代器失效的原因：
18. deque與vector的區(qū)別
1）vector是單向開口的連續(xù)線性空間，deque是雙向開口的連續(xù)線性空間熊杨。（雙向開口是指可以在頭尾兩端分別做元素的插入和刪除操作）曙旭。
2）deque沒有提供空間保留功能盗舰，而vector則要提供空間保留功能。
3）deque也提供隨機(jī)訪問迭代器桂躏，但是其迭代器比vector迭代器復(fù)雜很多钻趋。
19.不允許有遍歷行為的容器有哪些（不提供迭代器）？
1）queue剂习，除了頭部外蛮位，沒有其他方法存取deque的其他元素。
2）stack（底層以deque實(shí)現(xiàn)）鳞绕，除了最頂端外土至，沒有任何其他方法可以存取stack的其他元素。
3）heap猾昆，所有元素都必須遵循特別的排序規(guī)則陶因，不提供遍歷功能。
20.說說map底層機(jī)制
map以RB-TREE為底層機(jī)制垂蜗。RB-TREE是一種平衡二叉搜索樹楷扬，自動排序效果不錯。
通過map的迭代器不能修改其鍵值贴见，只能修改其實(shí)值烘苹。所以map的迭代器既不是const也不是mutable。
21.vector插入刪除和list有什么區(qū)別片部？
vector插入和刪除數(shù)據(jù)镣衡，需要對現(xiàn)有數(shù)據(jù)進(jìn)行復(fù)制移動，如果vector存儲的對象很大或者構(gòu)造函數(shù)很復(fù)雜档悠，則開銷較大廊鸥，如果是簡單的小數(shù)據(jù)，效率優(yōu)于list辖所。
list插入和刪除數(shù)據(jù)惰说，需要對現(xiàn)有數(shù)據(jù)進(jìn)行遍歷，但在首部插入數(shù)據(jù)缘回，效率很高吆视。
22.hashtable如何避免地址沖突？
1）線性探測：先用hash function計(jì)算某個元素的插入位置酥宴，如果該位置的空間已被占用啦吧，則繼續(xù)往下尋找，知道找到一個可用空間為止拙寡。
進(jìn)行元素搜索的時候授滓，如果hash function計(jì)算出來的位置上的元素值與我們搜尋目標(biāo)不符，就循環(huán)往下一一尋找，直到找到吻合者褒墨，或直到遇上空格元素。
其刪除采用惰性刪除：只標(biāo)記刪除記號擎宝，實(shí)際刪除操作等到表格重新整理時再進(jìn)行郁妈。（因?yàn)閔ash table中的每一個元素不僅表述它自己，也關(guān)系到其他元素的排列绍申。）
2）二次探測：如果計(jì)算出的位置為H且被占用噩咪，則依次嘗試H+1^2，H+2^2等（解決線性探測中主集團(tuán)問題）极阅。
3）開鏈：每一個哈希表元素中維護(hù)一個list鏈表胃碾，hash function為我們分配一個list，然后在那個list執(zhí)行插入筋搏、刪除等操作仆百。當(dāng)發(fā)生沖突時，該位置上的數(shù)據(jù)會用鏈表鏈起來奔脐，當(dāng)表中的某些位置沒有結(jié)點(diǎn)時俄周，該位置就為NULL！髓迎！這種方法在實(shí)現(xiàn)時就需要多加一個next指針峦朗，使這些結(jié)點(diǎn)才能鏈起來。
23. hashtable排龄，hash_set波势，hash_map的區(qū)別
hash_set以hashtable為底層，不具有排序功能橄维，能快速查找尺铣。其鍵值就是實(shí)值。（set以RB-TREE為底層争舞，具有排序功能迄埃。）
hash_map以以hashtable為底層，沒有自動排序功能兑障，能快速查找侄非，每一個元素同時擁有一個實(shí)值和鍵值。（map以RB-TREE為底層流译，具有排序功能逞怨。）
24 .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ù)量大小無關(guān)泳姐，屬于常數(shù)級別。而map的查找速度是logn級別暂吉。但不一定常數(shù)就比log小胖秒，而且hash_map還有hash function耗時。
如果考慮效率慕的，特別當(dāng)元素達(dá)到一定數(shù)量級時阎肝，用hash_map。
考慮內(nèi)存肮街，或者元素?cái)?shù)量較少時风题，用map。
25.紅黑樹有什么性質(zhì)嫉父？ ??紅黑樹(一)之 原理和算法詳細(xì)介紹 - 如果天空不死 - 博客園
1）每個結(jié)點(diǎn)是紅色或者黑色。
2）根結(jié)點(diǎn)為黑色赴恨。
3）葉結(jié)點(diǎn)為黑色的NULL結(jié)點(diǎn)疹娶。
4）如果結(jié)點(diǎn)為紅，其子節(jié)點(diǎn)必須為黑伦连。
5）任一結(jié)點(diǎn)到NULL的任何路徑雨饺，所含黑結(jié)點(diǎn)數(shù)必須相同。
紅黑樹的應(yīng)用比較廣泛惑淳，主要是用它來存儲有序的數(shù)據(jù)额港，它的時間復(fù)雜度是O(lgn)，效率非常之高歧焦。例如移斩，Java集合中的TreeSet和TreeMap，C++ STL中的set、map向瓷，以及Linux虛擬內(nèi)存的管理肠套，都是通過紅黑樹去實(shí)現(xiàn)的。
26.map和set的3個問題
1）為何map和set的插入刪除效率比其他序列容器高猖任。
因?yàn)椴恍枰獌?nèi)存拷貝和內(nèi)存移動
2）為何map和set每次Insert之后你稚，以前保存的iterator不會失效？
因?yàn)椴迦氩僮髦皇墙Y(jié)點(diǎn)指針換來換去超升，結(jié)點(diǎn)內(nèi)存沒有改變入宦。而iterator就像指向結(jié)點(diǎn)的指針哺徊，內(nèi)存沒變室琢，指向內(nèi)存的指針也不會變。
3）當(dāng)數(shù)據(jù)元素增多時（從10000到20000）落追，map和set的查找速度會怎樣變化盈滴？
RB-TREE用二分查找法，時間復(fù)雜度為logn轿钠，所以從10000增到20000時巢钓，查找次數(shù)從log10000=4次到log20000=5次，多了1次而已疗垛。
set常用方法：比如先創(chuàng)建 set<int> s
s.begin()???? ,返回set容器的第一個元素
s.end() ,返回set容器的最后一個元素
s.clear()?? ??? ?,刪除set容器中的所有的元素
s.empty() ,判斷set容器是否為空
s.max_size() ,返回set容器可能包含的元素最大個數(shù)
s.size() ,返回當(dāng)前set容器中的元素個數(shù)
s.rbegin ,返回的值和end()相同
s.rend() ,返回的值和rbegin()相同
map的相關(guān)操作 ： ?C/C++——map的基本操作總結(jié) - CSDN博客
27.vector中begin和end函數(shù)返回的是什么症汹？
begin返回的是第一個元素的迭代器，end返回的是最后一個元素后面位置的迭代器贷腕。
28.為什么vector的插入操作可能會導(dǎo)致迭代器失效背镇？
vector動態(tài)增加大小時，并不是在原空間后增加新的空間泽裳，而是以原大小的兩倍在另外配置一片較大的新空間瞒斩，然后將內(nèi)容拷貝過來，并釋放原來的空間涮总。由于操作改變了空間胸囱，所以迭代器失效。
29.vector瀑梗、list烹笔、map、deque用erase（it）后抛丽，迭代器的變化
vector和deque是序列式容器箕宙，其內(nèi)存分別是連續(xù)空間和分段連續(xù)空間，刪除迭代器it后铺纽，其后面的迭代器都失效了柬帕，此時it及其后面的迭代器會自動加1，使it指向被刪除元素的下一個元素。
list刪除迭代器it時陷寝，其后面的迭代器都不會失效锅很，將前面和后面連接起來即可。
map也是只能使當(dāng)前刪除的迭代器失效凤跑，其后面的迭代器依然有效爆安。
30. hashtable和hashmap的區(qū)別
hashmap以hashtable為底層。主要有以下幾點(diǎn)不同：
1）hashtable是Dictionary的子類仔引，而hashmap是Map接口的一個實(shí)現(xiàn)類扔仓。
2）hashtable中的方法是同步的，而hashmap的方法不同步咖耘。
重點(diǎn)說 ? hashtable：
哈希表（hash table, 也叫散列表）翘簇，是種根據(jù)關(guān)鍵字(Key value)而直接進(jìn)行訪問數(shù)據(jù)結(jié)構(gòu)，它可以提供快速的插入操作和查找操作儿倒。也就是說版保，它通過把關(guān)鍵字值映射到一個位置來訪問記錄，以加快查找的速度夫否。這個映射函數(shù)稱為哈希函數(shù)（也稱為散列函數(shù)）彻犁，映射過程稱為哈希化凰慈，存放記錄的數(shù)組叫做哈希表（散列表）汞幢。哈希表最大的優(yōu)點(diǎn)，就是把數(shù)據(jù)的存儲和查找消耗的時間大大降低微谓，幾乎可以看成是常數(shù)時間森篷；而代價僅僅是消耗比較多的內(nèi)存。
哈希函數(shù)構(gòu)造
當(dāng)需要使用一個下標(biāo)范圍比較大的數(shù)組來存儲元素時堰酿，可以設(shè)計(jì)一個函數(shù)（哈希函數(shù)疾宏， 也叫做散列函數(shù)），使得每個元素的關(guān)鍵字都與一個函數(shù)值（即數(shù)組下標(biāo)）相對應(yīng)触创，于是用這個數(shù)組單元來存儲這個元素坎藐。也可以簡單的理解為，按照關(guān)鍵字為每一 個元素“分類”哼绑，然后將這個元素存儲在相應(yīng)“類”所對應(yīng)的地方岩馍。點(diǎn)擊打開鏈接
Hashtable底層實(shí)現(xiàn)是通過開鏈法來實(shí)現(xiàn)的，hash table表格內(nèi)的元素稱為桶（bucket),而由桶所鏈接的元素稱為節(jié)點(diǎn)（node),其中保存桶元素的容器為vector容器抖韩。之所以選擇vector為存放桶元素的基礎(chǔ)容器蛀恩，主要是因?yàn)関ector容器本身具有動態(tài)擴(kuò)容能力，無需人工干預(yù)茂浮。而節(jié)點(diǎn)元素為自定義的結(jié)構(gòu)體：
可以看到双谆，這本身就是一種很典型的鏈?zhǔn)搅斜碓氐谋硎痉椒枪荆ㄟ^當(dāng)前節(jié)點(diǎn)，我們可以很方便地通過節(jié)點(diǎn)自身的next指針來獲取下一鏈接節(jié)點(diǎn)元素顽馋。
無序容器在存儲上組織為一組桶谓厘，每個桶保存0個或多個元素。無序容器使用一個哈希函數(shù)將元素映射到桶寸谜。為了訪問一個元素竟稳，（1）容器首先計(jì)算元素的哈希值， 它指出應(yīng)該搜索哪個桶熊痴；（2）容器將具有一個特定哈希值的所有元素都保存在相同的桶中他爸；因此，無序容器的性能依賴于哈希函數(shù)的質(zhì)量和桶數(shù)量和大小果善。
實(shí)際工作中需視不同情況采用不同的哈希函數(shù)诊笤，通常，考慮的因素有：
（1）計(jì)算哈希函數(shù)所需時間（包括硬件指令的因素）岭埠；
（2）關(guān)鍵字的長度盏混；
（3）哈希表的大形蹬浮惜论；
（4）關(guān)鍵字的分布情況；
（5）記錄的查找頻率止喷。
31. priority_queue
priority_queue優(yōu)先級隊(duì)列相當(dāng)于一個有權(quán)值的單向隊(duì)列queue馆类，在這個隊(duì)列中，所有元素是按照優(yōu)先級排列的弹谁。
priority_queue根據(jù)堆的處理規(guī)則來調(diào)整元素之間的位置乾巧，關(guān)于堆的原理，可以參考堆预愤；
根據(jù)堆的特性沟于，優(yōu)先級隊(duì)列實(shí)現(xiàn)了取出最大最小元素時間復(fù)雜度為O(1),? 對于插入和刪除，其最壞情況為O(lgn)植康。
32.STL 空間配置器 allocator?
為什么要有空間配置器呢旷太？這主要是從兩個方面來考慮的。
1销睁、小塊內(nèi)存帶來的內(nèi)存碎片問題
單從分配的角度來看供璧。由于頻繁分配、釋放小塊內(nèi)存容易在堆中造成外碎片(極端情況下就是堆中空閑的內(nèi)存總量滿足一個請求冻记，但是這些空閑的塊都不連續(xù)睡毒，導(dǎo)致任何一個單獨(dú)的空閑的塊都無法滿足這個請求)。
2冗栗、小塊內(nèi)存頻繁申請釋放帶來的性能問題演顾。
? 開辟空間的時候供搀，分配器會去找一塊空閑塊給用戶，找空閑塊也是需要時間的钠至，尤其是在外碎片比較多的情況下趁曼。如果分配器其找不到，就要考慮處理假碎片現(xiàn)象(釋放的小塊空間沒有合并)棕洋，這時候就要將這些已經(jīng)釋放的的空閑塊進(jìn)行合并挡闰，這也是需要時間的。 malloc在開辟空間的時候掰盘，這些空間會帶有一些附加的信息摄悯，這樣的話也就造成了空間的利用率有所降低，尤其是在頻繁申請小塊內(nèi)存的時候愧捕。
內(nèi)存池的概念
為了解決上面這些問題奢驯，所以就提出有了內(nèi)存池的概念。內(nèi)存池最基本的思想就是一次向heap申請一塊很大的內(nèi)存(內(nèi)存池)次绘，如果申請小塊內(nèi)存的話就直接到內(nèi)存池中去要瘪阁。這樣的話，就能夠有效的解決上面所提到的問題邮偎。
下面剖析一下STL里面的空間配置器(SGI版)
STL里面的空間配置主要分為兩級管跺，一級空間配置器(__malloc_alloc_template)和二級空間配置器(__default_alloc_template)。在STL中默認(rèn)如果要分配的內(nèi)存大于128個字節(jié)的話就是大塊內(nèi)存禾进，調(diào)用一級空間配置器直接向系統(tǒng)申請豁跑，如果小于等于128個字節(jié)的話則認(rèn)為是小內(nèi)存，則就去內(nèi)存池中申請泻云。
（1）一級空間配置器很簡單艇拍，直接封裝了malloc和free處理，增加_malloc_alloc_oom_handle處理機(jī)制宠纯。
（2）二級空間配置器才是STL的精華卸夕，二級空間配置器主要由? 內(nèi)存池+自由鏈表 ? 構(gòu)成。
? 二級空間配置器使用內(nèi)存池+自由鏈表的形式避免了小塊內(nèi)存帶來的碎片化婆瓜，提高了分配的效率快集，提高了利用率。SGI的做法是先判斷要開辟的大小是不是大于128勃救，如果大于128則就認(rèn)為是一塊大塊內(nèi)存碍讨，調(diào)用一級空間配置器直接分配。否則的話就通過內(nèi)存池來分配蒙秒，假設(shè)要分配8個字節(jié)大小的空間勃黍，那么他就會去內(nèi)存池中分配多個8個字節(jié)大小的內(nèi)存塊，將多余的掛在自由鏈表上晕讲，下一次再需要8個字節(jié)時就去自由鏈表上取就可以了覆获，如果回收這8個字節(jié)的話马澈，直接將它掛在自由鏈表上就可以了。
?為了便于管理弄息，二級空間配置器在分配的時候都是以8的倍數(shù)對齊痊班。也就是說二級配置器會將任何小塊內(nèi)存的需求上調(diào)到8的倍數(shù)處(例如：要7個字節(jié)，會給你分配8個字節(jié)摹量。要9個字節(jié)涤伐，會給你16個字節(jié)),盡管這樣做有內(nèi)碎片的問題，但是對于我們管理來說卻簡單了不少缨称。因?yàn)檫@樣的話只要維護(hù)16個free_list就可以了凝果，free_list這16個結(jié)點(diǎn)分別管理大小為8,16,24,32,40,48,56,64,72,80,88,86,96,104,112,120,128字節(jié)大小的內(nèi)存塊就行了。
