目录
list 模拟实现详解
1. 基本框架与节点结构
list的底层实现通常采用带头双向循环链表，每个节点包含指向前后节点的指针和数据域。
namespace practice_list
{
template<class T>
struct __list_node
{
__list_node<T>* _next; // 指向下一个节点的指针
__list_node<T>* _prev; // 指向前一个节点的指针
T _data; // 存储的数据
// 节点构造函数，使用默认参数初始化
__list_node(const T& x = T())
: _data(x) // 初始化数据域
, _next(nullptr) // 初始化next指针
, _prev(nullptr) // 初始化prev指针
{}
};
}关键点说明：
使用模板类实现泛型编程，支持任何数据类型
节点包含前后指针，实现双向链表结构
构造函数使用默认参数，方便创建头节点和数据节点
2. 迭代器初步实现
迭代器是让链表能够像容器一样被遍历的关键，它封装了节点指针并重载了相关运算符。
2.1 简单迭代器实现
template<class T>
struct __list_iterator
{
typedef __list_node<T> Node;
Node* _node; // 封装节点指针
// 构造函数，通过节点指针初始化迭代器
__list_iterator(Node* node)
:_node(node)
{}
// 解引用操作符重载，返回节点数据的引用
T& operator*()
{
return _node->_data;
}
// 前置++操作符重载，移动到下一个节点
__list_iterator<T>& operator++()
{
_node = _node->_next;
return *this;
}
// 不等于操作符重载，用于比较两个迭代器
bool operator!=(const __list_iterator<T>& it)
{
return _node != it._node;
}
};关键点说明：
迭代器本质上是对节点指针的封装
通过重载运算符实现指针-like的行为
operator*返回数据引用，使我们可以通过迭代器修改数据operator++让迭代器移动到下一个节点operator!=用于比较迭代器是否指向相同节点
3. 基础list类实现
3.1 类定义与迭代器类型声明
template<class T>
class list
{
typedef __list_node<T> Node;
public:
// 声明迭代器类型
typedef __list_iterator<T> iterator;
// 获取指向第一个元素的迭代器
iterator begin()
{
return iterator(_head->_next); // 匿名对象写法
}
// 获取尾后迭代器（指向头节点）
iterator end()
{
return iterator(_head); // 匿名对象写法
}
// 构造函数，初始化带头双向循环链表
list()
{
_head = new Node; // 创建头节点
_head->_next = _head; // 头节点的next指向自己
_head->_prev = _head; // 头节点的prev指向自己
}
// 尾插函数
void push_back(const T& x)
{
Node* tail = _head->_prev; // 找到当前尾节点
Node* newnode = new Node(x); // 创建新节点
// 链接新节点与前一个节点（尾节点）
tail->_next = newnode;
newnode->_prev = tail;
// 链接新节点与后一个节点（头节点）
newnode->_next = _head;
_head->_prev = newnode;
}
private:
Node* _head; // 头节点指针
};关键点说明：
list类维护一个头节点指针
_headbegin()返回第一个有效元素的迭代器（头节点的下一个节点）
end()返回尾后迭代器（指向头节点本身）
构造函数初始化一个空链表，头节点指向自己
push_back()在链表尾部插入新节点
3.2 测试函数
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}4. 完整迭代器实现
更完整的迭代器实现需要考虑const迭代器、前后移动等功能。
4.1 进阶迭代器设计
// 使用三个模板参数支持普通迭代器和const迭代器
// 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类型（T&或const T&）
Ref operator*()
{
return _node->_data;
}
// 前置++
Self& operator++()
{
_node = _node->_next;
return *this;
}
// 后置++（int参数用于区分前置和后置）
Self operator++(int)
{
Self ret = _node; // 保存当前状态
++(*this); // 调用前置++
return ret; // 返回之前保存的状态
}
// 前置--
Self& operator--()
{
_node = _node->_prev;
return *this;
}
// 后置--
Self operator--(int)
{
Self ret = _node;
--(*this);
return ret;
}
// 不等于操作符
bool operator!=(const Self& it)
{
return _node != it._node;
}
// 等于操作符
bool operator==(const Self& it)
{
return !(_node != it._node);
}
// 箭头操作符，用于访问成员
Ptr operator->()
{
return &(_node->_data);
}
};关键点说明：
使用三个模板参数实现普通迭代器和const迭代器的统一实现
添加了前后移动操作（++和--的前置和后置版本）
实现了箭头操作符，用于直接访问成员变量
使用Self类型别名简化代码编写
5. 完整list类实现
5.1 类型定义与构造函数
template<class T>
class list
{
typedef __list_node<T> Node;
private:
Node* _head; // 头节点指针
public:
// 普通迭代器类型
typedef __list_iterator<T, T&, T*> iterator;
// const迭代器类型
typedef __list_iterator<T, const T&, const T*> const_iterator;
// 构造函数
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
// 析构函数
~list(){
clear(); // 清空所有节点
delete _head; // 删除头节点
_head = nullptr;
}
// 获取起始迭代器
iterator begin()
{
return iterator(_head->_next);
}
// 获取尾后迭代器
iterator end()
{
return iterator(_head);
}
// 获取const起始迭代器
const_iterator begin() const
{
return const_iterator(_head->_next);
}
// 获取const尾后迭代器
const_iterator end() const
{
return const_iterator(_head);
}
5.2 拷贝构造与赋值重载
// 拷贝构造函数
list(const list<T>& lt)
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
// 遍历源链表，插入数据
const_iterator it = lt.begin();
while (it != lt.end())
{
push_back(*it);
++it;
}
// 使用范围for，更简洁
/*for (auto e : lt)
{
push_back(*it);
}*/
}
/* 赋值重载 */
/*list<T>& operator=(const list<T>& lt)
{
if (this != <)
{
clear();
for (auto e : lt)
{
push_back(e);
}
}
else
return *this;
}*/
// 赋值运算符（简洁写法）
list<T>& operator=(list<T> lt) // 传参调用拷贝构造
{
swap(_head, lt._head); // 交换头指针
return *this; // 返回当前对象
}5.3 元素访问与修改函数
// 尾插
void push_back(const T& x)
{
/*
Node* tail = _head->_prev;
Node* newnode = new Node(x);
// 链接newnode与newnode前一个节点tail
tail->_next = newnode;
newnode->_prev = tail;
// 链接newnode与newnod后一个节点"头节点"
newnode->_next = _head;
_head->_prev = newnode;
*/
insert(end(), x); // 在end()前插入
}
// 尾删
void pop_back()
{
/*Node* tail = _head->_prev;
Node* newtail = tail->_prev;
delete[] tail;
_head->_prev = newtail;
newtail->_next = _head;*/
erase(--end());
// erase(iterator(_head->_prev)); 这种写法也可以
}
// 头插
void push_front(const T& x)
{
insert(begin(), x); // 在begin()前插入
}
// 头删
void pop_front()
{
erase(begin()); // 删除第一个元素
}
// 在指定位置前插入
void insert(iterator pos, const T& x)
{
Node* cur = pos._node; // 当前节点
Node* prev = cur->_prev; // 前一个节点
Node* newnode = new Node(x); // 新节点
// 链接新节点与前一个节点
prev->_next = newnode;
newnode->_prev = prev;
// 链接新节点与当前节点
newnode->_next = cur;
cur->_prev = newnode;
}
// 删除指定位置元素
void erase(iterator pos)
{
assert(pos != end()); // 不能删除头节点
Node* cur = pos._node;
Node* next = cur->_next;
Node* prev = cur->_prev;
delete cur; // 释放节点内存
// 重新链接前后节点
next->_prev = prev;
prev->_next = next;
}
// 清空链表（保留头节点）
void clear()
{
iterator it = begin();
while (it != end())
{
erase(it++); // 使用后置++避免迭代器失效
}
}
};6. 测试代码与特殊用例
6.1 基本功能测试
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}6.2 结构体访问测试
struct Date
{
int _year = 0;
int _month = 1;
int _day = 1;
};
void test_list2()
{
list<Date> lt;
lt.push_back(Date());
lt.push_back(Date());
list<Date>::iterator it = lt.begin();
while (it != lt.end())
{
cout << it->_year << "-" << it->_month << "-" << it->_day << endl;
++it;
}
cout << endl;
}关键点说明：
it->等价于it.operator->()，返回Date*编译器特殊处理了
it->member，使其等价于(it.operator->())->member这种语法糖提高了代码的可读性
6.3 const迭代器测试
void print_list(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
// *it = 1; // 错误：不能修改const引用指向的值
cout << *it << " ";
++it;
}
cout << endl;
}6.4 拷贝构造与赋值测试
void test_list4()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int> lt2(lt); // 测试拷贝构造函数
print_list(lt2);
}
void test_list5()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int> lt2;
lt2.push_back(10);
lt2.push_back(20);
lt2.push_back(30);
lt2.push_back(40);
lt = lt2; // 测试赋值运算符
print_list(lt);
}7. 补充说明与注意事项
7.1 迭代器设计的关键点
封装指针行为：迭代器封装了节点指针，使其能够像指针一样使用
模板技巧：通过模板参数区分普通迭代器和const迭代器
前后置运算符：正确实现++和--的前置和后置版本
箭头运算符：特殊处理
->操作符以直接访问成员
7.2 链表操作的关键点
边界处理：始终维护双向循环链表的完整性
异常安全：在修改链表结构前分配资源，确保异常安全
迭代器失效：插入和删除操作可能导致迭代器失效，需要特别注意
内存管理：确保所有动态分配的节点都被正确释放
7.3 可行的改进点
异常处理：可以添加异常处理机制增强鲁棒性
性能优化：可以考虑添加移动语义支持(C++11)
更多容器操作：实现如resize(), merge(), sort()等常用操作
迭代器萃取：添加迭代器特性支持，与STL算法更好地配合