深入解析list：一个完整的C++双向链表实现

template <class T> struct list_node { T _data; // 存储的数据 list_node<T>* _next; // 指向下一个节点 list_node<T>* _prev; // 指向前一个节点 // 构造函数 list_node(const T& data = T()) :_data(data) ,_next(nullptr) ,_prev(nullptr) {} };

详细分析：

模板结构体：支持任意类型的数据
双向指针：_next和_prev实现双向链接，支持双向遍历
默认构造函数：
- 使用T()作为默认值，支持内置类型和自定义类型
- T()对于内置类型是零初始化，对于自定义类型调用默认构造函数
成员初始化列表：高效初始化成员变量
命名约定：使用下划线前缀_data、_next、_prev，常见于成员变量命名

二、迭代器设计（核心部分）

代码展示了迭代器设计的完整演进过程，分为三个阶段：

2.1 第一阶段：两个独立的迭代器类（被注释的初始设计）

这部分代码被注释掉，展示了最初的实现思路：

2.1.1 普通迭代器 `list_iterator<T>`

cpp

template<class T> struct list_iterator { typedef list_node<T> Node; typedef list_iterator<T> Self; // 类成员变量，list迭代器本质是链表节点的指针 Node* _node; // 构造函数 list_iterator(Node* node) :_node(node) {} // 不用写拷贝构造，浅拷贝足够了 // 析构也不用写了 T& operator*() { return _node->_data; // 返回非常量引用 } T* operator->() { return &_node->_data; // 返回非常量指针 } // 简化一下，类型名字有点长 typedef list_iterator<T> Self; // list_iterator<T> operator++() Self& operator++() // 前置++ { _node = _node->_next; return *this; } Self operator++(int) // 后置++ { Self temp = *this; _node = _node->_next; return temp; } Self& operator--() // 前置-- { _node = _node->_prev; return *this; } Self operator--(int) // 后置-- { Self temp = *this; _node = _node->_prev; return temp; } bool operator==(const Self& s)const { return _node == s._node; } bool operator!=(const Self& s)const { return _node != s._node; } };

2.1.2 const迭代器 `list_const_iterator<T>`

cpp

template<class T> struct list_const_iterator { typedef list_node<T> Node; typedef list_const_iterator<T> Self; // 类成员变量，list迭代器本质是链表节点的指针 Node* _node; // 构造函数 list_const_iterator(Node* node) :_node(node) {} // 不用写拷贝构造，浅拷贝足够了 // 析构也不用写了 const T& operator*() { return _node->_data; // 返回常量引用 } const T* operator->() { return &_node->_data; // 返回常量指针 } // 简化一下，类型名字有点长 typedef list_iterator<T> Self; // list_iterator<T> operator++() Self& operator++() // 前置++ { _node = _node->_next; return *this; } Self operator++(int) // 后置++ { Self temp = *this; _node = _node->_next; return temp; } Self& operator--() // 前置-- { _node = _node->_prev; return *this; } Self operator--(int) // 后置-- { Self temp = *this; _node = _node->_prev; return temp; } bool operator==(const Self& s)const { return _node == s._node; } bool operator!=(const Self& s)const { return _node != s._node; } };

2.1.3 第一阶段设计的详细分析：

代码重复问题：
- 两个类几乎完全相同，只有operator*和operator->的返回类型不同
- list_iterator返回T&和T*
- list_const_iterator返回const T&和const T*
- 其他所有代码（构造函数、自增自减、比较操作符）都完全相同
设计思想：
- 迭代器本质上是指向链表节点的指针
- 通过操作符重载提供类似指针的语法
- Self类型别名简化代码编写
优缺点：
- 优点：逻辑清晰，分别处理常量和非常量迭代器
- 缺点：代码重复严重，违反DRY原则（Don't Repeat Yourself）

2.2 第二阶段：改进的单一模板迭代器

这是当前使用的实现，解决了代码重复问题：

cpp

template<class T, class Ref, class Ptr> struct list_iterator { typedef list_node<T> Node; typedef list_iterator<T, Ref, Ptr> Self; // 类成员变量，list迭代器本质是链表节点的指针 Node* _node; // 构造函数 list_iterator(Node* node) :_node(node) {} // 不用写拷贝构造，浅拷贝足够了 // 析构也不用写了 Ref operator*() { return _node->_data; // Ref可能是T&或const T& } Ptr operator->() { return &_node->_data; // Ptr可能是T*或const T* } // 简化一下，类型名字有点长 typedef list_iterator<T> Self; // list_iterator<T> operator++() Self& operator++() // 前置++ { _node = _node->_next; return *this; } Self operator++(int) // 后置++ { Self temp = *this; _node = _node->_next; return temp; } Self& operator--() // 前置-- { _node = _node->_prev; return *this; } Self operator--(int) // 后置-- { Self temp = *this; _node = _node->_prev; return temp; } bool operator==(const Self& s)const { return _node == s._node; } bool operator!=(const Self& s)const { return _node != s._node; } };

2.2.1 第二阶段设计的详细分析：

模板参数设计：
- T：元素类型
- Ref：解引用操作符的返回类型（引用）
- Ptr：箭头操作符的返回类型（指针）
类型别名系统：cpp// 在list类中的定义 typedef list_iterator<T, T&, T*> iterator; typedef list_iterator<T, const T&, const T*> const_iterator;
- iterator：传递T&和T*，返回非常量引用和指针
- const_iterator：传递const T&和const T*，返回常量引用和指针
优势：
- 代码复用：一个模板实现两种迭代器
- 编译时多态：通过模板参数决定行为
- 类型安全：编译时检查类型一致性
设计模式：
- 这是模板元编程的典型应用
- 通过模板参数实现策略模式

2.3 迭代器操作符的详细分析

2.3.1 解引用操作符 `operator*()`

cpp

Ref operator*() { return _node->_data; }

返回节点数据的引用
Ref模板参数决定是常量引用还是非常量引用
使得*it可以访问或修改元素值

2.3.2 箭头操作符 `operator->()`

cpp

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

返回指向节点数据的指针
Ptr模板参数决定是常量指针还是非常量指针
使得it->member可以访问结构体/类成员

2.3.3 自增操作符

前置自增：

cpp

Self& operator++() { _node = _node->_next; // 移动到下一个节点 return *this; // 返回当前对象的引用 }

修改自身状态
返回引用，支持链式调用

后置自增：

cpp

Self operator++(int) { Self temp = *this; // 保存当前状态 _node = _node->_next; // 移动到下一个节点 return temp; // 返回原来的状态 }

参数int仅用于区分前置和后置版本
返回临时对象，不能链式调用
性能略低于前置版本

2.3.4 自减操作符

实现原理与自增类似，只是移动方向相反。

2.3.5 比较操作符

cpp

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

比较底层节点指针
都是const成员函数，支持const对象比较
简单高效，时间复杂度O(1)

三、链表类实现

3.1 成员变量

cpp

private: Node* _head; // 指向哨兵节点 size_t _size; // 链表大小

详细分析：

哨兵节点设计：
- _head指向一个不存储有效数据的节点
- 链表为空时：_head->_next == _head且_head->_prev == _head
- 简化边界条件处理，避免空指针检查
大小维护：
- 维护_size变量使size()操作为O(1)
- 否则需要遍历链表计算大小，时间复杂度O(n)

3.2 迭代器访问函数

3.2.1 begin() 和 end()

cpp

iterator begin() { iterator it(_head->_next); // 第一个有效元素 return it; } iterator end() { iterator it(_head); // 哨兵节点作为结束位置 return it; }

代码中的三种等价写法（注释中展示）：

cpp

// 写法1：显式创建临时对象（当前使用的写法） iterator it(_head->_next); return it; // 写法2：返回匿名对象 return iterator(_head->_next); // 写法3：依赖隐式类型转换（单参数构造函数） return _head->_next; // 编译器自动转换为iterator

3.2.2 const版本的begin()和end()

cpp

const_iterator begin()const { const_iterator it(_head->_next); return it; } const_iterator end()const { const_iterator it(_head); return it; }

用于const对象
返回const_iterator，只读访问

3.3 初始化函数

cpp

void empty_init() { _head = new Node; // 创建哨兵节点 _head->_next = _head; // 指向自己 _head->_prev = _head; // 指向自己 _size = 0; // 大小为0 }

所有构造函数的基础
创建自循环的哨兵节点
注意：哨兵节点的_data使用默认构造函数初始化

3.4 构造函数

3.4.1 默认构造函数

cpp

list() { empty_init(); }

创建一个空链表
只有哨兵节点

3.4.2 初始化列表构造函数

cpp

list(initializer_list<T> il) { empty_init(); for (auto& e : il) { push_back(e); // 逐个添加元素 } }

支持现代C++语法：

cpp

yyq::list<int> lst = {1, 2, 3, 4, 5}; // 初始化列表

3.4.3 拷贝构造函数

cpp

list(const list<T>& lt) { empty_init(); for (auto& e : lt) { push_back(e); // 深拷贝每个元素 } }

详细分析：

深拷贝：创建新节点复制数据
使用范围for循环：依赖迭代器支持
时间复杂度：O(n)，n为源链表大小
异常安全：如果push_back抛出异常，已分配的资源需要清理

3.5 赋值操作符

3.5.1 交换函数

cpp

void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); }

使用std::swap交换指针和大小
效率高，不涉及元素复制

3.5.2 赋值操作符（现代实现）

cpp

list<T>& operator=(list<T> lt) { swap(lt); return *this; }

拷贝并交换技法详细分析：

参数lt是值传递，自动调用拷贝构造函数
交换当前对象和lt的资源
lt离开作用域时自动析构，释放原资源
异常安全：如果拷贝构造失败，不会修改当前对象
自赋值安全：参数是值传递，不会影响自赋值

3.6 析构函数

cpp

~list() { clear(); // 删除所有有效节点 delete _head; // 删除哨兵节点 _head = nullptr; }

详细分析：

先调用clear()删除所有数据节点
再删除哨兵节点
将指针置为nullptr避免悬空指针
注意：对于自定义类型，会调用每个元素的析构函数

3.7 清空链表

cpp

void clear() { // iterator it = begin(); auto it = begin(); while (it != end()) { it = erase(it); // 返回下一个迭代器 } }

详细分析：

使用auto：简化类型声明
安全删除方式：使用erase的返回值更新迭代器
避免迭代器失效：直接使用erase(it)会使it失效
时间复杂度：O(n)，n为链表大小

四、链表操作实现

4.1 插入操作

4.1.1 通用插入函数

cpp

iterator insert(iterator pos, const T& x) { Node* newnode = new Node(x); // 创建新节点 Node* cur = pos._node; // 当前位置节点 Node* prev = cur->_prev; // 前一个节点 // 连接新节点 newnode->_next = cur; cur->_prev = newnode; newnode->_prev = prev; prev->_next = newnode; ++_size; // 更新大小 return newnode; // 返回指向新节点的迭代器 }

连接步骤详细分析：

newnode->_next = cur：新节点的next指向当前位置
cur->_prev = newnode：当前位置的prev指向新节点
newnode->_prev = prev：新节点的prev指向前一个节点
prev->_next = newnode：前一个节点的next指向新节点

返回值：返回指向新插入元素的迭代器，符合STL规范

4.1.2 被注释的push_back实现

cpp

//void push_back(const T& x) //{ // Node* newnode = new Node(x); // Node* tail = _head->_prev; // 当前尾节点 // // tail->_next = newnode; // newnode->_prev = tail; // // newnode->_next = _head; // _head->_prev = newnode; // // ++_size; //}

详细分析：

直接实现：不依赖insert
效率：可能比insert(end(), x)略高（少一次函数调用）
代码复用：当前实现使用insert(end(), x)，更简洁
逻辑：在哨兵节点前插入，即链表尾部

4.1.3 头部插入

cpp

void push_front(const T& x) { insert(begin(), x); // 在开始位置插入 }

4.1.4 尾部插入

cpp

void push_back(const T& x) { insert(end(), x); // 在结束位置前插入 }

注意：插入到end()位置实际上是在哨兵节点前插入，即链表尾部

4.2 删除操作

4.2.1 通用删除函数

cpp

iterator erase(iterator pos) { assert(pos != end()); // 不能删除哨兵节点 Node* next = pos._node->_next; Node* prev = pos._node->_prev; // 跳过要删除的节点 prev->_next = next; next->_prev = prev; delete pos._node; // 释放节点内存 --_size; // 更新大小 return next; // 返回下一个有效迭代器 }

详细分析：

断言检查：确保不删除哨兵节点
连接调整：
- prev->_next = next：前一个节点跳过当前节点
- next->_prev = prev：后一个节点跳过当前节点
内存释放：delete节点，调用元素析构函数
返回值：返回下一个有效迭代器，避免迭代器失效

4.2.2 被注释的erase实现

cpp

//void erase(iterator pos) //{ // Node* cur = pos._node; // Node* prev = cur->_prev; // Node* next = cur->_next; // // prev->_next = next; // next->_prev = prev; // // delete cur; // cur = nullptr; // // --_size; //}

对比分析：

没有返回值：调用者无法知道删除后的下一个有效位置
迭代器失效：调用后pos失效，但调用者不知道
当前实现更好：返回下一个迭代器，更安全

4.2.3 头部删除

cpp

void pop_front() { erase(begin()); // 删除第一个元素 }

4.2.4 尾部删除

cpp

void pop_back() { // erase(end()._node->_prev); erase(--end()); // 删除最后一个元素 }

两种写法：

erase(--end())：使用迭代器操作
erase(end()._node->_prev)：直接访问节点指针

4.3 容量相关函数

cpp

size_t size()const { return _size; // 直接返回存储的大小 } bool empty()const { return _size == 0; // 检查大小是否为0 // 或者: return _head->_next == _head; }

详细分析：

O(1)复杂度：维护_size变量
注释中的替代方案：_head->_next == _head检查链表是否为空
const成员函数：可以用于const对象

五、辅助函数

5.1 通用容器打印函数

cpp

template<class Container> void print_container(const Container& con) { // 方法1：使用迭代器 typename Container::const_iterator it = con.begin(); while (it != con.end()) { cout << *it << " "; ++it; // 注意：原代码这里缺少++it，是bug } cout << endl; // 方法2：使用范围for循环 for (auto e : con) { cout << e << " "; } cout << endl; }

详细分析：

模板函数：可以打印任何支持迭代器的容器
typename关键字：
- 必须使用，告诉编译器Container::const_iterator是一个类型
- 因为Container是模板参数，编译器不知道const_iterator是类型还是静态成员
Bug：原代码while循环中缺少++it，会导致死循环
两种遍历方式：
- 传统迭代器遍历
- 范围for循环（依赖容器的begin()和end()）
通用性：可以用于yyq::list、yyq::vector等任何STL兼容容器

六、设计模式与编程技巧

6.1 哨兵节点模式

目的：简化边界条件处理
实现：创建不存储数据的头节点
优点：统一插入删除逻辑，避免空指针检查

6.2 拷贝并交换惯用法

目的：实现异常安全的赋值操作
实现：参数值传递 + swap
优点：自动处理自赋值，异常安全

6.3 模板元编程

目的：代码复用，编译时多态
实现：迭代器模板参数化
优点：消除代码重复，类型安全

6.4 RAII（资源获取即初始化）

目的：自动管理资源
实现：构造函数分配，析构函数释放
优点：避免资源泄漏

七、存在的问题与改进建议

7.1 存在的问题

异常安全性不足：
- new可能失败，抛出std::bad_alloc
- 插入操作中如果new失败，应保持链表不变
缺少移动语义支持（C++11）：
- 移动构造函数
- 移动赋值运算符
- emplace操作
迭代器安全性：
- 缺少迭代器有效性验证
- 多线程环境不安全
功能不完整：
- 缺少反向迭代器
- 缺少sort、merge、unique等算法
- 缺少resize、assign等方法

7.2 改进建议

7.2.1 异常安全改进

cpp

iterator insert(iterator pos, const T& x) { Node* newnode = nullptr; try { newnode = new Node(x); // 可能抛出异常 } catch (...) { // 如果new失败，链表保持不变 throw; // 重新抛出异常 } // ... 连接操作（不会抛出异常） return iterator(newnode); }

7.2.2 添加移动语义支持

cpp

// 移动构造函数 list(list&& other) noexcept : _head(other._head) , _size(other._size) { other._head = nullptr; other._size = 0; } // 移动赋值运算符 list& operator=(list&& other) noexcept { if (this != &other) { clear(); delete _head; _head = other._head; _size = other._size; other._head = nullptr; other._size = 0; } return *this; } // emplace操作 template <typename... Args> iterator emplace(iterator pos, Args&&... args) { Node* newnode = new Node(T(std::forward<Args>(args)...)); // ... 连接操作 return iterator(newnode); }

7.2.3 添加反向迭代器

cpp

typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

八、教学价值与学习要点

8.1 数据结构学习

双向链表的基本操作
哨兵节点的优势与应用
链表与数组的性能对比

8.2 C++模板编程

类模板与函数模板
模板参数推导
模板元编程技巧

8.3 STL设计思想

迭代器模式
容器与算法的分离
泛型编程哲学

8.4 现代C++特性

异常安全编程
RAII原则
移动语义

九、总结

这个yyq::list实现是一个优秀的教学范例，它完整展示了：

从简单到复杂的演进过程：
- 初始的两个独立迭代器类
- 改进的模板化迭代器
- 展示了代码重构和优化的思路
完整的功能实现：
- 链表节点的创建与连接
- 迭代器的完整实现
- 基本操作的实现
- 拷贝控制和资源管理
现代C++编程实践：
- 模板编程
- 异常安全考虑
- 代码复用技巧
STL兼容性设计：
- 标准的迭代器接口
- 容器约定的方法
- 与算法协同工作

虽然与标准库的std::list相比还有差距，但作为一个教学实现，它完美展示了双向链表和迭代器的核心原理，是学习C++容器设计和模板编程的优秀范例。通过分析这个实现，可以深入理解STL的设计哲学和实现细节。

概述

一、整体架构与设计

1.1 命名空间与头文件保护

1.2 链表节点设计

二、迭代器设计（核心部分）

2.1 第一阶段：两个独立的迭代器类（被注释的初始设计）

2.1.1 普通迭代器 list_iterator<T>

2.1.2 const迭代器 list_const_iterator<T>

2.1.3 第一阶段设计的详细分析：

2.2 第二阶段：改进的单一模板迭代器

2.2.1 第二阶段设计的详细分析：

2.3 迭代器操作符的详细分析

2.3.1 解引用操作符 operator*()

2.3.2 箭头操作符 operator->()

2.3.3 自增操作符

2.3.4 自减操作符

2.3.5 比较操作符

三、链表类实现

3.1 成员变量

3.2 迭代器访问函数

3.2.1 begin() 和 end()

3.2.2 const版本的begin()和end()

3.3 初始化函数

3.4 构造函数

3.4.1 默认构造函数

3.4.2 初始化列表构造函数

3.4.3 拷贝构造函数

3.5 赋值操作符

3.5.1 交换函数

3.5.2 赋值操作符（现代实现）

3.6 析构函数

3.7 清空链表

四、链表操作实现

4.1 插入操作

4.1.1 通用插入函数

4.1.2 被注释的push_back实现

4.1.3 头部插入

4.1.4 尾部插入

4.2 删除操作

4.2.1 通用删除函数

4.2.2 被注释的erase实现

4.2.3 头部删除

4.2.4 尾部删除

4.3 容量相关函数

五、辅助函数

5.1 通用容器打印函数

六、设计模式与编程技巧

6.1 哨兵节点模式

6.2 拷贝并交换惯用法

6.3 模板元编程

6.4 RAII（资源获取即初始化）

七、存在的问题与改进建议

7.1 存在的问题

7.2 改进建议

7.2.1 异常安全改进

7.2.2 添加移动语义支持

7.2.3 添加反向迭代器

八、教学价值与学习要点

8.1 数据结构学习

8.2 C++模板编程

8.3 STL设计思想

8.4 现代C++特性

九、总结

Read more

Java新手入门：从零开始安装JDK并配置环境变量

Java 大视界 -- Java 大数据在智能物流仓储货位优化与库存周转率提升中的应用实战

飞算 JavaAI 转 SpringBoot 项目沉浸式体验：高效开发在线图书借阅平台

小智医疗（尚硅谷项目笔记）Java+AI(基于Langchain4j）

2.1.1 普通迭代器 `list_iterator<T>`

2.1.2 const迭代器 `list_const_iterator<T>`

2.3.1 解引用操作符 `operator*()`

2.3.2 箭头操作符 `operator->()`