某日二師兄參加XXX科技公司的C++工程師開發崗位第24面：
面試官：
list用過嗎？二師兄：嗯，用過，
面試官：請講一下
list的實作原理，二師兄：
std::list被稱為雙向鏈表，和C中手寫雙向鏈表本質上沒有大的區別，list物件中有兩個指標，一個指向上一個節點（node），一個指向下一個節點（node），二師兄：與手寫雙向鏈表不同的是，
list中有一個base node，此node并不存盤資料，從C++11開始，此node中包含一個size_t型別的成員變數，用來記錄list的長度，二師兄：所以說從C++11開始，
size()的時間復雜度是O(1)，在此之前是O(N)，面試官：是每個
node都包含一個記錄長度的成員變數嗎？二師兄：不是，GCC中的實作只有在
header node上記錄了長度資訊，其他node并沒有記錄，
struct _List_node_base
{
_List_node_base* _M_next;
_List_node_base* _M_prev;
...
};
struct _List_node_header : public _List_node_base
{
#if _GLIBCXX_USE_CXX11_ABI
std::size_t _M_size;
#endif
...
};
面試官：添加和洗掉元素會導致迭代器失效嗎？
二師兄：并不會，因為在任意位置添加和洗掉元素只需要改變
prev/next指標指向的物件，而不需要移動元素的位置，所以不會導致迭代器失效，面試官：
list和vector相比，有哪些優勢？什么情況下使用list，什么情況下使用vector？二師兄：主要有2點優勢：1.
list在隨機插入資料不會導致資料的搬移，2.list隨機洗掉也不會導致資料搬移，所以在頻繁的隨機插入/洗掉的場景使用list，其他場景使用vector，面試官：你知道
std::sort和list成員函式sort有什么區別嗎？二師兄：
std::sort是STL演算法的一部分，它排序的容器需要有隨機訪問迭代器，所以只能支持vector和deque，list成員函式sort用于list排序，時間復雜度是O(N*logN)，面試官：
forward_list了解嗎？知道如何實作的嗎？二師兄：
std::forward_list是C++11引入的新容器之一，它的底層是單向鏈表，引入它的主要目的是為了達到手寫鏈表的性能，同時節省了部分記憶體空間，（只有一根指標）
面試官：
list在pop_front/pop_back的時候需要注意哪些問題？二師兄：需要判斷
list的size()不能為0，如果list為空，pop_front/pop_back會導致coredump，面試官：你知道
list的成員函式insert和forward_list的成員函式的insert_after有什么區別？二師兄：兩者都可以向特定位置添加元素，不同的是
insert把元素插入到當前迭代器前，而insert_after把元素插入到當前迭代器后，面試官：以下代碼的輸出是什么？
#include <iostream>
#include <list>
int main(int argc, char const *argv[])
{
std::list<int> li = {1,2,3,4,5,6};
for(auto it = li.begin(); it!= li.end(); ++it)
{
if(0 == *it % 2) li.erase(it);
}
for(auto& i : li) std::cout << i << " ";
std::cout << std::endl;
}
二師兄：應該是
1 3 5，面試官：遍歷兩個元素數目相同的
vector和list，哪個效率高？二師兄：
vector和list的遍歷效率都是O(N)，效率應該是一樣的，面試官：好的，回去等通知吧，
讓我們看以下二師兄今日的表現：
以下代碼的輸出是什么？
這里實際上會輸出Segmentation fault，原因是因為當從list中erase這個node，這個node的prev和next指標被清空，而++it是通過當前的node的next指標去找下一個node，解參考一個空指標，導致coredump，
erase函式回傳下一個有效迭代器，所以可以把if(0 == *it % 2) li.erase(it)修改為if(0 == *it % 2) it = li.erase(it)來解決這個問題，
遍歷兩個元素數目相同的
vector和list，哪個效率高？
這里二師兄回答的倒是沒有毛病，但是沒有考慮到快取問題，實際上因為vector底層采用陣列存盤資料，所以它的空間區域性更好，對快取更友好（Cache-friendly），所以遍歷vector的效率要高于遍歷list，
最后多啰嗦一點，如果你沒有特別的理由選擇其他容器，使用vector是最好的選擇，
二師兄今日的面試旅程結束了，感謝各位小伙伴的關注和點贊，為了保證面試質量，以后不一定能保證日更，文章中有任何技術性問題，請留言反饋，在此感謝！
關注我，帶你21天“精通”C++！（狗頭）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/555856.html
標籤：其他
上一篇：Python潮流周刊#8：Python 3.13 計劃將解釋器提速 50%！
下一篇：返回列表