unordered_map：带有一对std :: string_view的std :: string的查找对

Question

给定一个在一对字符串上键入的hashmap，例如：

std :: unordered_map＆lt; std :: pair＆lt; string，string＆gt;，int＆gt; mymap;

如何使用一对std :: string_view（例如：

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);
myMap.find(std::make_pair(sv, sv2));

我想我需要在某个地方定义自己的比较器）进行查找，但是我不确定从哪里开始。

Answer 1

使用C ++ 20年代的异质查找，可以完成此操作（请参阅 unordered_map :: find（） ）。为此，必须定义一个hash函数和平等函数，例如：

struct hash {
    template <typename T>
    auto operator()(const std::pair<T, T>& pair) const {
        return std::hash<T>{}(pair.first) ^ std::hash<T>{}(pair.second); // not to be used in production (combining hashes using XOR is bad practice)
    }

    using is_transparent = void; // required to make find() work with different type than key_type
};

struct equal {
    template <typename A, typename B>
    auto operator()(const std::pair<A, A>& a,
                    const std::pair<B, B>& b) const {
        return a.first == b.first && a.second == b.second;
    }

    using is_transparent = void; // required to make find() work with different type than key_type
};

地图的类型必须更改为 std :: unordered_map＆lt＆std :: pair＆lt＆lt＆std :: string :: std :: std ::字符串＆gt;，int，hash，quare＆gt; ，以便使用定义的函数。

find（）现在按预期工作：

using namespace std::literals;

std::unordered_map<std::pair<std::string, std::string>, int, hash, equal> map{};

map.insert({std::pair{"a"s, "b"s}, 42});

if (auto it = map.find(std::pair{"a"sv, "b"sv}); it != map.end())
  std::cout << it->second << std::endl;

if (auto it = map.find(std::pair{"x"s, "y"s}); it != map.end())
  std::cout << it->second << std::endl;

// prints 42

可以使用在这里

Answer 2

由于您正在使用 unordered_map ，因此您需要为您的自定义密钥类型提供 hash函数和 keyequal ，而不是键类型的比较器仅通过排序的容器（例如 set/map ）或排序的容器适配器（ PRIRISITION_QUEUE ）才需要。

在您的示例中，密钥类型为 pair＆lt; string_view，string_view＆gt; 。 std :: Pair 类型已经定义了其 == 运算符，但它不提供哈希功能。因此，我们只需要为 std :: Pair 类型定义哈希函数。幸运的是，STL已经为 std :: String_view 提供了哈希模板专业化，这使我们的任务变得更加容易。这是代码：

#include <iostream>
#include <string>
#include <string_view>
#include <unordered_map>
 
struct Hash {
    size_t operator()(const std::pair<std::string_view, std::string_view> &key) const {
        return std::hash<std::string_view>()(key.first) ^ std::hash<std::string_view>()(key.second);
    }
};

int main() {
    std::unordered_map<std::pair<std::string_view, std::string_view>, int, Hash> myMap;

    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);
    
    myMap.insert({{sv, sv2}, 1});
    
    // To print the map
    for (auto &[key, val] : myMap) {
        std::cout << "{" << key.first << ", " << key.second << "}: " << val << std::endl;
    }
    
    // To search
    auto it = myMap.find({sv, sv2});
    if (it != myMap.end()) std::cout << "Found key with value: " << it->second << std::endl;
    
    return 0;
}

输出是：

{I'm a string, I'm also a string}: 1
Found key with value: 1