使用 list 之前需要包含 list 头文件，list 文档介绍。
C++算法
C++ List 容器详解：结构与常用操作
系统讲解了 C++ List 容器的底层数据结构（带头双向循环链表）、构造函数用法、迭代器特性及遍历方式。详细说明了增删查改接口（push_back, insert, erase 等）及常见操作函数（sort, merge, splice 等），对比了 List 与 Vector 的性能差异，并提供了大数据量下的排序优化建议。
系统讲解了 C++ List 容器的底层数据结构（带头双向循环链表）、构造函数用法、迭代器特性及遍历方式。详细说明了增删查改接口（push_back, insert, erase 等）及常见操作函数（sort, merge, splice 等），对比了 List 与 Vector 的性能差异，并提供了大数据量下的排序优化建议。
使用 list 之前需要包含 list 头文件，list 文档介绍。
list 是 C++ 的一个序列容器，插入和删除元素的效率较高，时间复杂度为常数级别。list 容器的底层数据结构为带头双向循环链表，这使得 list 的元素可以存储在非相邻的内存中。在 list 内部，不同元素之间通过指向前一个元素的指针以及指向后一个元素的指针相关联。
list 容器与其他序列容器如 string、vector 相比，由于其底层数据结构为带头双向循环链表，因此 list 在插入删除元素方面很有优势，在列表的任意位置进行插入和删除操作的时间复杂度为 O(1)。但不能直接通过位置 (下标) 来直接访问元素。想要访问 list 的某个元素，必须从 list 的一端（或已知位置）迭代到该元素。另外，list 还需要额外的存储空间来储存前一个元素和后一个元素的指针信息。
list 也同样是一个类模板，我们也需要显示实例化。
list 容器底层为带头双向循环链表，带头双向循环链表每个节点包含指向前驱节点的 prev 指针，指向后继节点的 next 指针以及节点的数据。list 存储结构如下图所示：哨兵节点表示链表的第一个元素节点，且不保存任何数据。
从 list 使用文档里面，我们可以看到 list 有如下的几个构造函数：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> l1;
return 0;
}
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> l2(10, 1);
for (auto& ele : l2) {
cout << ele << " ";
}
cout << endl;
return 0;
}
这个构造函数会将一个迭代器区间的值用来初始化我们的 list，这个迭代器不要求和 list 迭代器一样，也可以使用其他类型的迭代器，只要求里面数据的类型一样就可以了。
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> l2(10, 7);
list<int> l3(l2.begin(),l2.end());
for (auto& ele : l3) {
cout << ele << " ";
}
cout << endl;
return 0;
}
使用 string 类型的迭代器来初始化一个 list 容器，如下所示：
#include<iostream>
using namespace std;
#include<list>
#include<string>
int main() {
string s1("abcdefg");
list<char> l3(s1.begin(), s1.end());
for (auto& ele : l3) {
cout << ele << " ";
}
cout << endl;
return 0;
}
我们这里虽然是 list 容器，但是使用的是 string 类型的迭代器进行初始化的。
拷贝构造是使用一个已经初始化好的 list 来创建另外一个 list。如下所示：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<double> ld(5, 1.5);
list<double> ld2(ld);
for (auto& ele : ld2) {
cout << ele << " ";
}
cout << endl;
return 0;
}
这个构造函数是 C++11 后来新加的，使用大括号初始化，函数原型如下：
C++11 增加了一个类型，将花括号括起来的内容成为 initializer_list，如下所示：
底层逻辑是在栈区开一个数组，这个 il 对象里面有两个指针，一个指针指向数组的开始位置，一个指针指向数组的结束位置，所以这个对象的大小是 8 字节（32 位）。
使用大括号初始化代码如下：
int main() {
list<int> mylist({ 1,2,3,4,5,6,7});
for (auto& ele : mylist) {
cout << ele << " ";
}
cout << endl;
return 0;
}
list mylist({ 1,2,3,4,5,6,7});也可以将这一行写出这样：
list mylist={ 1,2,3,4,5,6,7}; 这样写的话就是隐式类型转换。
迭代器属于其对应容器的类域，所以我们在声明 list 迭代器时，需要指定类域。
与 string 类似，vector 也有八种迭代器，如下所示：
最常用的就是前面两个:begin() 和 end()
begin() 返回的是第一个元素的迭代器；
end() 返回的是最后一个元素的下一个位置的迭代器；
注意： list 容器的迭代器不再是原生指针了，不能再支持 + 和 - 了。 迭代器从功能上划分，可以分为 iterator;reverse_iterator;const_iterator;const_reverse_iterator; 迭代器从性质上划分可以分为：单向迭代器:forward_list/unordered_map... 能够支持 ++ 双向迭代器:list/map/set... 能够支持 ++，-- 随机迭代器:vector/string/deque... 能够支持 ++，--，+，- 迭代器的性质是由底层的结构决定的。 像 vector、string 之类的，它们的底层是连续的物理空间，所以他们的迭代器就能够支持 + 和 -。 如何看一个容器的迭代器是具有什么性质的呢？ 可以在 list 文档 里面的 Member types 里面看到 list 迭代器的类型，如下所示： bidirectional iterator 表示的就是双向迭代器的意思。 同样的，我们也可以在 vector 文档 里面的 Member types 里面看到 vector 迭代器的类型，如下所示： random access iterator 表示的就是随机迭代器的意思。 我们也可以在 unordered_map 文档 里面查看 unordered_map 迭代器的类型，如下所示： forward iterator 表示的就是单向迭代器的意思。 这个迭代器性质可以决定可以使用哪些算法。 我们可以查看 algorithm 里面的 sort 函数，函数原型如下所示： 虽然算法库里面的 sort 是一个模板，传任意类型迭代器都可以，可以根据模板来推导类型，但是真的能传任意类型的迭代器嘛？sort函数原型的参数给了暗示，要想去使用算法库里面的 sort 排序，这个迭代器类型必须是 RandomAccessIterator，也就是随机迭代器。如果传过来的参数不是随机迭代器，就会报错，这是因为 sort 算法使用的排序是快排，快排里面需要三数取中等，它需要支持 +，-，[] 等随机访问的。所以 list 容器里面自己支持了一个 sort 算法。 我们再查看 algorithm 里面的 reverse 函数，函数原型如下所示： reverse 函数需要传入双向迭代器，所以 list 和 vector 等都可以使用这个函数来进行翻转。但是 forward_list 就不能使用这个函数来进行翻转，因为 reverse 函数内部需要用到 --。 我们可以理解为随机迭代器和双向迭代器都是一种特殊的单项迭代器，随机迭代器是一种特殊的双向迭代器。它们之间有一种特殊的继承关系，如下所示： 我们在上面没有讲过 input 类型的迭代器，我们可以查看 algorithm 里面的 find 函数，函数原型如下： 这个函数要求参数是 InputIterator 类型的迭代器， InputIterator 类型的迭代器是个什么迭代器？ C++ 里面引出了两个不存在的迭代器，没有实体对应的迭代器，input 和 output 迭代器。有些算法里面的参数迭代器类型是 InputIterator，InputIterator 指的是可以传入任意类型的迭代器。 为什么 find 里面需要传入 InputIterator 类型的迭代器呢？ 因为 find 函数里面之后对迭代器进行 ++ 操作，所以什么类型的迭代器都可以传。
所以我们想要使用一些算法的时候，需要查看这个容器的迭代器到底支不支持这种算法。如果某种算法不支持这种迭代器，就会报错。
因为 List 容器不支持 [] 来访问元素，所以 list 容器的遍历方式就只有迭代器和范围 for 了
代码如下：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> mylist1;
mylist1.push_back(10);
mylist1.push_back(20);
mylist1.push_back(30);
mylist1.push_back(50);
mylist1.push_back(60);
mylist1.push_back(70);
list<int>::iterator it = mylist1.begin();
while (it != mylist1.end()) {
cout << *it << " ";
it++;
}
cout << endl;
return 0;
}
运行如下所示：
代码如下所示：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> mylist1;
mylist1.push_back(1);
mylist1.push_back(2);
mylist1.push_back(3);
mylist1.push_back(5);
mylist1.push_back(6);
mylist1.push_back(7);
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
return 0;
}
运行如下所示：
list 中的节点在内存中是离散存放的，没有像 vector 和 string 这么多的容量函数。插入数据也不需要扩容，只需要 new 一个节点来存放数据和前后节点的指针就可以了，list 有以下三个容量函数
| 接口名称 | 接口说明 |
|---|---|
| size() | 返回 list 中元素个数 |
| empty() | 判断 list 是否为空 |
| resize() | 重新设置 list 的元素个数 |
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls(10, 1);
cout << ls.size() << endl;
return 0;
}
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls1(10, 1);
list<int> ls2;
cout << ls1.empty() << endl;
cout << ls2.empty() << endl;
return 0;
}
resize 的函数原型如下：
1、当 n 大于 list 的 size 时，会在尾部插入 val，如果我们传入了 val，就插入我们传入的 val，如果没有传入，就调用 val 类型的默认构造函数。
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls(10, 1);
cout << "当前 list 的 size 是:" << ls.size() << endl;
ls.resize(15, 4);
cout << "现在 list 的 size 是:" << ls.size() << endl;
for (auto& ele : ls) {
cout << ele << " ";
}
cout << endl;
return 0;
}
2、当 n 小于 list 的 size 时，会删除 list 中的元素。
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls(10, 1);
cout << "当前 list 的 size 是:" << ls.size() << endl;
ls.resize(5);
cout << "现在 list 的 size 是:" << ls.size() << endl;
for (auto& ele : ls) {
cout << ele << " ";
}
cout << endl;
return 0;
}
因为 list 在内存中不是连续存放的，所以就不能通过方括号和 at 来进行访问，list 提供了 front 和 back 函数来访问 list 第一个元素和最后一个元素。
| 接口名称 | 接口说明 |
|---|---|
| front() | 返回一个元素的引用 |
| back() | 返回最后一个元素的引用 |
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
ls.push_back(4);
ls.push_back(5);
cout << ls.front() << endl;
return 0;
}
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
ls.push_back(4);
ls.push_back(5);
cout << ls.back() << endl;
return 0;
}
| 接口名称 | 接口说明 |
|---|---|
| push_back() | 尾插一个元素 |
| pop_back() | 尾删一个元素 |
| push_front() | 头插一个元素 |
| pop_front() | 头删一个元素 |
| insert() | 在指定迭代器位置之前插入一个元素 |
| erase() | 删除迭代器位置的元素 |
| swap() | 用来交换两个 list 容器 |
| clear() | 用来清空 list 容器 |
| assign() | 替换数据 |
| emplace_back() | 这个函数和 push_back() 函数具有一样的功能 |
这个函数的作用是在 list 尾部插入一个元素，代码如下：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls;
ls.push_back(10);
ls.push_back(20);
ls.push_back(30);
ls.push_back(40);
for (auto& ele : ls) {
cout << ele << " ";
}
cout << endl;
return 0;
}
这个函数的作用是在 list 尾部删除一个元素，代码如下：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls;
ls.push_back(10);
ls.push_back(20);
ls.push_back(30);
ls.push_back(40);
ls.pop_back();
for (auto& ele : ls) {
cout << ele << " ";
}
cout << endl;
return 0;
}
这个函数的作用是在 list 头部插入一个元素，代码如下：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls;
ls.push_front(10);
ls.push_front(20);
ls.push_front(30);
ls.push_front(40);
for (auto& ele : ls) {
cout << ele << " ";
}
cout << endl;
return 0;
}
这个函数的作用是在 list 头部删除一个元素，代码如下：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
ls.push_back(4);
ls.push_back(5);
ls.pop_front();
for (auto& ele : ls) {
cout << ele << " ";
}
cout << endl;
return 0;
}
insert() 函数原型如下：
insert 重载了三个版本：
这个函数是往迭代器位置之前插入一个 value 元素。
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
ls.push_back(4);
list<int>::iterator it = ls.begin();
it++;
ls.insert(it, 100); //在第二个位置之前插入 100
for (auto& ele : ls) {
cout << ele << " ";
}
return 0;
}
这个函数是往迭代器位置之前插入 num 个 value 元素。
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
ls.push_back(4);
list<int>::iterator it = ls.begin();
it++;
ls.insert(it, 5,100);//在第二个位置之前插入 5 个 100
for (auto& ele : ls) {
cout << ele << " ";
}
return 0;
}
这个函数是往迭代器位置之前插入另外迭代器区间的元素。这个迭代器区间可以是其他类型的迭代器区间。
#include<iostream>
using namespace std;
#include<list>
#include<vector>
int main() {
list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
ls.push_back(4);
list<int>::iterator it = ls.begin();
it++;
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
//在第二个位置之前插入 vector 容器的数据
ls.insert(it, v.begin(),v.end());
for (auto& ele : ls) {
cout << ele << " ";
}
return 0;
}
因为 list 里面的元素在内存里面是离散存放的，所以我们插入数据不会导致迭代器失效。
erase() 函数原型如下：
erase 重载了两个版本
返回值是删除元素的下一个迭代器。
这个函数是删除迭代器指向的元素
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls;
ls.push_back(10);
ls.push_back(20);
ls.push_back(30);
ls.push_back(40);
list<int>::iterator it = ls.begin();
it++; //删除第二个元素
ls.erase(it);
for (auto& ele : ls) {
cout << ele << " ";
}
cout << endl;
return 0;
}
这个函数是删除迭代器区间的元素。
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls;
ls.push_back(10);
ls.push_back(20);
ls.push_back(30);
ls.push_back(40);
ls.push_back(50);
ls.push_back(60);
list<int>::iterator it = ls.begin();
it++;
list<int>::iterator ite = ls.end();
ite--; //删除 [it,ite) 之间的元素
ls.erase(it,ite);
for (auto& ele : ls) {
cout << ele << " ";
}
cout << endl;
return 0;
}
erase 会导致删除元素的迭代器失效，因为这个元素被删除了，但是不会影响其他的迭代器
用来交换连个 list 容器。实际上是交换 list 的头节点的指针。
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> ls1;
ls1.push_back(1);
ls1.push_back(2);
ls1.push_back(3);
ls1.push_back(4);
list<int> ls2;
ls2.push_back(10);
ls2.push_back(20);
ls2.push_back(30);
ls2.push_back(40);
cout << "交换前：" << endl;
cout << "ls1:" << endl;
for (auto& ele : ls1) {
cout << ele << " ";
}
cout << endl;
cout << "ls2:" << endl;
for (auto& ele : ls2) {
cout << ele << " ";
}
cout << endl;
ls1.swap(ls2);
cout << "交换后：" << endl;
cout << "ls1:" << endl;
for (auto& ele : ls1) {
cout << ele << " ";
}
cout << endl;
cout << "ls2:" << endl;
for (auto& ele : ls2) {
cout << ele << " ";
}
cout << endl;
}
这个函数是清空 list 容器，但是头节点不会被删除。
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> lt(5, 1);
for (auto e : lt) {
cout << e << " ";
}
cout << endl;
lt.clear(); //清空容器
for (auto e : lt) {
cout << e << " ";
}
cout << endl; //(无数据)
return 0;
}
函数原型如下：
这个函数的作用是给 list 容器新的元素，将原来的元素给替换掉。它有两个重载版本
这个重载版本是将 list 中的元素替换为这两个迭代器区间的元素，代码如下：
#include<iostream>
using namespace std;
#include<list>
#include<algorithm>
#include<vector>
int main() {
vector<int> v;
for (int i = 1; i < 10; i++) {
v.push_back(i);
}
list<int> mylist1;
mylist1.push_back(10);
mylist1.push_back(20);
mylist1.push_back(30);
cout << "assign 之前："<<endl;
cout << "mylist：" << endl;
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
mylist1.assign(v.begin(), v.end());
cout << "assign 之后：" << endl;
cout << "mylist：" << endl;
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
return 0;
}
运行结果如下：会将 [v.begin() v.end()) 之间的元素拷贝到 list 容器
这个重载版本是将 list 中的元素替换为 n 个 val，代码如下：
#include<iostream>
using namespace std;
#include<list>
#include<algorithm>
#include<vector>
int main() {
list<int> mylist1;
mylist1.push_back(10);
mylist1.push_back(20);
mylist1.push_back(30);
cout << "assign 之前：" << endl;
cout << "mylist：" << endl;
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
mylist1.assign(10,33);
cout << "assign 之后：" << endl;
cout << "mylist：" << endl;
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
return 0;
}
运行结果如下：会将 list 中的元素替换为 10 个 33
这个函数和 push_back() 函数具有一样的功能，只不过这个函数的功能更加强大。从日常的角度，使用 emplace_back() 函数或者使用 push_back() 函数是一样的。emplace_back() 函数在部分的场景会更加高效一点。所以后续的一些标准都推荐使用 emplace 系列。
日常使用如下所示：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> lt;
lt.push_back(21);
lt.emplace_back(22);
lt.emplace_back(23);
lt.emplace_back(24);
for (auto& ele : lt) {
cout << ele << " ";
}
cout << endl;
return 0;
}
高效的场景如下所示：现在我们理解这么用就可以，emplace_back() 函数涉及到很多没有学过的知识。只了解用法，不关心底层细节。
#include<iostream>
using namespace std;
#include<list>
struct A {
public:
A(int a1 = 1,int a2=1) :_a1(a1), _a2(a2) {}
int _a1;
int _a2;
};
int main() {
list<A> lta;
A aa1(1, 1);
lta.push_back(aa1);
lta.push_back(A(2,2)); //lta.push_back(2, 2);//不支持这样写
lta.emplace_back(aa1);
lta.emplace_back(A(2, 2)); //emplace_back() 支持直接传入构造 A 对象的参数
lta.emplace_back(3,3);//支持这样写
for (auto& ele : lta) {
cout << ele._a1 <<":"<< ele._a2<<endl;
}
cout << endl;
return 0;
}
| 接口名称 | 接口说明 |
|---|---|
| remove() | 删除 list 中的特定值的元素 |
| remove_if() | 删除 list 中满足条件的元素 |
| unique() | 删除连续的重复值 |
| merge() | 合并两个有序 list |
| sort() | 排序 |
| reverse | 反转 list |
| splice | 将 list 中的元素转移到 list(这个 list 可以是相同的 list，也可以是不同的 list) |
函数原型如下：
这个函数的作用是删除 list 中节点值等于 val 的节点。
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> mylist;
mylist.push_back(10);
mylist.push_back(20);
mylist.push_back(30);
mylist.push_back(40);
mylist.push_back(10);
mylist.push_back(10);
cout << "删除前：" << endl;
for (auto& ele : mylist) {
cout << ele << " ";
}
cout << endl;
mylist.remove(10); //删除节点中值为 10 的节点
cout << "删除后：" << endl;
for (auto& ele : mylist) {
cout << ele << " ";
}
cout << endl;
return 0;
}
函数原型如下：
这个函数的作用是删除 list 中满足这个条件的节点，这个函数的参数是一个仿函数，学到后面就理解了。
#include<iostream>
using namespace std;
#include<list>
bool single_digit(const int value) {
return value<10;
}
int main() {
list<int> mylist;
mylist.push_back(11);
mylist.push_back(2);
mylist.push_back(32);
mylist.push_back(4);
mylist.push_back(14);
mylist.push_back(1);
mylist.push_back(8);
cout << "删除前：" << endl;
for (auto& ele : mylist) {
cout << ele << " ";
}
cout << endl;
mylist.remove_if(single_digit);//删除小于 10 的数
cout << "删除后：" << endl;
for (auto& ele : mylist) {
cout << ele << " ";
}
cout << endl;
return 0;
}
这个函数的作用是删除 list 中连续的重复值，使用这个函数删除重复值需要 list 是有序的，如果不是有序的，就只能删除相邻的重复值，后面不相邻的重复值就不会删除。
以下是无序的例子：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> mylist;
mylist.push_back(1);
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(2);
mylist.push_back(1);
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(1);
mylist.unique();
for (auto& ele : mylist) {
cout << ele << " ";
}
return 0;
}
以下是有序的例子：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> mylist;
mylist.push_back(1);
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(2);
mylist.push_back(1);
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(1);
mylist.sort();
mylist.unique();
for (auto& ele : mylist) {
cout << ele << " ";
}
return 0;
}
这个函数的作用是合并两个有序列表，形成一个大的有序 list。这个函数会将参数的那个 list 的元素给移动到调用这个函数的 list。所以会导致一个 list 元素清空。代码如下所示：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> mylist1;
mylist1.push_back(1);
mylist1.push_back(3);
mylist1.push_back(5);
list<int> mylist2;
mylist2.push_back(2);
mylist2.push_back(4);
mylist2.push_back(6);
cout << "合并前" << endl;
cout << "mylist1:";
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
cout << "mylist2:";
for (auto& ele : mylist2) {
cout << ele << " ";
}
cout << endl;
mylist1.merge(mylist2);
cout << "合并后" << endl;
cout << "mylist1:";
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
cout << "mylist2:";
for (auto& ele : mylist2) {
cout << ele << " ";
}
cout << endl;
return 0;
}
运行结果如下：
会将 mylist 给移到 mylist1 里面，所以 mylist2 为空。
这个函数的作用是将 list 排序，默认是从小到大排序，可以加上仿函数来从大到小来排序。
不使用仿函数代码如下：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> mylist1;
mylist1.push_back(11);
mylist1.push_back(3);
mylist1.push_back(52);
mylist1.push_back(77);
mylist1.push_back(45);
mylist1.push_back(1);
mylist1.push_back(45);
cout << "排序前：" << endl;
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
mylist1.sort();
cout << "排序后：" << endl;
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
return 0;
}
运行结果如下所示：
使用仿函数代码如下：
仿函数是一个特殊的类，自带了 less 和 greater 的类。less ls;greater gt;
从小到大排序就用 ls，从大到小就用 gt；
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> mylist1;
mylist1.push_back(11);
mylist1.push_back(3);
mylist1.push_back(52);
mylist1.push_back(77);
mylist1.push_back(45);
mylist1.push_back(1);
mylist1.push_back(45);
cout << "排序前：" << endl;
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
greater<int> gt;
mylist1.sort(gt);
cout << "排序后：" << endl;
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
return 0;
}
运行结果如下：
但是我们使用 sort 之前还需要再实例化一个对象，是不是太复杂了呢？我们可以直接传入一个匿名对象，如下所示：
mylist1.sort(greater());
我们 list 容器里面自己实现了一个 sort 函数，为什么算法库里面有还需要自己来实现呢？上面迭代器部分讲过：算法库里面的 sort 函数需要传入随机迭代器，而 list 容器的迭代器是双向迭代器。
此外，list 容器中的 sort 函数效率非常低，数据量少可以用它排序，数据量多了尽量不要用它来排序。数据量多的时候，我们可以将 list 容器里面的数据拷贝一份给 vector，让 vector 来排序，排序完成之后再拷贝给 list，虽然上面需要三步，但是这三步花费的时间是要比直接给 list 排序花费的时间少的。我们写一段代码来测试一下：测试要使用 release 情况下测试，debug 没有参考价值（debug 会打很多调试信息，所以没有参考价值）。
代码 1：测试算法库中的 sort 和 list 容器自带的 sort 的性能：给一百万的数据
#include<iostream>
using namespace std;
#include<list>
#include<algorithm>
#include<vector>
int main() {
srand(time(0));
const int N = 1000000;
list<int> lt1;
vector<int> v;
v.reserve(N);
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;
return 0;
}
运行结果如下：
list 和 vector 在相同的数据情况下，vector 排序要比 list 排序快的多。
代码二：测试将 list 数据拷贝给 vector，排序然后再拷贝回来的时间与直接使用 list 排序的时间相比
#include<iostream>
using namespace std;
#include<list>
#include<algorithm>
#include<vector>
int main() {
srand(time(0));
const int N = 1000000;
list<int> lt1;
list<int> lt2;
for (int i = 0; i < N; i++) {
auto e = rand() + i;
lt1.push_back(e);
lt2.push_back(e);
}
int begin1 = clock(); //拷贝到 vector
vector<int> v(lt1.begin(), lt1.end());
//排序
sort(v.begin(), v.end());
//拷贝回 lt1
lt1.assign(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
lt2.sort();
int end2 = clock();
cout << "list->vector->list sort:" << end1 - begin1 << endl;
cout << "list sort:" << end2 - begin2 << endl;
return 0;
}
运行结果如下：
我们将 list 容器里面的数据拷贝一份给 vector，让 vector 来排序，排序完成之后再拷贝给 list 这个所花费的时间还没有直接给 list 排序花费的时间多。
这个函数的作用是翻转 list 里面中的元素。
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> mylist1;
mylist1.push_back(111);
mylist1.push_back(222);
mylist1.push_back(333);
mylist1.push_back(444);
mylist1.push_back(555);
mylist1.push_back(666);
mylist1.push_back(777);
cout << "翻转前：" << endl;
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
mylist1.reverse();
cout << "翻转后：" << endl;
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
return 0;
}
运行如下所示：
splice 函数原型如下：
将容器 x 中的所有元素转移到 position 这个位置之前。代码如下：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> mylist1;
list<int> mylist2;
for (int i = 1; i <= 4; i++) {
mylist1.push_back(i); //mylist1: 1 2 3 4
}
for (int i = 1; i <= 3; i++) {
mylist2.push_back(i*10); //mylist2: 10 20 30
}
cout << "splice() 之前" << endl;
cout << "mylist1:";
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
cout << "mylist2:";
for (auto& ele : mylist2) {
cout << ele << " ";
}
cout << endl;
list<int>::iterator it = mylist1.begin();
it++; //it 指向 mylist1 容器的第二个元素
mylist1.splice(it, mylist2); //转移容器 mylist2 中的元素到 it 位置之前
cout << "splice() 之后" << endl;
cout << "mylist1:";
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
cout << "mylist2:";
for (auto& ele : mylist2) {
cout << ele << " ";
}
cout << endl;
return 0;
}
运行结果如下：
将容器 x 中从迭代器 i 的元素转移到 position 这个位置之前。代码如下：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> mylist1;
list<int> mylist2;
for (int i = 1; i <= 4; i++) {
mylist1.push_back(i); //mylist1: 1 2 3 4
}
for (int i = 1; i <= 3; i++) {
mylist2.push_back(i * 10); //mylist2: 10 20 30
}
cout << "splice() 之前" << endl;
cout << "mylist1:";
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
cout << "mylist2:";
for (auto& ele : mylist2) {
cout << ele << " ";
}
cout << endl;
list<int>::iterator it = mylist1.begin();
it++; //it 指向 2
list<int>::iterator itbegin = mylist2.begin();
itbegin++; //itbegin 指向 20
mylist1.splice(it, mylist2,itbegin); //会将 mylist2 中的 20 元素转移到 2 这个元素之前
cout << "splice() 之后" << endl;
cout << "mylist1:";
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
cout << "mylist2:";
for (auto& ele : mylist2) {
cout << ele << " ";
}
cout << endl;
return 0;
}
运行结果如下所示：
将容器 x 中从迭代器 first 开始到迭代器 last 之间的元素转移到 position 这个位置之前。代码如下：
#include<iostream>
using namespace std;
#include<list>
int main() {
list<int> mylist1;
list<int> mylist2;
for (int i = 1; i <= 4; i++) {
mylist1.push_back(i); //mylist1: 1 2 3 4
}
for (int i = 1; i <= 7; i++) {
mylist2.push_back(i * 10); //mylist2: 10 20 30 40 50 60 70
}
cout << "splice() 之前" << endl;
cout << "mylist1:";
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
cout << "mylist2:";
for (auto& ele : mylist2) {
cout << ele << " ";
}
cout << endl;
list<int>::iterator it = mylist1.begin();
it++; //it 指向 2
it++; //it 指向 3
list<int>::iterator itbegin = mylist2.begin();
itbegin++; //itbegin 指向 20
list<int>::iterator itend = mylist2.end();
itend--; //itend 指向 70
mylist1.splice(it, mylist2, itbegin,itend); //会将 mylist2 迭代器 [itbegin,itend) 之间的元素转移到 3 这个元素之前
cout << "splice() 之后" << endl;
cout << "mylist1:";
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
cout << "mylist2:";
for (auto& ele : mylist2) {
cout << ele << " ";
}
cout << endl;
return 0;
}
运行结果如下所示：
有时我们会将 list 容器 [1,2,3,4,5,6,7,8,9] 中的 6 移到开始位置，我们就可以使用 splice，如果不使用 splice，我们就需要 delete6 这个节点，然后再 new 一个节点，效率低下，所以我们就可以使用 splice 函数。代码如下所示：我们输入哪一个数字，就会把哪一个元素放到第一个位置。
#include<iostream>
using namespace std;
#include<list>
#include<algorithm>
int main() {
list<int> mylist1;
for (int i = 1; i <= 9; i++) {
mylist1.push_back(i);
}
int x;
cin >> x;
cout << "splice() 之前" << endl;
cout << "mylist1:";
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
auto posx = find(mylist1.begin(), mylist1.end(),x);
if (posx != mylist1.end()) {
mylist1.splice(mylist1.begin(), mylist1, posx);
}
cout << "splice() 之后" << endl;
cout << "mylist1:";
for (auto& ele : mylist1) {
cout << ele << " ";
}
cout << endl;
return 0;
}
运行结果如下所示：
| 对比 | vector | list |
|---|---|---|
| 底层结构 | 动态顺序表，连续空间 | 带头结点的双向循环链表 |
| 访问 | 支持随机访问，首地址 + 下标 | 不能随机访问，可通过 find 查找，访问随即元素时间复杂度 O(N) |
| 插入删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为 O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为 O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率较高，缓存利用率高。可以一次将一个数据附近的空间都加载到缓存，不用频繁地从内存读取数据 | 底层节点动态开辟，容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对指针进行了封装 |
| 迭代器失效 | 容量相关的操作都有可能导致迭代器失效，如插入引起的扩容，删除元素等 | 插入元素不会导致迭代器失效，删除节点会导致，且只影响当前迭代器，其他迭代器不受影响 |
| 使用场景 | 不关心插入和删除效率，支持随机访问 | 大量插入和删除操作，不关心随机访问的场景 |
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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