【C++进阶】拒绝黑盒！纯手撕 list 底层源码与迭代器高级封装
✨ 把代码写进星轨，用逻辑丈量宇宙。
| 导航 | 链接 |
|---|---|
| 个人主页 | 🏠 星轨初途 |
| 基础语言专栏 | 💻 C语言 、 📚 数据结构 |
| C++ 进阶专栏 | 🏆 C++学习（竞赛类） 、 ⚙️ C++专栏（开发类） |
| 刷题实战专栏 | 🚀 算法及编程题分享 |
文章目录
环境声明：本文所有底层源码均按 C++11 标准编写；功能测试在 Visual Studio 2022 (MSVC) / GCC 环境下编译通过。文末性能压测数据来自 Windows + MinGW g++ 15.2.0，编译参数为
-std=c++11 -O2 -DNDEBUG，仅用于观察复杂度趋势。实现范围：为了聚焦底层机制，本文模拟实现
list的节点、双向迭代器、构造/拷贝/赋值/析构、插入删除与基础容量接口，不展开 allocator、异常安全和完整标准库适配细节。
前言
在上一篇中，我们详细学习了 list 的基本接口和底层逻辑【C++ 进阶】list 核心机制解析及 vector 巅峰对决。俗话说：“纸上得来终觉浅，绝知此事要躬行”。为了真正吃透双向循环链表的底层机制，彻底明白**“为什么迭代器不能用原生指针”以及“增删查改到底是怎么运作的”**，本篇我们将亲自手撕一个简化版的 list 容器！
一、底层基石：节点类（list_node）的设计
vector 在内存中是连续的，而 list 是由一个个离散的节点拼接而成的双向循环链表。因此，实现 list 的第一步，就是要把底层的“砖块”——节点给造出来。
节点需要存储三样东西：前驱指针（_prev）、后继指针（_next）和数据（_data）。
namespace xingguichutu
{
// 链表节点结构
template<class T>
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _data;
// 构造函数：初始化指针为空，数据设为默认值
list_node(const T& x = T())
: _prev(nullptr)
, _next(nullptr)
, _data(x)
{ }
};
}
💡 【深度解析 & 注意事项】
为什么这里用struct而不是class？
在 C++ 中，struct的成员默认是public的，而class默认是private。因为我们在后续的list和list_iterator类中需要极其频繁地访问节点的_prev、_next和_data，如果用class还需要写繁琐的友元类或get/set方法。为了方便底层开发，这里直接使用struct是最简洁优雅的选择。
二、核心难点：迭代器类（list_iterator）的封装
这是模拟实现 list 中最难、但也最精妙的一环！也是面试中最爱考的知识点。
为什么不能像 vector 一样直接用原生指针当迭代器？
因为 vector 内存连续，原生指针执行 ptr++ 就能完美走到下一个元素。但 list 的节点在内存中是随机乱序分配的，如果直接对节点指针执行 node_ptr++，它只会跳到内存中的下一块未知区域，变成野指针。
为了让使用者能像操作数组一样，用 ++ 走向下一个节点，用 * 获取数据，我们必须把节点指针封装成一个类，并重载相关的运算符。
namespace xingguichutu
{
// ==========================================
// 迭代器结构封装
// 核心设计：用模板参数 Ref 和 Ptr 区分普通和 const 迭代器
// ==========================================
template<class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node; // 内部封装的节点指针
// 构造函数：接收一个节点指针进行初始化
list_iterator(Node* node)
:_node(node)
{ }
// 1. 遍历操作：核心是将 ++ 转化为底层的指针跳转
Self& operator++() // 前置++ (返回变化后的自身)
{
_node = _node->_next; // 走到下一个节点
return *this;
}
Self operator++(int) // 后置++ (返回变化前的副本)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--() // 前置-- (走向前一个节点)
{
_node = _node->_prev;
return *this;
}
Self operator--(int) // 后置--
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
// 2. 比较操作：判断两个迭代器是否指在同一个节点
bool operator!=(const Self& s) { return _node != s._node; }
bool operator==(const Self& s) { return _node == s._node; }
// 3. 访问操作：解引用获取数据
Ref operator*() { return _node->_data; }
Ptr operator->() { return &_node->_data; }
};
}
💡 【深度解析 & 注意事项】
神秘的模板参数Ref和Ptr是干什么用的？
我们需要实现普通迭代器（可读可写）和const迭代器（只读）。如果分开写两个类，代码会极其冗余（99%的代码是一样的，只有返回值不同）。
STL 大佬使用了模板复用的终极技巧：
- 当传入
<T, T&, T*>时，它实例化出的就是普通迭代器。- 当传入
<T, const T&, const T*>时，它实例化出的就是const迭代器。
仅仅多了两个模板参数，就省去了一百多行代码，这就是泛型编程的魅力！
三、顶层调度：链表主类（list）的实现
有了底层的“节点”和作为桥梁的“迭代器”，我们终于可以实现真正的 list 容器了。
1 基本框架与哨兵位初始化
list 本质是一个带头双向循环链表，所以它只需要掌握一个“头指针（哨兵位）”就能顺藤摸瓜找到所有数据。我们还额外增加了一个 _size 变量，这样调用 size() 接口时就是 O ( 1 ) O(1) O(1) 复杂度，不需要遍历全表。
template<class T>
class list
{
typedef list_node<T> Node;
public:
// 利用我们刚才写的迭代器类，一键声明两种迭代器
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
private:
Node* _head; // 指向哨兵位节点
size_t _size; // 记录有效节点数量
// 私有工具函数：初始化哨兵位，让它自己指向自己，形成初始的闭环
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
// ... 后续接口
};
2 默认成员函数（造大楼与拆大楼）
构造、拷贝、赋值、析构是容器的“四大件”。有了上面的 empty_init() 工具函数，构造函数写起来非常轻松。
// 1. 默认构造
list() { empty_init(); }
// 2. 拷贝构造：先建好带哨兵位的空屋子，再把别人的数据挨个尾插进来
list(const list<T>& lt)
{
empty_init();
for (auto& u : lt) { push_back(u); }
}
// 3. 赋值重载 (现代写法：Copy & Swap，极度优雅)
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt) // 传值传参，自动触发拷贝构造生成局部变量 lt
{
swap(lt); // 把局部变量的数据“偷”过来
return *this;
} // 函数结束，局部变量 lt 自动销毁，顺便帮我们清空了旧数据！
// 4. 析构函数：先清空有效节点，最后删掉哨兵位
void clear()
{
iterator it = begin();
while (it != end()) { it = erase(it); }
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
3 迭代器与容量接口
// begin 是第一个有效数据（哨兵位的下一个）
iterator begin() { return _head->_next; }
const_iterator begin() const { return _head->_next; }
// end 就是哨兵位本身（最后一个数据的下一个位置）
iterator end() { return _head; }
const_iterator end() const { return _head; }
size_t size() const { return _size; }
bool empty() const { return _size == 0; }
4 增删查改：深刻体会代码复用的艺术
只要写好了 insert（任意位置插入）和 erase（任意位置删除），头尾的增删不过是这俩函数的马甲罢了！
// 指定位置前插入 (画图连线是关键)
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* new_node = new Node(x);
// prev new_node cur
prev->_next = new_node;
new_node->_prev = prev;
new_node->_next = cur;
cur->_prev = new_node;
_size++;
return iterator(new_node);
}
// 尾插和头插直接复用 insert
void push_back(const T& x) { insert(end(), x); }
void push_front(const T& x) { insert(begin(), x); }
// 删除指定位置节点
iterator erase(iterator pos)
{
assert(pos != end()); // 哨兵位绝对不能删！
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
// 让前后节点直接牵手，跨过 cur
prev->_next = next;
next->_prev = prev;
delete cur; // 释放内存
_size--;
return iterator(next); // 必须返回下一个迭代器，防止外部迭代器失效！
}
// 尾删和头删直接复用 erase
void pop_back() { erase(--end()); }
void pop_front() { erase(begin()); }
💡 【深度解析 & 注意事项】
- 连线顺序：在
insert中，只要你拿到了prev和cur，那四句指针赋值语句的顺序无论怎么打乱都不会出错！这就是双向链表提前保存指针的好处。- 迭代器失效防范：看
erase的最后一行，它返回了被删节点的下一个位置。使用者必须用it = lt.erase(it)来接收，这就是防止迭代器变成野指针的终极武器！
四、终极整合：完整代码与测试
为了避免完整源码变成一大段“代码堆砌”，下面把 list.h 拆成三段展示：节点与迭代器、主类基础框架、增删与资源管理。三段按顺序拼接，就是完整头文件。
- list.h（第一段：节点与迭代器）
#pragma once
#include<iostream>
#include<assert.h>
#include<algorithm>
namespace xingguichutu
{
// ==========================================
// 1. 链表节点结构 (已完成)
// ==========================================
template<class T>
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _data;
list_node(const T& x = T())
: _prev(nullptr)
, _next(nullptr)
, _data(x)
{
}
};
// ==========================================
// 2. 迭代器结构封装
// 核心设计：用模板参数 Ref 和 Ptr 区分普通和 const 迭代器
// ==========================================
template<class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node; // 内部封装的节点指针
// 构造函数
list_iterator(Node* node)
:_node(node)
{
}
// 遍历操作 (++/--)
Self& operator++() // 前置++
{
_node = _node->_next;
return *this;
}
Self operator++(int) // 后置++
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--() // 前置--
{
_node = _node->_prev;
return *this;
}
Self operator--(int) // 后置--
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
// 比较操作
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
// 访问操作 (* / ->)
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
};
有了节点和迭代器之后，接下来组装 list 主类。这里先放生命周期、迭代器入口和容量接口，它们负责把“带头双向循环链表”的基本骨架立起来。
// ==========================================
// 3. 链表主类
// ==========================================
template<class T>
class list
{
typedef list_node<T> Node;
public:
// 声明普通迭代器与 const 迭代器
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
// ------------------------------------------
// 构造、拷贝、赋值与析构
// ------------------------------------------
list() // 默认构造
{
empty_init();
}
list(const list<T>& lt) // 拷贝构造
{
empty_init();
for (auto& u : lt)
{
push_back(u);
}
}
list<T>& operator=(list<T> lt) // 赋值重载 (现代写法)
{
swap(lt);
return *this;
}
~list() // 析构函数
{
clear();
delete _head;
_head = nullptr;
}
// ------------------------------------------
// 迭代器接口
// ------------------------------------------
iterator begin()
{
return _head->_next;//隐式类型转换=return iterator(_head->next)
}
const_iterator begin() const
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator end() const
{
return _head;
}
// ------------------------------------------
// 容量接口
// ------------------------------------------
size_t size() const
{
return _size;
}
bool empty() const
{
return _size == 0;
}
最后再接上最核心的增删逻辑。你会发现头插、尾插、头删、尾删都只是 insert 和 erase 的复用，这也是容器源码里最值得反复品的地方。
// ------------------------------------------
// 增删查改接口
// ------------------------------------------
iterator insert(iterator pos, const T& x) // 指定位置前插入
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* new_node = new Node(x);
prev->_next = new_node;
new_node->_prev = prev;
new_node->_next = cur;
cur->_prev = new_node;
_size++;
return iterator(new_node);
}
void push_back(const T& x) // 尾插
{
insert(end(), x);
}
void push_front(const T& x) // 头插
{
insert(begin(), x);
}
iterator erase(iterator pos) // 删除指定位置节点
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
_size--;
return iterator(next);
}
void pop_back() // 尾删
{
erase(--end());
}
void pop_front() // 头删
{
erase(begin());
}
void clear() // 清空有效节点
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
void swap(list<T>& lt) // 交换底层指针
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
private:
void empty_init() // 私有工具函数：初始化哨兵位
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
Node* _head; // 指向哨兵位节点
size_t _size; // 记录有效节点数量，实现 O(1) 的 size() 接口
};
}
test.cpp 测试运行
#include <iostream>
#include <string>
#include "list.h" // 引入我们自己手写的 list
using namespace std;
template<typename T>
void print_list(const xingguichutu::list<T>& lt, const string& name)
{
cout << name << ": ";
for (auto e : lt) { cout << e << " "; }
cout << "\n";
}
int main()
{
xingguichutu::list<int> lt1;
// 1. 测试增
lt1.push_back(10);
lt1.push_back(20);
lt1.push_front(5);
lt1.insert(lt1.end(), 30);
print_list(lt1, "插入数据后 lt1"); // 预期: 5 10 20 30
// 2. 测试删
lt1.pop_front();
lt1.pop_back();
print_list(lt1, "头尾各删一次 lt1"); // 预期: 10 20
// 3. 测试拷贝和现代写法赋值
xingguichutu::list<int> lt2(lt1);
print_list(lt2, "拷贝构造 lt2"); // 预期: 10 20
xingguichutu::list<int> lt3;
lt3.push_back(999);
lt3 = lt2;
print_list(lt3, "赋值重载 lt3"); // 预期: 10 20
return 0;
}
五、避坑指南：list 迭代器失效深度解析
在之前学习 vector 时，我们知道由于它底层是连续的内存空间，一旦发生扩容（底层换了新房子），或者删除了前面的元素（后面的元素往前补位），都会导致原有的迭代器瞬间变成野指针，或者指向意义错误的元素。这就叫“迭代器失效”。
但在我们刚刚手撕的 list 中，情况却大不相同。由于 list 的底层是内存物理地址不连续的独立节点，它的迭代器失效表现得非常“温柔”且“局部”。
1. 插入操作 (insert / push) —— 永远不会失效
回忆一下我们刚刚写的 insert 源码：我们只是 new 出了一个新节点，然后改变了相邻几个节点的 _next 和 _prev 的指向。
原本那个节点在内存中的物理位置，有发生任何改变吗？
答案是：完全没有！
- 结论：在
list中进行任何插入操作，原有的所有迭代器都不会失效。它们依然忠实地指向原来那块内存地址。这与vector扩容导致的“全军覆没”形成了鲜明对比。
2. 删除操作 (erase / pop) —— 仅当前节点失效
再回忆一下我们写的 erase 源码：我们把当前节点的前后节点连在了一起，然后执行了 delete cur;。
此时，指向 cur 的那个迭代器，它内部封装的 _node 指针变成了一块被释放的死内存（野指针）。如果你再对它进行 ++ 操作，程序就会因为访问非法内存而当场崩溃。
- 结论：在
list中删除节点时，只有指向“当前被删节点”的那个迭代器会失效，指向其他未被删除节点的迭代器依然绝对安全。
3. 经典踩坑现场：删除链表中的所有偶数
这是初学者 100% 会踩坑的经典代码，请看错误示范：
// 💣 错误示范：会导致程序崩溃！
auto it = lt.begin();
while (it != lt.end())
{
if (*it % 2 == 0)
{
lt.erase(it); // ❌ 危险！执行完这句后，it 内部的节点已经被 delete 了！
}
++it; // ❌ 此时 it 是野指针，再对它调用 operator++() 去访问 _next，直接引发段错误！
}
4. 正确的破局之法
解决办法就藏在我们刚刚手写的 erase 源码的最后一行：return iterator(next);。
标准库的设计者早就想到了这个问题，所以规定 erase 操作必须返回被删除节点下一个位置的有效迭代器。我们只需要接收这个返回值，就能让断掉的线索重新接上。
// ✅ 正确示范：完美避开迭代器失效
auto it = lt.begin();
while (it != lt.end())
{
if (*it % 2 == 0)
{
// 用返回值更新 it，此时 it 指向了被删节点的下一个安全位置
it = lt.erase(it);
}
else
{
// 只有在没删除的情况下，才手动向后走一步
++it;
}
}
六、性能压测：list 与 vector 头插的降维打击
前面我们一直在说：list 头插是 O ( 1 ) O(1) O(1)，而 vector 头插是 O ( N ) O(N) O(N)。但只停留在复杂度符号上，读者很难直观看到差距到底会怎样放大。所以这里补一组真实压测，把抽象结论变成可观察数据。
测试目标很明确：连续执行 push_front / insert(begin)，比较二者在头插场景下的时间增长趋势。为了排除 vector 扩容的干扰，代码里先 reserve(n)，这样 vector 的主要成本就集中在“每次头插都要整体搬移已有元素”上。
#include <iostream>
#include <vector>
#include <ctime> // 引入传统的时间头文件
#include "list.h" // 引入我们自己手写的 list
using namespace std;
int main()
{
volatile size_t sink = 0; // 防止编译器极度聪明把测试代码当作“无用代码”优化掉
// 分别测试 1万、5万、10万 级别的数据量
for (int n : {10000, 50000, 100000})
{
size_t list_time = 0;
size_t vector_time = 0;
const int round = 5; // 每个量级跑 5 轮求平均值，让数据更准
for (int r = 0; r < round; ++r)
{
// ==========================================
// 测试 1：list 头插 (O(1) 复杂度)
// ==========================================
xingguichutu::list<int> lt;
size_t begin1 = clock(); // 记录开始时间
for (int i = 0; i < n; ++i)
{
lt.push_front(i);
}
size_t end1 = clock(); // 记录结束时间
list_time += (end1 - begin1);
sink += lt.size();
// ==========================================
// 测试 2：vector 头插 (O(N) 复杂度)
// ==========================================
std::vector<int> v;
v.reserve(n); // ⚠️即使我们提前给了它足量的空间，头插依然要挪动数据！
size_t begin2 = clock(); // 记录开始时间
for (int i = 0; i < n; ++i)
{
// 在头部插入，会导致后面的所有数据统统往后挪一位
v.insert(v.begin(), i);
}
size_t end2 = clock(); // 记录结束时间
vector_time += (end2 - begin2);
sink += v.size();
}
// 打印对比结果
cout << "数据量: " << n << " | "
<< "list 头插平均耗时: " << list_time / round << " ms | "
<< "vector 头插平均耗时: " << vector_time / round << " ms\n";
}
return 0;
}
测试环境：Windows + MinGW g++ 15.2.0，编译参数 -std=c++11 -O2 -DNDEBUG，每组运行 5 轮取平均。
| 数据规模 | 手写 list::push_front 平均耗时 |
vector::insert(begin) 平均耗时 |
|---|---|---|
| 1 万 | <1 ms | 2 ms |
| 5 万 | 1 ms | 66 ms |
| 10 万 | 2 ms | 268 ms |
这组数据的重点不是某个固定数字，而是增长趋势：
list每次头插只需要新建节点，并改动哨兵位附近的_next/_prev指针，单次近似 O ( 1 ) O(1) O(1)，连续插入 N N N 次就是 O ( N ) O(N) O(N)。vector即使提前reserve，每次在头部插入也必须把已有元素整体后移，连续插入的总搬移量是 1 + 2 + . . . + ( N − 1 ) 1 + 2 + ... + (N - 1) 1+2+...+(N−1)，最终接近 O ( N 2 ) O(N^2) O(N2)。
所以，list 并不是“任何场景都比 vector 快”。它赢在任意位置插入删除时不需要搬移其他节点；而 vector 赢在连续内存带来的随机访问和缓存友好性。容器选择的关键，从来不是背结论，而是先看操作模型。
七、总结与反思
经过这次长途跋涉，我们手撕完整个 list 容器，相信你一定会有所感悟：
- 指针封装的艺术：以前觉得迭代器非常神秘，现在恍然大悟，迭代器的本质就是对原生指针的“智能包装”。通过重载运算符，我们强行改变了
++和*的行为，让底层的内存离散存储对上层用户完全透明。这正是面向对象封装思想的巅峰体现。 - 代码复用的优雅：在主类实现中，我们发现只要写好了基础的
insert和erase，所谓的头尾增删，甚至带区间的清空操作，都可以直接调用这俩哥们。不要重复造轮子（Don’t Repeat Yourself），能复用的绝不重写，这不仅减少了代码量，更极大降低了出 Bug 的概率。 - 敬畏内存管理：在编写
clear()和析构函数时，如果少写了一句delete或者指针对接错误，立刻就会引发内存泄漏或越界崩溃。C++ 把内存的控制权完全交给了程序员，这既是权力，更是沉甸甸的责任。
手撕 STL 源码不仅是为了应付面试，更是为了在以后的开发中，当我们写下 lt.push_back() 或者遇到报错时，脑海中能清晰地浮现出底层内存指针是如何交织跳跃的。下一篇我们将讲解栈stack和队列queue，让我们共同进步吧！
更多推荐
32
0- 0
已为社区贡献6条内容
所有评论(0)