【C++】12：List容器的理解和使用（超详细）
使用list之前需要包含list头文件，list文档介绍。
目录
7.5.2 insert(iterator, num, value)
7.5.3 insert(iterator, iterator1, iterator2)
7.6.2 erase(iterator1,iterator2)
7.9.1 void assign(InputIterator first,InputIterator last)
7.9.2 void assign(size_type n,const value_type& val)
8.7.1 void splice(iterator position,list& x)
8.7.2 void splice(iterator position,list& x,iterator i)
8.7.3 void splice(iterator position,list& x,iterator first,iterator last)
一、List的介绍
list是C++的一个序列容器，插入和删除元素的效率较高，时间复杂度为常数级别，list容器的底层数据结构为带头双向循环链表，这使得 list的元素可以存储在非相邻的内存中，在list内部，不同元素之间通过指向前一个元素的指针以及指向后一个元素的指针相关联。
list 容器与其他序列容器如string,vector相比，由于其底层数据结构为带头双向循环链表，因此 list 在插入删除元素方面很有优势，在列表的任意位置进行插入和删除操作的时间复杂度为O(1)。但不能直接通过位置(下标)来直接访问元素。想要访问list的某个元素，必须从list的一端（或已知位置）迭代到该元素。另外，list还需要额外的存储空间来储存前一个元素和后一个元素的指针信息。
list也同样是一个类模板，我们也需要显示实例化。
1.1 List的存储结构
list 容器底层为带头双向循环链表，带头双向循环链表每个节点包含指向前驱节点的prev指针，指向后继节点的next指针以及节点的数据。list存储结构如下图所示： 哨兵节点表示 链表的第一个元素节点，且不保存任何数据。
1.2 List的优点
- 高效的插入和删除：由于std::list是基于带头双向循环链表实现的，插入和删除操作在任意位置都具有常数时间复杂度O(1)，不需要移动其他元素。这使得std::list在需要频繁插入和删除元素的场景下非常高效。
- 稳定的迭代器：在std::list中进行插入和删除操作不会使得迭代器失效。这意味着在插入或删除元素后，仍然可以继续使用之前获取的迭代器进行遍历和操作。
- 动态内存管理：std::list可以动态调整大小，根据需要分配和释放内存。这使得std::list能够有效地处理大量元素的情况，而不会浪费过多的内存空间。
1.3 List的缺点
- 不支持随机访问：由于std::list的存储结构是带头双向循环链表，访问元素时需要从头或尾开始遍历链表，因此在列表中进行随机访问的效率较低。获取特定位置的元素需要遍历链表，时间复杂度为O(n)，其中n是元素的总数量。
- 占用额外内存：相较于其他容器，std::list在存储上需要额外的指针来维护链表结构，因此在存储大量元素时，它可能占用更多的内存空间。
- 迭代器不支持+和-：std::list的迭代器不支持指针算术运算，无法像指针那样直接进行加减操作，这限制了一些操作的灵活性。
二、List的构造函数
从list使用文档里面，我们可以看到list有如下的几个构造函数：
2.1 默认构造函数
#include<iostream> using namespace std; #include<list> int main() { list<int> l1; return 0; }2.2 构造并初始化n个value
#include<iostream> using namespace std; #include<list> int main() { list<int> l2(10, 1); for (auto& ele : l2) { cout << ele << " "; } cout << endl; return 0; }2.3 使用迭代器区间构造初始化
这个构造函数会将一个迭代器区间的值用来初始化我们的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类型的迭代器进行初始化的。
2.4 拷贝构造
拷贝构造是使用一个已经初始化好的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; }2.5 使用大括构造初始化
这个构造函数是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<int> mylist({ 1,2,3,4,5,6,7});也可以将这一行写出这样：
list<int> mylist={ 1,2,3,4,5,6,7}; 这样写的话就是隐式类型转换。
三、List的迭代器
迭代器属于其对应容器的类域，所以我们在声明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容器不支持[]来访问元素，所以list容器的遍历方式就只有迭代器和范围for了
4.1 迭代器方式遍历
代码如下：
#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; }运行如下所示：
4.2 范围for遍历
代码如下所示：
#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容量的函数
list中的节点在内存中是离散存放的，没有像vector和string这么多的容量函数。插入数据也不需要扩容，只需要new一个节点来存放数据和前后节点的指针就可以了，list有以下三个容量函数
| 接口名称 | 接口说明 |
| size() | 返回list中元素个数 |
| empty() | 判断list是否为空 |
| resize() | 重新设置list的元素个数 |
5.1 size()函数
#include<iostream> using namespace std; #include<list> int main() { list<int> ls(10, 1); cout << ls.size() << endl; return 0; }5.2 empty()函数
#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; }5.3 resize()函数
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的元素获取
因为list在内存中不是连续存放的，所以就不能通过方括号和at来进行访问，list提供了front和back函数来访问list第一个元素和最后一个元素。
| 接口名称 | 接口说明 |
| front() | 返回一个元素的引用 |
| back() | 返回最后一个元素的引用 |
6.1 front()函数
#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; }6.2 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.back() << endl; return 0; }七、List的增删查改
| 接口名称 | 接口说明 |
| push_back() | 尾插一个元素 |
| pop_back() | 尾删一个元素 |
| push_front() | 头插一个元素 |
| pop_front() | 头删一个元素 |
| insert() | 在指定迭代器位置之前插入一个元素 |
| erase() | 删除迭代器位置的元素 |
| swap() | 用来交换两个list容器 |
| clear() | 用来清空list容器 |
| assign() | 替换数据 |
| emplace_back() | 这个函数和push_back()函数具有一样的功能 |
7.1 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; }7.2 pop_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); ls.pop_back(); for (auto& ele : ls) { cout << ele << " "; } cout << endl; return 0; }7.3 push_front()函数
这个函数的作用是在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; }7.4 pop_front()函数
这个函数的作用是在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; }7.5 insert()函数
insert()函数原型如下：
insert重载了三个版本：
- insert(iterator, value);
- insert(iterator, num, value);
- insert(iterator, iterator1, iterator2);
7.5.1 insert(iterator, value)
这个函数是往迭代器位置之前插入一个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; }7.5.2 insert(iterator, num, value)
这个函数是往迭代器位置之前插入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; }7.5.3 insert(iterator, iterator1, iterator2)
这个函数是往迭代器位置之前插入另外迭代器区间的元素。这个迭代器区间可以是其他类型的迭代器区间。
#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里面的元素在内存里面是离散存放的，所以我们插入数据不会导致迭代器失效。
7.6 erase()函数
erase()函数原型如下：
erase重载了两个版本
- erase(iterator)
- erase(iterator1,iterator2)
返回值是删除元素的下一个迭代器。
7.6.1 erase(iterator)
这个函数是删除迭代器指向的元素
#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; }7.6.2 erase(iterator1,iterator2)
这个函数是删除迭代器区间的元素。
#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会导致删除元素的迭代器失效，因为这个元素被删除了，但是不会影响其他的迭代器
7.7 swap()函数
用来交换连个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; }7.8 clear()函数
这个函数是清空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; }7.9 assign()函数
函数原型如下：
这个函数的作用是给list容器新的元素，将原来的元素给替换掉。它有两个重载版本
7.9.1 void assign(InputIterator first,InputIterator last)
这个重载版本是将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容器
7.9.2 void assign(size_type n,const value_type& val)
这个重载版本是将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
7.10 emplace_back()函数
这个函数和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; }八、List常见的操作函数
| 接口名称 | 接口说明 |
| remove() | 删除list中的特定值的元素 |
| remove_if() | 删除list中满足条件的元素 |
| unique() | 删除连续的重复值 |
| merge() | 合并两个有序list |
| sort() | 排序 |
| reverse | 反转list |
| splice | 将list中的元素转移到list(这个list可以是相同的list，也可以是不同的list) |
8.1 remove()函数
函数原型如下：
这个函数的作用是删除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; }8.2 remove_if()函数
函数原型如下：
这个函数的作用是删除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; }8.3 unique()函数
这个函数的作用是删除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; }8.4 merge()函数
这个函数的作用是合并两个有序列表，形成一个大的有序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为空。
8.5 sort()函数
这个函数的作用是将list排序，默认是从小到大排序，可以加上仿函数来从大到小来排序。
8.5.1 sort()函数的使用
不使用仿函数代码如下：
#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<int> ls;greater<int> 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<int>());
8.5.2 sort()函数的效率问题
我们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排序花费的时间多。
8.6 reverse()函数
这个函数的作用是翻转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; }运行如下所示：
8.7 splice()函数
splice函数原型如下：
8.7.1 void splice(iterator position,list& x)
将容器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; }运行结果如下：
8.7.2 void splice(iterator position,list& x,iterator i)
将容器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; }运行结果如下所示：
8.7.3 void splice(iterator position,list& x,iterator first,iterator last)
将容器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; }运行结果如下所示：
九、list和vector的比较
| 对比 | vector | list |
|---|---|---|
| 底层结构 | 动态顺序表，连续空间 | 带头结点的双向循环链表 |
| 访问 | 支持随机访问，首地址+下标 | 不能随机访问，可通过find查找，访问随即元素时间复杂度O(N) |
| 插入删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率较高，缓存利用率高。可以一次将一个数据附近的空间都加载到缓存，不用频繁地从内存读取数据 | 底层节点动态开辟，容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对指针进行了封装 |
| 迭代器失效 | 容量相关的操作都有可能导致迭代器失效，如插入引起的扩容，删除元素等 | 插入元素不会导致迭代器失效，删除节点会导致，且只影响当前迭代器，其他迭代器不受影响 |
| 使用场景 | 不关心插入和删除效率，支持随机访问 | 大量插入和删除操作，不关心随机访问的场景 |
