17370845950

std::list::sort只能对自身原地排序，不接受迭代器范围，也不支持其他容器；它是稳定归并排序，时间复杂度O(N log N)，要求比较器满足严格弱序且不可修改元素。

std::list::sort 只能对 list 自身排序，不能传入 vector 或其他容器

std::list 的 sort() 是成员函数，不是算法函数，它只能对当前 std::list 实例原地排序，不接受迭代器范围（比如 begin(), end()），也不支持对 std::vector、std::deque 调用。误以为它是 std::sort 的替代写法，是常见误解。

• std::list::sort() 无参数时按 operator 升序排列
• 可传入自定义比较器，类型必须满足 Compare const&，且不能是 lambda 捕获变量（除非用 std::function 包装或定义为 static/全局）
• 不能对空 list 或只含一个元素的 list 调用出错，但也没必要——它本身是安全的

自定义比较函数必须满足严格弱序，且不能修改元素

传给 sort() 的比较器如果违反严格弱序（比如返回 a ），行为未定义；若在比较过程中修改了被比较对象（例如通过引用修改值），可能导致迭代器失效或无限循环。

• 推荐使用普通函数指针或无捕获 lambda（C++17 起允许无捕获 lambda 作为模板参数）
• 有状态比较需用仿函数类，确保 const operator() 且不改变成员变量语义
• 避免在比较器中做耗时操作（如 IO、内存分配），list::sort() 是归并排序，比较次数约 O(N log N)

与 std::sort 算法的关键区别：稳定、不依赖随机访问

std::list::sort() 是稳定排序，相同元素相对顺序不变；它不依赖迭代器的随机访问能力，仅需双向迭代器，因此比 std::sort（要求随机访问迭代器）更适合链表结构。但代价是无法像 std::sort 那样用 std::execution::par 并行化。

• std::list::sort() 时间复杂度是 O(N log N)，空间复杂度 O(log N)（递归栈深度）
• 若已用 std::vector 存数据，别为了排序转成 list 再调用 sort()——拷贝开销远大于 std::sort 原地排序收益
• 插入频繁 + 偶尔排序 → list::sort() 合理；纯排序场景 → vector + std::sort 更快

完整可运行示例：升序、降序、按成员排序

#include 
#include 

struct Person {
    std::string name;
    int age;
};

int main() {
    std::list people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};

    // 升序：按 age
    people.sort([](const Person& a, const Person& b) { return a.age < b.age; });

    // 降序：注意不能写 a.age > b.age 直接替换，要保持严格弱序逻辑清晰
    people.sort([](const Person& a, const Person& b) { return a.age > b.age; });

    // 按 name 字典序（需包含 ）
    people.sort([](const Person& a, const Person& b) { return a.name < b.n
ame; });

    for (const auto& p : people) {
        std::cout << p.name << "(" << p.age << ") ";
    }
    // 输出类似：Alice(30) Bob(25) Charlie(35)（取决于最后一次 sort）
}

注意：多次调用 sort() 会覆盖前一次顺序；若需保留原始顺序，应先 assign 或构造新 list。