☀️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.1
    second.sort();//1.4 3.7 7.1

    first.merge(second);//1.4 2.2 2.9 3.1 3.7 7.1
    cout << "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所在的节点。