跳到主要内容C++算法
C++ STL list 容器详解：使用与模拟实现
STL list 基于双向循环链表实现，支持 O(1) 插入删除但不支持随机访问。解析其常用接口如构造、迭代器操作及内存管理细节，并通过手写模拟实现展示节点设计、迭代器模板技巧及关键函数逻辑。对比 vector 可见 list 在频繁增删场景下的优势，适合理解底层数据结构与内存安全机制。
活在当下5 浏览 
1. list 的介绍及使用
1.1 list 的介绍
在 C++ STL 的容器家族里，list 是个很特别的成员。它底层是带头结点的双向循环链表。和 vector 不同，list 在任意位置插入和删除元素的时间复杂度都是 O(1)，但它不支持随机访问，也就是说不能通过下标直接访问元素。
1.2 list 的使用
list 提供了丰富的接口，这里挑几个常见且重要的讲讲。
1.2.1 list 的构造
| 构造函数 | 接口说明 |
|---|
list(size_type n, const value_type& val) | 构造包含 n 个值为 val 的元素的 list |
list() | 构造空的 list |
list(const list& x) | 拷贝构造函数 |
list(InputIterator first, InputIterator last) | 用区间 [first, last) 中的元素构造 list |
1.2.2 list 迭代器的使用
迭代器可以暂时理解为指向 list 中某个节点的指针。
begin()：返回指向第一个元素的迭代器end()：返回指向最后一个元素下一个位置的迭代器rbegin()：返回指向最后一个元素的反向迭代器（即 end() 位置）rend()：返回指向第一个元素前一个位置的反向迭代器（即 begin() 位置）
注意：
begin 和 end 是正向迭代器，++ 向后移动。rbegin 和 rend 是反向迭代器，++ 向前移动。
1.2.3 list capacity
| 函数声明 | 接口说明 |
|---|
empty() | 检测 list 是否为空 |
size() | 返回 list 中有效节点的个数 |
1.2.4 list element access
| 函数声明 | 接口说明 |
|---|
front() | 返回第一个节点中值的引用 |
back() | 返回最后一个节点中值的引用 |
1.2.5 list modifiers
| 函数声明 | 接口说明 |
|---|
push_front | 在 list 首元素前插入值为 val 的元素 |
pop_front | 删除 list 中第一个元素 |
push_back | 在 list 尾部插入值为 val 的元素 |
pop_back | 删除 list 中最后一个元素 |
insert | 在 position 位置插入值为 val 的元素 |
erase | 删除 position 位置的元素 |
swap | 交换两个 list 中的元素 |
clear | 清空 list 中的有效元素 |
1.2.6 list 的迭代器失效
由于 list 的底层是双向循环链表，插入操作不会导致迭代器失效。只有在删除元素时，指向被删除节点的迭代器才会失效，其他迭代器不受影响。
while (it != l.end()) {
l.erase(it);
++it;
}
2. list 的模拟实现
2.1 基本结构
2.1.1 节点类 (list_node)
我们先从最基础的节点定义入手，这是 list 的基石。
template<class T> class list_node {
public:
T _data;
list_node<T>* _next;
list_node<T>* _prev;
list_node(const T& data = T()) :_data(data) ,_next(nullptr) ,_prev(nullptr) { }
};
_data: 存储实际数据_next: 指向下一个节点_prev: 指向上一个节点
2.1.2 迭代器类 (list_iterator)
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& s) { return _node != s._node; }
};
- 通过模板参数
Ref 和 Ptr 实现 const 和非 const 迭代器的统一，避免代码重复。
- 支持前后遍历操作，符合 STL 习惯。
- 支持箭头操作符访问成员。
2.2 list 容器类
2.2.1 类型定义和迭代器
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;
iterator begin() { return _head->_next; }
iterator end() { return _head; }
const_iterator begin() const { return _head->_next; }
const_iterator end() const { return _head; }
};
Node* 可以隐式转换为 iterator，因为 list_iterator 有单参数构造函数。begin() 返回第一个有效元素位置。end() 返回头节点位置，符合 STL 左闭右开原则。
2.2.2 构造函数和初始化
void empty_init() {
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list() { empty_init(); }
list(list<T>& lt) {
empty_init();
for (auto& e : lt) { push_back(e); }
}
list(initializer_list<int> il) {
empty_init();
for (auto& e : il) { push_back(e); }
}
2.2.3 插入操作
插入的核心在于调整指针指向，这里有个技巧：复用 insert 来实现 push_front 和 push_back。
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 newnode;
}
void push_back(const T& x) { insert(end(), x); }
void push_front(const T& x) { insert(begin(), x); }
2.2.4 删除操作
iterator erase(iterator pos) {
assert(pos != end());
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
--_size;
return next;
}
void pop_back() { erase(--end()); }
void pop_front() { erase(begin()); }
erase 返回下一个有效位置的迭代器，方便后续遍历。- 正确处理删除操作后的迭代器续接。
2.2.5 容量操作
size_t size() const { return _size; }
bool empty() const { return _size == 0; }
void clear() {
auto it = begin();
while (it != end()) {
it = erase(it);
}
}
2.2.6 赋值操作
list<T>& operator=(list<T> lt) {
swap(lt);
return *this;
}
void swap(list<T>& lt) {
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
2.3 迭代器模板技巧
通过模板参数实现 const 和非 const 迭代器的统一，这种设计避免了重复代码，只需要一个模板类就能同时支持普通迭代器和 const 迭代器。
2.4 测试示例
void test_list01() {
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;
}
void test_list02() {
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();
lt.insert(it, 10); *it += 100;
it = lt.begin();
while (it != lt.end()) {
if (*it % 2 == 0) { it = lt.erase(it); } else { ++it; }
}
}
#pragma once
#include<assert.h>
namespace bit {
template<class T> class list_node {
public:
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;
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--(int) { Self tmp(*this); _node = _node->_prev; return tmp; }
Self& operator--() { _node = _node->_prev; return *this; }
bool operator!=(const Self& s) { return _node != s._node; }
};
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;
iterator begin() { return _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() { clear(); delete _head; _head = nullptr; }
void clear() { auto it = begin(); while (it != end()) { it = erase(it); } }
list<T>& operator=(list<T> lt) { swap(lt); return *this; }
void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); }
list(list<T>& lt) { empty_init(); for (auto& e : lt) { push_back(e); } }
list(initializer_list<int> il) { empty_init(); for (auto& e : il) { push_back(e); } }
void push_back(const T&x) { insert(end(), x); }
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 newnode;
}
void push_front(const T& x) { insert(begin(), x); }
void pop_back() { erase(--end()); }
void pop_front() { erase(begin()); }
iterator erase(iterator pos) {
assert(pos != end());
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
return next;
}
size_t size() const { return _size; }
bool empty() const { return _size == 0; }
private:
Node* _head;
size_t _size;
};
struct AA { int _a1; int _a2; };
template<class Container> void print_container(const Container& con) {
auto it = con.begin();
while (it != con.end()) { cout << *it << " "; ++it; }
cout << endl;
}
void test_list01() {
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;
list<AA> lta;
lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA()); lta.push_back(AA());
list<AA>::iterator ita = lta.begin();
while (ita != lta.end()) { cout << ita->_a1 << ":" << ita->_a2 << endl; ++ita; }
cout << endl;
print_container(lt);
}
void test_list02() {
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();
lt.insert(it, 10); *it += 100; print_container(lt);
it = lt.begin();
while (it != lt.end()) {
if (*it % 2 == 0) { it=lt.erase(it); } else { ++it; }
}
print_container(lt);
}
void test_list03() {
list<int> lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4);
list<int> lt2(lt1); print_container(lt1); print_container(lt2);
list<int> lt3; lt3.push_back(10); lt3.push_back(20); lt3.push_back(30); lt3.push_back(40);
lt1 = lt3; print_container(lt1); print_container(lt3);
}
void func(const list<int>& lt) { print_container(lt); }
void test_list04() {
list<int> lt0 ( { 1,3,5 });
list<int> lt1= {1, 2, 3, 4, 5}; print_container(lt1);
auto il = { 1,2,3,4 }; cout << typeid(il).name() << endl;
func(lt1); func({ 1,3,6,7 });
}
};
2.5 设计要点总结
- 双向循环链表：头节点连接首尾，简化边界处理
- 迭代器封装：隐藏底层指针，提供统一接口
- 模板复用：通过模板参数减少代码重复
- 异常安全：正确管理资源，避免内存泄漏
- STL 兼容：遵循 STL 接口规范
这个实现展示了 list 容器的核心机制，包括节点管理、迭代器设计、插入删除操作等关键技术点。
3. list 与 vector 的对比
| 对比维度 | vector | list |
|---|
| 底层结构 | 动态顺序表，连续空间 | 带头结点的双向循环链表 |
| 随机访问 | 支持 O(1) | 不支持，访问元素 O(N) |
| 插入删除 | 任意位置效率低 O(N)，可能增容 | 任意位置效率高 O(1) |
| 空间利用率 | 连续空间，内存碎片少，缓存友好 | 节点动态开辟，易产生内存碎片 |
| 迭代器类型 | 原生态指针 | 对节点指针进行封装 |
| 迭代器失效 | 插入删除可能导致全部或部分失效 | 删除时仅当前迭代器失效 |
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
