使用自定义比较器的std::multiset查找非存在值返回true如何解决

问题根源 #

C++有序关联容器的等价性判断规则完全依赖传入的比较器：对于任意两个键a和b，只要满足!cmp(a,b) && !cmp(b,a)，就会被判定为等价，容器不会额外做值相等校验。

你当前的比较器接收两个索引参数，比较的是索引对应v数组的值，当调用s.find(3)时，3会被当做索引传入比较器，取v[3]的值（示例中为1）和集合中存储的索引对应的值比对，只要集合里存在值为1的元素，就会被判定为等价，因此返回了有效迭代器，不符合预期。 #

优雅解决方案：启用比较器的透明查找特性 #

C++14及以上版本支持关联容器的透明查找能力，不需要引入任何额外辅助数据结构，仅需要改造自定义比较器即可实现按实际值查找的需求：

1. 给比较器添加is_transparent标记，通知容器启用透明查找
2. 重载比较器的调用运算符，支持索引和目标值直接比较

完整示例代码 #

#include <vector>
#include <set>

int main() {
    std::vector<int> v = {1,1,1,1,2,2};
    
    // 改造后的自定义比较器
    struct IndexCmp {
        const std::vector<int>& val_arr;
        // 标记支持透明比较
        using is_transparent = void;

        // 原有排序逻辑：两个索引比较，对应值小的排在前面
        bool operator()(size_t idx_a, size_t idx_b) const {
            return val_arr[idx_a] < val_arr[idx_b];
        }

        // 新增：索引和目标值比较
        bool operator()(size_t idx, int target) const {
            return val_arr[idx] < target;
        }

        // 新增：目标值和索引比较
        bool operator()(int target, size_t idx) const {
            return target < val_arr[idx];
        }
    };

    // 注意：集合存储的是数组索引，类型应为size_t，修正原有int类型的错误
    std::multiset<size_t, IndexCmp> s(IndexCmp{v});

    // 插入索引，对应值分别为1、1、2、2
    s.insert(1);
    s.insert(2);
    s.insert(4);
    s.insert(5);

    // 现在直接查找目标值3，会按值匹配判断，不存在则返回end
    auto iter = s.find(3);
    bool present = iter != s.end(); // present值为false，符合预期
}

方案优势 #

• 无额外数据结构开销，仅修改比较器逻辑即可
• 原有排序、遍历逻辑完全不变，依然按v中值的顺序迭代
• 查找时间复杂度保持O(logn)，无性能损失
• 逻辑清晰直观，完全匹配需求

如果使用的C++版本低于14，可以临时用lower_bound配合值校验实现：先获取第一个大于等于目标值的迭代器，再判断迭代器是否有效且对应值等于目标值，但透明比较器方案是更符合标准设计的优雅实现。

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