目录
C++标准库中的list底层是双向循环链表，这是一种与vector（动态数组）完全不同的数据结构，核心特点是节点独立存储，通过指针连接，因此在插入/删除操作上有独特优势。
1. 节点(list_node) 的结构
template<class T>
struct list_node
{
T _data; // 存储节点数据
list_node<T>* _prev; // 正确：指向前一个节点
list_node<T>* _next; // 正确：指向后一个节点
// 节点构造函数（初始化数据和指针）
list_node(const T& val = T())
: _data(val), _prev(nullptr), _next(nullptr) {}
};2. 哨兵位头节点
曾经实现单链表的时候，进行尾插操作，那么我们要判断当前链表是否为空，如果链表为空，直接插入；如果链表不为空，找到尾节点再插入。为了简化边界判断，list中会额外创建一个哨兵位头节点（不存储实际数据），整个链表形成双向循环结构，链表为空时，哨兵位的_prev和_next都指向自己。
3. list容器的成员变量
list类内部只存储两个核心信息：
template<class T>
class list
{
private:
list_node<T>* _head; // 指向哨兵位头节点的指针
size_t _size; // 记录有效元素个数（非必需，但方便快速获取大小）
};4. 插入/删除操作
list的插入/删除操作远高于vector，核心原因是：只需修改指针，无需移动元素。
4.1 插入操作（insert）
//在 pos 迭代器指向的节点前插入val
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node; //pos 指向的节点
Node* prev = cur->_prev; //pos 前一个节点
Node* newnode = new Node(val);//创建新节点
//调整指针： prev newnode cur
newnode->_next = cur;
newnode->_prev = prev;
prev->_next = newnode;
cur->_prev = newnode;
++_size; //有效元素+1
return newnode; //返回指向新节点的迭代器
}4.2 删除操作（erase）
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node; //要删除的节点
Node* prev = cur->_prev; //前一个节点
Node* next = cur->_next; //后一个节点
//调整指针： prev cur next
prev->_next = next;
next->_prev = prev;
delete cur; //释放节点内存
--_size; //有效元素-1
return next; //返回被删除元素的下一个有效迭代器
}5. 迭代器的实现
list迭代器本质是节点指针的封装，通过重载++/--运算符实现遍历。
//普通迭代器（可修改元素）
template<class T>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T> Self;
Node* _node;
list_iterator(Node* node) : _node(node) {}
T& operator*() { return _node->_data; } // 返回非const引用，允许修改
T* operator->() { return &_node->_data; } // 返回非const指针
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迭代器（const_iterator）的核心目标是：允许遍历元素但禁止通过迭代器修改元素的值，它的实现逻辑与普通迭代器（iterator）类似，需要通过修改解引用和箭头运算符的返回类型来限制写操作。
- 普通迭代器（iterator）：解引用返回T&，箭头运算符返回T*，允许通过迭代器修改元素（*it = value 或 it->member = value）。
- const迭代器（const_iterator）：解引用返回const T&，箭头运算符返回const T*，仅允许读取元素，禁止修改（*it 和 it->member 都是只读的）。
我们有两种方式实现它：
方式1：
直接复制普通迭代器的代码，仅修改operator*和operator->的返回类型，其余操作（++、--、比较等）完全复用，但是这种方式代码冗余，重复代码太多。
//const迭代器（仅可读，不可修改元素） template<class T> struct list_const_iterator { typedef list_node<T> Node; typedef list_const_iterator<T> Self; Node* _node; // 仍指向普通节点（节点本身可修改，但通过迭代器访问的元素不可修改） list_const_iterator(Node* node) : _node(node) {} // 核心区别：返回const引用/指针，禁止修改元素 const T& operator*() { return _node->_data; } // 只读 const T* operator->() { return &_node->_data; } // 只读 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：
用模版参数复用代码，将普通迭代器和const迭代器的共性代码合并到一个模版中，仅通过参数控制是否为const。
template<class T, class Ref, class Ptr> //Ref: T& 或 const T&； Ptr: T* 或 const T* 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; } // Ref为const T&时，返回只读引用 Ptr operator->() { return &_node->_data; } // Ptr为const T*时，返回只读指针 // 移动操作完全复用（与是否const无关） 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迭代器这两种具体类型时，主动明确地把它们的具体值（比如T&或const T&）传给list_iterator模版，从而生成了“能改”和“不能改”两种不同功能的迭代器。在list类提供const版本的begin()和end()，用于const对象的遍历：
template<class T> class list { private: typedef list_node<T> Node; Node* _head; // 哨兵节点 size_t _size; public: //1.定义普通迭代器：Ref=T& Ptr=T* typedef list_iterator<T, T&, T*> iterator; //2.定义const迭代器：Ref=const T& Ptr=const T* typedef list_iterator<T, const T&, const T*> const_iterator; // 普通迭代器接口 iterator begin() { return _head->_next; } //第一个有效节点 iterator end() { return _head; } //哨兵节点（尾后位置） // const迭代器接口（供const对象使用） const_iterator begin() const { return _head->_next; } //第一个有效节点 const_iterator end() const { return _head; } //哨兵节点（尾后位置） // …… 其他成员函数（构造、push_back等，省略） };
遍历打印元素
template<class Container> void print_container(const Container& con) { typename Container:: const_iterator it = con.begin(); //auto it = con.begin(); while (it != con.end()) { //*it += 10; 编译错误：const_iterator禁止修改元素 cout << *it << " "; //可以读取 ++it; } cout << endl; for (auto e : con) { cout << e << " "; } cout << endl; }
6. 不同迭代器和const容器的限制
void test_list2()
{
list<int> lst = { 1,2,3 };
//1. 普通迭代器
list<int>::iterator it = lst.begin();
*it = 10;//合法：可修改元素
++it;//合法：可移动迭代器
//2. const迭代器(元素不可修改的迭代器)
list<int> ::const_iterator cit = lst.begin();
//*cit = 20; 报错：不能修改元素 （const_iterator特性）
++cit;//合法：可移动迭代器
//3. const修饰迭代器(迭代器变量本身不可修改)，【实际这种迭代器几乎不用】
//情况A：const修饰普通迭代器
const list<int>::iterator const_it1 = lst.begin();
*const_it1 = 30;//合法：普通迭代器仍可修改元素 但只能改第一个元素，使用场景极窄！
//++const_it1; //报错：迭代器变量本身不可移动 无法修改第二个、第三个元素
//情况B：const修饰const_iterator(迭代器不可移动，元素也不可修改)
const list<int>::const_iterator const_it2 = lst.begin();
//*const_it2 = 40; //报错：不能修改元素
//++const_it2; //报错：迭代器本身不可移动
cout << *const_it2; //只能读第一个元素，使用场景极窄！
//4. const容器 ->"容器的状态不可变"->而容器的状态不仅包括内部指针，还包括其管理的元素
const list<int> const_lst = { 4,5,6 };
list<int>::const_iterator clst = const_lst.begin(); //const容器只能返回const迭代器
//*clst = 50; //报错：const容器元素不可修改
++clst; //合法：迭代器本身可移动
//const_lst.push_back(7); //报错：容器对象状态不可改变(包括容器长度、节点数量、节点存储的数据等)，
//push_back是非const的成员函数，const容器只能调用const成员函数，添加、删除、清空元素同样都不可以。
}7. 重载operator->
为什么要重载operator->呢？
假设链表存储自定义对象，相当于链表的每一个节点存储的都是对象。
struct Person
{
string name;
int age;
};
list<Person> people; // 存储Person对象的链表当我们用迭代器it指向链表中的某个Person对象时，需要访问其成员（如name或age），如果没有重载operator->，访问方式会是：
list<Person> lst; lst.push_back({ "张三", 20 }); auto it = lst.begin(); //迭代器，指向第一个Person对象 (*it).name; //先解引用迭代器得到Person对象，再用.访问成员当写*it时，本质是调用 it.operator*()，这个函数会通过迭代器的_node找到对应的链表节点，返回节点中_data的引用即（Person&类型），*it等价于 “迭代器所指向节点中的Person对象。
operator->的重载逻辑
T* operator->() { return &_node->_data; // 返回指向节点中数据的指针 }
而有了operator->重载后，访问方式可以简化为：
list<Person> lst; lst.push_back({ "张三", 20 }); auto it = lst.begin(); //迭代器，指向第一个Person对象 it->name; //迭代器用->访问成员（看似一步，实则两步）编译器会自动拆解为(it.operator->())->name编译器会把 it->name; 这个表达式自动拆解为两步：
- 第一步：显示触发重载操作，执行 it.operator->()，得到 Person* 指针（指向节点中存储的Person对象的指针），取名叫 p。
- 第二步：再对 p 执行 “原生 -> 操作”：p->name（这一步是隐藏的，编译器自动补全）。
总共 2 次-> 相关操作，其中第 2 次是编译器按标准自动隐藏执行的，目的是让迭代器用起来和原生指针一样简单。
不管是标准库还是自定义的迭代器，只要正确重载了operator->，编译器就会自动补充第二次->，这是C++标准规定的行为，目的是让类类型的对象可以模拟指针的->操作。
这种设计的目的是让迭代器的用法和原生指针完全一致，降低使用成本，如果编译器不自动补充第二次->，用户就必须写成( it.operator->( ) ) -> name，不仅麻烦，还会让迭代器和原生指针的用法脱节，违背了迭代器“模拟指针”的设计初衷。
8. 迭代器失效问题
在C++中，list的迭代器失效问题和vector 等连续内存容器有显著区别，这源于list当节点式存储结构（非连续内存）。
insert操作
插入元素时，只会在目标位置创建新节点，并调整相邻节点的指针，不会改变原有任何节点的内存地址，因此，所有已存在的迭代器(包括插入位置的迭代器)都不会失效。
标准库实现insert，返回值为指向新插入元素的迭代器，插入后可直接通过返回值操作新元素。【4.1插入操作】
list<int> lst = {1, 3, 4}; auto it = lst.begin(); // 指向1的迭代器 lst.insert(++it, 2); // 在3前插入2，lst变为{1,2,3,4} // 原it仍指向3（有效），新节点2的迭代器需通过insert返回值获取
erase操作
删除元素时，被删除的节点会被销毁，指向该节点的迭代器会失效；但其它节点的内存地址没变，因此除了被删除节点的迭代器外，其他所有迭代器仍然有效。
erase返回指向被删除元素的下一个元素的迭代器，避免使用已失效的迭代器。【4.2删除操作】
//删除偶数 std::list<int> lst = {1, 2, 3, 4}; auto it = lst.begin(); while (it != lst.end()) { if (*it % 2 == 0) { //lst.erase(it);it已失效，不能再使用，下一次判断会导致未定义行为 it = lst.erase(it); //用返回值更新it（指向被删元素的下一个） } else { ++it; // 奇数不删除则正常移动迭代器 } } // 最终lst为{1,3}
9. 析构函数
第一种实现：
~list()
{
Node* current = _head->_next; //从第一个有效节点开始遍历
while (current != _head)
{
Node* nextNode = current->_next; //先保存下一个节点
delete current; //销毁当前节点
current = nextNode; //移动到下一个节点
}
//销毁哨兵节点
delete _head;
_head = nullptr;
//重置大小
_size = 0;
cout << "链表已销毁" << endl;
}第二种实现：复用clear() 和 erase()
~list()
{
clear();
delete _head; //释放哨兵节点
_head = nullptr;
_size = 0;
cout << "链表已销毁" << endl;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it); //复用erase逻辑删除单个节点
}
}10. 拷贝构造函数
在链表中，必须手动实现拷贝构造函数，不能依赖编译器默认生成的默认拷贝构造函数，核心原因是：编译器默认的拷贝构造函数是浅拷贝，仅复制指针值，导致多个链表共享节点内存，引发双重释放、野指针等问题（原链表和拷贝出的新链表会共享同一份节点内存，当其中一个链表析构时，导致另一个链表的指针变成野指针，指向已释放的内存，若对其中一个链表修改，会直接影响另一个链表，两个链表析构时，会双重释放导致程序崩溃）。
手动实现拷贝构造函数需要完成深拷贝：为新链表创建独立的节点，确保每个链表拥有自己的资源。
//空初始化 (创建独立的哨兵节点_head,形成自循环，_size为0) void empty_init() { _head = new Node(); _head->_next = _head; _head->_prev = _head; _size = 0; } //拷贝构造函数 lt2(lt1) list(const list<T>& lt) { empty_init(); //初始化新链表的基础结构 for (auto& e : lt) { push_back(e); } }
11. 赋值运算符重载
传统写法
//赋值运算符重载(传统写法)
list<T>& operator=(const list<T>& lt)
{
//处理自赋值(避免释放自身资源后无法拷贝)
if (this != <)
{
//释放当前链表所有节点
clear();
//从lt复制元素到当前链表
for (auto& e : lt)
{
push_back(e);
}
}
return *this;//返回自身引用(支持连续赋值如a=b=c)
}现代写法
//交换两个链表的成员
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
//赋值运算符重载(现代写法)
//利用拷贝构造函数创建临时副本，再交换成员变量 lt1 = lt3
list<T>& operator=(list<T> lt) //形参lt是按值传递，调用拷贝构造函数创建lt3的临时副本lt
{
swap(lt); //交换当前对象与临时副本的资源
return *this; //临时副本离开作用域自动析构
}
//等价写法
//list<T>& operator=(const list<T>& lt)
//{
// list<T> tmp(lt); //显式调用拷贝构造函数创建lt的临时副本
// swap(tmp);
// return *this;
//}12. C++11引入的列表初始化
C++及以后标准中引入了列表初始化，使用方式：
std::list<int> lt{ 1,2,3,4 }; //等价于std::list<int> lt = { 1,2,3,4 }; std::list<int> lt2({1,2,3,4});//显示传参，语法较传统
上面代码执行过程：
- 当编译器看到{1,2,3,4}这个花括号初始化列表时，会自动生成一个std::initializer_list<int>类型的临时对象，并让它“包裹”花括号里面所有的元素。（具体操作：编译器会在栈上创建一个临时的int数组，存储1,2,3,4。）
- 调用std::list里面接收initializer_list<int>参数的构造函数，将步骤1创建的临时对象作为实参传递给这个构造函数。
- std::list构造函数内部会遍历这个临时对象，创建链表节点。
- 当lt构造完成后，临时对象和它指向的临时数组自动销毁。
像std::list、std::vector等标准容器都专门提供了接收initializer_list<T>参数的构造函数，对于自定义实现list，我们也想用这种方式初始化，就需要添加这个构造函数，例如：
template<typename T> class list { public: //接收initializer_list的构造函数 list(initializer_list<T> il) { empty_init(); for (auto& e : il) { push_back(e); } } …… };
13. 总结
namespace cat
{
//定义节点的结构
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)
{}
};
//实现迭代器来模拟指针
template<class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node; //成员变量 _node指针变量专门用于指向链表中的某个节点
list_iterator(Node* node)
:_node(node)
{}
Ref operator*() //返回引用 *it = 100;
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()//前置++ 指针++返回指针本身，迭代器++返回迭代器本身
{
_node = _node->_next;
return *this;
}
Self operator++(int) //后置++(有int占位参数)：先保存当前状态，再移动，再返回原状态
{ //后置++不能返回引用，tmp是局部临时对象，出了作用域会销毁，如果返回引用，会导致悬垂引用问题(引用的对象已不存在)
Self temp(*this); //保存当前迭代器 调用拷贝构造函数构造temp
_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;
}
};
//定义链表
template<class T>
class list
{
private:
typedef list_node<T> Node;
Node* _head; //指向哨兵节点
size_t _size;
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
/*iterator it(_head->_next);
return it;*/
return _head->_next;//返回指向第一个元素节点的迭代器，函数返回的类型(Node*)和函数声明的返回类型(iterator对象)不匹配
//iterator类有单参数构造函数，支持隐式类型转换，自动调用构造函数将_head->next作为参数,创建一个临时的iterator对象
//等价于return iteartor(_head->next); (显示调用构造函数)
}
iterator end()
{
return _head;
}
const_iterator begin()const
{
return _head->_next;
}
const_iterator end()const
{
return _head;
}
//空初始化
void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
//无参构造函数
list()
{
empty_init();
}
list(initializer_list<T> il) //接收initializer_list<T>参数的构造函数
{
empty_init();
for (auto& e : il)
{
push_back(e);
}
}
//拷贝构造函数 lt2(lt1)
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
//赋值运算符重载(现代写法) lt1 = lt3
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
//析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
cout << "链表已销毁" << endl;
}
//清除元素
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}
//交换两个链表的成员
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
//尾插
void push_back(const T& x)
{
insert(end(), x);
}
//头插
void push_front(const T& x)
{
insert(begin(), x);
}
//插入数据
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
//prev newnode cur
newnode->_next = cur;
newnode->_prev = prev;
prev->_next = newnode;
cur->_prev = newnode;
++_size;
return newnode;//返回指向新节点的迭代器
}
//删除数据
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
//prev cur next
prev->_next = next;
next->_prev = prev;
delete cur;
--_size;
return next; //返回被删除元素的下一个有效迭代器
}
//尾删
void pop_back()
{
erase(--end());
}
//头删
void pop_front()
{
erase(begin());
}
size_t size() const
{
return _size;
}
//判空
bool empty() const
{
return _size == 0;
}
};
template<class Container>
void print_container(const Container& con)
{
typename Container:: const_iterator it = con.begin(); //auto it = con.begin();
while (it != con.end())
{
//*it += 10;// error！
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : con)
{
cout << e << " ";
}
cout << endl;
}
void test_list()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
print_container(lt);
list<int> lt2 = { 1,2,3,4 };//调用接收initializer_list<int>参数的构造函数
list<int> lt3({ 1,2,3,4 }); //同上
const list<int>& lt4{ 1,2,3 }; //lt4是临时对象的引用
print_container(lt4);
}