跳到主要内容
C++ STL list 容器底层实现详解 | 极客日志
C++ 算法
C++ STL list 容器底层实现详解 C++ STL list 容器基于双向链表实现,包含哨兵节点。文章解析了 list_node 结构体存储数据及前后指针,list_iterator 封装指针支持迭代操作。详细说明了构造函数、析构函数、拷贝构造及赋值重载。重点阐述了迭代器运算符重载(*、->、++、--、==、!=)原理。展示了 begin、end、insert、erase、push_back、pop_front 等核心函数的逻辑与代码实现,涵盖头尾插删及清空功能。
魔法巫师 发布于 2026/3/29 更新于 2026/4/23 1 浏览前言
在学习了 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* _prev
后继指针:Node* _next
链表存储的节点值:T _data
typedef 将 list_node 重命名为 Node 以简化代码。
1.2 结构体 list_iterator
对于双向链表的迭代器 struct list_iterator:
重命名结构体名:typedef list_node Node,typedef list_iterator< T, Ref, Ptr> Self。
核心成员变量:Node* _pnode。
模板参数分析:template<class T, class Ref, class Ptr>
class T:用于接收容器中实际存储的元素类型。
class Ref:迭代器解引用操作符 operator*() 的返回类型。普通迭代器传入 T&(允许修改),常量迭代器传入 const T&(只读)。
class Ptr:迭代器箭头操作符 operator->() 的返回类型。普通迭代器传入 T*,常量迭代器传入 const T*。
1.3 类 class list
重命名结构体名:typedef list_node Node,typedef list_iterator<T, T&, T*> iterator,typedef list_iterator<T, const T&, const T*> const_iterator。
核心变量 Node* _head:哨兵位结点指针。
二、默认成员函数
2.1 list_node 的构造函数
const T& data = T() (数据部分):T 是模板类型。const T& 表示常引用接收数据,避免拷贝开销。data= T() 为默认值,若 T 是 int 则为 0,指针则为空。
Node* prev = nullptr (前驱指针)
Node* next = nullptr (后继指针)
2.2 list_iterator 的构造函数 list_iterator 的普通构造:允许从普通迭代器构造 const 迭代器
2.3 class list 的构造函数 template <class T > void list<T>::CreateHead () {
template <class T > void list<T>::swap (list<T>& lt) { std::swap (_head, lt._head); }
三、list 的迭代器
3.1 重载运算符* 函数原型:Ref operator*()
函数功能:返回迭代器所指向的值。
如果是普通迭代器,Ref 被推导为 T&。
如果是常量迭代器,Ref 被推导为 const T&。
模拟实现指针解引用的功能:当用户对我的迭代器使用 * 号时,去底层节点里把真实的数据拿出来给他。
3.2 重载运算符-> 函数原型:Ptr operator->()
函数功能:返回迭代器所指向的元素的地址。
如果是普通迭代器,Ptr 被推导为 T*,可以通过箭头修改对象的成员。
如果是常量迭代器,Ptr 被推导为 const T*,只能通过箭头读取成员。
Ptr operator ->() { return &(_pnode->_data); }
C++ 中 operator-> 的'魔法':如果 operator-> 返回的是一个指针,编译器会自动在后面再加一个隐式的 ->。
struct Student { string name; int age; };
当你在代码中写下 it->age 时,编译器在底层到底做了什么?
编译器看到 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&:既支持了 C++ 的连续调用语法(链式操作),通过引用返回减少了拷贝的消耗。
Self& operator ++() { _pnode = _pnode->_next; return *this ; }
3.4 重载运算符后置++ 函数原型:Self operator++(int)
函数功能:目的是让迭代器指向下一个节点。
Self operator ++(int ) { Self tmp = *this ; ++(*this ); return tmp; }
3.5 重载运算符前置-- 函数原型:Self& operator--()
函数功能:目的是让迭代器指向上一个节点。
Self& operator --() { _pnode = _pnode->_prev; return *this ; }
3.6 重载运算符后置-- 函数原型:Self operator--(int)
函数功能:目的是让迭代器指向上一个节点。
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 中第一个元素的迭代器。
4.2 end
iterator end();
const_iterator end() const
函数功能:返回一个指向 vector 容器中最后一个元素之后的元素。
4.3 insert 函数原型:
template
iterator insert (iterator position, const T& val);
函数功能:容器通过在指定位置之前插入新元素来扩展。
template <class T > typename list<T>::iterator list<T>::insert (iterator pos, const T& x) {
4.4 erase 函数原型:iterator erase (iterator position);
函数功能:从 list 容器中删除单个元素(位置)。
template <class T > typename list<T>::iterator list<T>::erase (iterator pos) {
4.5 push_back 函数原型:
template
void push_back (const T& val);
template <class T > void list<T>::push_back (const T& x) { insert (end (), x); }
4.6 push_front 函数原型:
template
void push_front (const T& val);
template <class T > void list<T>::push_front (const T& x) { insert (begin (), x); }
4.7 pop_back template <class T > void list<T>::pop_back () { erase (--end ()); }
4.8 pop_front template <class T > void list<T>::pop_front () { erase (begin ()); }
4.9 clear 函数功能:从 list 容器中移除所有元素(这些元素将被销毁),使容器的大小变为 0。
template <class T > void list<T>::clear () {
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
Markdown转HTML 将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online