在C++标准库中，std::list是基于双向链表实现的容器，它的内存布局不连续，因此不能使用普通数组容器的sort函数，而是提供了自带的排序接口，同时还有很多链表特有的操作函数。下面我们逐一讲解相关用法。
std::list的基本排序用法
std::list内置了sort成员函数，不需要依赖全局的std::sort算法，这是因为全局sort需要随机访问迭代器，而std::list的迭代器是双向迭代器，不满足要求。默认的sort函数会按照元素的小于运算符进行升序排序。
默认升序排序示例
以下代码演示了对存储int类型的std::list进行默认排序：
#include <iostream>
#include <list>
int main() {
std::list<int> num_list = {5, 2, 8, 1, 3};
// 调用list自带的sort函数进行升序排序
num_list.sort();
// 遍历输出排序后的结果
for (int val : num_list) {
std::cout << val << " ";
}
// 输出结果：1 2 3 5 8
return 0;
}
自定义规则排序
如果需要降序排序或者按照自定义规则排序，可以给sort函数传入一个比较函数或者函数对象，比较函数需要接收两个参数，返回true表示第一个参数应该排在第二个参数前面。
以下是降序排序的示例：
#include <iostream>
#include <list>
int main() {
std::list<int> num_list = {5, 2, 8, 1, 3};
// 传入lambda表达式作为比较规则，实现降序排序
num_list.sort([](int a, int b) {
return a > b;
});
for (int val : num_list) {
std::cout << val << " ";
}
// 输出结果：8 5 3 2 1
return 0;
}
std::list的链表特有操作
除了排序之外，std::list还有很多链表特有的操作，这些操作的时间复杂度大多为O(1)，比普通数组容器更高效。
拼接操作splice
splice函数可以将一个list的元素转移到另一个list中，不需要拷贝元素，只是调整链表节点的指针，效率很高。它有三个重载版本：
- 将整个链表拼接到当前链表的指定位置
- 将另一个链表的单个元素拼接到当前链表
- 将另一个链表的一段区间拼接到当前链表
以下是splice的使用示例：
#include <iostream>
#include <list>
int main() {
std::list<int> list1 = {1, 2, 3};
std::list<int> list2 = {4, 5, 6};
// 将list2的所有元素拼接到list1的begin位置之前
list1.splice(list1.begin(), list2);
// 此时list2为空，list1为4 5 6 1 2 3
for (int val : list1) {
std::cout << val << " ";
}
return 0;
}
链表特有删除操作remove和unique
remove函数会删除链表中所有值等于指定值的元素，unique函数会删除链表中相邻的重复元素，这两个函数都是链表特有的成员函数。
以下是使用示例：
#include <iostream>
#include <list>
int main() {
std::list<int> num_list = {1, 2, 2, 3, 2, 4, 4};
// 删除所有值为2的元素
num_list.remove(2);
// 此时list为1 3 4 4
// 删除相邻的重复元素
num_list.unique();
// 此时list为1 3 4
for (int val : num_list) {
std::cout << val << " ";
}
return 0;
}
链表合并操作merge
merge函数可以将两个已经有序的list合并成一个新的有序list，合并后原来的两个list会被修改，合并过程也是通过调整指针实现，效率较高。
使用示例：
#include <iostream>
#include <list>
int main() {
std::list<int> list1 = {1, 3, 5};
std::list<int> list2 = {2, 4, 6};
// 合并两个有序list，结果升序排列
list1.merge(list2);
// 此时list2为空，list1为1 2 3 4 5 6
for (int val : list1) {
std::cout << val << " ";
}
return 0;
}
注意事项
使用std::list的排序和操作时需要注意，sort函数会修改原链表的元素顺序，而splice、merge等操作会修改参与操作的链表本身。另外，自定义排序规则时需要保证比较函数的严格弱序，否则会导致未定义行为。如果需要频繁随机访问元素，std::list并不适合，因为它的随机访问时间复杂度为O(n)，这种情况应该选择std::vector等连续内存容器。