某日二师兄加入 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++！（狗头）