C++从入门到实战（二十）详细讲解C++List的使用及模拟实现

---

前言

• 上一篇博客中，我们深入学习了vector容器——作为动态数组，它以连续内存为核心，支持随机访问，但在头部/中间插入删除时效率较低。
• 本篇将聚焦STL中的另一个核心容器——list。它与vector在底层结构上完全不同：list是双向循环链表，通过节点间的指针连接数据，这使得它在头部/中间插入删除时效率极高，但不支持随机访问。
• 我们将从list的核心概念入手，讲解其常用接口（尤其是与vector差异显著的操作）、特殊接口（如splice、unique），并深入模拟实现list的底层结构，帮助大家理解链表容器的设计思想。

我的个人主页，欢迎来阅读我的其他文章
https://blog.csdn.net/2402_83322742?spm=1011.2415.3001.5343
我的C++知识文章专栏
欢迎来阅读指出不足
https://blog.csdn.net/2402_83322742/category_12880513.html?spm=1001.2014.3001.5482

---

C++官方list文档
https://cplusplus.com/reference/list/list/

一、什么是List

std::list 是C++ STL中的双向循环链表容器，==其底层由一个个独立的“节点”==组成，每个节点包含数据、前驱指针（指向前一个节点）和后继指针（指向后一个节点），最终形成循环结构（尾节点的后继指向头节点，头节点的前驱指向尾节点）。

1.1 List的核心特性

• 非连续内存：节点在内存中离散存储，无需整块连续内存。
• 双向访问：通过前驱/后继指针，可从任意节点向前或向后遍历。
• 高效插入删除：在任意位置（头部、中间、尾部）插入/删除节点时，仅需修改指针指向，时间复杂度为 O(1)（前提是已找到目标位置）。
• 不支持随机访问：无法通过下标（如list[i]）直接访问元素，必须从头部或尾部逐步遍历，访问效率低于vector。

1.2 List与vector的核心差异

list和vector是STL中最常用的两个序列容器，但适用场景完全不同，其核心差异如下表所示：

对比维度	vector（动态数组）	list（双向循环链表）
底层结构	连续内存空间	离散节点（带前驱/后继指针）
访问方式	支持随机访问（下标[]、at()）	仅支持双向遍历（迭代器逐步移动）
插入/删除效率	头部/中间插入删除：O(n)（需移动元素）	任意位置（已知迭代器）：O(1)（改指针）
尾部操作效率	尾插（无扩容）：O(1)；扩容时：O(n)	尾插/尾删：O(1)（无需扩容）
内存利用率	可能存在内存浪费（容量>大小）	无内存浪费（节点按需分配/释放）
迭代器类型	随机访问迭代器（支持it+2）	双向迭代器（仅支持++it/--it）

1.3 List的构造、拷贝构造与析构

list的构造方式与vector类似，但需注意其“链表特性”（无“容量”概念，仅关注节点数量）。

1.3.1 常用构造函数

1. 默认构造：创建空list（仅初始化“哨兵位头节点”，无数据节点）

   list<T>();  // T为元素类型（如int、自定义类）
   

   例子：

   #include <list>
   #include <iostream>
   using namespace std;int main() {list<int> l1;  // 空list（仅含哨兵位，无数据节点）list<string> l2;  // 存储string类型的空listcout << l1.empty() << endl;  // 输出：1（true，空）return 0;
   }
   

   

2. 指定数量+初始值构造：创建包含n个值为val的节点

   list<T>(size_t n, const T& val);
   

   例子：

   list<int> l(3, 10);  // 3个节点，每个节点值为10
   for (auto num : l) {cout << num << " ";  
   }
   

3. 迭代器范围构造：从其他容器（如vector、list）复制元素

   template <class InputIterator>
   list<T>(InputIterator first, InputIterator last);
   

   例子：

   vector<int> v = {1, 2, 3};
   list<int> l(v.begin(), v.end());  // 从vector复制元素到list
   for (auto num : l) {cout << num << " ";  // 输出：1 2 3
   }

   

4. 拷贝构造：复制已有list的所有节点

   list<T>(const list<T>& other);
   

   例子：

   list<int> l1 = {1, 2, 3};
   list<int> l2(l1);  // 拷贝构造，l2与l1完全相同
   for (auto num : l2) {cout << num << " ";  // 输出：1 2 3
   }
   

5. 列表初始化（C++11起）：直接指定元素

   list<T> l = {a, b, c, ...};  // 或 list<T> l{a, b, c, ...};
   

   例子：

   list<int> l = {10, 20, 30};  // 3个节点：10、20、30
   

1.3.2 析构函数

list的析构函数会逐个释放所有数据节点，最后释放哨兵位头节点，避免内存泄漏。

• 过程：从哨兵位开始，遍历所有数据节点，依次delete每个节点，最后delete哨兵位。
• 无需手动调用：容器生命周期结束时，析构函数自动执行。

1.4 List的迭代器

list的迭代器是理解其用法的核心——由于list内存不连续，其迭代器不是原生指针，而是封装了“节点指针”的自定义类，通过重载运算符（++、--、*、->）模拟指针行为。

1.4.1 迭代器类型与用法

list支持4种常用迭代器，用法与vector类似，但需注意仅支持双向移动（不能it+2，只能++it两次）：

迭代器类型	功能	语法示例
正向迭代器（iterator）	遍历元素，可修改元素	list<int>::iterator it = l.begin();
反向迭代器（reverse_iterator）	反向遍历元素，可修改元素	list<int>::reverse_iterator rit = l.rbegin();
const正向迭代器（const_iterator）	遍历元素，不可修改元素	list<int>::const_iterator it = l.cbegin();
const反向迭代器（const_reverse_iterator）	反向遍历元素，不可修改元素	list<int>::const_reverse_iterator rit = l.crbegin();

示例1：正向迭代器遍历

list<int> l = {1, 2, 3};
// 正向遍历（从第一个元素到最后一个元素）
for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {*it *= 2;  // 修改元素（2、4、6）cout << *it << " ";  // 输出：2 4 6
}

• begin()：指向第一个数据节点的迭代器。
• end()：指向哨兵位头节点的迭代器（不存储数据，作为遍历结束标志）。

示例2：反向迭代器遍历

list<int> l = {1, 2, 3};
// 反向遍历（从最后一个元素到第一个元素）
for (list<int>::reverse_iterator rit = l.rbegin(); rit != l.rend(); ++rit) {cout << *rit << " ";  // 输出：3 2 1
}

• rbegin()：指向最后一个数据节点的反向迭代器。
• rend()：指向哨兵位头节点的反向迭代器（遍历结束标志）。

示例3：const迭代器（只读遍历）

const list<int> l = {1, 2, 3};  // const list，元素不可修改
for (list<int>::const_iterator it = l.cbegin(); it != l.cend(); ++it) {// *it = 10;  // 错误！const迭代器不可修改元素cout << *it << " ";  // 输出：1 2 3
}

1.4.2 List迭代器的核心特性

• 双向移动：仅支持++it（向后移动）和--it（向前移动），不支持it + n或it - n（随机访问）。
• 迭代器不失效：插入/删除节点时，仅修改指针指向，其他节点的迭代器不会失效（vector插入时可能因扩容导致迭代器失效）。
  例外：被删除节点的迭代器会失效，需避免使用。

二、List的使用

list提供了丰富的接口，其中部分与vector同名，但实现逻辑不同；还有部分是list特有的接口（如splice、unique），需重点掌握。

2.1 List常用核心接口

以下是企业开发中list最常用的接口，按“增删查改”分类：

2.1.1 元素添加（增）

接口	功能	时间复杂度
push_back(val)	在尾部添加一个节点（值为val）	O(1)
push_front(val)	在头部添加一个节点（值为val）	O(1)
insert(pos, val)	在迭代器pos指向的位置插入val节点	O(1)

示例：

list<int> l;
l.push_back(1);    // 尾部添加：1
l.push_front(0);   // 头部添加：0 → 1
l.insert(++l.begin(), 5);  // 在0和1之间插入5 → 0 5 1for (auto num : l) {cout << num << " ";  // 输出：0 5 1
}

2.1.2 元素删除（删）

接口	功能	时间复杂度	注意事项
pop_back()	删除尾部节点	O(1)	不能对空list使用
pop_front()	删除头部节点	O(1)	不能对空list使用
erase(pos)	删除迭代器pos指向的节点，返回下一个节点的迭代器	O(1)	被删除的pos迭代器失效，需用返回值更新
clear()	删除所有数据节点（保留哨兵位）	O(n)	清空后list为空（size=0）

示例：

list<int> l = {0, 5, 1};
l.pop_back();  // 删除尾部节点1 → 0 5auto it = l.begin();
++it;  // it指向5
it = l.erase(it);  // 删除5，返回指向0后一个节点（哨兵位）的迭代器
cout << *it << endl;  // 错误！it指向哨兵位，无数据（需避免访问）l.clear();  // 清空所有节点，list为空
cout << l.size() << endl;  // 输出：0

2.1.3 其他常用接口

接口	功能	说明
size()	返回数据节点的个数	无“容量”概念，仅返回实际元素数
empty()	判断list是否为空（size==0）	返回true/false
swap(list& other)	交换两个list的节点（仅交换哨兵位指针）	效率极高，O(1)时间
front()	返回头部节点的值（第一个数据节点）	等价于*l.begin()
back()	返回尾部节点的值（最后一个数据节点）	等价于*--l.end()

示例：

list<int> l = {1, 2, 3};
cout << l.size() << endl;    // 输出：3
cout << l.front() << endl;   // 输出：1
cout << l.back() << endl;    // 输出：3list<int> l2 = {4, 5};
l.swap(l2);  // 交换l和l2的节点
for (auto num : l) cout << num << " ";  // 输出：4 5

2.2 emplace_back：更高效的元素构造

emplace_back是C++11新增的接口，与push_back功能类似（尾部添加元素），但效率更高——原因是它直接在链表尾部的节点中构造对象，而push_back需要先构造临时对象，再将临时对象拷贝到节点中。

核心差异：构造次数

以自定义类Person为例，对比push_back和emplace_back的构造行为：

#include <list>
#include <string>
#include <iostream>
using namespace std;class Person {
public:Person(string name, int age) : _name(name), _age(age) {cout << "Person构造函数调用" << endl;}Person(const Person& p) : _name(p._name), _age(p._age) {cout << "Person拷贝构造函数调用" << endl;}
private:string _name;int _age;
};int main() {list<Person> l;cout << "--- push_back ---" << endl;l.push_back(Person("张三", 20));  // 1次构造（临时对象）+ 1次拷贝构造cout << "--- emplace_back ---" << endl;l.emplace_back("李四", 22);  // 仅1次构造（直接在节点中构造）return 0;
}

输出结果：

--- push_back ---
Person构造函数调用  // 临时对象构造
Person拷贝构造函数调用  // 拷贝到list节点
--- emplace_back ---
Person构造函数调用  // 直接在节点中构造（无拷贝）

结论：对于自定义类型，emplace_back比push_back少一次拷贝构造，效率更高；对于内置类型（如int），两者效率差异可忽略。

2.3 仿函数：自定义操作规则

“仿函数”（Functor）本质是重载了()运算符的类或结构体，可以像函数一样被调用。在list的部分接口（如sort、unique）中，仿函数用于自定义操作规则（如排序的比较逻辑、去重的判断逻辑）。

示例1：仿函数实现自定义排序

list的sort接口默认按“升序”排序，若需降序，可传入自定义仿函数：

#include <list>
#include <iostream>
using namespace std;// 自定义仿函数：降序比较
struct Greater {bool operator()(int a, int b) const {return a > b;  // a > b时返回true，即a排在b前面}
};int main() {list<int> l = {3, 1, 4, 2};l.sort(Greater());  // 传入仿函数对象，按降序排序for (auto num : l) {cout << num << " ";  // 输出：4 3 2 1}return 0;
}

示例2：仿函数实现自定义去重

unique接口默认删除“值相等”的相邻重复元素，若需按自定义规则去重（如“绝对值相等”），可传入仿函数：

// 自定义仿函数：判断绝对值是否相等
struct AbsEqual {bool operator()(int a, int b) const {return abs(a) == abs(b);}
};int main() {list<int> l = {1, -1, 2, -2, 3};l.sort();  // 去重前需先排序（确保重复元素相邻）l.unique(AbsEqual());  // 按绝对值去重for (auto num : l) {cout << num << " ";  // 输出：-2 -1 3（或其他排序后去重结果）}return 0;
}

2.4 unique：删除相邻重复元素

unique是list的特有接口，功能是删除相邻的重复元素，但需注意两个关键点：

1. 仅删除“相邻”重复元素：若重复元素不相邻，需先调用sort()排序，确保重复元素相邻。
2. 不改变list的大小：删除的是“重复的多余元素”，最终保留一个不重复的元素。

语法

void unique();  // 默认：删除值相等的相邻元素
template <class BinaryPredicate>
void unique(BinaryPredicate pred);  // 自定义：按pred仿函数判断重复

示例（默认去重）

list<int> l = {1, 2, 2, 3, 3, 3};
l.unique();  // 删除相邻重复元素
for (auto num : l) {cout << num << " ";  // 输出：1 2 3
}

示例（排序后去重）

list<int> l = {2, 1, 2, 3, 1, 3};
l.sort();  // 先排序：1 1 2 2 3 3
l.unique();  // 去重后：1 2 3

2.5 splice：高效转移元素

splice是list最具特色的接口之一，功能是将一个list的元素“转移”到另一个list的指定位置，其核心优势是效率极高（O(1)时间）——仅需修改节点的前驱/后继指针，无需复制元素。

语法（三种常用形式）

语法	功能
splice(pos, other)	将other的所有元素转移到当前list的pos位置，other清空
splice(pos, other, it)	将other中it指向的元素转移到当前list的pos位置
splice(pos, other, first, last)	将other中[first, last)范围的元素转移到当前list的pos位置

示例1：转移整个list

list<int> l1 = {1, 2, 3};
list<int> l2 = {4, 5};// 将l2的所有元素转移到l1的开头（pos = l1.begin()）
l1.splice(l1.begin(), l2);cout << "l1: ";  // 输出：l1: 4 5 1 2 3
for (auto num : l1) cout << num << " ";
cout << "\nl2: ";  // 输出：l2: （l2为空）
for (auto num : l2) cout << num << " ";

示例2：转移单个元素

list<int> l1 = {1, 2, 3};
list<int> l2 = {4, 5};auto it = l2.begin();  // it指向4
// 将l2中的4转移到l1的2和3之间（pos = ++l1.begin()）
l1.splice(++l1.begin(), l2, it);cout << "l1: ";  // 输出：l1: 1 4 2 3
for (auto num : l1) cout << num << " ";
cout << "\nl2: ";  // 输出：l2: 5
for (auto num : l2) cout << num << " ";

2.6 慎用list::sort

list自带sort接口，但在实际开发中尽量避免使用，推荐将list的元素拷贝到vector中，用STL全局sort排序后再拷贝回list。原因如下：

核心原因：排序效率差异

• list::sort：基于“归并排序”实现，时间复杂度O(n log n)，但由于list不支持随机访问，每次比较都需通过迭代器移动，实际效率较低。
• 全局sort（std::sort）：基于“快速排序”（或混合排序）实现，仅支持随机访问迭代器（vector的迭代器符合要求），可直接通过指针访问元素，效率远高于list::sort。

代码对比：list::sort vs std::sort

#include <list>
#include <vector>
#include <algorithm>  // 包含std::sort
using namespace std;int main() {list<int> l = {3, 1, 4, 2};// 1. 使用list::sort（不推荐）l.sort();for (auto num : l) cout << num << " ";  // 输出：1 2 3 4// 2. 推荐：拷贝到vector，用std::sort排序后拷贝回listvector<int> v(l.begin(), l.end());  // list → vectorsort(v.begin(), v.end());           // 全局sort（高效）l.assign(v.begin(), v.end());       // vector → listfor (auto num : l) cout << num << " ";  // 输出：1 2 3 4return 0;
}

结论：除非必须直接在list上排序（如元素不可拷贝），否则优先使用vector+std::sort的组合。

2.7 迭代器分类：双向、随机、单向

STL根据迭代器支持的操作，将其分为5类，其中与list、vector相关的主要是3类：单向迭代器、双向迭代器、随机访问迭代器。理解迭代器分类，能帮助我们正确选择容器和算法。

迭代器类型	支持的操作	代表容器	适用算法
单向迭代器	++it（仅向后移动）、*it、!=、==	forward_list（单向链表）	仅支持单向遍历的算法
双向迭代器	++it、–it（双向移动）、*it、!=、==	list（双向链表）	支持双向遍历的算法（如reverse）
随机访问迭代器	双向迭代器的所有操作 + it+n、it-n、it1-it2	vector、string、数组	支持随机访问的算法（如sort）

关键差异示例

vector<int> v = {1, 2, 3};
list<int> l = {1, 2, 3};auto it_v = v.begin();
auto it_l = l.begin();// 随机访问迭代器（vector）支持的操作（list不支持）
it_v += 2;  // 合法：直接移动2步，指向3
// it_l += 2;  // 错误：list的双向迭代器不支持随机移动cout << *(it_v) << endl;  // 输出：3
cout << *(it_l++) << endl;  // 合法：list迭代器仅支持++

三、List的模拟实现

要深入理解list，最好的方式是模拟实现其核心结构。list的模拟实现需包含三部分：节点结构、迭代器类、list类。

3.1 底层框架：节点、迭代器、list类

3.1.1 节点结构（Node）

list的节点需存储数据、前驱指针、后继指针，定义为模板结构体：

template <class T>
struct ListNode {ListNode<T>* _prev;  // 前驱指针ListNode<T>* _next;  // 后继指针T _data;             // 数据// 节点构造函数（初始化数据和指针）ListNode(const T& data = T()) : _prev(nullptr), _next(nullptr), _data(data){}
};

3.1.2 迭代器类（Iterator）

list的迭代器需封装节点指针，并重载++、--、*、->等运算符，模拟指针行为：

template <class T, class Ref, class Ptr>  // Ref：引用类型，Ptr：指针类型
struct ListIterator {typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;  // 封装节点指针// 迭代器构造函数ListIterator(Node* node) : _node(node) {}// 重载*：返回节点数据的引用Ref operator*() {return _node->_data;}// 重载->：返回节点数据的指针（用于自定义类型）Ptr operator->() {return &(_node->_data);}// 重载++：向后移动（指向后继节点）Self& operator++() {_node = _node->_next;return *this;}// 重载--：向前移动（指向前驱节点）Self& operator--() {_node = _node->_prev;return *this;}// 重载!=：判断两个迭代器是否指向不同节点bool operator!=(const Self& other) const {return _node != other._node;}// 重载==：判断两个迭代器是否指向相同节点bool operator==(const Self& other) const {return _node == other._node;}
};

• 模板参数说明：Ref和Ptr用于区分“普通迭代器”和“const迭代器”：
  • 普通迭代器：ListIterator<T, T&, T*>
  • const迭代器：ListIterator<T, const T&, const T*>

3.1.3 List类（核心框架）

list类需包含哨兵位头节点指针（简化边界操作），并提供构造、析构、拷贝构造、赋值重载等接口：

template <class T>
class List {typedef ListNode<T> Node;
public:// 迭代器类型定义typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;// 1. 构造函数：初始化哨兵位头节点List() {_head = new Node();  // 哨兵位节点（无数据）_head->_prev = _head;  // 双向循环：前驱指向自己_head->_next = _head;}// 2. 析构函数：释放所有节点~List() {clear();  // 先释放所有数据节点delete _head;  // 再释放哨兵位_head = nullptr;}// 3. 清空数据节点（保留哨兵位）void clear() {iterator it = begin();while (it != end()) {it = erase(it);  // erase返回下一个迭代器}}// 4. 获取迭代器iterator begin() {return iterator(_head->_next);  // 第一个数据节点}iterator end() {return iterator(_head);  // 哨兵位（结束标志）}const_iterator cbegin() const {return const_iterator(_head->_next);}const_iterator cend() const {return const_iterator(_head);}private:Node* _head;  // 哨兵位头节点指针
};

3.2 核心接口模拟实现

基于上述框架，实现push_back、push_front、insert、erase等核心接口：

3.2.1 push_back：尾部添加节点

void push_back(const T& data) {Node* newNode = new Node(data);  // 创建新节点Node* tail = _head->_prev;       // 找到尾节点（哨兵位的前驱）// 调整指针：tail → newNode → _headtail->_next = newNode;newNode->_prev = tail;newNode->_next = _head;_head->_prev = newNode;
}

3.2.2 push_front：头部添加节点

void push_front(const T& data) {Node* newNode = new Node(data);  // 创建新节点Node* first = _head->_next;      // 找到第一个数据节点// 调整指针：_head → newNode → first_head->_next = newNode;newNode->_prev = _head;newNode->_next = first;first->_prev = newNode;
}

3.2.3 insert：指定位置插入节点

iterator insert(iterator pos, const T& data) {Node* newNode = new Node(data);  // 创建新节点Node* cur = pos._node;           // 迭代器指向的当前节点Node* prev = cur->_prev;         // 当前节点的前驱// 调整指针：prev → newNode → curprev->_next = newNode;newNode->_prev = prev;newNode->_next = cur;cur->_prev = newNode;return iterator(newNode);  // 返回指向新节点的迭代器
}

3.2.4 erase：删除指定位置节点

iterator erase(iterator pos) {Node* cur = pos._node;           // 要删除的节点Node* prev = cur->_prev;         // 前驱节点Node* next = cur->_next;         // 后继节点// 调整指针：prev → next（跳过cur）prev->_next = next;next->_prev = prev;delete cur;  // 释放当前节点return iterator(next);  // 返回指向后继节点的迭代器（避免迭代器失效）
}

3.3 开源代码解析（SGI STL为例）

SGI STL是最经典的STL实现之一，其list的设计与我们的模拟实现核心一致，但增加了更多细节优化：

3.3.1 节点结构（SGI STL）

template <class T>
struct __list_node {typedef void* void_pointer;void_pointer prev;  // 用void*，需强转（兼容不同类型）void_pointer next;T data;
};

• 与我们的模拟实现差异：前驱/后继用void*，需在迭代器中强转为__list_node*，兼容性更强。

3.3.2 迭代器（SGI STL）

template <class T, class Ref, class Ptr>
struct __list_iterator {typedef __list_node<T>* link_type;link_type node;  // 封装节点指针// 重载++、--、*、->等运算符（逻辑与我们的模拟实现一致）Ref operator*() const { return (*node).data; }Ptr operator->() const { return &(operator*()); }__list_iterator& operator++() { node = (link_type)((*node).next); return *this; }__list_iterator& operator--() { node = (link_type)((*node).prev); return *this; }};

• 核心逻辑与我们的模拟实现完全一致：通过封装节点指针，重载运算符模拟双向移动。

3.3.3 list类（SGI STL）

SGI STL的list类同样使用哨兵位头节点，并提供了sort、splice、unique等接口，实现逻辑与我们的模拟实现相似，但增加了：

1. 内存分配器：使用allocator管理节点内存（我们的模拟实现直接用new，SGI用自定义内存分配器，效率更高）。
2. 空节点优化：当list为空时，哨兵位节点可复用（减少内存开销）。
3. 更多接口：如merge（合并两个有序list）、reverse（反转list）等。

---

以上就是这篇博客的全部内容，下一篇我们将继续探索STL中List的更多内容。

我的个人主页，欢迎来阅读我的其他文章
https://blog.csdn.net/2402_83322742?spm=1011.2415.3001.5343
我的C++知识文章专栏
欢迎来阅读指出不足
https://blog.csdn.net/2402_83322742/category_12880513.html?spm=1001.2014.3001.5482

非常感谢您的阅读，喜欢的话记得三连哦