【C++笔记】STL详解：list容器的实现

Ne0inhk

25 Mar 2026 — 20 min read

前言：

在学习了list容器的基本使用的前提下，本文将重点分析容器类的常用接口及其应用实现。

一、list的成员变量

如图所示，list的底层数据结构为：双向链表

通过下面三个结构体和类实现list：



①结构体 struct list_node ：用来存储链表结点的信息。



②结构体 struct list_iterator：用来封装结点指针，使其能够通过重载运算符访问结点。



③类 class list ：用来实现双向链表的各种增删查改操作

1.1 结构体list_node

template<class T> struct list_node { //对struct list_node重命名为 Node typedef list_node<T> Node; //链表存储的节点值 T _data; //前驱指针 Node* _prev; //后继指针 Node* _next; };

对于双向链表的结点 struct list_node：



①前驱指针：Node* _prev



②后继指针：Node* _next



③链表存储的节点值：T _data;



温馨提示：因为struct list_node过长，通过typedef将其重命名为Node。

如下图所示：

1.2 结构体list_iterator

//迭代器：对结点指针进行封装 template<class T, class Ref, class Ptr> struct list_iterator { //将list_node 结构体类型重命名为Node typedef list_node<T> Node; //将list_iterator 结构体类型重命名为Self typedef list_iterator< T, Ref, Ptr> Self; //定义结点指针 Node* _pnode; };

对于双向链表的迭代器 struct list_iterator：



①重命名结构体名



typedef list_node<T> Node，将list_node 结构体类型重命名为Node

typedef list_iterator< T, Ref, Ptr> Self，将list_iterator 结构体类型重命名为Self



②核心成员变量：Node* _pnode





③模板参数分析：template<class T, class Ref, class Ptr>



核心目的：仅用一个类模板，就能同时生成普通迭代器 (iterator) 和常量迭代器 (const_iterator)，从而避免代码重复。



A.class T



含义: 用于接收容器中实际存储的元素类型。



作用：用于定义迭代器内部节点的数据类型，或者作为某些通用操作的类型推导基础



示例：如果你的容器存储的是整数，那么 T 就是 int。





B.class Ref



含义：迭代器解引用操作符 operator*() 的返回类型



作用：决定了通过迭代器访问元素时，该元素是否可以被修改。



示例：对于普通迭代器，传入 T&（允许修改），对于常量迭代器，传入 const T&（只读）。





C. class Ptr



含义：迭代器箭头操作符 operator->() 的返回类型。



作用：决定了通过迭代器访问元素成员时，底层指针的属性。



示例：对于普通迭代器，传入 T*；对于常量迭代器，传入 const T*。

1.3 类class list

//链表 template<class T> class list { public: //将list_node 结构体类型重命名为Node typedef list_node<T> Node; //将list_iterator 结构体类型重命名为iterator typedef list_iterator<T, T&, T*> iterator; //将list_iterator 结构体类型重命名为const_iterator typedef list_iterator<T, const T&, const T*> const_iterator; private: //哨兵位结点指针 Node* _head; };

双向链表class list：



①重命名结构体名



A. typedef list_node<T> Node ：将list_node 结构体类型重命名为Node



B. typedef list_iterator<T, T&, T*> iterator ：将list_iterator 结构体类型重命名为iterator


C. typedef list_iterator<T, const T&, const T*> const_iterator：将list_iterator 结构体类型重命名为const_iterator




②核心变量 Node* _head：哨兵位结点指针

二、默认成员函数

2.1 list_node的构造函数

list_node的默认构造函数

//默认构造函数 list_node(const T& data = T(), Node* prev = nullptr, Node* next = nullptr) : _data(data) , _prev(prev) , _next(next) {}

①const T& data = T() (数据部分)：



A. T 是模板类型（例如： int 、string...等）



B. const T&：表示我们通过常引用来接收数据，如果是大型对象（比如复杂的结构体），传引用可以避免产生昂贵的拷贝开销。



const 保证我们在构造时不会意外修改传入的原数据。



C. data= T()：这是默认值。如果你创建节点时不给数据，它就会调用类型 T 的默认构造函数。



例如：若T 是 int，默认就是 0 若T 是指针，默认就是空指针。





② Node* prev = nullptr (前驱指针)





③ Node* next = nullptr (后继指针)

2.2 list_iterator的构造函数

list_iterator的默认构造

//迭代器的默认构造函数 list_iterator(Node* pnode = nullptr) :_pnode(pnode) {}

list_iterator的普通构造：允许从普通迭代器构造 const 迭代器

// 允许从普通迭代器构造 const 迭代器 list_iterator(const list_iterator<T, T&, T*>& it) : _pnode(it._pnode) {}

2.3 class list的构造函数

list的无参构造

template<class T> void list<T>::CreateHead() { //1.这里会自动调用带有默认参数的构造函数：data为T(), prev为nullptr, next为nullptr _head = new Node; //2.然后再手动将其构造成一个自循环的结构 _head->_next = _head; _head->_prev = _head; } //无参构造 list() { CreateHead(); }

list的拷贝构造

//拷贝构造函数 list(const list& lt) { CreateHead(); for (const auto& elem : lt) { push_back(elem); } }

list的赋值重载

template<class T> void list<T>::swap(list<T>& lt) { std::swap(_head, lt._head); } //赋值重载函数 list<T>& operator=(list<T> lt) { swap(lt); return *this; }

list的析构函数

//析构函数 ~list() { //释放除哨兵结点以外的结点 clear(); //释放哨兵节点 delete _head; //将哨兵_head指针置空 _head = nullptr; }

三、list的迭代器

3.1 重载运算符*

函数原型：Ref operator*()

函数功能：返回迭代器所指向的值



函数参数：



A.如果是普通迭代器，Ref 被推导为 T&。



B.如果是常量迭代器，Ref 被推导为 const T&。





模拟实现指针解引用的功能：



当我们拿到一个普通指针 int* p 时，我们会用 *p 来获取它指向的数据。



现在你的迭代器是一个自定义的类（class/struct），直接对一个类写 *it 编译器是会报错的。



这段代码就是告诉编译器：“当用户对我的迭代器使用 * 号时，你应该去底层节点里把真实的数据拿出来给他。

代码实现：重载运算符*

//运算符重载 Ref operator*() { return _pnode->_data; }

功能演示：

// 假设这是你写代码时的场景 list<int>::iterator it = mylist.begin(); // 场景 1：读取数据 cout << *it << endl; // 发生的事情：调用 operator*() -> 找到 _pnode -> 返回 _data 的引用 -> 打印出来 // 场景 2：修改数据 (如果 it 是普通迭代器) *it = 999; // 发生的事情：调用 operator*() -> 返回了 _data 的引用 (int&) -> 将 999 赋值给这个引用 -> 节点里的数据真正变成了 999

3.2 重载运算符->

函数原型：Ptr operator->()



函数功能：返回迭代器所指向的元素的地址



函数参数分析：



A. 如果是普通迭代器，Ptr 被推导为 T*，你可以通过箭头修改对象的成员。



B. 如果是常量迭代器，Ptr 被推导为 const T*，你只能通过箭头读取成员，或者调用 const 成员函数，保护了数据的安全。

代码实现：重载运算符->

Ptr operator->() { return &(_pnode->_data); }

C++ 中 operator-> 的“魔法” (隐藏的二次调用)，这是 C++ 语法中一个非常特殊的设计。

假设你链表里存的是一个结构体：

struct Student { string name; int age; };

当你在代码中写下 it->age 时，编译器在底层到底做了什么？



按照字面意思，it.operator->() 返回的是一个 Student* 指针，那岂不是变成了 (Student*)age，这语法不对啊？



实际上，C++ 编译器对 -> 运算符做了特殊处理：如果 operator-> 返回的是一个指针，编译器会自动在后面再加一个隐式的 ->。





真实的底层转换过程是这样的：



①编译器看到 it->age。



②编译器调用 it.operator->()，得到了真实数据的指针：Student* p = &(_pnode->_data)。



③编译器自动帮你对这个指针再调用一次箭头，变成了 p->age。





我们只需要简单地返回数据的地址 &(_pnode->_data)，用户端用起来就极其自然，仿佛迭代器本身就是一个原生指针一样。

3.3 重载运算符前置++

函数原型：Self& operator++()



函数功能：目的是让迭代器指向下一个节点。



函数参数：



Self：typedef list_iterator<T, Ref, Ptr> Self 的别名定义，使用 Self 可以避免在返回值中反复写冗长的模板参数。



Self&：既支持了C++ 的连续调用语法（链式操作），通过引用返回减少了拷贝的消耗。

代码实现：重载运算符前置++

Self& operator++() { _pnode = _pnode->_next; return *this; }

3.4 重载运算符后置++

函数原型：Self operator++(int)



函数功能：目的是让迭代器指向下一个节点。



函数参数：



Self：typedef list_iterator<T, Ref, Ptr> Self 的别名定义，使用 Self 可以避免在返回值中反复写冗长的模板参数。

代码实现：重载运算符后置++

Self operator++(int) { Self tmp = *this; ++(*this); return tmp; }

3.5 重载运算符前置--

函数原型：Self& operator--()



函数功能：目的是让迭代器指向上一个节点。



函数参数：



Self：typedef list_iterator<T, Ref, Ptr> Self 的别名定义，使用 Self 可以避免在返回值中反复写冗长的模板参数。



Self&：既支持了C++ 的连续调用语法（链式操作），通过引用返回减少了拷贝的消耗。

代码实现：重载运算符前置--

Self& operator--() { _pnode = _pnode->_prev; return *this; }

3.6 重载运算符后置--

函数原型：Self operator--(int)



函数功能：目的是让迭代器指向上一个节点。



函数参数：



Self：typedef list_iterator<T, Ref, Ptr> Self 的别名定义，使用 Self 可以避免在返回值中反复写冗长的模板参数。

代码实现：重载运算符后置--

Self operator--(int) { Self tmp = *this; --(*this); return tmp; }

3.7 重载运算符!=

函数原型：bool operator!=(const Self& s)

函数功能：判断两个迭代器指向的位置是否不同

代码实现：重载运算符!=

bool operator!=(const Self& s) { return _pnode != s._pnode; }

3.8 重载运算符==

函数原型：bool operator==(const Self& s)

函数功能：判断两个迭代器指向的位置是否相同

代码实现：重载运算符==

bool operator==(const Self& s) { return _pnode == s._pnode; }

四、list相关函数操作

4.1 begin

函数原型：



① iterator begin();



② const_iterator begin() const



函数功能：返回一个指向 list 中第一个元素的迭代器。

代码实现：

iterator begin() { //指向容器中第一个元素的迭代器 return iterator(_head->_next); //返回匿名对象 } const_iterator begin() const { return const_iterator(_head->_next); //返回匿名对象 }

4.2 end

函数原型：



① iterator end();



② const_iterator end() const



函数功能：返回一个指向 vector 容器中最后一个元素之后的元素。

代码实现

iterator end() { //指向容器中最后一个元素之后位置的迭代器 return iterator(_head); //返回匿名对象 } const_iterator end() const { return const_iterator(_head); //返回匿名对象 }

4.3 insert

函数原型：



template<class T>

iterator insert (iterator position, const T& val);



函数功能：容器通过在指定位置之前插入新元素来扩展。

代码实现：insert函数

template<class T> typename list<T>::iterator list<T>::insert(iterator pos, const T& x) { //申请一个新结点 Node* newnode = new Node(x); //pos位置结点指针 Node* cur = pos._pnode; newnode->_prev = cur->_prev; newnode->_next = cur; cur->_prev->_next = newnode; cur->_prev = newnode; return iterator(newnode); }

如下图所示：插入一个元素

4.4 erase

函数原型：iterator erase (iterator position);

函数功能：从 list 容器中删除单个元素（位置）

代码实现： erase函数

template<class T> typename list<T>::iterator list<T>::erase(iterator pos) { //不能删除哨兵结点 assert(pos._pnode != _head); //pos位置的结点指针 Node* cur = pos._pnode; //pos位置前一个位置的结点指针 Node* prev = cur->_prev; //pos位置后一个位置的结点指针 Node* next = cur->_next; prev->_next = next; next->_prev = prev; //cur->_prev->_next = cur->_next; //cur->_next->_prev = cur->_prev; delete cur; return iterator(next); //通过匿名变量，返回下一个位置的结点指针 }

如下图所示：删除一个元素

4.5 push_back

函数原型：



template<class T>

void push_back (const T& val);



函数功能：在末尾添加元素

代码实现：通过复用insert实现尾插元素

template<class T> void list<T>::push_back(const T& x) { insert(end(), x); }

如下图所示：尾插一个元素

4.6 push_front

函数原型：

template<class T>

void push_front (const T& val);

函数功能：在开头插入元素。

代码实现：通过复用insert实现头插元素

template<class T> void list<T>::push_front(const T& x) { insert(begin(), x); }

如下图所示：头插一个元素

4.7 pop_back

函数原型：void pop_back();

函数功能：删除最后一个元素。

代码实现：通过复用erase函数实现尾删元素

template<class T> void list<T>::pop_back() { erase(--end()); }

如下图所示：尾删一个元素

4.8 pop_front

函数原型：void pop_front();

函数功能：在开头删除元素。

代码实现：复用erase实现头删元素

template<class T> void list<T>::pop_front() { erase(begin()); }

如下图所示：头删一个元素

4.9 clear

函数原型：void clear();

函数功能：从 list 容器中移除所有元素（这些元素将被销毁），使容器的大小变为 0

代码实现：list 容器中移除所有元素

template<class T> void list<T>::clear() { //it 可能是const_iterator 或则 iterator auto it = begin(); while (it != end()) { // erase 返回的是被删结点的下一个位置，所以迭代器不会失效 it=erase(it); } }

既然看到这里了，不妨关注+点赞+收藏，感谢大家，若有问题请指正。