C++算法
C++ list 容器详解：介绍使用与模拟实现
C++ STL list 容器基于带头双向循环链表实现，提供高效的插入删除操作。本文详解 list 的构造、迭代器使用、容量访问及修改接口，对比 push_back 与 emplace_back 差异，分析 list 与 vector 排序性能区别，并给出 list 模拟实现的完整代码示例，涵盖节点结构、迭代器重载及内存管理逻辑。
C++ STL list 容器基于带头双向循环链表实现，提供高效的插入删除操作。本文详解 list 的构造、迭代器使用、容量访问及修改接口，对比 push_back 与 emplace_back 差异，分析 list 与 vector 排序性能区别，并给出 list 模拟实现的完整代码示例，涵盖节点结构、迭代器重载及内存管理逻辑。
list 中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，以达到可扩展的能力。以下为 list 中一些常见的重要接口。
| 构造函数 | 接口说明 |
|---|---|
| list (size_type n, const value_type& val = value_type()) | 构造的 list 中包含 n 个值为 val 的元素 |
| list() | 构造空的 list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用 [first, last) 区间中的元素构造 list |
此处，大家可暂时将迭代器理解成一个指针，该指针指向 list 中的某个节点。
| 函数声明 | 接口说明 |
|---|---|
| begin()+end() | 返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器 |
| rbegin()+rend() | 返回第一个元素的 reverse_iterator，即 end 位置，返回最后一个元素下一个位置的 reverse_iterator，即 begin 位置 |
注意
| 函数说明 | 接口说明 |
|---|---|
| empty | 检测 list 是否为空，是返回 true，否则返回 false |
| size | 返回 list 中有效节点的个数 |
| 函数说明 | 接口说明 |
|---|---|
| front | 返回 list 的第一个节点中值的引用 |
| back | 返回 list 的最后一个节点中值的引用 |
| 函数说明 | 接口说明 |
|---|---|
| push_front | 在 list 首元素前插入值为 val 的元素 |
| pop_front | 删除 list 中第一个元素 |
| push_back | 在 list 尾部插入值为 val 的元素 |
| pop_back | 删除 list 中最后一个元素 |
| insert | 在 list position 位置中插入值为 val 的元素 |
| erase | 删除 list position 位置的元素 |
| swap | 交换两个 list 中的元素 |
| clear | 清空 list 中的有效元素 |
（这里涉及到前面几节所讲的拷贝构造，隐式类型转换，直接构造啥的，要是忘记了就复习回来啦，我爱 C++）
int main() {
list<Pos> lt;
Pos p1(1, 1); //构造 + 拷贝构造
lt.push_back(p1);//有名对象，先创建一个对象，再将对象进行 push_back
lt.push_back(Pos(2, 2));//匿名对象
lt.push_back({ 2,2 });//隐式类型转换
lt.emplace_back(p1);//那是一个模版，传一个 Pos 类型的对象，模版参数推出形参的类型为 Pos
lt.emplace_back(Pos(2,2));//对于匿名对象，emplace_back 的模版参数也可以推导出为 Pos 类型
//lt.emplace_back({ 2,2 }); //直接构造
lt.emplace_back(3, 3);//但是可以支持这样玩，直接将初始化 pos 的值给它传过去
return 0;
}
lt.push_back({1,1});//本质是隐式类型转换—>这里也是构造 + 拷贝构造（隐式类型转换，实参传给形参，先用 (1,1) 构造一个临时对象，形参引用的是临时对象，这种场景下就解释了为什么形参的部分要加上 const，因为它引用的临时对象具有常性！）lt.emplace_back(1, 1);//不仅仅可以传 pos 类型的对象，也可以传构造链表里面 pos 的参数直接最后去构造 pos，所以形参也叫可变模版参数所以相比于 push_back，emplace_back 的高效之处仅在于直接构造的那种情况！
int main() {
list<int> lt1 = { -1,90,100,-8,34 };
for (auto e : lt1) { cout << e << " "; }
cout << endl;
//排序 sort，默认是升序，less
lt1.sort();
for (auto e : lt1) { cout << e << " "; }
cout << endl;
//排降序 > greater<int> gt;//有名对象做实参，干脆直接用匿名对象:lt1.sort(greater<int>());
lt1.sort(gt);
for (auto e : lt1) { cout << e << " "; }
cout << endl;
//对于 vector，算法库里面有现成的 sort，现在试用一下
vector<int> v1 = { 1,3,-2,90,9 };
for (auto e : v1) { cout << e << " "; }
cout << endl;
//默认是升序
//sort(v1.begin(), v1.end());
sort(v1.begin(), v1.end(), greater<int>());//现在加入仿函数，> 是降序
for (auto e : v1) { cout << e << " "; }
cout << endl;
//但是 list 就不可以使用算法库里面的 sort，只能用 STL 里面的 sort
//sort(lt1.begin(), lt2.end(), greater<int>());
return 0;
}
运行结果见下：
（vector 的 sort 底层是递归，算法库里面的 sort 底层是归并）
下面是在 Release 下，对 vector 使用算法库里面的 sort 和 list 使用自己实现的 sort 各自效率的测试
void test_op1() {
srand((unsigned int)time(0));
const int N = 1000000;
list<int> lt1;
list<int> lt2;
vector<int> v;
for (int i = 0; i < N; i++) {
auto e = rand() + i;
lt1.push_back(e);
v.push_back(e);
}
int begin1 = clock();
//排序，用算法库里面的 sort 给 vector 排序
sort(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
lt1.sort();//默认排升序
int end2 = clock();
cout << "vector sort:" << end1 - begin1 << endl;
cout << "list sort:" << end2 - begin2 << endl;
}
void test_op2() {
srand((unsigned int)time(0));
const int N = 1000000;
list<int> lt1;
list<int> lt2;
for (size_t i = 0; i < N; i++) {
auto e = rand();
lt1.push_back(e);
lt2.push_back(e);
}
int begin1 = clock();
//拷贝 vector
vector<int> v(lt2.begin(), lt2.end());//用迭代器区间进行构造
sort(v.begin(), v.end());
//拷贝回 lt2
lt2.assign(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
lt1.sort();
int end2 = clock();
cout << "vector sort(copy):" << end1 - begin1 << endl;
cout << "list sort:" << end2 - begin2 << endl;
}
int main() {
test_op1();
test_op2();
return 0;
}
运行结果如下：显而易见，要排序的话最好使用 vector，vector 排序的效率更高！
list 中还有一些操作，需要用到时大家可参阅 list 的文档说明。
#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;
// 示例 1：基础遍历
/*
int main() {
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
lt1.push_back(5);
list<int>::iterator it1 = lt1.begin();
while (it1 != lt1.end()) {
cout << *it1 << " ";
it1++;
}
cout << endl;
list<int> lt2 = { 1,2,3,4,5,6 };
for (auto e : lt2) {
cout << e << " ";
}
cout << endl;
return 0;
}
*/
class Pos {
int _row;
int _col;
public:
Pos(int row, int col) :_row(row), _col(col) { }
};
// 示例 2：push_back vs emplace_back
/*
int main() {
list<Pos> lt;
Pos p1(1, 1);
lt.push_back(p1);
lt.push_back(Pos(2, 2));
lt.push_back({ 2,2 });
lt.emplace_back(p1);
lt.emplace_back(Pos(2,2));
lt.emplace_back(3, 3);
return 0;
}
*/
// 示例 3：erase 与 reverse
/*
int main() {
list<int> lt1 = { 1,2,3,4,5 };
for (auto e : lt1) { cout << e << " "; }
cout << endl;
int x;
cin >> x;
auto it = find(lt1.begin(), lt1.end(), x);
if (it != lt1.end()) {
lt1.erase(it);
}
for (auto e : lt1) { cout << e << " "; }
cout << endl;
//逆置
lt1.reverse();
for (auto e : lt1) { cout << e << " "; }
cout << endl;
return 0;
}
*/
// 示例 4：splice (LRU 模拟)
/*
int main() {
list<int> lt1 = { 1,2,3,4,5,6 };
int x;
while (cin >> x) {
auto pos = find(lt1.begin(), lt1.end(), x);
lt1.splice(lt1.begin(), lt1, pos);
for (auto e : lt1) { cout << e << " "; }
cout << endl;
}
return 0;
}
*/
// 示例 5：sort 对比
/*
int main() {
list<int> lt1 = { -1,90,100,-8,34 };
for (auto e : lt1) { cout << e << " "; }
cout << endl;
lt1.sort();
for (auto e : lt1) { cout << e << " "; }
cout << endl;
greater<int> gt;
lt1.sort(gt);
for (auto e : lt1) { cout << e << " "; }
cout << endl;
vector<int> v1 = { 1,3,-2,90,9 };
for (auto e : v1) { cout << e << " "; }
cout << endl;
sort(v1.begin(), v1.end(), greater<int>());
for (auto e : v1) { cout << e << " "; }
cout << endl;
return 0;
}
*/
// 示例 6：性能测试
void test_op1() {
srand((unsigned int)time(0));
const int N = 1000000;
list<int> lt1;
vector<int> v;
for (int i = 0; i < N; i++) {
auto e = rand() + i;
lt1.push_back(e);
v.push_back(e);
}
int begin1 = clock();
sort(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
lt1.sort();
int end2 = clock();
cout << "vector sort:" << end1 - begin1 << endl;
cout << "list sort:" << end2 - begin2 << endl;
}
void test_op2() {
srand((unsigned int)time(0));
const int N = 1000000;
list<int> lt1;
list<int> lt2;
for (size_t i = 0; i < N; i++) {
auto e = rand();
lt1.push_back(e);
lt2.push_back(e);
}
int begin1 = clock();
vector<int> v(lt2.begin(), lt2.end());
sort(v.begin(), v.end());
lt2.assign(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
lt1.sort();
int end2 = clock();
cout << "vector sort(copy):" << end1 - begin1 << endl;
cout << "list sort:" << end2 - begin2 << endl;
}
int main() {
test_op1();
test_op2();
return 0;
}
const 容器必须使用 const 迭代器进行遍历，const 迭代器不是迭代器本身不能修改而是迭代器指向的内容不能修改
要模拟实现 list，必须要熟悉 list 的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现 list。
#pragma once
#include<assert.h>
namespace bit {
// 惯例
// 全部都是公有，一般用 struct
template<class T>
struct list_node {
T _data;
list_node<T>* _next;
list_node<T>* _prev;
list_node(const T& x = T()) :_data(x), _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--() { _node = _node->_prev; return *this; }
Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; }
Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; }
bool operator!=(const Self& s) { return _node != s._node; }
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 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); }
void empty_init() {
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list() { empty_init(); }
list(const list<T>& lt) {
empty_init();
for (auto& e : lt) { push_back(e); }
}
list<T>& operator=(list<T> lt) {
swap(lt);
return *this;
}
~list() {
clear();
delete _head;
_head = nullptr;
}
void swap(list<T>& tmp) {
std::swap(_head, tmp._head);
std::swap(_size, tmp._size);
}
void clear() {
auto it = begin();
while (it != end()) {
it = erase(it);
}
}
list(size_t n, const T& val = T()) {
empty_init();
for (size_t i = 0; i < n; i++) { push_back(val); }
}
void push_back(const T& x) { insert(end(), x); }
void push_front(const T& x) { insert(begin(), x); }
void pop_front() { erase(begin()); }
void pop_back() { erase(--end()); }
iterator insert(iterator pos, const T& val) {
Node* cur = pos._node;
Node* newnode = new Node(val);
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return iterator(newnode);
}
iterator erase(iterator pos) {
assert(pos != end());
Node* del = pos._node;
Node* prev = del->_prev;
Node* next = del->_next;
prev->_next = next;
next->_prev = prev;
delete del;
--_size;
return iterator(next);
}
private:
Node* _head;
size_t _size;
};
template <class T>
void swap(T& a, T& b) {
T c(a);
a = b;
b = c;
}
template <class T>
void swap(list<T>& a, list<T>& b) {
a.swap(b);
}
}
运算符重载 -> ,第一个 -> 的结果是 Pos*,第二个是找 Pos 这个结构体里面的_row。
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<algorithm>
#include<list>
#include<vector>
using namespace std;
class Pos {
public:
int _row;
int _col;
Pos(int row = 0, int col = 0) :_row(row), _col(col) { cout << "Pos(int row, int col)" << endl; }
Pos(const Pos& p) :_row(p._row), _col(p._col) { cout << "Pos(const Pos& p)" << endl; }
};
void test_op1() {
srand(time(0));
const int N = 1000000;
list<int> lt1;
list<int> lt2;
vector<int> v;
for (int i = 0; i < N; ++i) {
auto e = rand() + i;
lt1.push_back(e);
v.push_back(e);
}
int begin1 = clock();
sort(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
lt1.sort();
int end2 = clock();
printf("vector sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}
void test_op2() {
srand(time(0));
const int N = 1000000;
list<int> lt1;
list<int> lt2;
for (int i = 0; i < N; ++i) {
auto e = rand();
lt1.push_back(e);
lt2.push_back(e);
}
int begin1 = clock();
vector<int> v(lt2.begin(), lt2.end());
sort(v.begin(), v.end());
lt2.assign(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
lt1.sort();
int end2 = clock();
printf("list copy vector sort copy list sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}
#include"List.h"
int main() {
bit::list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
lt1.push_front(0);
lt1.push_front(-1);
bit::list<int> lt2(10, 1);
int i = 1, j = 2;
bit::swap(i, j);
bit::swap(lt1, lt2);
for (auto e : lt1) { cout << e << " "; }
cout << endl;
for (auto e : lt2) { cout << e << " "; }
cout << endl;
return 0;
}
list 结束！
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online