在C++项目中，如何根据具体需求精准选择std::vector还是std::list？

本文共计1589个文字，预计阅读时间需要7分钟。

某日二哥参加XXX科技有限公司的C++工程师开发岗位第24面：面试官：list 用过吗？二哥：嗯，用过。面试官：请讲一下list的实现原理。二哥：std::list 被称为双向链表，C++中是手动实现的。

某日二师兄参加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并没有记录。