c語(yǔ)言入門知識(shí)之STL篇

這周終于可以給大家把STL方面的面試題總結(jié)出來(lái)了，突然發(fā)現(xiàn)它里面的細(xì)節(jié)非常多，只有你想不到的，沒(méi)有它沒(méi)有的。對(duì)于C++程序員來(lái)說(shuō)，STL庫(kù)里面的知識(shí)也是非常重要的，只要想在技術(shù)這條路線上有長(zhǎng)遠(yuǎn)的發(fā)展，那么就一定要掌握它。不管是學(xué)習(xí)中，面試中，工作中，它都有不可估量的地位。

之前有寫過(guò)一片關(guān)于STL庫(kù)的文章，現(xiàn)在來(lái)看確實(shí)也是非常有用的知識(shí)點(diǎn)。

這篇文章主要是講解在面試過(guò)程中遇到的一些面試題，細(xì)節(jié)很多，量也很大，大家在看的時(shí)候，不僅僅只是看一遍而已，還要多了解背后的原理，在不懂的時(shí)候，還是需要看看相關(guān)權(quán)威書籍。

STL篇

1、講講STL的六大組件

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

2、簡(jiǎn)單說(shuō)說(shuō)vector

動(dòng)態(tài)開(kāi)辟的二維數(shù)組。元素在內(nèi)存連續(xù)存放。隨機(jī)存取任何元素都能在常數(shù)時(shí)間完成。在尾端增刪元素具有較佳的性能。

3、vector底層原理

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

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

• vector在push_back以成倍增長(zhǎng)可以在均攤后達(dá)到O(1)的事件復(fù)雜度，相對(duì)于增長(zhǎng)指定大小的O(n)時(shí)間復(fù)雜度更好。
• 為了防止申請(qǐng)內(nèi)存的浪費(fèi)，現(xiàn)在使用較多的有2倍與1.5倍的增長(zhǎng)方式，而1.5倍的增長(zhǎng)方式可以更好的實(shí)現(xiàn)對(duì)內(nèi)存的重復(fù)利用。

5、vector擴(kuò)容的過(guò)程

• 完全棄用現(xiàn)有的內(nèi)存空間，重新申請(qǐng)更大的內(nèi)存空間；
• 將舊內(nèi)存空間中的數(shù)據(jù)，按原有順序移動(dòng)到新的內(nèi)存空間中；
• 最后將舊的內(nèi)存空間釋放。

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

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

7、size、resize、reserve、capacity的區(qū)別

• size表示當(dāng)前vector中有多少個(gè)元素（即finish – start）；當(dāng)前容器所存儲(chǔ)的個(gè)數(shù)，
• resize可以改變有效空間的大小，也有改變默認(rèn)值的功能。capacity的大小也會(huì)隨著改變?？梢杂卸鄠€(gè)參數(shù)。創(chuàng)建指定數(shù)量的元素并指定vector的存儲(chǔ)空間。既分配空間又創(chuàng)建對(duì)象。
• reserve是直接擴(kuò)充到已經(jīng)確定的大小，可以減少多次開(kāi)辟、釋放空間的問(wèn)題（優(yōu)化push_back），從而達(dá)到提高效率的目的，其次還可以減少多次要拷貝數(shù)據(jù)的問(wèn)題。reserve它只是保證vector中的空間大?。╟apacity）最少達(dá)到參數(shù)所指定的大小n。并且它只有一個(gè)參數(shù)。指定vector的元素總數(shù)，不創(chuàng)建對(duì)象。
• capacity函數(shù)表示它已經(jīng)分配的內(nèi)存中可以容納多少元素（即end_of_storage – start）。即容器在分配新的存儲(chǔ)空間能存儲(chǔ)的元素總數(shù)。返回vector中能存儲(chǔ)元素的最大數(shù)。

8、vector迭代器失效問(wèn)題

迭代器的主要作用就是讓算法能夠不用關(guān)心底層數(shù)據(jù)結(jié)構(gòu)，其底層實(shí)際就是一個(gè)指針，或者是對(duì)指針進(jìn)行了 封裝，比如：vector的迭代器就是原生態(tài)指針T*。因此迭代器失效，實(shí)際就是迭代器底層對(duì)應(yīng)指針?biāo)赶虻?空間被銷毀了，而使用一塊已經(jīng)被釋放的空間，造成的后果是程序崩潰(即如果繼續(xù)使用已經(jīng)失效的迭代器， 程序可能會(huì)崩潰)。

9、對(duì)于vector可能導(dǎo)致其迭代器失效的操作有哪些

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

• 指定位置元素的刪除操作--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位置的數(shù)據(jù)，導(dǎo)致pos迭代器失效。
      v.erase(pos);
      cout << *pos << endl; // 此處會(huì)導(dǎo)致非法訪問(wèn)
      return 0;
  }
  

erase刪除pos位置元素后，pos位置之后的元素會(huì)往前移動(dòng)，沒(méi)有導(dǎo)致底層空間的改變，理論上講迭代器應(yīng)該不會(huì)失效，但是如果pos剛好是最后一個(gè)元素，刪完之后pos剛好是end位置，而end位置是沒(méi)有元素的，那么pos就失效了。所以刪除vector中任意位置上元素時(shí)，vs就認(rèn)為該位置迭代器失效了。

10、push_back和emplace_back的區(qū)別

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

11、聊聊STL庫(kù)中的list

• list 是順序容器的一種。list 是一個(gè)雙向鏈表。使用 list 需要包含頭文件 list。雙向鏈表的每個(gè)元素中都有一個(gè)指針指向后一個(gè)元素，也有一個(gè)指針指向前一個(gè)元素。
• 在 list 容器中，在已經(jīng)定位到要增刪元素的位置的情況下，增刪元素能在常數(shù)時(shí)間內(nèi)完成。
• list不支持根據(jù)下標(biāo)隨機(jī)存取元素。
• 在任何位置都能高效地插入和刪除元素，只要改變?cè)氐闹羔樦担恍枰截愒亍?/li>

12、list的底層原理

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

13、list的常用函數(shù)

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

14、vector插入、list插入問(wèn)題

• vector中插入大量連續(xù)的數(shù)據(jù)時(shí)，如果預(yù)知數(shù)據(jù)量大小，可以通過(guò)resize來(lái)調(diào)整原先vector的空間大小，同時(shí)利用賦值“=”，可以減少耗時(shí)。
• list可以通過(guò)遍歷list然后insert插入，但還可以通過(guò)成員方法splice來(lái)進(jìn)行插入，且效率較高，耗時(shí)較少。

15、vector和list的優(yōu)缺點(diǎn)

1. vector的優(yōu)點(diǎn)

• 下標(biāo)隨機(jī)訪問(wèn)

vector的底層是一段連續(xù)的物理空間，所以支持隨機(jī)訪問(wèn)。

• 尾插尾刪效率高
  跟數(shù)組類似，我們能夠很輕易的找到最后一個(gè)元素，并完成各種操作。
• cpu高速緩存命中率高
  因?yàn)橄到y(tǒng)在底層拿空間的時(shí)候，是拿一段進(jìn)cpu，不是只拿單獨(dú)一個(gè)，會(huì)提前往后多拿一點(diǎn)，vector的物理地址是連續(xù)的，所以我們?cè)倌玫綌?shù)據(jù)的時(shí)候，cpu訪問(wèn)后面的數(shù)據(jù)會(huì)更快。

2. vector的缺點(diǎn)

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

3. list的優(yōu)點(diǎn)

• 按需申請(qǐng)釋放，不需要擴(kuò)容
  list是一個(gè)帶頭雙向循環(huán)鏈表，那么鏈表就是一個(gè)個(gè)獨(dú)立的空間鏈接起的，需要多少，就new多少，不存在空間浪費(fèi)。
• 任意位置的插入刪除效率高（對(duì)比vector）
  因?yàn)閘ist是雙向循環(huán)鏈表，我們需要插入新的元素只需要改變?cè)瓟?shù)據(jù)的next和prev，所以我們的插入刪除效率是O(1)。

4. list的缺點(diǎn)

• 不支持下標(biāo)隨機(jī)訪問(wèn)
  因?yàn)閘ist是鏈表，在存放數(shù)據(jù)的物理地址并不是連續(xù)的，所以我們也就不能支持隨機(jī)訪問(wèn)。
• CPU高速緩存命中率低
  主要還是跟它的物理地址不連續(xù)有關(guān)，CPU提前存的一段數(shù)據(jù)，可能跟下一個(gè)數(shù)據(jù)完全沒(méi)有聯(lián)系，因?yàn)樗鼈兛臻g不連續(xù)，所以就命中率低。

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

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

17、總結(jié)一下vector和list具體是怎么實(shí)現(xiàn)的呢？常見(jiàn)操作的時(shí)間復(fù)雜度是多少嘞

1. vector 一維數(shù)組（元素在內(nèi)存連續(xù)存放）

   • 倍放開(kāi)辟三倍的內(nèi)存
   • 舊的數(shù)據(jù)開(kāi)辟到新的內(nèi)存
   • 釋放舊的內(nèi)存
   • 指向新內(nèi)存
   1. 是動(dòng)態(tài)數(shù)組，在堆中分配內(nèi)存，元素連續(xù)存放，有保留內(nèi)存，如果減少大小后，內(nèi)存也不會(huì)釋放；如果新增大小當(dāng)前大小時(shí)才會(huì)重新分配內(nèi)存。
   2. 擴(kuò)容方式：

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

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

3. 常見(jiàn)時(shí)間復(fù)雜度

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

18、簡(jiǎn)單說(shuō)說(shuō)deque

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

19、詳細(xì)講講deque實(shí)現(xiàn)原理

動(dòng)態(tài)開(kāi)辟的二維數(shù)組空間，第二維固定長(zhǎng)度的數(shù)組空間，擴(kuò)容的時(shí)候（第一維的數(shù)組進(jìn)行2倍擴(kuò)容）。

deque內(nèi)部實(shí)現(xiàn)的是一個(gè) 雙向隊(duì)列 。元素在內(nèi)存連續(xù)存放。隨機(jī)存取任何元素都在常數(shù)時(shí)間完成（僅次于vector）。所有適用于vector的操作都適用于deque。在兩端增刪元素具有較佳的性能（大部分情況下是常數(shù)時(shí)間）。

20、你了解deque的中控器嗎

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

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

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

2. buffer_size函數(shù)：

   static size_t buffer_size(){
       return __deque_buf_size(BufSiz, sizeof(T));
   }
   //如果n不為0,傳回n,表示buffer size 由自己定義
   如果n為0,表示buffer_size 采用默認(rèn)值
   如果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函數(shù)

當(dāng)?shù)魈幵诋?dāng)前緩沖區(qū)的邊緣時(shí)，一旦前進(jìn)或者后退，就要考慮超過(guò)當(dāng)前緩沖區(qū)的情況，此時(shí)需要跳轉(zhuǎn)到下一個(gè)緩沖區(qū)，這時(shí)候set_node就派上用場(chǎng)了。

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

22、說(shuō)一說(shuō)deque的數(shù)據(jù)結(jié)構(gòu)

deque維護(hù)著一個(gè)map，用來(lái)記錄每個(gè)緩沖區(qū)的位置。除了map外，deque的數(shù)據(jù)結(jié)構(gòu)還維護(hù)著start和finish兩個(gè)迭代器，分別指向deque的首尾。此外，他還必須知道m(xù)ap的大小，一旦map提供的節(jié)點(diǎn)不足，就需要配置一塊更大的map。

23、deque常用的函數(shù)

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

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

• vector可以隨機(jī)存儲(chǔ)元素（即可以通過(guò)公式直接計(jì)算出元素地址，而不需要挨個(gè)查找），但在非尾部插入刪除數(shù)據(jù)時(shí)，效率很低，適合對(duì)象簡(jiǎn)單，對(duì)象數(shù)量變化不大，隨機(jī)訪問(wèn)頻繁。除非必要，我們盡可能選擇使用vector而非deque，因?yàn)閐eque的迭代器比vector迭代器復(fù)雜很多。
• list不支持隨機(jī)存儲(chǔ)，適用于對(duì)象大，對(duì)象數(shù)量變化頻繁，插入和刪除頻繁，比如寫多讀少的場(chǎng)景。
• 需要從首尾兩端進(jìn)行插入或刪除操作的時(shí)候需要選擇deque。

也即：

• 需要對(duì)數(shù)據(jù)高效的隨機(jī)訪問(wèn)（存?。辉诤醪迦牒蛣h除的效率，采用vector。
• 需要大量插入、刪除數(shù)據(jù)，而不關(guān)心隨機(jī)訪問(wèn)數(shù)據(jù)，采用list。
• 需要隨機(jī)訪問(wèn)數(shù)據(jù)，而且關(guān)心前后增刪數(shù)據(jù)的能力，采用deque。
• 對(duì)數(shù)據(jù)中間的增刪操作比較多，采用list，建議在排序的基礎(chǔ)上，批量進(jìn)行增刪可以對(duì)運(yùn)行效率提供最大的保證。

25、說(shuō)說(shuō)STL迭代器是怎么刪除元素的

1. 對(duì)于序列容器vector，deque來(lái)說(shuō)，使用erase后，后邊的每個(gè)元素的迭代器都會(huì)失效，后邊每個(gè)元素都往前移動(dòng)一位，erase返回下一個(gè)有效的迭代器；
2. 對(duì)于關(guān)聯(lián)容器map，set來(lái)說(shuō)，使用了erase后，當(dāng)前元素的迭代器失效，但是其結(jié)構(gòu)是紅黑樹(shù)，刪除當(dāng)前元素，不會(huì)影響下一個(gè)元素的迭代器，所以在調(diào)用erase之前，記錄下一個(gè)元素的迭代器即可；
3. 對(duì)于list來(lái)說(shuō)，它使用了不連續(xù)分配的內(nèi)存，并且它的erase方法也會(huì)返回下一個(gè)有效的迭代器，因此上面兩種方法都可以使用。

26、了解優(yōu)先級(jí)隊(duì)列嗎？展開(kāi)講講

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

優(yōu)先隊(duì)列（priority_queue）容器與隊(duì)列一樣，只能從隊(duì)尾插入元素，從隊(duì)首刪除元素。但是它有一個(gè)特性，隊(duì)列中最大的元素總是位于隊(duì)首。出隊(duì)時(shí)，并非按照先進(jìn)先出的原則進(jìn)行，而是將當(dāng)前隊(duì)列中最大的元素出隊(duì)。這點(diǎn)類似于給隊(duì)列里的元素進(jìn)行了由大到小的順序排序。元素的比較規(guī)則默認(rèn)按元素值由大到小排序，可以重載“<”操作符來(lái)重新定義比較規(guī)則。在優(yōu)先隊(duì)列中，隊(duì)首元素一定是當(dāng)前隊(duì)列中優(yōu)先級(jí)最高的那一個(gè)。

27、你知道STL容器動(dòng)態(tài)鏈接可能產(chǎn)生的問(wèn)題嘛

• 可能產(chǎn)生的問(wèn)題

容器是一種動(dòng)態(tài)分配內(nèi)存空間的一個(gè)變量集合類型變量。在一般的程序函數(shù)里，局部容器，參數(shù)傳遞容器，參數(shù)傳遞容器的引用，參數(shù)傳遞容器指針都是可以正常運(yùn)行的，而在動(dòng)態(tài)鏈接庫(kù)函數(shù)內(nèi)部使用容器也是沒(méi)有問(wèn)題的，但是給動(dòng)態(tài)庫(kù)函數(shù)傳遞容器的對(duì)象本身，則會(huì)出現(xiàn)內(nèi)存堆棧破壞的問(wèn)題。

• 產(chǎn)生問(wèn)題的原因

容器和動(dòng)態(tài)鏈接庫(kù)相互支持不夠好，動(dòng)態(tài)鏈接庫(kù)函數(shù)中使用容器時(shí)，參數(shù)中只能傳遞容器的引用，并且要保證容器的大小不能超出初始大小，否則導(dǎo)致容器自動(dòng)重新分配，就會(huì)出現(xiàn)內(nèi)存堆棧破壞問(wèn)題。

28、你了解map和unordered_map嘛？底層實(shí)現(xiàn)呢

• map實(shí)現(xiàn)機(jī)理

map內(nèi)部實(shí)現(xiàn)了一個(gè) 紅黑樹(shù) （紅黑樹(shù)是非嚴(yán)格平衡的二叉搜索樹(shù)，而AVL是嚴(yán)格平衡二叉搜索樹(shù)），紅黑樹(shù)有自動(dòng)排序的功能，因此map內(nèi)部所有元素都是有序的，紅黑樹(shù)的每一個(gè)節(jié)點(diǎn)都代表著map的一個(gè)元素。因此，對(duì)于map進(jìn)行的查找、刪除、添加等一系列的操作都相當(dāng)于是對(duì)紅黑樹(shù)進(jìn)行的操作。map中的元素是按照二叉樹(shù)（又名二叉查找樹(shù)、二叉排序樹(shù)）存儲(chǔ)的，特點(diǎn)就是左子樹(shù)上所有節(jié)點(diǎn)的鍵值都小于根節(jié)點(diǎn)的鍵值，右子樹(shù)所有節(jié)點(diǎn)的鍵值都大于根節(jié)點(diǎn)的鍵值。使用中序遍歷可將鍵值按照從小到大遍歷出來(lái)。

• unordered_map實(shí)現(xiàn)機(jī)理

unordered_map內(nèi)部實(shí)現(xiàn)了一個(gè) 哈希表 （也叫散列表），通過(guò)把關(guān)鍵碼值映射到Hash表中一個(gè)位置來(lái)訪問(wèn)記錄，查找時(shí)間復(fù)雜度可達(dá)O（1），其中在海量數(shù)據(jù)處理中有著廣泛應(yīng)用。因此，元素的排列順序是無(wú)序的。

29、map和unordered_map的優(yōu)缺點(diǎn)

• map的優(yōu)點(diǎn)
  • 有序
  • 基于紅黑樹(shù)實(shí)現(xiàn)，查找的時(shí)間復(fù)雜度是O(nlogn)
• map的缺點(diǎn)
  • 空間占用率比較高，雖然說(shuō)底層是紅黑樹(shù)實(shí)現(xiàn)的，提高了運(yùn)行效率，但是每個(gè)節(jié)點(diǎn)都要保存父節(jié)點(diǎn)和孩子節(jié)點(diǎn)和紅黑樹(shù)的性質(zhì)，使得每一個(gè)節(jié)點(diǎn)都占用膽量的空間。
• 適用情況
  • 對(duì)于有序的結(jié)構(gòu)
• unordered_map的優(yōu)點(diǎn)
  • 底層是用哈希表實(shí)現(xiàn)的，查找效率非常高，時(shí)間復(fù)雜度為O(1)。
• unordered_map的缺點(diǎn)
  • 哈希表的建立比較費(fèi)時(shí)。
• 適用場(chǎng)景
  • 對(duì)于查找問(wèn)題，使用unordered_map更好。

30、set的底層實(shí)現(xiàn)為什么不用哈希表而是用紅黑樹(shù)

• set中元素是經(jīng)過(guò)排序的，紅黑樹(shù)也是有序的，哈希是無(wú)序的
• 如果只是單純的查找元素的話，那么肯定要選哈希表了，因?yàn)楣１碓诘淖詈貌檎視r(shí)間復(fù)雜度為O(1)，并且如果用到set中那么查找時(shí)間復(fù)雜度的一直是O（1），因?yàn)閟et中是不允許有元素重復(fù)的。而紅黑樹(shù)的查找時(shí)間復(fù)雜度為O(logn)。

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

因?yàn)榇鎯?chǔ)的是節(jié)點(diǎn)，不需要內(nèi)存拷貝和內(nèi)存移動(dòng)。

插入操作只是節(jié)點(diǎn)指針換來(lái)?yè)Q去，節(jié)點(diǎn)內(nèi)存沒(méi)有改變，而iterator就像指向節(jié)點(diǎn)的指針，內(nèi)存沒(méi)變，指向內(nèi)存de指針也不會(huì)變。

32、為什么map和set不能像vector一樣有個(gè)reserve函數(shù)來(lái)預(yù)分配數(shù)據(jù)

因?yàn)樵趍ap和set內(nèi)部存儲(chǔ)的已經(jīng)不是元素本身了，而是包含元素的節(jié)點(diǎn)。也就是說(shuō)map內(nèi)部使用的Alloc并不是map聲明的時(shí)候從參數(shù)中傳入的Alloc。

33、你知道m(xù)ap和set有什么區(qū)別嘛？分別是怎么實(shí)現(xiàn)的呢

• set是一種關(guān)聯(lián)式容器，其特性如下：
  • set以RBTree作為底層容器
  • 所得元素的只有key沒(méi)有value，value就是key
  • 不允許出現(xiàn)鍵值重復(fù)
  • 所有的元素都會(huì)被自動(dòng)排序
  • 不能通過(guò)迭代器來(lái)改變set的值，因?yàn)閟et的值就是鍵，set的迭代器是const的
• map和set一樣是關(guān)聯(lián)式容器，其特性如下：
  • map以RBTree作為底層容器
  • 所有元素都是鍵+值存在
  • 不允許鍵重復(fù)
  • 所有元素是通過(guò)鍵進(jìn)行自動(dòng)排序的
  • map的鍵是不能修改的，但是其鍵對(duì)應(yīng)的值是可以修改的

綜上所述，map和set底層實(shí)現(xiàn)都是紅黑樹(shù)；map和set的區(qū)別在于map的值不作為鍵，鍵和值是分開(kāi)的。

34、vector越界訪問(wèn)下標(biāo)，map越界訪問(wèn)下標(biāo)，vector刪除元素時(shí)會(huì)不會(huì)釋放空間

• 通過(guò)下標(biāo)訪問(wèn)vector中的元素時(shí)會(huì)做邊界檢查，但該處的實(shí)現(xiàn)方式要看具體IDE，不同IDE的實(shí)現(xiàn)方式不一樣，確保不可訪問(wèn)越界地址。
• map的下標(biāo)運(yùn)算符[]的作用是：將key作為下標(biāo)去執(zhí)行查找，并返回相應(yīng)的值；如果不存在這個(gè)key，就將一個(gè)具有該key和value的某人值插入這個(gè)map。
• erase()函數(shù)，只能刪除內(nèi)容，不能改變?nèi)萘看笮?

erase成員函數(shù)，它刪除了itVect迭代器指向的元素，并且返回要被刪除的itVect之后的迭代器，迭代器相當(dāng)于一個(gè)智能指針;clear()函數(shù)，只能清空內(nèi)容，不能改變?nèi)萘看笮?如果要想在刪除內(nèi)容的同時(shí)釋放內(nèi)存，那么你可以選擇deque容器。

35、map中[ ]與find的區(qū)別

• map的下標(biāo)運(yùn)算符[ ]的作用是：將關(guān)鍵碼作為下標(biāo)去執(zhí)行查找，并返回對(duì)應(yīng)的值；如果不存在這個(gè)關(guān)鍵碼，就將一個(gè)具有該關(guān)鍵碼和值類型的默認(rèn)值的項(xiàng)插入這個(gè)map。
• map的find函數(shù)：用關(guān)鍵碼執(zhí)行查找，找到了返回該位置的迭代器；如果不存在這個(gè)關(guān)鍵碼，就返回尾迭代器。

36、你了解STL的內(nèi)存優(yōu)化嘛

STL內(nèi)存管理使用二級(jí)內(nèi)存配置器。

1. 第一級(jí)配置器：

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

2. 第二級(jí)配置器：

第一級(jí)配置器直接調(diào)用malloc和free帶來(lái)了幾個(gè)問(wèn)題：

• 內(nèi)存分配/釋放的效率低。
• 當(dāng)配置大量的小內(nèi)存塊時(shí)，會(huì)導(dǎo)致內(nèi)存碎片比較嚴(yán)重。
• 配置內(nèi)存時(shí)，需要額外的部分空間存儲(chǔ)內(nèi)存塊信息，所以配置大量的小內(nèi)存塊時(shí)，還會(huì)導(dǎo)致額外內(nèi)存負(fù)擔(dān)。

如果分配的區(qū)塊小于128bytes，則以內(nèi)存池管理，第二級(jí)配置器維護(hù)了一個(gè)自由鏈表數(shù)組，每次需要分配內(nèi)存時(shí)，直接從相應(yīng)的鏈表上取出一個(gè)內(nèi)存節(jié)點(diǎn)就完成工作，效率很高。

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

37、頻繁對(duì)vector調(diào)用push_back()對(duì)性能的影響和原因

在一個(gè)vector的尾部之外的任何位置添加元素，都需要重新移動(dòng)元素。而且，向一個(gè)vector添加元素可能引起整個(gè)對(duì)象存儲(chǔ)空間的重新分配。重新分配一個(gè)對(duì)象的存儲(chǔ)空間需要分配新的內(nèi)存，并將元素從舊的空間移到新的空間。

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

39、講一講set的用法和它的特點(diǎn)

• 用法：count()-返回某個(gè)值元素的個(gè)數(shù)（set中最多為1）、find()-返回一個(gè)指向被查找到元素的迭代器、equal_range()-返回集合中與給定值相等的上下限的兩個(gè)迭代器。
• 特點(diǎn)：元素不允許有重復(fù)，在默認(rèn)情況下會(huì)對(duì)元素進(jìn)行自動(dòng)排序，數(shù)據(jù)被組織成一棵紅黑樹(shù)，查找的速度非?？欤ǘ郑?，時(shí)間復(fù)雜度是O(logN)，set中的元素不能被修改，只能刪除后再添加。