完整实现了 C++ 模板类 yyq::list，模拟 std::list 双向链表。涵盖节点设计、迭代器演进（从双类到单模板）、核心操作（插入删除）、内存管理（RAII、拷贝交换）及改进建议（移动语义、异常安全）。适合学习数据结构与 STL 设计思想。
这是一个完整的模板类 yyq::list 的实现，模仿 C++ 标准库中的 。作为 STL 中最经典的双向链表容器，list 的实现展示了 C++ 模板编程、迭代器设计、链表操作和内存管理的核心技术。本文将完整分析所有代码，包括被注释的部分，不遗漏任何细节。
std::listnamespace yyq { // 链表实现 }
yyq 避免与标准库冲突#pragma once 防止头文件重复包含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，常见于成员变量命名代码展示了迭代器设计的完整演进过程，分为三个阶段：
这部分代码被注释掉，展示了最初的实现思路：
list_iterator<T>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; }
};
list_const_iterator<T>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; }
};
operator* 和 operator-> 的返回类型不同list_iterator 返回 T& 和 T*list_const_iterator 返回 const T& 和 const T*Self 类型别名简化代码编写这是当前使用的实现，解决了代码重复问题：
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, Ref, Ptr> 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; }
};
T：元素类型Ref：解引用操作符的返回类型（引用）Ptr：箭头操作符的返回类型（指针）// 在 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*，返回常量引用和指针operator*()Ref operator*() { return _node->_data; }
Ref 模板参数决定是常量引用还是非常量引用*it 可以访问或修改元素值operator->()Ptr operator->() { return &_node->_data; }
Ptr 模板参数决定是常量指针还是非常量指针it->member 可以访问结构体/类成员前置自增：
Self& operator++() {
_node = _node->_next; // 移动到下一个节点
return *this; // 返回当前对象的引用
}
后置自增：
Self operator++(int) {
Self temp = *this; // 保存当前状态
_node = _node->_next; // 移动到下一个节点
return temp; // 返回原来的状态
}
int 仅用于区分前置和后置版本实现原理与自增类似，只是移动方向相反。
bool operator==(const Self& s)const { return _node == s._node; }
bool operator!=(const Self& s)const { return _node != s._node; }
private:
Node* _head; // 指向哨兵节点
size_t _size; // 链表大小
详细分析：
_head 指向一个不存储有效数据的节点_head->_next == _head 且 _head->_prev == _head_size 变量使 size() 操作为 O(1)iterator begin() {
iterator it(_head->_next); // 第一个有效元素
return it;
}
iterator end() {
iterator it(_head); // 哨兵节点作为结束位置
return it;
}
代码中的三种等价写法（注释中展示）：
// 写法 1：显式创建临时对象（当前使用的写法）
iterator it(_head->_next);
return it;
// 写法 2：返回匿名对象
return iterator(_head->_next);
// 写法 3：依赖隐式类型转换（单参数构造函数）
return _head->_next; // 编译器自动转换为 iterator
const_iterator begin()const {
const_iterator it(_head->_next);
return it;
}
const_iterator end()const {
const_iterator it(_head);
return it;
}
void empty_init() {
_head = new Node; // 创建哨兵节点
_head->_next = _head; // 指向自己
_head->_prev = _head; // 指向自己
_size = 0; // 大小为 0
}
_data 使用默认构造函数初始化list() { empty_init(); }
list(initializer_list<T> il) {
empty_init();
for (auto& e : il) {
push_back(e); // 逐个添加元素
}
}
支持现代 C++ 语法：
yyq::list<int> lst = {1, 2, 3, 4, 5}; // 初始化列表
list(const list<T>& lt) {
empty_init();
for (auto& e : lt) {
push_back(e); // 深拷贝每个元素
}
}
详细分析：
void swap(list<T>& lt) {
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
std::swap 交换指针和大小list<T>& operator=(list<T> lt) {
swap(lt);
return *this;
}
拷贝并交换技法详细分析：
lt 是值传递，自动调用拷贝构造函数lt 的资源lt 离开作用域时自动析构，释放原资源~list() {
clear(); // 删除所有有效节点
delete _head; // 删除哨兵节点
_head = nullptr;
}
详细分析：
clear() 删除所有数据节点nullptr 避免悬空指针void clear() {
// iterator it = begin();
auto it = begin();
while (it != end()) {
it = erase(it); // 返回下一个迭代器
}
}
详细分析：
auto：简化类型声明erase 的返回值更新迭代器erase(it) 会使 it 失效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 规范
//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(end(), x) 略高（少一次函数调用）insert(end(), x)，更简洁void push_front(const T& x) {
insert(begin(), x); // 在开始位置插入
}
void push_back(const T& x) {
insert(end(), x); // 在结束位置前插入
}
注意：插入到 end() 位置实际上是在哨兵节点前插入，即链表尾部
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 节点，调用元素析构函数//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 失效，但调用者不知道void pop_front() {
erase(begin()); // 删除第一个元素
}
void pop_back() {
// erase(end()._node->_prev);
erase(--end()); // 删除最后一个元素
}
两种写法：
erase(--end())：使用迭代器操作erase(end()._node->_prev)：直接访问节点指针size_t size()const { return _size; // 直接返回存储的大小 }
bool empty()const { return _size == 0; // 检查大小是否为 0
// 或者：return _head->_next == _head; }
详细分析：
_size 变量_head->_next == _head 检查链表是否为空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，会导致死循环
}
cout << endl;
// 方法 2：使用范围 for 循环
for (auto e : con) {
cout << e << " ";
}
cout << endl;
}
详细分析：
typename 关键字：
Container::const_iterator 是一个类型Container 是模板参数，编译器不知道 const_iterator 是类型还是静态成员++it，会导致死循环，此处已修正new 可能失败，抛出 std::bad_allocnew 失败，应保持链表不变sort、merge、unique 等算法resize、assign 等方法iterator insert(iterator pos, const T& x) {
Node* newnode = nullptr;
try {
newnode = new Node(x); // 可能抛出异常
} catch (...) {
// 如果 new 失败，链表保持不变
throw; // 重新抛出异常
}
// ... 连接操作（不会抛出异常）
return iterator(newnode);
}
// 移动构造函数
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);
}
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());
}
这个 yyq::list 实现是一个优秀的教学范例，它完整展示了：
虽然与标准库的 std::list 相比还有差距，但作为一个教学实现，它完美展示了双向链表和迭代器的核心原理，是学习 C++ 容器设计和模板编程的优秀范例。通过分析这个实现，可以深入理解 STL 的设计哲学和实现细节。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online