C++自定义对象排序问题：Compare谓词不符合严格弱序如何修正？

需求回顾 #

容器为std::vector<MyObject*>，MyObject包含id、number（值为-1或唯一正整数）、timestamp（全局唯一）属性。排序规则：

• 若两个对象的number均为正整数，按number降序排列；
• 其他情况（至少一个对象number为-1），按timestamp降序排列。

问题根源 #

原比较函数不符合C++标准库要求的严格弱序关系，导致std::sort行为未达预期。严格弱序需满足：

1. 自反性：comp(a,a)必须返回false；
2. 非对称性：若comp(a,b)为true，则comp(b,a)必为false；
3. 传递性：若comp(a,b)和comp(b,c)为true，则comp(a,c)必为true；
4. 等价传递性：若a与b等价（!comp(a,b) && !comp(b,a)）、b与c等价，则a与c必等价。

正确的比较函数实现 #

以下实现严格遵循上述规则，同时满足业务排序需求：

1. 静态成员函数形式

#include <vector>
#include <algorithm>

struct MyObject {
    int id;
    int number;
    long long timestamp; // 假设用长整型存储唯一时间戳

    static bool compare(const MyObject* a, const MyObject* b) {
        // 优先处理两个均为有效number的情况
        if (a->number != -1 && b->number != -1) {
            // number降序：a的number更大时，a排在b前面
            return a->number > b->number;
        }
        // 其余情况（含一个/两个number为-1），按timestamp降序
        return a->timestamp > b->timestamp;
    }
};

// 调用示例
void sortContainer(std::vector<MyObject*>& objList) {
    std::sort(objList.begin(), objList.end(), MyObject::compare);
}

2. Lambda表达式形式（更灵活）

// 直接在sort调用中定义排序逻辑
std::sort(objList.begin(), objList.end(), [](const MyObject* a, const MyObject* b) {
    if (a->number != -1 && b->number != -1) {
        return a->number > b->number;
    }
    return a->timestamp > b->timestamp;
});

为什么这个实现符合严格弱序？ #

• 自反性：无论number还是timestamp判断，自身与自身比较时，a->number > a->number和a->timestamp > a->timestamp均返回false，符合要求；
• 非对称性：
  • 若两个对象均为有效number，a->number > b->number为true时，b->number > a->number必然为false；
  • 若涉及-1的number，因timestamp全局唯一，a->timestamp > b->timestamp为true时，b->timestamp > a->timestamp必然为false；
• 传递性：
  • 同有效number组内，降序排序的传递性自然成立；
  • 混合/全-1组内，基于唯一timestamp的降序排序传递性也成立；
• 等价传递性：因timestamp唯一、有效number唯一，仅当两个指针指向同一对象时才会等价，等价关系的传递性自然满足。

内容的提问来源于stack exchange，提问作者Giorgio R