C++面试八股文:std::vector和std::list,如何选择?
某日二师兄参加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++!(狗头)