List的基本功能（1）

前言

上一节我们结束了对vector的讲解，本节我们主要来讲解一下list的功能，那么废话不多说，我们正式进入今天的学习

List的功能介绍

list的结构我们应该相当的熟悉了，他就是数据结构阶段的带头双向循环链表。之所以采用这样的结构是因为带头双向循环链表是链表里面最完美的结构，它有头节点所以找尾节点非常方便，尾插、尾删效率高，双向指针向前找或者向后找都很方便

这里我们要稍微注意一下，List不再支持下标+[]访问了。虽然语法角度来说是可以支持的，但是它如果支持[]的话，就要从头开始向后寻找，时间成本就会变得很高，它的时间复杂度是O(N)，我们之前学习的vector和string的时间复杂度是O(1)，因为数组和字符串是一个连续的空间，通过+i就可以寻找到对应下标的数据；而链表的存储空间是不连续的，不能简单的通过+i来寻找数据

下面我们就来一一分析List一些重要接口的功能

List的构造函数、析构函数、赋值重载

构造函数：

一：全缺省的构造函数（默认构造函数）

二：使用n个value构造的构造函数

三：迭代器区间构造函数

四：拷贝构造函数

析构函数：

这里的功能非常常规，和之前的STL一样，就不做过多解释了

赋值重载：

同为List类型的数据之间的相互赋值

迭代器

begin	返回正向迭代器的开始位置
end	返回正向迭代器的结束位置
rbegin	返回反向迭代器的开始位置
rend	返回反向迭代器的结束位置
cbegin	返回正向const迭代器的开始位置
cend	返回正向const迭代器的结束位置
crbegin	返回反向const迭代器的开始位置
crend	返回反向const迭代器的结束位置

void test_list1()
{list<int>l1{ 1, 2, 3, 4, 5 };auto it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;auto it1 = l1.rbegin();while (it1 != l1.rend()){cout << *it1 << " ";++it1;}cout << endl;
}

空间有关的接口

empty	若链表为空返回true，链表不为空返回false
size	返回链表中数据的个数
max_size	返回链表能容纳的最大数据个数

元素访问接口

front	返回链表最开始节点中的数据
back	返回链表最后节点中的数据

链表修改接口

assign	分配新内容添加到容器中，替换其当前内容，并修改其大小
emplace_front	在容器的开头插入一个新元素
push_front	头插
pop_front	头删
emplace_back	在容器的末尾插入一个新元素
push_back	尾插
pop_back	尾删
emplace	通过在某个位置插入新元素来扩展容器
insert	插入数据
erase	删除数据
swap	交换两个链表
resize	调整容器的大小，使其包含 n 个元素
clear	清空链表，与销毁不同，销毁会带着头结点一起删除，清空只是清空掉链表有效元素，会保留头结点

接口的使用与之前的vector和string相似，不做过多的讲解，这里简单提一下几个特别接口使用：

erase：

	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;for (auto e : lt){cout << e << " ";}cout << endl;it = lt.begin();lt.erase(it + 3);

erase在删除指定位置的时候不能用+来指定位置，因为list的物理空间不是连续的，所以list就没有重载+的使用，list迭代器的类型是双向迭代器

**************************************************************************************************************

这里来补充说明一下迭代器的分类：

迭代器可以按照功能或者性质来分类：

功能：

正向迭代器：iterator

反向迭代器：reverse_iterator

固定正向迭代器：const_iterator

固定反向迭代器：const_reverse_iterator

性质：

单向迭代器：只支持单一 ++ 或者 --；如：forward_list/unordered_map
双向迭代器（BidirectionalIterator）：既能++ 又能--；如：list/map/set
随机迭代器（RandomAccessIterator）：既能++，又能--，还能 + 或 - ；如：string/vector/deque……
（+ ，- 指 iterator 可以 +1 或 -1 ，这些操作是基于底层的存储空间是连续的才得以实现，存储空间不连续的就不行）

性质和功能是由底层结构决定的

迭代器还引申出了两个特殊的迭代器——只读和只写迭代器：

**************************************************************************************************************

emplace_back:

基本可以认为 emplace_back 与 push_back 功能一致，但在某些特定的场景下 emplace_back 比 push_back效率更高，绝大多数情况下二者相差无几

	struct A{public:A(int a1 = 1, int a2 = 1):_a1(a1), _a2(a2){cout << "A(int a1 = 1, int a2 = 1)" << endl;}A(const A& aa):_a1(aa._a1), _a2(aa._a2){cout << "A(const A& aa)" << endl;}int _a1;int _a2;};list<A> lt;A aa1(1, 1);lt.push_back(aa1);//第一种lt.push_back(A(2, 2));//第二种//lt.push_back(3, 3); 不支持A aa2(2, 2);lt.emplace_back(aa2);//第一种lt.emplace_back(A(2, 2));//第二种// 支持直接传构造A对象的参数emplace_backlt.emplace_back(3, 3);//第三种

emplace_back支持直接传自定义对象的参数完成构造，而push_back不支持。

这种语法编译器会拿传入的参数直接构造对象，而其他两种需要先构造一个对象再调用拷贝构造，所以在这种使用场景下emplace_back更高效，可以避免构造+拷贝或者匿名构造+拷贝

最后再来提一下insert函数：

可以看到，insert函数重载了三个函数

一：在pos位置插入一个value

二：在pos位置插入n个value

三：迭代器区间插入

因为list没有重载+，所以要想实现在第n个位置处插入就很麻烦，不能这样写：

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);//lt.insert(lt.begin() + 3, 30)

而是要这么使用：

	list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);//lt.insert(lt.begin() + 3, 30)auto it = lt.begin();int k = 3;while (k--){++it;}lt.insert(it, 30);for (auto e : lt){cout << e << " ";}cout << endl;

目前所例举出来的接口与之前所学的STL的功能基本一致，STL的一致性使得我们在学习每一个STL容器的时候，学习成本都大大降低

与操作相关的接口

splice	剪切并粘贴链表
remove	删除一个指定的值
remove_if	条件删除链表中的元素
unique	删除掉链表中的重复元素
merge	合并链表
sort	排序链表（默认升序）
reverse	逆置链表

splice接口用于剪切并粘贴链表：

splice接口不是复制再粘贴，它会修改被复制的链表

splice会把剪切的链表粘贴在position之前

  std::list<int> mylist1, mylist2;std::list<int>::iterator it;// set some initial values:for (int i=1; i<=4; ++i)mylist1.push_back(i);      // mylist1: 1 2 3 4for (int i=1; i<=3; ++i)mylist2.push_back(i*10);   // mylist2: 10 20 30it = mylist1.begin();++it;                         // points to 2mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4// mylist2 (empty)// "it" still points to 2 (the 5th element)

注意：splice接口可以用于自己转移给自己，所以splice接口有时候可以用于调整当前链表的顺序：

	// 调整当前链表节点的顺序list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);for (auto e : lt){cout << e << " ";}cout << endl;int x = 0;cin >> x;list<int>::iterator it = find(lt.begin(), lt.end(), x);if (it != lt.end()){lt.splice(lt.begin(), lt, it);}for (auto e : lt){cout << e << " ";}cout << endl;

remove接口用于删除一个指定的值

remove接口和erase接口相似，不同的在于remove需要给一个值，它会在链表中查找这个值，如果找到了就删除，没找到也不会报错

‌list的remove函数不会删除列表中所有匹配的元素，只会删除第一个匹配的元素

remove_if接口会配合一个条件来执行删除

它得配合仿函数完成功能，这里就不过多讲解了

unique接口用于删除链表之中重复的元素

unique接口要求链表有序，如果不是有序的链表就会存在一定的问题，因为底层在实现的时候默认链表就是有序的

	list<int> lt;lt.push_back(1);lt.push_back(20);lt.push_back(3);lt.push_back(5);lt.push_back(5);lt.push_back(4);lt.push_back(5);lt.push_back(6);lt.sort();for (auto e : lt){cout << e << " ";}cout << endl;lt.unique();for (auto e : lt){cout << e << " ";}cout << endl;

merge接口的作用是用于合并两个链表

注意merge接口的使用前提是两个待合并的链表之间都得是有序的，在调用merge接口前我们需要先调用sort将两个链表排好序

merge接口的底层就是比较两个链表的每个元素，取小的数据尾插，组成一个新链表，最终把新链表链接到第一个链表上，此时第二个链表为空

这个接口使用的较少，就不做过多的讲解了

list在这里自己实现了一个sort接口用来排序，因为算法库里面的sort它用不了。因为库的sort底层是快排，需要支持随机访问和下标±[]，所以list不可以使用库的sort，它不支持随机迭代器

list中的sort接口默认排的是升序，它的底层是用的归并排序，我们用代码演示一下：

	list<int> lt;lt.push_back(1);lt.push_back(4);lt.push_back(6);lt.push_back(3);lt.push_back(2);lt.push_back(5);//升序lt.sort();for (auto e : lt){cout << e << " ";}cout << endl;

如果我们想要排降序的话就需要使用到一个叫做仿函数的东西，仿函数是一种特殊的类。这里就不详细讲解仿函数的概念了，后面会提及（优先级队列）

	//降序 - 仿函数//less<int> ls;  排降序greater<int> gt; // 排升序lt.sort(gt);//或者使用匿名对象lt.sort(greater<int>());for (auto e : lt){cout << e << " ";}cout << endl;

reverse接口的使用效果和库中的reverse函数相同：

	lt.reverse();reverse(lt.begin(), lt.end());

个人认为这里的设计有一点冗余

提升list排序效率的措施

上一节我们在讲vector"类模板里面的成员函数，还可以接着是函数模板"的时候提到了用vector提升list的排序效率，那么我们现在来具体分析一下：

我们先写一串代码来验证vector和list之间的排序效率：

	srand(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();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);

debug下的排序效率：

release下的排序效率：

可以很明显的看到，基于底层的物理结构，vector的排序效率比list要高很多

基于这些，我们就会想到：能不能迭代器区间构造一个vector，将list里面的数据排序完以后再拷贝回list，这样的效率会不会更高？我们来写个代码验证一下：

	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();// 拷贝vectorvector<int> v(lt2.begin(), lt2.end());// 排序sort(v.begin(), v.end());// 拷贝回lt2lt2.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);

debug下：