C++重载set比较运算符后insert元素失败是什么原因

你自定义的std::set比较器不符合严格弱序要求，导致容器错误判定待插入元素和已有元素等价，最终插入失败。

相关问题代码 #

class Comp1 {
public:
    bool operator() (const pair<int, int> a1, const pair<int, int>a2) const{
        if (a1.first < a2.first)
            return false;
        else if (a1.second > a2.second)
            return true;
        else
            return false;
    }
};
set<pair<int, int>, Comp1> aset;
aset.insert(pair<int, int>(3, 4));
aset.insert(pair<int, int>(4, 1));

原理说明 #

std::set是基于严格弱序规则实现的有序关联容器，规则要求：

• 比较器comp(a,b)返回true代表a应当排在b之前
• 如果comp(a,b)和comp(b,a)的返回值均为false，容器会判定a和b等价，不会重复插入等价元素

你的比较器逻辑存在明显的维度混乱问题，没有按统一规则定义排序优先级：

1. 当比较已存在的(3,4)和待插入的(4,1)时，调用comp((4,1), (3,4))：a1.first=4不小于a2.first=3，继续判断a1.second=1是否大于a2.second=4，结果不成立，返回false
2. 反向调用comp((3,4), (4,1))：a1.first=3小于a2.first=4，直接返回false
3. 两次比较均返回false，容器判定两个元素等价，直接拒绝插入(4,1)

修复方案 #

如果你的排序需求是「优先按first字段降序排列，first相等时按second字段降序排列」，可以将比较器修改为如下符合严格弱序的实现，同时建议参数传const引用减少拷贝开销：

class Comp1 {
public:
    bool operator() (const pair<int, int>& a1, const pair<int, int>& a2) const{
        if (a1.first != a2.first) {
            return a1.first > a2.first;
        }
        return a1.second > a2.second;
    }
};

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