在C++ STL的序列式容器当中，list是一款特点很突出的容器，它底层靠着带头双向循环链表实现，和平时经常用到的vector相比，不管是底层结构还是运行性能都有很大区别，很多刚接触STL的新手大多只会熟练使用vector，不光对list的基础用法、底层原理了解不透彻，还常常在迭代器失效、插入删除数据的场景里频繁出错。
这篇博客会从基础内容讲起，全面梳理list容器的核心特点、常用接口用法，再带着大家手写代码模拟实现list的底层逻辑，彻底吃透它的底层运行规则，方便大家日后在项目开发里精准挑选容器、躲开各类常见问题。
一、list容器核心认知
1.1 底层结构
list的底层是带哨兵位头节点的双向循环链表，每一个单独的节点都包含数据存储区、前驱节点指针、后继节点指针这三个部分。
这种链表结构主要有这几个特点：物理内存空间不是连续的，节点分散在堆区开辟空间，靠着指针完成各个节点之间的连接，既能顺着链表从前往后遍历，也能倒着从后往前遍历，头节点的存在还简化了边界情况的处理，空链表时头节点的前驱和后继指针都会指向自己，而且在任意位置插入、删除数据的效率都很高，对应的时间复杂度为O(1)。
1.2 list与vector核心对比
不少新手都分不清vector和list到底该用在什么场景，接下来就简单说说两者的主要差异，vector底层是动态数组，内存空间连续排布，支持随机访问也就是通过下标[]、at()方法查找数据，但在链表头部、中间位置插入或者删除数据时，需要挪动大量元素导致整体效率偏低，而list不支持随机访问，没办法直接通过下标定位元素，不过在任意位置增删数据都不用挪动内容，只需要修改指针指向，运行效率要比vector高出不少。
简单概括两者的适用场景：如果需要频繁随机访问数据、只在尾部做插入删除操作，优先选用vector；如果需要经常在任意位置增删元素、对随机访问没有需求，优先选用list。
1.3 迭代器特性
list的迭代器属于双向迭代器，只支持++、--这类单步移动操作，不支持+、-、+=、-=这类随机跳转操作，这也是list无法实现随机访问的直接原因。
除此之外list迭代器还有一个关键优势，那就是插入操作不会让任何迭代器失效，只有删除操作会让指向被删节点的迭代器失效，其余迭代器都不会受到任何影响，这一点和vector区别很大，vector插入数据扩容后所有迭代器都会直接失效，这一点大家一定要牢牢记住。
二、list常用接口使用
使用list容器之前需要先包含头文件，该容器定义在std命名空间下，接下来就逐一讲解各类常用接口的使用方法。
2.1 构造函数
list自带多种构造方式，能够适配不同场景下的初始化需求，包括无参构造创建空链表、传入n和val创建含n个val值元素的list、借助其他容器或数组的迭代器区间完成初始化、通过已有list对象拷贝构造新对象这几种常用方式。
2.2 迭代器相关接口
迭代器是遍历list容器的唯一方式，常用的迭代器接口有获取首个有效元素迭代器的begin()、获取头节点迭代器的end()、专供const对象使用的cbegin()/cend()，以及用来反向遍历list的rbegin()/rend()。
遍历代码示例：
void test_list() {
list<int> lt = {1,2,3,4,5};
// 正向迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end()) {
cout << *it << " ";
++it;
}
cout << endl;
// 范围for遍历（底层也是迭代器）
for (auto& e : lt) {
cout << e << " ";
}
cout << endl;
}
2.3 容量操作
list的容量操作接口很简单，empty()用来判断容器是否为空，为空返回true反之返回false，size()则用来获取容器内部有效元素的总数量，同时要注意list没有capacity接口，因为它不需要提前预留内存空间，每次插入数据都会动态新建节点。
2.4 元素访问
list不支持随机访问，只能获取链表开头和结尾的元素，对应front()返回首个元素的引用，back()返回末尾元素的引用。
2.5 插入删除操作
插入删除操作是list最核心的优势，这类操作的效率远高于其他容器，主要分为头尾增删和指定位置增删两类，头尾操作包含尾部插入的push_back()、尾部删除的pop_back()、头部插入的push_front()、头部删除的pop_front()，指定位置操作则有insert()插入和erase()删除两种方法。
这里要重点提醒大家，删除元素时一定要接收erase的返回值，不然很容易出现迭代器失效的问题，甚至导致程序直接崩溃，大家可以对照错误写法和正确写法，理清迭代器的正确使用逻辑。
// 错误写法：迭代器失效后++，程序崩溃
auto it = lt.begin();
while (it != lt.end()) {
if (*it % 2 == 0) {
lt.erase(it);
}
++it;
}
// 正确写法
auto it = lt.begin();
while (it != lt.end()) {
if (*it % 2 == 0) {
it = lt.erase(it);
} else {
++it;
}
}
其余常用接口
list还有两个常用辅助接口，clear()可以清空容器内所有有效元素但保留头节点，swap()则能直接交换两个list对象的内部数据。
三、list容器模拟实现
想要彻底吃透list的底层逻辑，手写模拟实现是必不可少的步骤，我们按照STL的标准规范，将整体代码拆分为节点类、迭代器类、list容器类三部分编写，整套代码完整无缺失，可直接编译运行。
3.1 节点类实现
节点类主要用来封装链表单个节点，内部包含数据域、前驱指针、后继指针，通过构造函数就能直接完成节点的初始化工作。
template<class T>
struct list_node {
T _data;
list_node<T>* _prev;
list_node<T>* _next;
// 节点构造
list_node(const T& data = T())
:_data(data)
,_prev(nullptr)
,_next(nullptr)
{}
};
3.2 迭代器类实现
list的迭代器并不是普通的原生指针，而是对节点指针的封装，需要重载*、++、--、->这些常用运算符，同时借助模板参数实现普通迭代器与const迭代器的代码复用，减少冗余代码。
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 operator*() {
return _node->_data;
}
// 箭头运算符
Ptr operator->() {
return &_node->_data;
}
// 前置++
Self& operator++() {
_node = _node->_next;
return *this;
}
// 后置++
Self operator++(int) {
Self tmp = *this;
_node = _node->_next;
return tmp;
}
// 前置--
Self& operator--() {
_node = _node->_prev;
return *this;
}
// 后置--
Self operator--(int) {
Self tmp = *this;
_node = _node->_prev;
return tmp;
}
// 迭代器比较
bool operator!=(const Self& it) const {
return _node != it._node;
}
bool operator==(const Self& it) const {
return _node == it._node;
}
};
3.3 list容器类实现
list容器类主要封装链表头节点、有效元素个数，同时实现构造、析构、增删、迭代器获取等各类核心接口，完整还原STL list的基础功能。
template<class T>
class list {
typedef list_node<T> Node;
public:
// 迭代器重命名
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
// 空链表初始化
void empty_init() {
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
// 构造函数
list() {
empty_init();
}
// 迭代器区间构造
template<class InputIterator>
list(InputIterator first, InputIterator last) {
empty_init();
while (first != last) {
push_back(*first);
++first;
}
}
// 拷贝构造
list(const list<T>& lt) {
empty_init();
for (auto& e : lt) {
push_back(e);
}
}
// 析构函数
~list() {
clear();
delete _head;
_head = nullptr;
}
// 清空有效元素
void clear() {
iterator it = begin();
while (it != end()) {
it = erase(it);
}
_size = 0;
}
// 迭代器获取
iterator begin() {
return iterator(_head->_next);
}
iterator end() {
return iterator(_head);
}
const_iterator begin() const {
return const_iterator(_head->_next);
}
const_iterator end() const {
return const_iterator(_head);
}
// 容量
size_t size() const {
return _size;
}
bool empty() const {
return _size == 0;
}
// 元素访问
T& front() {
return *begin();
}
T& back() {
return *(--end());
}
// 插入
iterator 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;
++_size;
return iterator(newnode);
}
// 删除
iterator erase(iterator pos) {
// 不能删除头节点
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
// 指针解绑
prev->_next = next;
next->_prev = prev;
delete cur;
--_size;
return iterator(next);
}
// 尾插
void push_back(const T& x) {
insert(end(), x);
}
// 头插
void push_front(const T& x) {
insert(begin(), x);
}
// 尾删
void pop_back() {
erase(--end());
}
// 头删
void pop_front() {
erase(begin());
}
private:
Node* _head;
size_t _size;
};
四、模拟实现代码测试
完成模拟实现代码后，我们可以编写对应的测试代码，检验各个接口能否正常调用、功能是否正常。
void test_my_list() {
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_front(0);
// 遍历
for (auto e : lt) {
cout << e << " ";
}
cout << endl;
// 删除偶数
auto it = lt.begin();
while (it != lt.end()) {
if (*it % 2 == 0) {
it = lt.erase(it);
} else {
++it;
}
}
for (auto e : lt) {
cout << e << " ";
}
cout << endl;
cout << "size:" << lt.size() << endl;
}
int main() {
test_my_list();
return 0;
}
五、总结与避坑
最后给大家总结list核心知识点与避坑要点：list底层是带头双向循环链表，增删元素时间复杂度为O(1)且不支持随机访问，它的迭代器属于双向迭代器，仅支持++、--单步操作，插入操作不会让迭代器失效，删除操作只会让当前被删节点的迭代器失效，调用erase函数时必须接收返回值，否则会因迭代器失效引发程序崩溃，模拟实现的核心是迭代器封装，通过运算符重载让迭代器用起来和原生指针一致，日常开发中按需选容器，需要随机访问就选vector，需要频繁任意位置增删就选list。