实用指南：【C++】list容器的模拟实现

目录

1. 节点(list_node) 的结构

2. 哨兵位头节点

3. list容器的成员变量

4. 插入/删除操作

4.1 插入操作（insert）

4.2 删除操作（erase）

5. 迭代器的实现

 6. 不同迭代器和const容器的限制

7. 重载operator->

8. 迭代器失效问题

insert操作

erase操作

9. 析构函数

10. 拷贝构造函数

11. 赋值运算符重载

传统写法

现代写法

12. C++11引入的列表初始化

13. 总结

---

C++标准库中的list底层是双向循环链表，这是一种与vector（动态数组）完全不同的数据结构，核心特点是节点独立存储，通过指针连接，因此在插入/删除操作上有独特优势。

1. 节点(list_node) 的结构

template
struct list_node
{
T _data;                  // 存储节点数据
list_node* _prev;      // 正确：指向前一个节点
list_node* _next;      // 正确：指向后一个节点
// 节点构造函数（初始化数据和指针）
list_node(const T& val = T())
: _data(val), _prev(nullptr), _next(nullptr) {}
};

2. 哨兵位头节点

曾经实现单链表的时候，进行尾插操作，那么我们要判断当前链表是否为空，如果链表为空，直接插入；如果链表不为空，找到尾节点再插入。为了简化边界判断，list中会额外创建一个哨兵位头节点（不存储实际数据），整个链表形成双向循环结构，链表为空时，哨兵位的_prev和_next都指向自己。

3. list容器的成员变量

list类内部只存储两个核心信息：

template
class list
{
private:
list_node* _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
struct list_iterator
{
typedef list_node Node;
typedef list_iterator 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
struct list_const_iterator
{
typedef list_node Node;
typedef list_const_iterator 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  //Ref: T& 或 const T&；  Ptr: T* 或 const T*
struct list_iterator
{
typedef list_node Node;
typedef list_iterator 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 list
{
private:
typedef list_node Node;
Node* _head;  // 哨兵节点
size_t _size;
public:
//1.定义普通迭代器：Ref=T&  Ptr=T*
typedef list_iterator iterator;
//2.定义const迭代器：Ref=const T&  Ptr=const T*
typedef list_iterator  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
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 lst = { 1,2,3 };
//1. 普通迭代器
list::iterator it = lst.begin();
*it = 10;//合法：可修改元素
++it;//合法：可移动迭代器
//2. const迭代器(元素不可修改的迭代器)
list ::const_iterator cit = lst.begin();
//*cit = 20; 报错：不能修改元素 （const_iterator特性）
++cit;//合法：可移动迭代器
//3. const修饰迭代器(迭代器变量本身不可修改)，【实际这种迭代器几乎不用】
//情况A：const修饰普通迭代器
const list::iterator const_it1 = lst.begin();
*const_it1 = 30;//合法：普通迭代器仍可修改元素  但只能改第一个元素，使用场景极窄！
//++const_it1;  //报错：迭代器变量本身不可移动  无法修改第二个、第三个元素
//情况B：const修饰const_iterator(迭代器不可移动，元素也不可修改)
const list::const_iterator const_it2 = lst.begin();
//*const_it2 = 40;  //报错：不能修改元素
//++const_it2;      //报错：迭代器本身不可移动
cout "容器的状态不可变"->而容器的状态不仅包括内部指针，还包括其管理的元素
const list const_lst = { 4,5,6 };
list::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 people;  // 存储Person对象的链表

当我们用迭代器it指向链表中的某个Person对象时，需要访问其成员（如name或age），如果没有重载operator->，访问方式会是：

list 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 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 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 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& lt)
{
empty_init(); //初始化新链表的基础结构
for (auto& e : lt)
{
push_back(e);
}
}

11. 赋值运算符重载

传统写法

//赋值运算符重载(传统写法)
list& operator=(const list& lt)
{
//处理自赋值(避免释放自身资源后无法拷贝)
if (this != <)
{
//释放当前链表所有节点
clear();
//从lt复制元素到当前链表
for (auto& e : lt)
{
push_back(e);
}
}
return *this;//返回自身引用(支持连续赋值如a=b=c)
}

现代写法

//交换两个链表的成员
void swap(list& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
//赋值运算符重载(现代写法)
//利用拷贝构造函数创建临时副本，再交换成员变量  lt1 = lt3
list& operator=(list lt) //形参lt是按值传递，调用拷贝构造函数创建lt3的临时副本lt
{
swap(lt); //交换当前对象与临时副本的资源
return *this; //临时副本离开作用域自动析构
}
//等价写法
//list& operator=(const list& lt)
//{
//	list tmp(lt); //显式调用拷贝构造函数创建lt的临时副本
//	swap(tmp);
//	return *this;
//}

12. C++11引入的列表初始化

C++及以后标准中引入了列表初始化，使用方式：

std::list lt{ 1,2,3,4 }; //等价于std::list lt = { 1,2,3,4 };
std::list lt2({1,2,3,4});//显示传参，语法较传统

上面代码执行过程：

1. 当编译器看到{1,2,3,4}这个花括号初始化列表时，会自动生成一个std::initializer_list<int>类型的临时对象，并让它“包裹”花括号里面所有的元素。（具体操作：编译器会在栈上创建一个临时的int数组，存储1,2,3,4。）
2. 调用std::list里面接收initializer_list<int>参数的构造函数，将步骤1创建的临时对象作为实参传递给这个构造函数。
3. std::list构造函数内部会遍历这个临时对象，创建链表节点。
4. 当lt构造完成后，临时对象和它指向的临时数组自动销毁。

像std::list、std::vector等标准容器都专门提供了接收initializer_list<T>参数的构造函数，对于自定义实现list，我们也想用这种方式初始化，就需要添加这个构造函数，例如：

template
class list
{
public:
//接收initializer_list的构造函数
list(initializer_list il)
{
empty_init();
for (auto& e : il)
{
push_back(e);
}
}
……
};

13. 总结

namespace cat
{
//定义节点的结构
template
struct list_node
{
T _data;
list_node* _next;
list_node* _prev;
list_node(const T& data = T())
:_data(data)
,_next(nullptr)
,_prev(nullptr)
{}
};
//实现迭代器来模拟指针
template
struct list_iterator
{
typedef list_node Node;
typedef list_iterator 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 list
{
private:
typedef list_node Node;
Node* _head;   //指向哨兵节点
size_t _size;
public:
typedef list_iterator iterator;
typedef list_iterator  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 il) //接收initializer_list参数的构造函数
{
empty_init();
for (auto& e : il)
{
push_back(e);
}
}
//拷贝构造函数  lt2(lt1)
list(const list& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
//赋值运算符重载(现代写法)  lt1 = lt3
list& operator=(list lt)
{
swap(lt);
return *this;
}
//析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
cout & 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
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  lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
print_container(lt);
list lt2 = { 1,2,3,4 };//调用接收initializer_list参数的构造函数
list lt3({ 1,2,3,4 });	//同上
const list& lt4{ 1,2,3 }; //lt4是临时对象的引用
print_container(lt4);
}