C++ 比较器

比较器规则

以下使用 C++17。Student 和 byScore 在排序一节定义。

comp(a, b) 为 true，表示 a 在比较器定义的顺序中位于 b 之前。排序、堆和有序容器要求严格弱序：自身比较为假，先后关系可传递，等价关系也可传递。

comp(a, a) == false
comp(a, b) 为真 → comp(b, a) 为假
a 在 b 前，b 在 c 前 → a 在 c 前
等价：!comp(a, b) && !comp(b, a)
a 与 b 等价，b 与 c 等价 → a 与 c 等价

// 三种写法：均表示整数升序
bool ascending(int a, int b) { return a < b; }     // 普通函数
auto less = [](int a, int b) { return a < b; };    // Lambda
struct Less {                                   // 仿函数
    bool operator()(int a, int b) const { return a < b; }
};

算法传对象，容器模板参数填类型。C++17 的 Lambda 不能默认构造，构造容器时需传入对象；对象参数通常使用 const T&，仿函数的 operator() 加 const。

// <algorithm> <vector> <set>；沿用上面的三个比较器
std::vector<int> v{3, 1, 2};
std::sort(v.begin(), v.end(), ascending);         // 也可传 less 或 Less{}
std::set<int, decltype(&ascending)> a(ascending);
std::set<int, decltype(less)> b(less);
std::set<int, Less> c;

参考：C++ 标准草案 · 比较与排序要求

排序 sort

整数直接用默认比较或 greater；多字段先比主字段，相同时再比次字段。

// <algorithm> <functional> <vector>
std::vector<int> v{3, 1, 2};
std::sort(v.begin(), v.end());                       // 1, 2, 3
std::sort(v.begin(), v.end(), std::greater<int>{});   // 3, 2, 1

struct Student { int score, id; };
auto byScore = [](const Student& a, const Student& b) {
    if (a.score != b.score) return a.score > b.score; // 分数降序
    return a.id < b.id;                              // 同分编号升序
};
std::vector<Student> students{{90, 2}, {100, 3}, {90, 1}};
auto stable = students;
std::sort(students.begin(), students.end(), byScore);
// (100, 3), (90, 1), (90, 2)

std::stable_sort(stable.begin(), stable.end(),
    [](const Student& a, const Student& b) { return a.score > b.score; });
// (100, 3), (90, 2), (90, 1)：只比分数，同分保留输入顺序

sort 不保证等价元素的原顺序，stable_sort 保证。pair、tuple 默认按字典序逐项比较；全部字段升序时，可用 tie 简写。

// <algorithm> <utility> <tuple> <vector>
std::vector<std::pair<int, int>> pairs{{2, 1}, {1, 3}, {1, 2}};
std::sort(pairs.begin(), pairs.end());
// (1, 2), (1, 3), (2, 1)：先 first，再 second

struct Point { int x, y; };
auto byXY = [](const Point& a, const Point& b) {
    return std::tie(a.x, a.y) < std::tie(b.x, b.y);
};

优先队列 priority_queue

优先队列中 comp(a, b) 为真，表示 a 比 b 晚出队；top() 是比较顺序末端的元素。

// a < b：sort / set / map 升序；priority_queue / make_heap 为大顶堆
// a > b：sort / set / map 降序；priority_queue / make_heap 为小顶堆

// <queue> <vector> <functional>
std::priority_queue<int> maxHeap;
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
for (int x : {3, 1, 2}) { maxHeap.push(x); minHeap.push(x); }
// maxHeap.top() == 3，minHeap.top() == 1

struct Node { int distance, id; };
struct Later {
    bool operator()(const Node& a, const Node& b) const {
        if (a.distance != b.distance) return a.distance > b.distance;
        return a.id > b.id;
    }
};
std::priority_queue<Node, std::vector<Node>, Later> q;
q.push({5, 2}); q.push({2, 3}); q.push({2, 1});
// 出队顺序：(2, 1), (2, 3), (5, 2)

auto later = [](const Node& a, const Node& b) { return Later{}(a, b); };
std::priority_queue<Node, std::vector<Node>, decltype(later)> q2(later);

top()、pop() 要求队列非空；等价元素的出队次序不保证。

参考：C++ 标准草案 · priority_queue

有序容器 set / map

比较器同时决定顺序和键等价：双向比较都为 false，即视为同一个键，与 operator== 无关。map 只比较键。

// <set> <map> <functional>；沿用 Student、byScore
auto scoreOnly = [](const Student& a, const Student& b) {
    return a.score > b.score;
};
std::set<Student, decltype(scoreOnly)> one(scoreOnly);
one.insert({90, 1});
auto result = one.insert({90, 2});
// result.second == false：只比分数，同分即重复，size() == 1

std::set<Student, decltype(byScore)> distinct(byScore);
distinct.insert({90, 1}); distinct.insert({90, 2});
// 同时比较编号：两个键不同，size() == 2

std::multiset<Student, decltype(scoreOnly)> many(scoreOnly);
many.insert({90, 1}); many.insert({90, 2});
// multiset 允许等价键，size() == 2；map 对应 multimap

std::map<int, int, std::greater<int>> scores{{1, 90}, {3, 80}};
// 按键 3、1 遍历，不按分数排序

修改参与排序的键，应先移除再重新插入；元素仍在容器内时，不应通过指针或外部状态改变其相对顺序。

参考：C++ 标准草案 · 有序关联容器

二分查找

二分查找前，序列应按相同规则排序。找不到时返回 end()。

// <algorithm> <functional> <vector>
// lower_bound：首个 !comp(元素, 查询值) 的位置
// upper_bound：首个  comp(查询值, 元素) 的位置
// 升序：lower 为首个 >= x，upper 为首个 > x
// 降序：lower 为首个 <= x，upper 为首个 < x
std::vector<int> v{9, 7, 7, 3};
auto comp = std::greater<int>{};
auto lo = std::lower_bound(v.begin(), v.end(), 7, comp);
auto hi = std::upper_bound(v.begin(), v.end(), 7, comp);
// 下标分别为 1、3；hi - lo == 2，即 7 的个数

struct Item { int key; };
std::vector<Item> items{{1}, {3}, {3}, {7}};
auto first = std::lower_bound(items.begin(), items.end(), 3,
    [](const Item& item, int key) { return item.key < key; });
auto last = std::upper_bound(items.begin(), items.end(), 3,
    [](int key, const Item& item) { return key < item.key; });
// 参数顺序相反；下标分别为 1、3

set/map 优先使用成员函数，查找为 O(log n)；通用算法在这类迭代器上可能需要线性次数的迭代器移动。

// <set>
std::set<int> values{1, 3, 7};
auto lo = values.lower_bound(3);  // 指向 3
auto hi = values.upper_bound(3);  // 指向 7

参考：C++ 标准草案 · 二分查找算法

原理说明：二分查找

常见错误

// 错误：a <= b 或 a >= b，相等时为 true
// 正确：使用 a < b 或 a > b

// 错误：return a - b; 正负差都会转成 true，且可能溢出
// 正确：return a < b;

// 错误：return !comp(a, b); 等价时会变成 true
// 正确：return comp(b, a); 交换参数反转顺序

// 错误：a.x < b.x || a.y < b.y，可能双向为 true
// 正确：先比主字段，相同时再比次字段
// return a.x != b.x ? a.x < b.x : a.y < b.y;

比较器不修改元素，也不依赖变化中的排序依据。外部配置可按值捕获固定；优先队列中的距离更新可通过压入新快照、出队时丢弃旧记录处理。

// 浮点数：NaN 参与普通 < 比较，可能破坏等价关系的传递性
// 处理：排除 NaN，或明确定义 NaN 统一置前／置后的规则

// 容差：a < b - eps 也可能破坏等价关系的传递性
// 处理：先明确定义离散分组，再比较分组键

// 多字段混合升降序：不要靠 -a.x 凑升序
// 最小负整数取负可能溢出，直接按字段使用 < 或 >