C++如何用pair<string_view>查找pair<string>键的unordered_map

直接调用myMap.find(std::make_pair(sv, sv2))无法通过编译的核心原因有两个：

• C++标准库默认没有提供std::hash对std::pair类型的特化，你最开始写的std::unordered_map<std::pair<std::string, std::string>, int> myMap;本身就无法直接编译通过
• 无序容器默认不支持跨类型异构查找，就算补了pair的哈希，默认相等比较器也无法直接比较std::pair<std::string, std::string>和std::pair<std::string_view, std::string_view>两种类型，且默认哈希也不会接受string_view组成的pair作为参数

要实现零拷贝用string_view pair查找，基于C++20及以上版本的透明异构查找特性实现即可，步骤如下：

1. 实现支持异构计算的哈希器 #

哈希器需要标记is_transparent启用透明查找支持，同时保证内容相同的string、string_view计算出完全一致的哈希值：

#include <unordered_map>
#include <string>
#include <string_view>
#include <utility>

// 字符串哈希合并工具函数
template <typename T>
void hash_combine(std::size_t& seed, const T& val) {
    std::hash<T> hasher;
    seed ^= hasher(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

struct PairHash {
    using is_transparent = void; // 标记支持透明查找
    // 支持哈希存储的键类型：pair<string, string>
    std::size_t operator()(const std::pair<std::string, std::string>& key) const {
        std::size_t seed = 0;
        hash_combine(seed, key.first);
        hash_combine(seed, key.second);
        return seed;
    }
    // 支持哈希查找用的类型：pair<string_view, string_view>
    std::size_t operator()(const std::pair<std::string_view, std::string_view>& key) const {
        std::size_t seed = 0;
        hash_combine(seed, key.first);
        hash_combine(seed, key.second);
        return seed;
    }
};

2. 实现支持异构比较的相等谓词 #

同样标记is_transparent，支持跨pair类型逐元素比较内容。string和string_view的==运算符本身就支持跨类型比较，不会产生临时字符串拷贝：

struct PairEqual {
    using is_transparent = void; // 标记支持透明查找
    template <typename T1, typename T2>
    bool operator()(const std::pair<T1, T1>& a, const std::pair<T2, T2>& b) const {
        return a.first == b.first && a.second == b.second;
    }
};

3. 定义哈希表并直接用string_view pair查找 #

定义unordered_map时传入自定义的哈希器和相等谓词，之后就可以直接传pair<string_view, string_view>给find方法，全程无多余字符串拷贝：

int main() {
    // 传入自定义哈希和比较器类型
    std::unordered_map<std::pair<std::string, std::string>, int, PairHash, PairEqual> myMap;
    // 插入测试数据
    myMap[{"I'm a string", "I'm also a string"}] = 42;

    std::string s = "I'm a string";
    std::string s2 = "I'm also a string";
    std::string_view sv(s);
    std::string_view sv2(s2);
    // 直接查找，无需构造临时std::string
    auto it = myMap.find(std::make_pair(sv, sv2));
    if (it != myMap.end()) {
        // 此处可获取到值为42的元素
    }
    return 0;
}

注意事项 #

• 该方案依赖C20标准引入的无序容器异构查找接口，GCC 11+、Clang 14+、MSVC 2022及以上版本均已支持该特性。如果使用C17及更早版本，没有标准层面的透明查找支持，只能通过构造临时std::pair<std::string, std::string>传入find完成查找，会产生两次字符串拷贝开销。
• 不要随意修改哈希合并逻辑导致相同内容的string、string_view哈希结果不一致，否则会出现已存在的键查找不到的问题。

内容的提问来源于stack exchange，提问作者not an alien