自定义比较器的std::set为何find(4)返回存在？求解析

我正在研究std::set，编写了如下代码：

#include <set>
#include <iostream>
using namespace std;
struct cmp{
    bool operator () (const int & a,const int & b) const {
        if(abs(a-b)<=3)
            return false;
        return a < b;
    }
};
set<int,cmp> q{1, 2, 10};
int main(){
    if(q.find(4)!=q.end())
        cout << 1;
    else
        cout << 2;
}

程序输出为1。我通过自定义cmp结构体作为比较规则，意图让差值≤3的元素不被插入，但奇怪的是std::set的find()行为不符合预期：集合中并没有元素4，为何q.find(4)不等于q.end()？难道find()不是用于查找集合中等于目标值的元素吗？

问题根源解析 #

1. std::set的比较器必须满足严格弱序 #

std::set依赖严格弱序规则维护内部结构，你的自定义cmp完全违反了这个要求。严格弱序需要满足核心特性：

• 非自反性：cmp(a,a)必须返回false
• 不对称性：若cmp(a,b)为true，则cmp(b,a)必须为false
• 传递性：若cmp(a,b)和cmp(b,c)都为true，则cmp(a,c)必须为true
• 等价传递性：若a与b等价（!cmp(a,b) && !cmp(b,a)），b与c等价，则a与c也必须等价

你的cmp不满足等价传递性：比如1和4等价（差值3≤3），4和7等价（差值3≤3），但1和7差值6>3，cmp(1,7)返回true，直接导致std::set的所有操作（插入、查找等）行为未定义。

2. find()的匹配逻辑是"比较器等价"而非"值相等" #

std::set::find()不会直接匹配值相等的元素，而是找集合中与目标值比较器等价的元素——即满足!cmp(element, target) && !cmp(target, element)的元素。

回到你的代码：查找4时，集合中的元素1会被判定为和4等价——cmp(1,4)返回false（差值3≤3），cmp(4,1)也返回false，所以find()会返回指向1的迭代器，自然不等于q.end()，最终输出1。

3. 需求的正确实现方式 #

你想实现"差值≤3的元素不插入"，不能通过自定义比较器完成，这必然违反严格弱序。正确做法是：

• 使用默认的std::less<int>作为比较器
• 插入元素前，手动检查集合中是否存在与待插入元素差值≤3的元素，仅当不存在时执行插入

示例代码片段：

set<int> q{1,2,10};

bool canInsert(int val) {
    auto it = q.lower_bound(val - 3);
    while (it != q.end() && *it <= val + 3) {
        return false;
    }
    return true;
}

// 插入示例
int newVal = 4;
if (canInsert(newVal)) {
    q.insert(newVal);
}

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