stable_sort比sort慢但更“守规矩”：它保证相等元素相对顺序不变，因多采用归并类算法，需O(n)额外空间且常数因子大；sort用introsort，平均O(n log n)但不保序。
stable_sort 为什么比 sort 慢但更“守规矩”
stable_sort 保证相等元素的相对顺序不变，sort 不保证。这背后是算法选择差异：sort 通常用 introsort（快排+堆排+插排混合），平均 O(n log n)，但快排部分会打乱相同元素位置；stable_sort 多数实现用归并类策略（如 __merge_sort_with_buffer），需要额外 O(n) 空间，且常带更高常数因子。
实际表现上，小数组（比如 stable_sort 可能慢 1.5–2 倍，且内存分配更频繁。
- 若排序依据是
std::string或自定义类型中operator 仅比较部分字段（如只按id排，但需保留原始插入顺序），必须用stable_sort - 对 POD 类型（如
int、double）纯数值排序，sort足够，且缓存友好 - 在
std::vector上调用stable_sort时，若元素移动开销大（如含大数组成员），归并过程中的拷贝可能比sort的交换更重
当自定义比较函数返回 false 时，stable_sort 仍可能崩
很多人以为只要用了 stable_sort 就“安全”，其实不然。它依然依赖比较函数满足严格弱序（strict weak ordering）。若 comp(a, b) 和 comp(b, a) 同时为 true，或对同一对象 comp(a, a) 返回 true，行为未定义——崩溃、死循环、结果错乱都可能发生，和用不用 stable 无关。
常见翻车点：
立即学习“C++免费学习笔记（深入）”；
- 用浮点数直接比较：
return a.x 在NaN存在时失效（NaN 全为false） - 比较逻辑漏掉相等情况：比如按优先级排序，写成
return a.priority 是 OK 的；但若写成return a.priority 就破坏了严格弱序 - 在 lambda 中捕获外部变量，而该变量生命周期结束（比如引用局部容器的
begin()迭代器）
vector 和 list 的 stable_sort 实现根本不是一回事
std::vector::iterator 是随机访问迭代器，std::stable_sort 对其调用的是全局函数模板，底层走归并路径；而 std::list::sort() 成员函数虽也稳定，但它不是 stable_sort，而是基于指针重连的原地归并，不分配额外元素空间，但也不接受自定义 RandomAccessIterator —— 它只属于 list。
关键区别：
-
std::stable_sort(vec.begin(), vec.end(), comp)：可传任意比较函数，但要求迭代器支持随机访问，且会 allocate 临时缓冲区 -
lst.sort(comp)：仅限list，不 allocate 元素内存（只改指针），但 comp 不能抛异常（否则可能破坏链表结构） - 没有
std::deque::stable_sort成员函数，只能用全局stable_sort，但 deque 迭代器虽是随机访问，其内部分段特性可能导致归并时缓存不友好
多关键字排序时，stable_sort 的链式调用真香但有陷阱
想先按 score 降序，再按 name 升序？最简方案是两次 stable_sort：先按次要 key（name）排，再按主要 key（score）排。因为 stable_sort 不动相等 score 的元素顺序，所以它们内部仍保持 name 有序。
示例：
std::stable_sort(data.begin(), data.end(), [](const auto& a, const auto& b) {
return a.name < b.name;
});
std::stable_sort(data.begin(), data.end(), [](const auto& a, const auto& b) {
return a.score > b.score; // 降序用 >
});
注意点：
- 必须“次要 key 在前，主要 key 在后”，反了就白干
- 如果数据量极大，两次遍历 + 归并开销叠加，不如一次性写复合比较：
return a.score != b.score ? a.score > b.score : a.name （这时用sort也完全 OK） - 若
name是std::string且长度方差大，第一次排序的字符串比较成本可能远超预期
真正容易被忽略的是：当你在调试时把某次 stable_sort 临时换成 sort 验证逻辑，却忘了换回来——后续依赖稳定性的步骤就会静默出错，且难以复现。
