這周終于可以給大家把STL方面的面試題總結出來了，突然發現它里面的細節非常多，只有你想不到的，沒有它沒有的。對于C++程序員來說，STL庫里面的知識也是非常重要的，只要想在技術這條路線上有長遠的發展，那么就一定要掌握它。不管是學習中，面試中，工作中，它都有不可估量的地位。

之前有寫過一片關于STL庫的文章，現在來看確實也是非常有用的知識點。

這篇文章主要是講解在面試過程中遇到的一些面試題，細節很多，量也很大，大家在看的時候，不僅僅只是看一遍而已，還要多了解背后的原理，在不懂的時候，還是需要看看相關權威書籍。

STL篇

1、講講STL的六大組件

1. 容器（Containers）：各種數據結構，如Vector,List,Deque,Set,Map,用來存放數據，STL容器是一種Class Template,就體積而言，這一部分很像冰山載海面的比率。
2. 算法（Algorithms）：各種常用算法如Sort,Search,Copy,Erase,從實現的角度來看，STL算法是一種Function Templates。
3. 迭代器（Iterators）：扮演容器與算法之間的膠合劑，是所謂的“泛型指針”，共有五種類型，以及其它衍生變化，從實現的角度來看，迭代器是一種將：Operators*,Operator->,Operator++,Operator--等相關操作予以重載的Class Template。所有STL容器都附帶有自己專屬的迭代器——是的，只有容器設計者才知道如何遍歷自己的元素，原生指針（Native pointer）也是一種迭代器。
4. 仿函數（Functors）：行為類似函數，可作為算法的某種策略（Policy）,從實現的角度來看，仿函數是一種重載了Operator()的Class 或 Class Template。一般函數指針可視為狹義的仿函數。
5. 適配器（配接器）（Adapters）：一種用來修飾容器（Containers）或仿函數（Functors）或迭代器（Iterators）接口的東西，例如：STL提供的Queue和Stack，雖然看似容器，其實只能算是一種容器配接器，因為 它們的底部完全借助Deque，所有操作有底層的Deque供應。改變Functor接口者，稱為Function Adapter;改變Container接口者，稱為Container Adapter;改變Iterator接口者，稱為Iterator Adapter。配接器的實現技術很難一言蔽之，必須逐一分析。
6. 分配器（Allocators）：負責空間配置與管理，從實現的角度來看，配置器是一個實現了動態空間配置、空間管理、空間釋放的Class Template。

2、簡單說說vector

動態開辟的二維數組。元素在內存連續存放。隨機存取任何元素都能在常數時間完成。在尾端增刪元素具有較佳的性能。

3、vector底層原理

• 數據安排及操作方式與array非常相似。兩者的唯一差別在于空間運用的靈活性。
• 靜態空間，一旦配置好了就不能改變了，如果程序需要一個更大的array，只能自己再申請一個更大的array，然后將以前的array中的內容全部拷貝到新的array中。
• 動態開辟的空間，隨著元素的加入，它的內部機制會自動擴充空間以容納新的元素。vector的關鍵技術在于對大小的控制以及重新分配時的數據移動效率。
• 采用的數據結構是線性的連續空間（泛型的動態類型順序表），他以兩個迭代器start和finish分別指向配置得來的連續空間中目前已將被使用的空間。迭代器end_of_storage指向整個連續的尾部。
• 在增加元素時，如果超過自身最大的容量，vector則將自身的容量擴充為原來的兩倍。擴充空間需要經過的步驟：重新配置空間，元素移動，釋放舊的內存空間。一旦vector空間重新配置，則指向原來vector的所有迭代器都失效了，因為vector的地址改變了。

4、vector為什么要用加倍擴容而不是每次增加一個固定的擴容容量

• vector在push_back以成倍增長可以在均攤后達到O(1)的事件復雜度，相對于增長指定大小的O(n)時間復雜度更好。
• 為了防止申請內存的浪費，現在使用較多的有2倍與1.5倍的增長方式，而1.5倍的增長方式可以更好的實現對內存的重復利用。

5、vector擴容的過程

• 完全棄用現有的內存空間，重新申請更大的內存空間；
• 將舊內存空間中的數據，按原有順序移動到新的內存空間中；
• 最后將舊的內存空間釋放。

6、vector的擴容方式為什么是1.5倍或2倍

• 假如說我們是以2倍方式擴容（1，2，4，8，16），則第i次擴容期間所需要的空間總量就是2^i次方，如果第4次擴容時總共需要8個元素大小的空間，但是前3次已經釋放的空間加起來的總量，剛好是7，而7小于8，不足以我們第4次擴容時所需要的空間，也就是說，如果恰巧以2倍方式擴容，那么每次擴容時前面釋放的空間它都不足以支持本次的擴容！！！那么如果是以更高倍數的方式進行擴容，則這個空間它的浪費情況就會更高！！！也就是說，以2倍或者更高倍數的方式進行擴容，會存在2個問題：
  • 空間浪費可能比較大
  • 無法使用前面已經釋放的空間
• STL標準沒有嚴格說明我們應該按照哪一種方式進行擴容，因此不同STL的實現廠商都是按照自己的方式進行擴容的。
• 一般情況下，在Windows的VS系列編譯器下，是按照1.5倍的方式進行擴容，在Linux的g++中，是按照2倍的方式進行擴容的。

7、size、resize、reserve、capacity的區別

• size表示當前vector中有多少個元素（即finish – start）；當前容器所存儲的個數，
• resize可以改變有效空間的大小，也有改變默認值的功能。capacity的大小也會隨著改變。可以有多個參數。創建指定數量的元素并指定vector的存儲空間。既分配空間又創建對象。
• reserve是直接擴充到已經確定的大小，可以減少多次開辟、釋放空間的問題（優化push_back），從而達到提高效率的目的，其次還可以減少多次要拷貝數據的問題。reserve它只是保證vector中的空間大小（capacity）最少達到參數所指定的大小n。并且它只有一個參數。指定vector的元素總數，不創建對象。
• capacity函數表示它已經分配的內存中可以容納多少元素（即end_of_storage – start）。即容器在分配新的存儲空間能存儲的元素總數。返回vector中能存儲元素的最大數。

8、vector迭代器失效問題

迭代器的主要作用就是讓算法能夠不用關心底層數據結構，其底層實際就是一個指針，或者是對指針進行了 封裝，比如：vector的迭代器就是原生態指針T*。因此迭代器失效，實際就是迭代器底層對應指針所指向的 空間被銷毀了，而使用一塊已經被釋放的空間，造成的后果是程序崩潰(即如果繼續使用已經失效的迭代器， 程序可能會崩潰)。

9、對于vector可能導致其迭代器失效的操作有哪些

• resize、reserve、insert、assign、push_back等會引起其底層空間改變的操作，都有可能使迭代器失效。

• 指定位置元素的刪除操作--erase

  #include 
  using namespace std;
  #include 
  int main()
  {
      int a[] = { 1, 2, 3, 4 };
      vector<int> v(a, a + sizeof(a) / sizeof(int));
      // 使用find查找3所在位置的iterator
      vector<int>::iterator pos = find(v.begin(), v.end(), 3);
      // 刪除pos位置的數據，導致pos迭代器失效。
      v.erase(pos);
      cout << *pos << endl; // 此處會導致非法訪問
      return 0;
  }
  

erase刪除pos位置元素后，pos位置之后的元素會往前移動，沒有導致底層空間的改變，理論上講迭代器應該不會失效，但是如果pos剛好是最后一個元素，刪完之后pos剛好是end位置，而end位置是沒有元素的，那么pos就失效了。所以刪除vector中任意位置上元素時，vs就認為該位置迭代器失效了。

10、push_back和emplace_back的區別

emplace_back() 和 push_back() 的主要區別，就在于底層實現的機制不同。push_back() 向容器尾部添加元素時，首先會創建這個元素，然后再將這個元素拷貝或者移動到容器中（如果是拷貝的話，事后會自行銷毀先前創建的這個元素）；而 emplace_back() 在實現時，則是直接在容器尾部創建這個元素，省去了拷貝或移動元素的過程。

11、聊聊STL庫中的list

• list 是順序容器的一種。list 是一個雙向鏈表。使用 list 需要包含頭文件 list。雙向鏈表的每個元素中都有一個指針指向后一個元素，也有一個指針指向前一個元素。
• 在 list 容器中，在已經定位到要增刪元素的位置的情況下，增刪元素能在常數時間內完成。
• list不支持根據下標隨機存取元素。
• 在任何位置都能高效地插入和刪除元素，只要改變元素的指針值，不需要拷貝元素。

12、list的底層原理

• list的底層是一個 雙向鏈表 ，以結點為單位存放數據，結點的地址在內存中不一定連續，每次插入或刪除一個元素，就配置或釋放一個元素空間。
• 和vector容器迭代器的實現方式不同，由于 list 容器的元素并不是連續存儲的，所以該容器迭代器中，必須包含一個可以指向 list 容器的指針，并且該指針還可以借助重載的 *、++、--、==、!= 等運算符，實現迭代器正確的遞增、遞減、取值等操作。

13、list的常用函數

list.push_back(elem)    在尾部加入一個數據
list.pop_back()         刪除尾部數據
list.push_front(elem)   在頭部插入一個數據
list.pop_front()        刪除頭部數據
list.size()             返回容器中實際數據的個數
list.sort()             排序，默認由小到大 
list.unique()           移除數值相同的連續元素
list.back()             取尾部迭代器
list.erase(iterator)    刪除一個元素，參數是迭代器，返回的是刪除迭代器的下一個位置

14、vector插入、list插入問題

• vector中插入大量連續的數據時，如果預知數據量大小，可以通過resize來調整原先vector的空間大小，同時利用賦值“=”，可以減少耗時。
• list可以通過遍歷list然后insert插入，但還可以通過成員方法splice來進行插入，且效率較高，耗時較少。

15、vector和list的優缺點

1. vector的優點

• 下標隨機訪問

vector的底層是一段連續的物理空間，所以支持隨機訪問。

• 尾插尾刪效率高
  跟數組類似，我們能夠很輕易的找到最后一個元素，并完成各種操作。
• cpu高速緩存命中率高
  因為系統在底層拿空間的時候，是拿一段進cpu，不是只拿單獨一個，會提前往后多拿一點，vector的物理地址是連續的，所以我們再拿到數據的時候，cpu訪問后面的數據會更快。

2. vector的缺點

• 前面部分的插入刪除數據效率低
  如果我們要在前面或中間插入或者刪除數據，我們不能直接刪，我們需要挪動數據，去覆蓋或者增加一段空間，這樣我們挪動數據的效率就是O(N)。
• 擴容有消耗，可能存在一定的空間浪費
  正常情況下我們vector的擴容機制是一旦達到當前空間的capacity(容量)那么我們擴容原空間的1.5倍或者2倍數(vs一般是1.5倍而g++是2倍)，這樣擴容就有可能導致空間浪費，而且頻繁擴容也會影響效率。

3. list的優點

• 按需申請釋放，不需要擴容
  list是一個帶頭雙向循環鏈表，那么鏈表就是一個個獨立的空間鏈接起的，需要多少，就new多少，不存在空間浪費。
• 任意位置的插入刪除效率高（對比vector）
  因為list是雙向循環鏈表，我們需要插入新的元素只需要改變原數據的next和prev，所以我們的插入刪除效率是O(1)。

4. list的缺點

• 不支持下標隨機訪問
  因為list是鏈表，在存放數據的物理地址并不是連續的，所以我們也就不能支持隨機訪問。
• CPU高速緩存命中率低
  主要還是跟它的物理地址不連續有關，CPU提前存的一段數據，可能跟下一個數據完全沒有聯系，因為它們空間不連續，所以就命中率低。

16、vector和list中，如果刪除末尾的元素，其指針和迭代器如何變化？若刪除的是中間的元素呢？

1. 迭代器和指針之間的區別
   1. 迭代器不是指針，是類模板，表現的像指針。 他只是模擬了指針的一些功能，重載了指針的一些操作符，-->、++、--等。迭代器封裝了指針，是一個”可遍歷STL（ Standard Template Library）容器內全部或部分元素”的對象，本質是封裝了原生指針，是指針概念的一種提升，提供了比指針更高級的行為，相當于一種智能指針，他可以根據不同類型的數據結構來實現不同的++，--等操作。
   2. 迭代器返回的是對象引用而不是對象的值 ，所以cout只能輸出迭代器使用取值后的值而不能直接輸出其自身。
2. vector和list特性
   1. vector特性 動態數組。元素在內存連續存放。隨機存取任何元素都在常數時間完成。在尾端增刪元素具有較大的性能（大部分情況下是常數時間）。
   2. list特性 雙向鏈表。元素在內存不連續存放。在任何位置增刪元素都能在常數時間完成。不支持隨機存取。
3. vector和list增刪元素
   1. 對于vector而言，刪除某個元素以后，該元素后邊的每個元素的迭代器都會失效，后邊每個元素都往前移動一位，erase返回下一個有效的迭代器。
   2. 對于list而言，刪除某個元素，只有“指向被刪除元素”的那個迭代器失效，其它迭代器不受任何影響。

17、總結一下vector和list具體是怎么實現的呢？常見操作的時間復雜度是多少嘞

1. vector 一維數組（元素在內存連續存放）

   • 倍放開辟三倍的內存
   • 舊的數據開辟到新的內存
   • 釋放舊的內存
   • 指向新內存
   1. 是動態數組，在堆中分配內存，元素連續存放，有保留內存，如果減少大小后，內存也不會釋放；如果新增大小當前大小時才會重新分配內存。
   2. 擴容方式：

2. list 雙向鏈表（元素存放在堆中）

   • 隨機訪問不方便
   • 刪除插入操作方便
   1. 元素存放在堆中，每個元素都是放在一塊內存中，它的內存空間可以是不連續的，通過指針來進行數據的訪問，這個特點，使得它的隨機存取變得非常沒有效率，因此它沒有提供[ ]操作符的重載。但是由于鏈表的特點，它可以很有效的支持任意地方的刪除和插入操作。
   2. 特點：

3. 常見時間復雜度

   1. vector插入、查找、刪除時間復雜度分別為：O(n)、O(1)、O(n)；
   2. list插入、查找、刪除時間復雜度分別為：O(1)、O(n)、O(1)。

18、簡單說說deque

1. deque是一個雙向開口的容器，所謂雙向開口就是再頭尾兩端均可以做元素的插入和刪除操作。
2. deque相比于vector最大的差異就在于支持常熟時間內對首尾兩端進行插入和刪除操作，而且deque沒有容量的概念，其內部采用分段連續內存空間來存儲元素，在插入元素的時候隨時都可以重新增加一段新的空間并鏈接起來。
3. deque提供了Ramdon Access Iterator，同時也支持隨機訪問和存取，但是它也為此付出了昂貴的代價，其復雜度不能跟vector的原生指針迭代器相提并論。在下面的講解中會一一為大家介紹STL是怎樣”辛苦地”維持一個隨機訪問迭代器的。

19、詳細講講deque實現原理

動態開辟的二維數組空間，第二維固定長度的數組空間，擴容的時候（第一維的數組進行2倍擴容）。

deque內部實現的是一個 雙向隊列 。元素在內存連續存放。隨機存取任何元素都在常數時間完成（僅次于vector）。所有適用于vector的操作都適用于deque。在兩端增刪元素具有較佳的性能（大部分情況下是常數時間）。

20、你了解deque的中控器嗎

deque為了維持整體連續的假象，設計一個中控器，其用來記錄deque內部每一段連續空間的地址。大體上可以理解為deque中的每一段連續空間分布在內存的不連續空間上，然后用一個所謂的map作為主控，記錄每一段內存空間的入口，從而做到整體連續的假象。

21、deque的迭代器是怎么回事呢

1. deque提供的是一個隨機訪問迭代器，由于是分段連續空間，其必須記錄當前元素所在段的信息，從而在該段連續空間的邊緣進行前進或者后退的時候能知道跳躍到的上一個或下一個緩沖區。deque必須完完整整的掌握和控制這些信息，以達到正確的跳躍。

2. buffer_size函數：

   static size_t buffer_size(){
       return __deque_buf_size(BufSiz, sizeof(T));
   }
   //如果n不為0,傳回n,表示buffer size 由自己定義
   如果n為0,表示buffer_size 采用默認值
   如果sz(元素大小) < 512，傳回512/sz,如果不小于512 ，傳回1
   inline size_t __deque_buf_size(size_t n, size_t sz)
   {
       return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
   }
   

3. set_node函數

當迭代器處在當前緩沖區的邊緣時，一旦前進或者后退，就要考慮超過當前緩沖區的情況，此時需要跳轉到下一個緩沖區，這時候set_node就派上用場了。

void set_node(map_pointer new_node)
{
  node = new_node;      // 跳轉到相應緩沖區
  first = *new_node;    // 更新跳轉后緩沖區first信息
  last = first + difference_type(buffer_size());  // 更新跳轉后緩沖區last的信息
}

22、說一說deque的數據結構

deque維護著一個map，用來記錄每個緩沖區的位置。除了map外，deque的數據結構還維護著start和finish兩個迭代器，分別指向deque的首尾。此外，他還必須知道map的大小，一旦map提供的節點不足，就需要配置一塊更大的map。

23、deque常用的函數

deque.push_back(elem)在尾部加入一個數據。
deque.pop_back()刪除尾部數據。
deque.push_front(elem)在頭部插入一個數據。
deque.pop_front()刪除頭部數據。
deque.size() 返回容器中實際數據的個數。
deque.at(idx)傳回索引idx所指的數據，如果idx越界，拋出out_of_range。

24、vector、list、deque的選擇原則

• vector可以隨機存儲元素（即可以通過公式直接計算出元素地址，而不需要挨個查找），但在非尾部插入刪除數據時，效率很低，適合對象簡單，對象數量變化不大，隨機訪問頻繁。除非必要，我們盡可能選擇使用vector而非deque，因為deque的迭代器比vector迭代器復雜很多。
• list不支持隨機存儲，適用于對象大，對象數量變化頻繁，插入和刪除頻繁，比如寫多讀少的場景。
• 需要從首尾兩端進行插入或刪除操作的時候需要選擇deque。

也即：

• 需要對數據高效的隨機訪問（存取），而不在乎插入和刪除的效率，采用vector。
• 需要大量插入、刪除數據，而不關心隨機訪問數據，采用list。
• 需要隨機訪問數據，而且關心前后增刪數據的能力，采用deque。
• 對數據中間的增刪操作比較多，采用list，建議在排序的基礎上，批量進行增刪可以對運行效率提供最大的保證。

25、說說STL迭代器是怎么刪除元素的

1. 對于序列容器vector，deque來說，使用erase后，后邊的每個元素的迭代器都會失效，后邊每個元素都往前移動一位，erase返回下一個有效的迭代器；
2. 對于關聯容器map，set來說，使用了erase后，當前元素的迭代器失效，但是其結構是紅黑樹，刪除當前元素，不會影響下一個元素的迭代器，所以在調用erase之前，記錄下一個元素的迭代器即可；
3. 對于list來說，它使用了不連續分配的內存，并且它的erase方法也會返回下一個有效的迭代器，因此上面兩種方法都可以使用。

26、了解優先級隊列嗎？展開講講

底層數據結構一般以vector為底層容器，heap為處理規則來管理底層容器實現。

優先隊列（priority_queue）容器與隊列一樣，只能從隊尾插入元素，從隊首刪除元素。但是它有一個特性，隊列中最大的元素總是位于隊首。出隊時，并非按照先進先出的原則進行，而是將當前隊列中最大的元素出隊。這點類似于給隊列里的元素進行了由大到小的順序排序。元素的比較規則默認按元素值由大到小排序，可以重載“<”操作符來重新定義比較規則。在優先隊列中，隊首元素一定是當前隊列中優先級最高的那一個。

27、你知道STL容器動態鏈接可能產生的問題嘛

• 可能產生的問題

容器是一種動態分配內存空間的一個變量集合類型變量。在一般的程序函數里，局部容器，參數傳遞容器，參數傳遞容器的引用，參數傳遞容器指針都是可以正常運行的，而在動態鏈接庫函數內部使用容器也是沒有問題的，但是給動態庫函數傳遞容器的對象本身，則會出現內存堆棧破壞的問題。

• 產生問題的原因

容器和動態鏈接庫相互支持不夠好，動態鏈接庫函數中使用容器時，參數中只能傳遞容器的引用，并且要保證容器的大小不能超出初始大小，否則導致容器自動重新分配，就會出現內存堆棧破壞問題。

28、你了解map和unordered_map嘛？底層實現呢

• map實現機理

map內部實現了一個 紅黑樹 （紅黑樹是非嚴格平衡的二叉搜索樹，而AVL是嚴格平衡二叉搜索樹），紅黑樹有自動排序的功能，因此map內部所有元素都是有序的，紅黑樹的每一個節點都代表著map的一個元素。因此，對于map進行的查找、刪除、添加等一系列的操作都相當于是對紅黑樹進行的操作。map中的元素是按照二叉樹（又名二叉查找樹、二叉排序樹）存儲的，特點就是左子樹上所有節點的鍵值都小于根節點的鍵值，右子樹所有節點的鍵值都大于根節點的鍵值。使用中序遍歷可將鍵值按照從小到大遍歷出來。

• unordered_map實現機理

unordered_map內部實現了一個 哈希表 （也叫散列表），通過把關鍵碼值映射到Hash表中一個位置來訪問記錄，查找時間復雜度可達O（1），其中在海量數據處理中有著廣泛應用。因此，元素的排列順序是無序的。

29、map和unordered_map的優缺點

• map的優點
  • 有序
  • 基于紅黑樹實現，查找的時間復雜度是O(nlogn)
• map的缺點
  • 空間占用率比較高，雖然說底層是紅黑樹實現的，提高了運行效率，但是每個節點都要保存父節點和孩子節點和紅黑樹的性質，使得每一個節點都占用膽量的空間。
• 適用情況
  • 對于有序的結構
• unordered_map的優點
  • 底層是用哈希表實現的，查找效率非常高，時間復雜度為O(1)。
• unordered_map的缺點
  • 哈希表的建立比較費時。
• 適用場景
  • 對于查找問題，使用unordered_map更好。

30、set的底層實現為什么不用哈希表而是用紅黑樹

• set中元素是經過排序的，紅黑樹也是有序的，哈希是無序的
• 如果只是單純的查找元素的話，那么肯定要選哈希表了，因為哈希表在的最好查找時間復雜度為O(1)，并且如果用到set中那么查找時間復雜度的一直是O（1），因為set中是不允許有元素重復的。而紅黑樹的查找時間復雜度為O(logn)。

31、為什么map和set和插入刪除效率比其他序列容器高，而且每次insert之后，以前保存的iterator不會失效

因為存儲的是節點，不需要內存拷貝和內存移動。

插入操作只是節點指針換來換去，節點內存沒有改變，而iterator就像指向節點的指針，內存沒變，指向內存de指針也不會變。

32、為什么map和set不能像vector一樣有個reserve函數來預分配數據

因為在map和set內部存儲的已經不是元素本身了，而是包含元素的節點。也就是說map內部使用的Alloc并不是map聲明的時候從參數中傳入的Alloc。

33、你知道map和set有什么區別嘛？分別是怎么實現的呢

• set是一種關聯式容器，其特性如下：
  • set以RBTree作為底層容器
  • 所得元素的只有key沒有value，value就是key
  • 不允許出現鍵值重復
  • 所有的元素都會被自動排序
  • 不能通過迭代器來改變set的值，因為set的值就是鍵，set的迭代器是const的
• map和set一樣是關聯式容器，其特性如下：
  • map以RBTree作為底層容器
  • 所有元素都是鍵+值存在
  • 不允許鍵重復
  • 所有元素是通過鍵進行自動排序的
  • map的鍵是不能修改的，但是其鍵對應的值是可以修改的

綜上所述，map和set底層實現都是紅黑樹；map和set的區別在于map的值不作為鍵，鍵和值是分開的。

34、vector越界訪問下標，map越界訪問下標，vector刪除元素時會不會釋放空間

• 通過下標訪問vector中的元素時會做邊界檢查，但該處的實現方式要看具體IDE，不同IDE的實現方式不一樣，確保不可訪問越界地址。
• map的下標運算符[]的作用是：將key作為下標去執行查找，并返回相應的值；如果不存在這個key，就將一個具有該key和value的某人值插入這個map。
• erase()函數，只能刪除內容，不能改變容量大小;

erase成員函數，它刪除了itVect迭代器指向的元素，并且返回要被刪除的itVect之后的迭代器，迭代器相當于一個智能指針;clear()函數，只能清空內容，不能改變容量大小;如果要想在刪除內容的同時釋放內存，那么你可以選擇deque容器。

35、map中[ ]與find的區別

• map的下標運算符[ ]的作用是：將關鍵碼作為下標去執行查找，并返回對應的值；如果不存在這個關鍵碼，就將一個具有該關鍵碼和值類型的默認值的項插入這個map。
• map的find函數：用關鍵碼執行查找，找到了返回該位置的迭代器；如果不存在這個關鍵碼，就返回尾迭代器。

36、你了解STL的內存優化嘛

STL內存管理使用二級內存配置器。

1. 第一級配置器：

• 第一級配置器以malloc()，free()，realloc()等C函數執行實際的內存配置、釋放、重新配置等操作，并且能在內存需求不被滿足的時候，調用一個指定的函數。一級空間配置器分配的是大于128字節的空間，如果分配不成功，調用句柄釋放一部分內存，如果還不能分配成功，拋出異常。
• 第一級配置器只是對malloc函數和free函數的簡單封裝，在allocate內調用malloc，在deallocate內調用free。同時第一級配置器的oom_malloc函數，用來處理malloc失敗的情況。

2. 第二級配置器：

第一級配置器直接調用malloc和free帶來了幾個問題：

• 內存分配/釋放的效率低。
• 當配置大量的小內存塊時，會導致內存碎片比較嚴重。
• 配置內存時，需要額外的部分空間存儲內存塊信息，所以配置大量的小內存塊時，還會導致額外內存負擔。

如果分配的區塊小于128bytes，則以內存池管理，第二級配置器維護了一個自由鏈表數組，每次需要分配內存時，直接從相應的鏈表上取出一個內存節點就完成工作，效率很高。

• 自由鏈表數組：自由鏈表數組其實就是個指針數組，數組中的每個指針元素指向一個鏈表的起始節點。數組大小為16，即維護了16個鏈表，鏈表的每個節點就是實際的內存塊，相同鏈表上的內存塊大小都相同，不同鏈表的內存塊大小不同，從8一直到128。如下所示，obj為鏈表上的節點，free_list就是鏈表數組。
• 內存分配：allocate函數內先判斷要分配的內存大小，若大于128字節，直接調用第一級配置器，否則根據要分配的內存大小從16個鏈表中選出一個鏈表，取出該鏈表的第一個節點。若相應的鏈表為空，則調用refill函數填充該鏈表。默認是取出20個數據塊。
• 填充鏈表 refill：若allocate函數內要取出節點的鏈表為空，則會調用refill函數填充該鏈表。refill函數內會先調用chunk_alloc函數從內存池分配一大塊內存，該內存大小默認為20個鏈表節點大小，當內存池的內存也不足時，返回的內存塊節點數目會不足20個。接著refill的工作就是將這一大塊內存分成20份相同大小的內存塊，并將各內存塊連接起來形成一個鏈表。
• 內存池：chunk_alloc函數內管理了一塊內存池，當refill函數要填充鏈表時，就會調用chunk_alloc函數，從內存池取出相應的內存。
  • 在chunk_alloc函數內首先判斷內存池大小是否足夠填充一個有20個節點的鏈表，若內存池足夠大，則直接返回20個內存節點大小的內存塊給refill；
  • 若內存池大小無法滿足20個內存節點的大小，但至少滿足1個內存節點，則直接返回相應的內存節點大小的內存塊給refill；
  • 若內存池連1個內存節點大小的內存塊都無法提供，則chunk_alloc函數會將內存池中那一點點的內存大小分配給其他合適的鏈表，然后去調用malloc函數分配的內存大小為所需的兩倍。若malloc成功，則返回相應的內存大小給refill；若malloc失敗，會先搜尋其他鏈表的可用的內存塊，添加到內存池，然后遞歸調用chunk_alloc函數來分配內存，若其他鏈表也無內存塊可用，則只能調用第一級空間配置器。

37、頻繁對vector調用push_back()對性能的影響和原因

在一個vector的尾部之外的任何位置添加元素，都需要重新移動元素。而且，向一個vector添加元素可能引起整個對象存儲空間的重新分配。重新分配一個對象的存儲空間需要分配新的內存，并將元素從舊的空間移到新的空間。

38、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。

39、講一講set的用法和它的特點

• 用法：count()-返回某個值元素的個數（set中最多為1）、find()-返回一個指向被查找到元素的迭代器、equal_range()-返回集合中與給定值相等的上下限的兩個迭代器。
• 特點：元素不允許有重復，在默認情況下會對元素進行自動排序，數據被組織成一棵紅黑樹，查找的速度非常快（二分），時間復雜度是O(logN)，set中的元素不能被修改，只能刪除后再添加。