IT评测·应用市场-qidao123.com

标题: C++面试八股文：std::vector和std::list，如何选择？ [打印本页]

作者: 鼠扑 时间: 2023-6-24 18:14
标题: 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把元素插入到当前迭代器后。
面试官：以下代码的输出是什么？

[code]#include #include int main(int argc, char const *argv[]){ std::list 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

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)