如何用异类型值查找std::map的键？或选择合适替代容器

你不需要遍历整个map，利用std::map的有序特性，结合标准算法或C++14的新特性就能实现O(logn)的高效查找；也可以选择更贴合区间场景的容器。

方案1：现有std::map结合标准算法实现快速查找 #

你的map是按key的min升序排列的，借助std::lower_bound做二分查找，就能定位到目标区间：

#include <algorithm>

int target = 15;
// 查找第一个max < target的元素的下一个位置
auto it = std::lower_bound(map.begin(), map.end(), target,
    [](const std::pair<key, std::string>& elem, int v) {
        return elem.first.max < v;
    });

// 验证当前区间是否包含target
if (it != map.end() && target >= it->first.min && target <= it->first.max) {
    std::cout << "匹配结果：" << it->second << std::endl;
} else {
    std::cout << "无匹配区间" << std::endl;
}

lower_bound会利用map的有序性执行O(logn)的二分查找，定位到第一个可能包含target的区间，再做一次简单的范围验证即可，整体复杂度还是O(logn)。

方案2：C++14透明比较器让map直接支持异构查找 #

C++14新增了透明比较器特性，只要自定义比较器包含is_transparent类型，std::map的find方法就能直接接受非key类型的参数，自动完成二分查找：

// 定义透明比较器
struct KeyCompare {
    using is_transparent = void; // 标记为透明比较器，必须声明

    // 两个key之间的排序逻辑（保持原有的min比较）
    bool operator()(const key& a, const key& b) const {
        return a.min < b.min;
    }

    // 判断value是否小于key的min（在区间左侧）
    bool operator()(int v, const key& k) const {
        return v < k.min;
    }

    // 判断key的max是否小于value（在区间右侧）
    bool operator()(const key& k, int v) const {
        return k.max < v;
    }
};

// 声明map时指定该比较器
std::map<key, std::string, KeyCompare> map;

// 现在可以直接用int调用find
auto it = map.find(15);
if (it != map.end()) {
    std::cout << "匹配结果：" << it->second << std::endl;
} else {
    std::cout << "无匹配区间" << std::endl;
}

这种方式代码更简洁，查找效率和原生find一致，都是O(logn)。

方案3：专门的区间容器 #

如果你的业务场景大量涉及区间的插入、合并、查找操作，可以使用专门的区间容器，比如Boost库的boost::interval_map，它原生支持区间的管理和查找，无需自己实现比较逻辑。如果不想引入第三方库，前两种标准库方案完全够用。

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