当前位置：首页 > backend >正文

探索 List 的奥秘：自己动手写一个 STL List✨

backend 2025/8/24 14:33:54

📖引言

大家好！今天我们要一起来揭开 C++ 中 list 容器的神秘面纱——不是直接用 STL，而是亲手实现一个简化版的 list！🎉

你是不是曾经好奇过：

list 是怎么做到高效插入和删除的？🔍
迭代器到底是怎么工作的？🔄
为什么 list 是双向循环链表？🔗

在这篇博客中，我们将从零开始，一步步实现一个名为 amber::list 的模板类，包含：

✅ 双向链表结构 list_node
✅ 迭代器 __list_iterator（支持 ++、--、*、->）
✅ 常用接口：push_back、push_front、insert、erase、clear...
✅ 拷贝构造、赋值重载、初始化列表构造
✅ 异常安全的资源管理 🛡️

我们还会深入探讨：

🧠 迭代器的设计哲学
🔄 双向链表的插入与删除逻辑
💡 模板编程中的技巧与陷阱

不管你是刚学完数据结构，还是想深入理解 STL 的实现，这篇博客都会让你收获满满！🌟

接下来，就让我们一起进入 list 的世界吧！👇

在 list 的模拟实现中，我们一共会用到三个类，分别是 list_node，__list_iterator 和 list。我们需要多加关注的是如何利用c++的特性去模拟实现STL中的list（例如一个模板完成两种迭代器的实现）。

list<T> │├── 包含多个 list_node<T> 节点│└── 提供 iterator 和 const_iterator│└── 由 __list_iterator<T, Ref, Ptr> 实现│└── 内部持有 list_node<T>* 用于遍历

`1. list_node<T>`：链表节点类

template<class T>
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;explicit list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}
};

list_node<T>是链表节点类，用于list类的数据存储。
这个类一共有三个成员对象，存储数据的_data和用于指向前后节点的_prev和_next指针。

list_node构造函数初始化了一个阶段存放了数据 x，这里的参数接口设计采用了c++的匿名对象和参数缺省值的语法，然后赋值给const修饰的T类型引用的x形参，缺省值用匿名对象有效的防止了创建节点时未传参的情况。
如果没传参在会创建一个T类型的对象并且调用对应的默认构造，可以在不传参构建一个节点（在用list创建的链表对象的哨兵位节点_head就采用了这一特性，哨兵位节点只用于找链表的头与尾，不存储有效数据）。
我们通过初始化列表，在将x赋值给_data后把_next和_prev指针都初始化为nullptr空指针。
然后我们explicit关键字修饰构造函数防止了隐式类型转换，在编译时能够有效的发现代码编写错误。

`2. __list_iterator<T, Ref, Ptr>`：迭代器类

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){}//成员数据访问运算符Ref operator*(){return _node->_data;//返回当前节点的数据类型对象}//自定义类型成员数据访问运算符Ptr operator->(){return &_node->_data;}//前置++Self& operator++(){_node = _node->_next;//迭代器只想下一个节点return *this;//返回当前迭代器对象}//后置++Self operator++(int){Node* temp = _node;//创建一个临时对象保存当前迭代器指向_node = _node->_next;//迭代器指向下一个节点return temp;//返回临时对象}//前置--Self& operator--(){_node = _node->_prev;//迭代器指向当前节点的前一个节点return *this;//返回当前对象}//后置--Self operator--(int){Node* temp = _node;//创建一个临时对象保存当前迭代器指向_node = _node->_prev;//迭代器指向当前节点的前一个节点return temp;//返回临时对象}//不等于比较运算符bool operator!=(const Self& it) const{return _node != it._node;//两个迭代器指向节点不相等返回true}//等于比较运算符bool operator==(const Self& it) const{return _node == it._node;//两个迭代器指向节点相等返回true}
};

迭代器类采用了三个模版参数 数据类型T，数据对象引用 Ref 和 控制访问权限参数 Ptr。
T：元素类型。
Ref：引用类型（T& 或 const T&）。
Ptr：指针类型（T* 或 const T*）。
该类有一个成员对象为_node，并且把list_node<T>类型和__list_iterator<T, Ref, Ptr>类型进行了typedef为Node和Self便于读写以及实现不同版本的迭代器iterator和常量迭代器const_iterator，由于两种迭代器的实现仅仅只有类型的不同，所以我们通过一个迭代器模板就有效地减少了代码的冗余，符合STL一贯的书写习惯。

由于list链表在物理空间上的不连续性，无法通过简单的typedef指针类型来进行迭代器模拟。
基于此原因，我们需要单独把模拟实现的list的迭代器封装到一个类里面，并且自主实现前置后置版本的++和--，以及比较运算符，以便于模拟迭代器的行为有助于list链表对象的遍历。

->操作符

基于->操作符的特殊性，这里我们需要单独讲解一下->操作符：
//自定义类型成员数据访问运算符Ptr operator->(){return &_node->_data;}
对于有多个成员的内置结构类型的指针,我们可以通过一次->访问到其对应的成员，例如：
typedef struct student
{int score;int grade;
}student;student s1 = {99,1};
student* ps1 = &s1;//内置类型箭头访问操作
ps1->grade
而对于list的模板数据类型T也有可能是有多个成员的结构体类型或者类类型，我们就需要重载出对应的->访问操作符，但这里要特殊强调的是编译的底层理解。
void list_test_5()
{student s1 = { 100,1 };student* ps1 = &s1;std::cout << ps1->score << ps1->grade << std::endl;amber::list<student> slt;slt.push_back({ 99,4 });slt.push_back({ 98,5 });slt.push_back({ 97,6 });slt.push_back({ 96,7 });amber::list<student>::iterator sit = slt.begin();while (sit != slt.end()){std::cout << "{" << sit->grade << "," << (*sit).grade << "}" << " ";sit++;}std::cout << std::endl;
}
上面这段代码实现了一个自定义结构体类型的list对象的遍历和成员变量的访问，其中 sit->
grade看似是调用了一次->操作符，但实际上从编译器的角度来看是两次，先调用了一次迭代器的重载，然后调用了内置类型的->操作符。
sit->grade│├── 第1次->：调用 sit.operator->()│     ↓│    返回 student* (指向真实数据)│└── 第2次->：对返回的指针使用 ->↓访问真实的 grade 成员

3. `list<T>`：链表容器类

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;//常量迭代器iterator begin(){return iterator(_head->_next);//返回哨兵位的下一个节点（返回链表的头节点）}iterator end(){return iterator(_head);//返回哨兵位节点}const_iterator begin() const{return const_iterator(_head->_next);//返回哨兵位的下一个节点（返回链表的头节点）}const_iterator end() const{return const_iterator(_head);//返回哨兵位节点}//空链表初始化void empty_init(){_head = new Node;//new一个节点但不初始化赋值给哨兵位节点_head->_next = _head;_head->_prev = _head;//哨兵位的前后指针指向自己}//默认构造函数list(){empty_init();//调用空链表初始化}//拷贝构造函数list(const list<T>& lt){empty_init();//调用空链表初始化for (auto e : lt){push_back(e);//遍历lt对象并逐个尾插到当前链表}}///初始化链表构造list(std::initializer_list<T> il){empty_init();//调用空链表初始化for (const auto e : il){push_back(e);//遍历初始化链表的所有对象并逐个尾插到当前链表}}//成员交换函数void swap(list<T>& lt){std::swap(_head, lt._head);//调用std标准库交换函数，交换哨兵位节点std::swap(_size, lt._size);//调用std标准库交换函数，交换_size}//赋值运算符重载list<T>& operator=(list<T> lt){swap(lt);//创建一个形参lt并与当前对象交换return (*this);//返回当前对象}//析构函数~list(){clear();//清空链表delete _head;//回收哨兵位头节点资源_head = nullptr;//置空}//链表清空void clear(){iterator it = begin();while (it != end()){it = erase(it);//遍历链表并将成员逐个erase掉}}//尾插void push_back(const T& x){insert(end(), x);//复用指定位置插入}//头插void push_front(const T& x){insert(begin(), x);//复用指定位置插入}//尾删void pop_back(){erase(_head->_prev);//复用指定位置删除}//头删void pop_front(){erase(_head->_next);//复用指定位置删除}//指定位置插入iterator insert(iterator pos, const T& val){Node* cur = pos._node;//保存当前指定位置Node* newnode = new Node(val);//new一个新节点出来并用val初始化Node* prev = cur->_prev;//保存当前位置的前一个节点newnode->_next = cur;newnode->_prev = prev;prev->_next = newnode;cur->_prev = newnode;_size++;//更新_sizereturn newnode;//返回新节点}//指定位置删除iterator erase(iterator pos){if (_size == 0 || pos._node == _head){return end();//如果链表为空或者删除头节点时返回end()}Node* cur = pos._node;//保存当前指定位置Node* next = cur->_next;Node* prev = cur->_prev;if (prev != nullptr && next != nullptr)//确保前后指针的有效性{prev->_next = next;next->_prev = prev;//链接删除位置的前后节点}delete cur;//删除当前位置的节点_size--;//更新_sizereturn iterator(next);}//返回容量大小size_t size() const{return _size;}//全局友元交换函数friend void swap(list<T>& lhs, list<T>& rhs);private:Node* _head;//哨兵位节点size_t _size = 0;//节点数量
};// 在类外部定义友元函数模板
template<class T>
void swap(list<T>& lhs, list<T>& rhs) {lhs.swap(rhs);
}