文章目錄

• STL篇
• • vector的底層原理（此題本人踩坑，需重視）
  • vector中的reserve和resize的區別
  • vector中的size和capacity的區別
  • vector中erase方法與algorithn中的remove方法區別
  • vector迭代器失效的情況
  • 正確釋放vector的內存(clear(), swap(), shrink_to_fit())
  • vector的內存是分配在棧上還是堆上？（此題比較刁鉆，有陷阱，需要分具體情況回答，本人踩過坑）
  • list的底層原理
  • 什么情況下用vector，什么情況下用list，什么情況下用deque
  • priority_queue的底層原理
  • map 、set、multiset、multimap的底層原理
  • 為何map和set的插入刪除效率比其他序列容器高
  • 為何map和set每次Insert之后，以前保存的iterator不會失效？
  • 當數據元素增多時（從10000到20000），map的set的查找速度會怎樣變化？
  • map 、set、multiset、multimap的特點
  • 為何map和set的插入刪除效率比其他序列容器高，而且每次insert之后，以前保存的iterator不會失效？
  • 為何map和set不能像vector一樣有個reserve函數來預分配數據?
  • set的底層實現實現為什么不用哈希表而使用紅黑樹？
  • hash_map與map的區別？什么時候用hash_map，什么時候用map？
  • 迭代器失效的問題
  • STL線程不安全的情況
  • 正確釋放vector的內存(clear(), swap(),shrink_to_fit())
  • C++ 清空隊列(queue)的幾種方法
  • • 方法一:直接用空的隊列對象賦值
    • 方法二:遍歷出隊列
    • 方法三:使用swap，這種是最高效的，定義clear，保持STL容器的標準。
• 引經據典

---

STL篇

vector的底層原理（此題本人踩坑，需重視）

vector底層是一個動態數組，包含三個迭代器，start和finish之間是已經被使用的空間范圍，end_of_storage是整塊連續空間包括備用空間的尾部。

當空間不夠裝下數據（vec.push_back(val)）時，會自動申請另一片更大的空間（1.5倍或者2倍），然后把原來的數據拷貝到新的內存空間，接著釋放原來的那片空間[vector內存增長機制]。

當釋放或者刪除（vec.clear()）里面的數據時，其存儲空間不釋放，僅僅是清空了里面的數據。因此，對vector的任何操作一旦引起了空間的重新配置，指向原vector的所有迭代器會都失效了。

vector中的reserve和resize的區別

reserve是直接擴充到已經確定的大小，可以減少多次開辟、釋放空間的問題（優化push_back），就可以提高效率，其次還可以減少多次要拷貝數據的問題。reserve只是保證vector中的空間大小（capacity）最少達到參數所指定的大小n。reserve()只有一個參數。
resize()可以改變有效空間的大小，也有改變默認值的功能。capacity的大小也會隨著改變。resize()可以有多個參數。

vector中的size和capacity的區別

size表示當前vector中有多少個元素（finish - start）;
capacity函數則表示它已經分配的內存中可以容納多少元素（end_of_storage - start）;

vector中erase方法與algorithn中的remove方法區別

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

vector迭代器失效的情況

當插入一個元素到vector中，由于引起了內存重新分配，所以指向原內存的迭代器全部失效。
當刪除容器中一個元素后,該迭代器所指向的元素已經被刪除，那么也造成迭代器失效。erase方法會返回下一個有效的迭代器，所以當我們要刪除某個元素時，需要it=vec.erase(it);

正確釋放vector的內存(clear(), swap(), shrink_to_fit())

vec.clear()：清空內容，但是不釋放內存。
vector().swap(vec)：清空內容，且釋放內存，想得到一個全新的vector。
vec.shrink_to_fit()：請求容器降低其capacity和size匹配。
vec.clear();vec.shrink_to_fit();：清空內容，且釋放內存。

vector的內存是分配在棧上還是堆上？（此題比較刁鉆，有陷阱，需要分具體情況回答，本人踩過坑）

需要分情況來回答，如下：

std::vector<T> vec; std::vector<T>* Vec = new std::vector<T>(); std::vector<T*> vec;

對于std::vector<T> vec;

vec在棧上（stack），而其中的元素T保存在堆上（heap）；

對于std::vector<T>* Vec = new std::vector<T>();

vec和其中的元素T都保存在堆上；

對于std::vector<T*> vec;

vec在棧上（stack），而其中的元素T保存在堆上（heap）；和第一種情況類似。

list的底層原理

ist的底層是一個雙向鏈表，使用鏈表存儲數據，并不會將它們存儲到一整塊連續的內存空間中。恰恰相反，各元素占用的存儲空間（又稱為節點）是獨立的、分散的，它們之間的線性關系通過指針來維持,每次插入或刪除一個元素，就配置或釋放一個元素空間。
list不支持隨機存取，如果需要大量的插入和刪除，而不關心隨即存取。

什么情況下用vector，什么情況下用list，什么情況下用deque

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

priority_queue的底層原理

priority_queue：優先隊列，其底層是用堆來實現的。在優先隊列中，隊首元素一定是當前隊列中優先級最高的那一個。

map 、set、multiset、multimap的底層原理

map 、set、multiset、multimap的底層實現都是紅黑樹，epoll模型的底層數據結構也是紅黑樹，linux系統中CFS進程調度算法，也用到紅黑樹。

紅黑樹的特性：

每個結點或是紅色或是黑色；
根結點是黑色；
每個葉結點是黑的；
如果一個結點是紅的，則它的兩個兒子均是黑色；
每個結點到其子孫結點的所有路徑上包含相同數目的黑色結點。

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

因為不需要內存拷貝和內存移動

為何map和set每次Insert之后，以前保存的iterator不會失效？

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

當數據元素增多時（從10000到20000），map的set的查找速度會怎樣變化？

RB-TREE用二分查找法，時間復雜度為logn，所以從10000增到20000時，查找次數從log10000=14次到log20000=15次，多了1次而已。

map 、set、multiset、multimap的特點

set和multiset會根據特定的排序準則自動將元素排序，set中元素不允許重復，multiset可以重復。
map和multimap將key和value組成的pair作為元素，根據key的排序準則自動將元素排序（因為紅黑樹也是二叉搜索樹，所以map默認是按key排序的），map中元素的key不允許重復，multimap可以重復。
map和set的增刪改查速度為都是logn，是比較高效的。

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

存儲的是結點，不需要內存拷貝和內存移動。
插入操作只是結點指針換來換去，結點內存沒有改變。而iterator就像指向結點的指針，內存沒變，指向內存的指針也不會變。

為何map和set不能像vector一樣有個reserve函數來預分配數據?

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

set的底層實現實現為什么不用哈希表而使用紅黑樹？

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

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。

迭代器失效的問題

插入操作：

對于vector和string，如果容器內存被重新分配，iterators,pointers,references失效；如果沒有重新分配，那么插入點之前的iterator有效，插入點之后的iterator失效；
對于deque，如果插入點位于除front和back的其它位置，iterators,pointers,references失效；當我們插入元素到front和back時，deque的迭代器失效，但reference和pointers有效；
對于list和forward_list，所有的iterator,pointer和refercnce有效。 刪除操作：
對于vector和string，刪除點之前的iterators,pointers,references有效；off-the-end迭代器總是失效的；
對于deque，如果刪除點位于除front和back的其它位置，iterators,pointers,references失效；當我們插入元素到front和back時，off-the-end失效，其他的iterators,pointers,references有效；
對于list和forward_list，所有的iterator,pointer和refercnce有效。
對于關聯容器map來說，如果某一個元素已經被刪除，那么其對應的迭代器就失效了，不應該再被使用，否則會導致程序無定義的行為。

STL線程不安全的情況

在對同一個容器進行多線程的讀寫、寫操作時；
在每次調用容器的成員函數期間都要鎖定該容器；
在每個容器返回的迭代器（例如通過調用begin或end）的生存期之內都要鎖定該容器；
在每個在容器上調用的算法執行期間鎖定該容器。

正確釋放vector的內存(clear(), swap(),shrink_to_fit())

#include<iostream> #include<vector> using namespace std; int main() {vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;v.clear();cout << "after clear size:" << v.size() << endl;cout << "after clear capacity:" << v.capacity() << endl;return 0;}

//輸出

size:5 capacity:6 after clear size:0 after clear capacity:6

詳細請查閱：實戰c++中的vector系列–正確釋放vector的內存(clear(), swap(), shrink_to_fit())

C++ 清空隊列(queue)的幾種方法

C++中的queue自身是不支持clear操作的，但是雙端隊列deque是支持clear操作的。

方法一:直接用空的隊列對象賦值

queue<int> q1; // process // ... q1 = queue<int>();

方法二:遍歷出隊列

while (!Q.empty()) Q.pop();

方法三:使用swap，這種是最高效的，定義clear，保持STL容器的標準。

void clear(queue<int>& q) {queue<int> empty;swap(empty, q); }

引經據典

感謝以下博主的文章，如有遺漏，請聯系我添加，謝謝!

---

https://blog.csdn.net/weixin_43519366/article/details/118634870

https://blog.csdn.net/qq_31349683/article/details/112390579

總結

以上是生活随笔為你收集整理的C++面试八股文快问快答のSTL篇的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。