🌈一、认识list这个模版

1. ist是一个模版，需要结合一个具体的数据类型作为模版参数，
   即list$<T>$，才能成为一个类类型。
2. list是双向循环链表，是序列容器，允许在序列中的任何位置进行恒定时间的插入和消除操作，以及双向迭代。
   注意与单链表forward_list区分。
3. list的优势：与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
4. list的劣势：与其他序列式容器相比，list和forward_list不支持任意位置的随机访问，只能通过遍历的方式访问指定节点。
5. list相对forward_list的优势：可以双向遍历链表，并且不需要保证尾节点的next指针为空。

🌈二、list的基本操作函数

☀️1.构造、拷贝构造

🎈4个重载介绍：

1. 构造空list
2. 构造可包含n个T类型数据的list
3. 构造list，用first到last区间中的元素构造。注意可以是别的容器中的元素。（例如可以用vector$<int>$中的一段数据构造一个新的list$<int>$。还可以用string等等）。
4. 拷贝构造。用已有的一个list构造新的list。

☀️2.迭代器与遍历

🎈（1）迭代器

迭代器类型：std::list$<T>$::iterator、std::list$<T>$::const_iterator、std::list$<T>$::reverse_iterator、std::list$<T>$::const_reverse_iterator

返回迭代器的函数：

🎈（2）list的遍历

由于list的底层物理空间不是连续的，因此不能用while循环加<的遍历方式，如图：

正确方法1：将while中的符号变成!=。

正确方法2：for循环（底层为迭代器）

☀️3.大小

注意，无容量相关函数，因为链表不需要提前申请底层空间。只有大小的说法，有几个节点，链表的大小就是几。

☀️4.元素访问

通过front函数获得第一个结点中的数据的引用，通过back函数获得最后一个节点中的数据的引用。要想访问链表除头尾节点的内容，只能通过遍历的方式。

☀️5.增删改

🎈（1）增：插入

①插入新的头结点：push_front

②插入新的尾节点：push_back

③在链表内部插入多个节点：insert

3个重载介绍：

1. 在position位置插入一个包含数据val的节点。
2. 在position位置插入n个包含数据val的节点。
3. 在position位置插入从first到last这段区间的节点。注意first和last可以指向其他容器，比如将vector$<int>$中first到last区间的数据，包装成list$<int>$的节点，再插入至list$<int>$的position位置。

🎈（2）删：删除

①删除头节点：pop_front

②删除尾节点：pop_back

③删除指定节点（单个、多个）：erase

④清空所有有效元素：clear

清空完后，链表就相当于一个空链表。

🌟注意：删除引发迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。
因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

解决方法：下次使用前对迭代器重新赋值。

🎈（3）改：

①交换两个list中的有效元素：swap

②用新内容替换原内容：assign

2个重载介绍：

1. 用迭代器first和last区间的节点替换掉list中原来的所有节点。
2. 用n个包含数据val的节点替换掉list中原来的所有节点。

举例应用：
原链表内容是10个1，先将链表内容替换成5个2，再替换回原样。

#include<iostream>
#include<list>
using namespace std;
int main() {list<int> ls1(10, 1);for (auto node : ls1) {cout << node << ' ';}cout << endl;list<int> ls2(ls1);ls2.assign(5, 2);for (auto node : ls2) {cout << node << ' ';}cout << endl;ls2.assign(ls1.begin(), ls1.end());for (auto node : ls2) {cout << node << ' ';}cout << endl;
}

🌈三、list的特殊功能函数

☀️1.merge：两个有序链表归并成一个有序链表

🎈（1）2个重载介绍：

注：前提是原链表和链表x都为有序链表，默认升序。

1. 将有序链表x按照默认的升序合并至原链表中，合并后x变为空链表。合体后的整个链表仍有序，为默认的升序，即operator<函数的规则。
2. 将有序链表x按照comp函数的排序规则合并至原链表中，合并后x变为空链表。

🎈（2）理解comp：

1. comp本质是一个函数指针或函数（对象），用于设计排序规则，返回值为bool类型。
2. 函数有两个参数，如果第一个参数在其定义的排序中位于第二个参数之前，则返回true，否则返回false。
3. 在comp中设计数据的强弱规则，比如整数部分相同的数地位相等，无需管小数部分，等等。

🎈（3）举例使用merge函数

#include<iostream>
#include<list>
using namespace std;bool mycomparison(double first, double second)
{return (int(first) < int(second));
}int main()
{list<double> first, second;first.push_back(3.1);first.push_back(2.2);first.push_back(2.9);second.push_back(3.7);second.push_back(7.1);second.push_back(1.4);first.sort();//2.2 2.9 3.1second.sort();//1.4 3.7 7.1first.merge(second);//1.4 2.2 2.9 3.1 3.7 7.1cout << "first contains:";for (list<double>::iterator it = first.begin(); it != first.end(); ++it) {cout << ' ' << *it;}cout << '\n';// (second is now empty)second.push_back(2.1);second.push_back(2);second.push_back(3);second.push_back(7);first.merge(second, mycomparison);//1.4 2.2 2.9 (2.1) (2) 3.1 3.7 (3) 7.1 (7)cout << "first contains:";for (list<double>::iterator it = first.begin(); it != first.end(); ++it) {cout << ' ' << *it;}    cout << '\n';return 0;
}

分析：

1. second链表在第一次合并后被清空了，后序又对second链表先后插入了2.1、2、3、7这四个数。
2. first.merge(second, mycomparison); 这条指令发出后，开始在原来的first链表中按照myconparison函数设定的规则，按顺序插入second链表中的4个数。
3. myconparison函数设定的规则是这样的：只看整数部分排升序。比如两个数2.1和2，他们的整数部分都是2，因此该函数认为两数一样大，那么按照什么顺序插入他两的，最终他两就是啥顺序。
4. 于是上述程序中，2.1被mycomparison函数看作与2.2、2.9一样大，2.1是后来被插入的，因此就放在2.9的后面；同理，2被看做和2.2、2.9、2.1一样大，被放在2.1后面；3被看做和3.1、3.7一样大，被放在3.7后面；7被看做和7.1一样大，被放在7.1后面。

☀️2.unique：去除有序链表中的重复项

🎈（1）2个重载介绍：

1. 从容器中的每个相等元素的连续组中，移除除第一个元素之外的所有元素。
   注意，只有当一个元素与紧挨在它前面的元素进行比较时，它才会从列表容器中删除。因此，此函数对排序列表特别有用。
2. 依据binary_pred中规定的行为，对符合规定的数据进行删除。不仅局限于删除相等的连续数据，还可以有别的删除规则，比如删除整数部分相等的、删除比前一个数大5的。
   注意，该函数将为所有两两一组的元素对调用binary_pred（i，（i-1））（其中i是元素的迭代器，从第二个开始），如果谓词返回true，则从列表中删除i。

🎈（2）理解binary_pred

1. binary_pred本质是一个函数指针或函数（对象），用于设计删除数据的规则。
2. 函数形式为binary_pred（i，（i-1）），有两个参数，如果第一个参数在其定义的排序中位于第二个参数之前，则返回true，否则返回false。
3. 在binary_pred中设计删除数据的原则，比如删除整数部分相等的、删除比前一个数大5的。

🎈（3）举例使用unique函数

借助网站中给的例子：

输出：
mylist contains: 2.72 12.15 72.25

红框：same_integral_part和is_near都是binary_pred函数（指针或对象），但二者设定的删除规则不同。same_integral_part的规则是删除整数部分相同的数据；is_near的规则是，若后面的数减去前面的数小于5，则删除后面的数。

蓝框：三次调用unique函数。第一次就是最普遍的去除重复的，同样的数只保留一个；第二次是按照same_integral_part的规则，去除整数部分相同的数；第三次是参照is_near的规则，去除掉相对于前面的一个数大却大不过5的数。

☀️3.sort：归并排序

🎈（1）2个重载介绍

1. 按照升序排序，即operator<函数的规则。
2. 按照comp的规则排序。（comp和merge中介绍的一样）

🎈（2）两个sort函数的区别

算法库algorithm（使用时包含头文件#include$<algorithm>$）中也有一个sort函数，和list$<T>$的成员函数有何区别？

1. 底层原理：算法库里面sort本质是快排，底层涉及到迭代器相减；list的成员函数sort用的是归并。因此对于双向带头循环链表这样的物理空间不连续的容器，迭代器不能相减，不可以使用算法库里的sort。

注：算法库里sort函数的源码：

从而得知底层涉及迭代器相减，不可用于物理空间不连续的容器。

2. 运行效率：算法库里的快排sort比list$<T>$的sort成员函数效率高。
   效率对比：现在在vector$<int>$和list$<int>$类型的两个容器ve和li中存放完全相同（包括顺序）的一组无序数据，用算法库的sort对ve排序，用list的成员函数sort对li排序，比较二者运行时间：

#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;int main() {vector<int> ve;list<int> li;srand(time(0));for (int i = 0;i < 1000000;i++) {auto e = rand();ve.push_back(e);li.push_back(e);}int begin1 = clock();sort(ve.begin(), ve.end());int end1 = clock();int begin2 = clock();li.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);return 0;
}

结论：库里的sort时间短。

上面是debug版本，以下是release版本下的时间比较：

差距更明显了。因为vector排序底层用的是递归，深度比较深，递归在debug版本下的优化不太大，在release版本下的优化大，因此二者的时间差距更大。

🎈（3）举例使用sort

借助网站中给的例子：

1. comp在本例子中是一个叫compare_nocase的函数，该函数比较两个字符串中第一个不相同的字母，不区分大小写，若参数一中对应字母在参数二中对应字母的前面，则返回true，否则false。
2. 对于第一次用sort排好序的myList而言，会从前往后两两一组的对容器中的数据调用compare_nocase函数。第一次调用compare_nocase(Three,one)，字母T在字母o的后面，返回false，sort接收到返回值后对二者调换位置；第二次调用compare_nocase(Three,two)，不区分大小写，因此T和t登记相同，不进行调换。
3. 因此第二次按照compare_nocase的规则，myList从Three one two变成了one Three two。

☀️4.splice：转移至原链表

🎈（1）3个重载介绍：

1. 将链表x转移至原链表的position位置，从position位置开始就是原先x中数据了，转移后x不再是单独的链表。
2. 在原链表的position位置插入x链表中由迭代器i指向的那一个数据。
3. 在原链表的position位置插入x链表中迭代器first到last区间的所有数据。

注：
①直接转移x链表的指针至原链表，不涉及开辟空间或销毁空间。
②转移之前指向原链表的迭代器指向的是哪个节点，在有新数据转移进来之后，迭代器仍指向之前那个节点。（不会迭代器失效）

🎈（2）举例使用splice函数

借助网站中给的例子：

注：

1. 将myList2的所有数据转移至myList1后，myList2变为空链表。
2. 指向原链表的迭代器，永远指向那个节点，而不是固定指向链表中第某个节点。
3. 可以将自身的节点转移给自身，注意是转移而不是创建新节点再把旧值拷贝过去，相当于链表自己的节点在内部换了个位置。

🎈（3）splice应用场景

比如12345分别代表用户最近用到的5个程序，并且按照使用的先后顺序排列，1是最早用到的，5是最近用到的。如果我刚刚又用了2这个程序，那就把2从原先的位置拿出来转移到5后面。

#include<iostream>
#include<list>
using namespace std;int main() {list<int> li;li.push_back(1);li.push_back(2);li.push_back(3);li.push_back(4);li.push_back(5);for (auto e : li) {cout << e << ' ';}cout << endl;//用户用了2程序li.splice(li.end(), li, find(li.begin(), li.end(), 2));for (auto e : li) {cout << e << ' ';}cout << endl;//用户用了3程序li.splice(li.end(), li, find(li.begin(), li.end(), 3));for (auto e : li) {cout << e << ' ';}cout << endl;return 0;
}

思考：如果没有splice，如何实现上述操作？
先用2这个数据创建一个新的节点，再将新节点尾插至链表，再将原来的2所在的节点从原链表中剔除（交接好prev和next指针），最后销毁原来2所在的节点。