STL知識點總結

一、STL有哪些組件
STL提供六大組件，彼此可以組合套用：
1、容器
容器就是各種數據結構，我就不多說，看看下面這張圖回憶一下就好了，從實現角度看，STL容器是一種class template。

2、算法
各種常見算法，如sort，search，copy，erase等，我覺得其中比較值得學習的就是sort，next_permutation，partition，merge sort，從實現角度看，STL算法是一種function template。
3、迭代器
扮演容器與算法之間的膠合劑，是所謂的“泛型指針”。共有五種類型，從實現角度看，迭代器是一種將operator*，operator->，operator++，operator--等指針相關操作予以重載的class template。所有STL容器都附帶有自己專屬的迭代器，只有容器設計者才知道如何設計迭代器。原生指針也是一種迭代器。是設計模式的一種，所以被問到了解的設計模式可以用來湊數。
4、仿函數
行為類函數，可作為算法的某種策略，從實現角度看，仿函數是一種重載了operator()的class或class template。一般函數指針可視為狹義的仿函數。
5、容器配接器
一種用來修飾容器或者仿函數或迭代器接口的東西。比如queue和stack，看著像容器，其實就是deque包了一層皮。
6、空間配置器
負責空間配置與管理。從實現角度看，配置器是一個實現了動態空間配置、空間管理、空間釋放額class template。

二、STL常用的容器有哪些以及各自的特點是什么
1.vector:底層數據結構為數組 ，支持快速隨機訪問。
2.list:底層數據結構為雙向鏈表，支持快速增刪。
3.deque:底層數據結構為一個中央控制器和多個緩沖區，詳細見STL源碼剖析P146，支持首尾（中間不能）快速增刪，也支持隨機訪問。
4.stack:底層一般用23實現，封閉頭部即可，不用vector的原因應該是容量大小有限制，擴容耗時
5.queue:底層一般用23實現，封閉頭部即可，不用vector的原因應該是容量大小有限制，擴容耗時（stack和queue其實是適配器,而不叫容器，因為是對容器的再封裝）
6.priority_queue:的底層數據結構一般為vector為底層容器，堆heap為處理規則來管理底層容器實現
7.set:底層數據結構為紅黑樹，有序，不重復。
8.multiset:底層數據結構為紅黑樹，有序，可重復。?
9.map:底層數據結構為紅黑樹，有序，不重復。
10.multimap:底層數據結構為紅黑樹，有序，可重復。
11.hash_set:????底層數據結構為hash表，無序，不重復。
12.hash_multiset:底層數據結構為hash表，無序，可重復 。
13.hash_map :????底層數據結構為hash表，無序，不重復。
14.hash_multimap:底層數據結構為hash表，無序，可重復。?

三、說說std::vector的底層（存儲）機制。
? vector就是一個動態數組，里面有一個指針指向一片連續的內存空間，當空間不夠裝下數據時，會自動申請另一片更大的空間（一般是增加當前容量的50%或100%），然后把原來的數據拷貝過去，接著釋放原來的那片空間；當釋放或者刪除里面的數據時，其存儲空間不釋放，僅僅是清空了里面的數據。

四、vector插入刪除和list有什么區別？
vector插入和刪除數據，需要對現有數據進行復制移動，如果vector存儲的對象很大或者構造函數很復雜，則開銷較大，如果是簡單的小數據，效率優于list。
list插入和刪除數據，需要對現有數據進行遍歷，但在首部插入數據，效率很高。

五、什么情況下用vector，什么情況下用list。
vector可以隨機存儲元素（即可以通過公式直接計算出元素地址，而不需要挨個查找），但在非尾部插入刪除數據時，效率很低，適合對象簡單，對象數量變化不大，隨機訪問頻繁。
list不支持隨機存儲，適用于對象大，對象數量變化頻繁，插入和刪除頻繁。

六、vector中begin和end函數返回的是什么？
begin返回的是第一個元素的迭代器，end返回的是最后一個元素后面位置的迭代器。

七、為什么vector的插入操作可能會導致迭代器失效？
vector動態增加大小時，并不是在原空間后增加新的空間，而是以原大小的兩倍在另外配置一片較大的新空間，然后將內容拷貝過來，并釋放原來的空間。由于操作改變了空間，所以迭代器失效。
八、說說std::list的底層（存儲）機制。
以結點為單位存放數據，結點的地址在內存中不一定連續，每次插入或刪除一個元素，就配置或釋放一個元素空間

九、list自帶排序函數的排序原理。
將前兩個元素合并，再將后兩個元素合并，然后合并這兩個子序列成4個元素的子序列，重復這一過程，得到8個，16個，...，子序列，最后得到的就是排序后的序列。
時間復雜度：O(nlgn)
void List::sort()
{
List carry;
List counter[64]; //數組元素為鏈表
int fill = 0;
while (head->next != tail)
{
//head是哨兵，不存放有效值
//head->next元素被移走，所以while循環不需要head=head->next;
carry.transfer(carry.getHead()->next, head->next, head->next->next);

    int i = 0;
    while (i < fill && counter[i].getHead()->next != counter[i].getHead())

//counter[i]不是空
{
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if (i == fill) ++fill;
}
for (int i = 1; i < fill; i++)
counter[i].merge(counter[i - 1]);
//通過這個實現排序（將有序的鏈表合成一個新的有序鏈表）
swap(counter[fill - 1]);
}

十、deque與vector的區別。
1）vector是單向開口的連續線性空間，deque是雙向開口的連續線性空間。（雙向開口是指可以在頭尾兩端分別做元素的插入和刪除操作）。
2）deque沒有提供空間保留功能，而vector則要提供空間保留功能。
3）deque也提供隨機訪問迭代器，但是其迭代器比vector迭代器復雜很多。

十一、不允許有遍歷行為的容器有哪些（不提供迭代器）？
1）queue，除了頭部外，沒有其他方法存取deque的其他元素。
2）stack（底層以deque實現），除了最頂端外，沒有任何其他方法可以存取stack的其他元素。
3）heap，所有元素都必須遵循特別的排序規則，不提供遍歷功能。

十二、STL容器的參數allocate是用來做什么的？
一般用在容器中，作為容器的一個成員，但一般是用模版參數傳入，這樣才可以讓我們換成我們自定義的allocator；分配器用于封裝STL容器在內存管理上的低層細節

十三、你怎樣理解迭代器？
Iterator(迭代器)用于提供一種方法順序訪問一個聚合對象中各個元素, 而又不需暴露該對象的內部表示，相當于智能指針。包括Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, Random Access Iterator.

十四、 vector每次insert或erase之后，以前保存的iterator會不會失效？
理論上會失效，理論上每次insert或者erase之后，所有的迭代器就重新計算的，所以都可以看作會失效，原則上是不能使用過期的內存
但是vector一般底層是用數組實現的，我們仔細考慮數組的特性，不難得出另一個結論，
insert時，假設insert位置在p，分兩種情況：
a) 容器還有空余空間，不重新分配內存，那么p之前的迭代器都有效，p之后的迭
代器都失效
b) 容器重新分配了內存，那么p之后的迭代器都無效咯
erase時，假設erase位置在p，則p之前的迭代器都有效并且p指向下一個元素位置（如果之前p在尾巴上，則p指向無效尾end），p之后的迭代器都無效

十五、STL對于小內存塊請求與釋放的處理
STL考慮到小型內存區塊的碎片問題，設計了雙層級配置器，第一級配置直接使用malloc()和free()；第二級配置器則視情況采用不同的策略，當配置區大于128bytes時，直接調用第一級配置器；當配置區塊小于128bytes時，便不借助第一級配置器，而使用一個memory pool來實現。究竟是使用第一級配置器還是第二級配置器，由一個宏定義來控制。SGI STL中默認使用第二級配置器。
二級配置器會將任何小額區塊的內存需求量上調至8的倍數，(例如需求是30bytes,則自動調整為32bytes)，并且在它內部會維護16個free-list， 各自管理大小分別為8， 16， 24，…，128bytes的小額區塊，這樣當有小額內存配置需求時，直接從對應的free list中拔出對應大小的內存(8的倍數)；當客戶端歸還內存時，將根據歸還內存塊的大小，將需要歸還的內存插入到對應free list的最頂端。
小結：
STL中的內存分配器實際上是基于空閑列表(free list)的分配策略，最主要的特點是通過組織16個空閑列表，對小對象的分配做了優化。
1）小對象的快速分配和釋放。當一次性預先分配好一塊固定大小的內存池后，對小于128字節的小塊內存分配和釋放的操作只是一些基本的指針操作，相比于直接調用malloc/free，開銷小。
2）避免內存碎片的產生。零亂的內存碎片不僅會浪費內存空間，而且會給OS的內存管理造成壓力。
3）盡可能最大化內存的利用率。當內存池尚有的空閑區域不足以分配所需的大小時，分配算法會將其鏈入到對應的空閑列表中，然后會嘗試從空閑列表中尋找是否有合適大小的區域，
但是，這種內存分配器局限于STL容器中使用，并不適合一個通用的內存分配。因為它要求在釋放一個內存塊時，必須提供這個內存塊的大小，以便確定回收到哪個free list中，而STL容器是知道它所需分配的對象大小的，比如上述：
stl::vector?array;
array是知道它需要分配的對象大小為sizeof(int)。一個通用的內存分配器是不需要知道待釋放內存的大小的，類似于free(p)。

十六、vector和list的區別
vector和數組類似，擁有連續的內存空間，支持隨機的存取，在中間進行元素的插入和刪除的操作時間復雜度是O(n)
list是由雙向鏈表實現的，只能通過數組指針來進行數據訪問，遍歷中間的元素，時間的復雜度是O(n).

十七、vector中erase方法與algorithn中的remove方法區別
vector中erase方法真正刪除了元素，迭代器不能訪問了
remove只是簡單地將元素移到了容器的最后面，迭代器還是可以訪問到。因為algorithm通過迭代器進行操作，不知道容器的內部結構，所以無法進行真正的刪除。

十八、STL中的容器都有哪些，優缺點？
介紹一下STL，詳細說明STL如何實現vector。
STL(標準模板庫)可分為容器(containers)、迭代器(iterators)、空間配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函數(functors)六個部分。
STL (標準模版庫，Standard Template Library.它由容器、算法、迭代器組成。
STL有以下的一些優點：
可以方便容易地實現搜索數據或對數據排序等一系列的算法；
調試程序時更加安全和方便；
即使是人們用STL在UNIX平臺下寫的代碼你也可以很容易地理解（因為STL是跨平臺的）。
vector實質上就是一個動態數組，會根據數據的增加,動態的增加數組空間。
deque從邏輯上來看是連續的內存，本質上是由一段段固定大小 的連續空間組成。deque采用類似索引的結構管理內存。vector有capacity和reserve函數，deque和list一樣，沒有capacity和reserve函數。
總結如下：?

1. 在deque中間 插入或者刪除將使所有deque元素的迭代器、引用、指針失效?
2. 在deque首部或者尾部插入元素會使迭代器失效，但不會引起引用和指針失效?
3. 在其首部或尾部刪除元素則只會使指向被刪除元素的迭代器失效
   vector模板的數據在內存中連續的排列，所以隨機存取元素（即通過[]運算符存取）的速度最快，這一點和數組是一致的。同樣由于它的連續排列，所以它在除尾部以外的位置刪除或添加元素的速度很慢，在使用vector時，要避免這種操作。
   list模板的數據是鏈式存儲，所以不能隨機存取元素。它的優勢在于任意位置添加 刪除元素的速度。
   deque模板是通過鏈接若干片連續的數據實現的，所以均衡了以上兩個容器的特點

十九、說說std::deque的底層機制。
deque動態地以分段連續空間組合而成，隨時可以增加一段新的連續空間并鏈接起來。不提供空間保留功能。
注意：除非必要，我們盡可能選擇使用vector而非deque，因為deque的迭代器比vector迭代器復雜很多。對deque排序，為了提高效率，可先將deque復制到一個vector上排序，然后再復制回deque。
deque采用一塊map（不是STL的map容器）作為主控，其為一小塊連續空間，其中每個元素都是指針，指向另一段較大的連續空間（緩沖區）。
deque的迭代器包含4個內容：
1）cur：迭代器當前所指元素
2）first：此迭代器所指的緩沖區的頭。
3）last：緩沖區尾。
4）node：指向管控中心。

二十、說說std::map底層機制。
map以RB-TREE為底層機制。RB-TREE是一種平衡二叉搜索樹，自動排序效果不錯。
通過map的迭代器不能修改其鍵值，只能修改其實值。所以map的迭代器既不是const也不是mutable。

二十一、紅黑樹有什么性質？
1）每個結點是紅色或者黑色。
2）根結點為黑色。
3）葉結點為黑色的NULL結點。
4）如果結點為紅，其子節點必須為黑。
5）任一結點到NULL的任何路徑，所含黑結點數必須相同。

二十二、vector、list、map、deque用erase（it）后，迭代器的變化。
vector和deque是序列式容器，其內存分別是連續空間和分段連續空間，刪除迭代器it后，其后面的迭代器都失效了，此時it及其后面的迭代器會自動加1，使it指向被刪除元素的下一個元素。
list刪除迭代器it時，其后面的迭代器都不會失效，將前面和后面連接起來即可。
map也是只能使當前刪除的迭代器失效，其后面的迭代器依然有效。

二十三、hash_map與map的區別？什么時候用hash_map，什么時候用map？
構造函數：hash_map需要hash function和等于函數，而map需要比較函數（大于或小于）。
存儲結構：hash_map以hashtable為底層，而map以RB-TREE為底層。?
總的說來，hash_map查找速度比map快，而且查找速度基本和數據量大小無關，屬于常數級別。而map的查找速度是logn級別。但不一定常數就比log小，而且hash_map還有hash function耗時。
如果考慮效率，特別當元素達到一定數量級時，用hash_map。
考慮內存，或者元素數量較少時，用map。

二十四、hashtable，hash_set，hash_map的區別。
hash_set以hashtable為底層，不具有排序功能，能快速查找。其鍵值就是實值。（set以RB-TREE為底層，具有排序功能。）
hash_map以以hashtable為底層，沒有自動排序功能，能快速查找，每一個元素同時擁有一個實值和鍵值。（map以RB-TREE為底層，具有排序功能。）

二十五、map和set的3個問題。
1）為何map和set的插入刪除效率比其他序列容器高。
因為不需要內存拷貝和內存移動
2）為何map和set每次Insert之后，以前保存的iterator不會失效？
因為插入操作只是結點指針換來換去，結點內存沒有改變。而iterator就像指向結點的指針，內存沒變，指向內存的指針也不會變。
2）當數據元素增多時（從10000到20000），map的set的查找速度會怎樣變化？
RB-TREE用二分查找法，時間復雜度為logn，所以從10000增到20000時，查找次數從log10000=14次到log20000=15次，多了1次而已。

二十六、map是怎么實現的？查找的復雜度是多少？能不能邊遍歷邊插入？
紅黑樹和散列
O(logn)
不可以，map不像vector，它在對容器執行erase操作后不會返回后一個元素的迭代器，所以不能遍歷地往后刪除。

二十七、hash_map和map的區別在哪里？
hash_map底層是散列的所以理論上操作的平均復雜度是常數時間，map底層是紅黑樹，理論上平均復雜度是O(logn)，這里總結一下，選用map還是hash_map，關鍵是看關鍵字查詢操作次數，以及你所需要保證的是查詢總體時間還是單個查詢的時間。如果是要很多次操作，要求其整體效率，那么使用hash_map，平均處理時間短。如果是少數次的操作，使用 hash_map可能造成不確定的O(N)，那么使用平均處理時間相對較慢、單次處理時間恒定的map，考慮整體穩定性應該要高于整體效率，因為前提在操作次數較少。如果在一次流程中，使用hash_map的少數操作產生一個最壞情況O(N)，那么hash_map的優勢也因此喪盡了。

二十八、為何map和set不能像vector一樣有個reserve函數來預分配數據？
map和set內部存儲的已經不是元素本身了，而是包含元素的節點。也就是說map內部使用的Alloc并不是map聲明的時候從參數中傳入的Alloc。例如：
map, Alloc?> intmap;
這時候在intmap中使用的allocator并不是Alloc, 而是通過了轉換的Alloc，具體轉換的方法時在內部通過
Alloc::rebind重新定義了新的節點分配器，詳細的實現參看徹底學習STL中的Allocator。
其實你就記住一點，在map和set里面的分配器已經發生了變化，reserve方法你就不要奢望了。