某日二師兄參加XXX科技公司的C++工程師開發(fā)崗位第24面：

面試官：list用過嗎？

二師兄：嗯，用過。

面試官：請講一下list的實現(xiàn)原理。

二師兄：std::list被稱為雙向鏈表，和C中手寫雙向鏈表本質(zhì)上沒有大的區(qū)別。list對象中有兩個指針，一個指向上一個節(jié)點（node），一個指向下一個節(jié)點（node）。

二師兄：與手寫雙向鏈表不同的是，list中有一個base node，此node并不存儲數(shù)據(jù)，從C++11開始，此node中包含一個size_t類型的成員變量，用來記錄list的長度。

二師兄：所以說從C++11開始，size()的時間復(fù)雜度是O(1)，在此之前是O(N)。

面試官：是每個node都包含一個記錄長度的成員變量嗎？

二師兄：不是，GCC中的實現(xiàn)只有在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
...
};

面試官：添加和刪除元素會導(dǎo)致迭代器失效嗎？

二師兄：并不會，因為在任意位置添加和刪除元素只需要改變prev/next指針指向的對象，而不需要移動元素的位置，所以不會導(dǎo)致迭代器失效。

面試官：list和vector相比，有哪些優(yōu)勢？什么情況下使用list，什么情況下使用vector？

二師兄：主要有2點優(yōu)勢：1.list在隨機插入數(shù)據(jù)不會導(dǎo)致數(shù)據(jù)的搬移。2.list隨機刪除也不會導(dǎo)致數(shù)據(jù)搬移。所以在頻繁的隨機插入/刪除的場景使用list，其他場景使用vector。

面試官：你知道std::sort和list成員函數(shù)sort有什么區(qū)別嗎？

二師兄：std::sort是STL算法的一部分。它排序的容器需要有隨機訪問迭代器，所以只能支持vector和deque。list成員函數(shù)sort用于list排序，時間復(fù)雜度是O(N*logN)。

面試官：forward_list了解嗎？知道如何實現(xiàn)的嗎？

二師兄：std::forward_list是C++11引入的新容器之一。它的底層是單向鏈表，引入它的主要目的是為了達到手寫鏈表的性能。同時節(jié)省了部分內(nèi)存空間。（只有一根指針）

面試官：list在pop_front/pop_back的時候需要注意哪些問題？

二師兄：需要判斷list的size()不能為0，如果list為空，pop_front/pop_back會導(dǎo)致coredump。

面試官：你知道list的成員函數(shù)insert和forward_list的成員函數(shù)的insert_after有什么區(qū)別？

二師兄：兩者都可以向特定位置添加元素。不同的是insert把元素插入到當(dāng)前迭代器前，而insert_after把元素插入到當(dāng)前迭代器后。

面試官：以下代碼的輸出是什么？

#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;
}

二師兄：應(yīng)該是1 3 5。

面試官：遍歷兩個元素數(shù)目相同的vector和list，哪個效率高？

二師兄：vector和list的遍歷效率都是O(N)，效率應(yīng)該是一樣的。

面試官：好的，回去等通知吧。

讓我們看以下二師兄今日的表現(xiàn)：

以下代碼的輸出是什么？

這里實際上會輸出Segmentation fault，原因是因為當(dāng)從list中erase這個node，這個node的prev和next指針被清空，而++it是通過當(dāng)前的node的next指針去找下一個node，解引用一個空指針，導(dǎo)致coredump。

erase函數(shù)返回下一個有效迭代器，所以可以把if(0 == *it % 2) li.erase(it)修改為if(0 == *it % 2) it = li.erase(it)來解決這個問題。

遍歷兩個元素數(shù)目相同的vector和list，哪個效率高？

這里二師兄回答的倒是沒有毛病，但是沒有考慮到緩存問題。實際上因為vector底層采用數(shù)組存儲數(shù)據(jù)，所以它的空間局部性更好，對緩存更友好（Cache-friendly），所以遍歷vector的效率要高于遍歷list。

最后多啰嗦一點，如果你沒有特別的理由選擇其他容器，使用vector是最好的選擇。

二師兄今日的面試旅程結(jié)束了，感謝各位小伙伴的關(guān)注和點贊。為了保證面試質(zhì)量，以后不一定能保證日更。文章中有任何技術(shù)性問題，請留言反饋，在此感謝！

關(guān)注我，帶你21天“精通”C++?。ü奉^）文章來源地址http://www.zghlxwxcb.cn/news/detail-498361.html

到了這里，關(guān)于C++面試八股文：std::vector和std::list，如何選擇？的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！