C++ vector怎么排序 C++ sort函数对vector自定义排序写法【算法】

std::sort对vector默认升序排序需传入begin()和end()迭代器，按operator

vector 默认升序排序用 std::sort

直接调用 std::sort 对 vector 排序，必须传入迭代器范围，不是容器本身。它默认按元素类型的小于关系（operator）升序排列，适用于 int、double、string 等内置或已重载比较运算符的类型：

#include 
#include 
std::vector v = {3, 1, 4, 1, 5};
std::sort(v.begin(), v.end()); // → {1, 1, 3, 4, 5}

注意：别写成 std::sort(v) 或 std::sort(v.data(), v.size()) —— 编译失败。

对 vector 排序需提供比较逻辑

结构体默认没有 operator，std::sort 不知道怎么比。常见写法有三种，按推荐顺序列出：

• 在结构体内定义 operator（最简洁，适合单一自然序）：

struct Person {
    std::string name;
    int age;
    bool operator<(const Person& other) const {
        return age < other.age; // 按年龄升序
    }
};
std::vector people = {{"Alice", 30}, {"Bob", 25}};
std::sort(people.begin(), people.end()); // ✅ 可用

• 传入 lambda 表达式（最灵活，适合临时多条件排序）：

std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.age != b.age ? a.age < b.age : a.name < b.name; // 先按年龄，再按姓名
});

• 单独写比较函数或仿函数（适合复用、或需捕获外部变量但 lambda 不便时）：

bool cmp_by_name(const Person& a, const Person& b) {
    return a.name < b.name;
}
std::sort(people.begin(), people.end(), cmp_by_name);

降序排序和稳定排序要注意什么

降序不能只改 > 就完事，得确保比较逻辑严格弱序（即不满足 a 且不满足 b 时，认为相等）。错误写法：return a > b 在浮点或自定义类型中可能违反严格弱序；正确做法是翻转原比较逻辑：

• 基础类型：用 std::greater() 或 lambda [](int a, int b) { return a > b; }
• 结构体：lambda 中显式写出反向条件，比如 return a.age > b.age（前提是 age 是整型且无 NaN 等异常值）

如果需要相同元素保持原有相对顺序（比如排序前两个同龄人 A 在 B 前，排完还在前面），不能用 std::sort —— 它不保证稳定。该换 std::stable_sort：

std::stable_sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.age < b.age;
});

性能与常见坑：迭代器失效和 const 正确性

std::sort 是就地排序，不改变 vector

容量或指针有效性，但会重排元素——所以排序过程中所有指向元素的原始指针/引用仍有效，但迭代器在排序期间不要保存并后续使用（虽通常不崩，但标准未保证）。

lambda 或比较函数里，参数务必加 const&，否则编译不过（std::sort 内部传的是 const 迭代器解引用结果）：

• 错：[](Person a, Person b) { ... }（值传递，效率低且可能编译失败）
• 错：[](Person& a, Person& b) { ... }（非 const 引用，无法绑定 const 临时对象）
• 对：[](const Person& a, const Person& b) { ... }

真正容易被忽略的是：如果你的比较逻辑依赖某个外部状态（比如按当前用户偏好动态切换排序字段），lambda 必须显式捕获（[&] 或 [=]），且确保被捕获对象生命周期长于排序调用——否则运行时崩溃。