《C++：从代码到机器》：面试官：“说说 list 怎么模拟实现？” 我掏出这份代码，他点头了

Ne0inhk

15 Mar 2026 — 9 min read

✨ 孤廖：个人主页

🎯 个人专栏：《C++：从代码到机器》

🎯 个人专栏：《Linux系统探幽：从入门到内核》

🎯 个人专栏：《算法磨剑：用C++思考的艺术》

折而不挠，中不为下

文章目录

正文：
结语

正文：

1.list的介绍与使用

1.1 list的介绍 list的介绍

list的文档介绍

1.2 list的使用

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

1.2.1 list的构造

1.2.2 list iterator的使用

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点

【注意】:

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

list中还有一些操作，需要用到时大家可参阅list的文档说明。

1.2.6 list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭
代器，其他迭代器不会受到影响。vector迭代器失效可以看我主页的一篇文章
《C++：从代码到机器》：vector 的坑只有 C++ 党懂？介绍使用 + 深度剖析 + 模拟实现，帮你全避开

代码解释：

#include<iostream>#include<list>usingnamespace std;// 存在问题的函数voidTestListIterator1(){int array[]={1,2,3,4,5,6,7,8,9,0}; list<int>l(array, array +sizeof(array)/sizeof(array[0]));auto it = l.begin();while(it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值 l.erase(it);++it;}}// 改正后的函数voidTestListIterator(){int array[]={1,2,3,4,5,6,7,8,9,0}; list<int>l(array, array +sizeof(array)/sizeof(array[0]));auto it = l.begin();while(it != l.end()){ l.erase(it++);// it = l.erase(it);}}intmain(){// 可以取消下面的注释来测试函数// TestListIterator1();// TestListIterator();return0;}

2. list的模拟实现

2.1 模拟实现list

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现list。
希望大家有时间可以自己实现一下底层来增强理解

#pragmaonce#include<iostream>#include<assert.h>usingnamespace std;//模拟stl_list//带头双向循环链表namespace twg {template<classT>structlist_node{//数据域 T _data;//指针域 list_node<T>* next; list_node<T>* prev;list_node(const T& data =T()):_data(data),next(nullptr),prev(nullptr){}};template<classT,classRef,classPtr>structlist_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self; Node* _node;//原生指针//默认构造 list_iterator<T, Ref, Ptr>(Node* node):_node(node){}//重载运算符//前置 Self&operator++(){ _node = _node->next;return*this;} Self&operator--(){ _node = _node->prev;return*this;}//后置 Self operator++(int){ Self cur =*this; _node = _node->next;return cur;} Self operator--(int){ Self cur =*this; _node = _node->prev;return cur;}//重载* Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;}booloperator!=(const Self& s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}};template<classT>classlist{typedef list_node<T> Node;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T,const T&,const T*> const_iterator;typedef list<T> container;public:voidempty_init(){ Head =new Node; Head->next = Head; Head->prev = Head; _size =0;}//默认构造list(){empty_init();}//拷贝构造list(const list<T>& s){empty_init();for(auto& e : s){push_back(e);}}//析构~list(){clear();delete Head; Head =nullptr;}//清理 资源voidclear(){auto it =begin();while(it !=end()){ it =erase(it);}}//赋值 list<T>&operator=(const list<T>& s){ list<T>tmp(s);swap(tmp);return*this;}voidswap(container& s){ std::swap(s.Head, Head); std::swap(s._size, _size);}//普通迭代器//begin iterator begin(){return Head->next;//返回时本质是调用了iterator()的构造函数产生了临时对象}//end iterator end(){return Head;}//const 迭代器//begin const_iterator begin()const{return Head->next;//返回时本质是调用了iterator()的构造函数产生了临时对象} const_iterator end()const{return Head;}//insertvoidinsert(iterator pos,const T& x){ Node* cur = pos._node; Node* prev = cur->prev; Node* newnode =new Node; newnode->_data = x; newnode->next = cur; newnode->prev = prev; prev->next = newnode; cur->prev = newnode; _size++;}//erase iterator erase(iterator pos){ iterator tmp = pos;++tmp;assert(pos !=end()); Node* cur = pos._node; iterator next = tmp; cur->prev->next = cur->next; cur->next->prev = cur->prev;delete cur; cur =nullptr; _size--;return next;}//push_bakcvoidpush_back(const T& x){insert(end(), x);}//pop_backvoidpop_back(){assert(_size !=0);erase(--end());}voidprint1()const{auto it =begin();while(it !=end()){ cout <<*it <<" ";++it;} cout << endl;}voidprint2()const{auto it =begin();while(it !=end()){ cout << it->a <<" ";++it;} cout << endl;}boolempty()const{return _size ==0;} size_t size()const{return _size;}private: Node* Head; size_t _size;};voidtest1(){ list<int> l1; l1.push_back(1); l1.push_back(2); l1.push_back(3); l1.push_back(4); l1.push_back(5); l1.print1();}voidtest2(){structAA{int a =1;}; list<AA> l1; l1.push_back({1}); l1.push_back({2}); l1.push_back({3}); l1.push_back({4}); l1.push_back({5}); l1.print2(); l1.clear(); l1.print2();}}

list的模拟实现码云

2.2 list的反向迭代器

通过前面例子知道，反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

【代码解释】:

template<classIterator>classReverseIterator{typedeftypenameIterator::Ref Ref;typedeftypenameIterator::Ptr Ptr;typedef ReverseIterator<Iterator> Self;public:// 构造ReverseIterator(Iterator it):_it(it){}// 具有指针类似行为 Ref operator*(){ Iterator temp = _it;--temp;return*temp;} Ptr operator->(){return&(operator*());}// 迭代器运算符++ Self&operator++(){--_it;return*this;} Self operator++(int){ Self temp(*this);--_it;return temp;} Self&operator--(){++_it;return*this;} Self operator--(int){ Self temp(*this);++_it;return temp;}// 迭代器支持比较booloperator!=(const Self& l)const{return _it != l._it;}booloperator==(const Self& l)const{return _it == l._it;}private: Iterator _it;};

3. list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

结语

看到这里，你已经把 STL 里的 list 彻底“吃透”啦——从双向链表的底层逻辑，到迭代器的使用（连容易栽跟头的“失效坑”都摸清了），再到亲手模拟实现核心功能，最后还能清晰对比它和 vector 在“增删效率”“随机访问”“空间利用”上的差异。这些知识就像给你搭好了“序列式容器”的骨架，让你对 STL 的理解更扎实。

不过，STL 的容器家族里，还有**栈（stack）和队列（queue）**这对“特殊选手”等着我们探索～它们看似简单（只允许一端/两端操作），实则藏着巧妙的“适配器”设计（比如依赖其他容器实现自身逻辑），而且在“表达式求值”“广度优先搜索”等场景中是绝对的主力。下一篇，我们就来解锁栈和队列：从它们的接口用法，到适配器模式的底层原理，再到实战中的经典应用，带你把这对“容器搭档”玩明白。

要是现在对 list 的“迭代器模拟”“反向迭代器包装”还有模糊的地方，不妨再翻翻代码注释；想更直观感受 list 和 vector 的性能差距，也可以自己写个测试（比如批量插入 10 万条数据）。欢迎在评论区分享你和 list 打交道的故事，或者聊聊你对栈和队列的好奇，咱们一起把 STL 从“会用”变成“用得溜”～