unordered_map：使用std::string_view的一对匹配查找std::string的一对。

Question

假设有一个以一对字符串为键的哈希映射表，例如：

std::unordered_map<std::pair<String, String>, int> 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));

我猜我需要在某个地方定义自己的比较器，但我不确定从哪里开始。

- not an alien

---

https://dev59.com/wWIj5IYBdhLWcg3wYkNY - NathanOliver

@Enlico 在我的示例中，关键字是唯一提供的参数...只是这个关键字本身是一对。 - not an alien

@notanalien，糟糕，我误读了myMap的声明 :D - Enlico

@Enlico，很容易做到！ - not an alien

找到了一个相关的帖子... https://dev59.com/41sW5IYBdhLWcg3wyJl3#53530846听起来在 C++20 之前，对于 unordered_map 来说没有简单的方法。 - not an alien

这应该是答案。https://stackoverflow.com/questions/58944520/how-to-define-a-custom-key-equivalence-predicate-for-an-stdunordered-set/58945096#58945096 但我无法让它工作。以下是建议：https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0919r3.html - Homer512

Answer 1

使用C++20的异构查找，这可以实现（请参见unordered_map::find()文档）。 为了使其正常工作，需要定义哈希函数和相等函数，例如：

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<std::pair<std::string, std::string>, int, hash, equal>。

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

可以在这里进行实现。

- Quxflux

Answer 2

由于您正在使用unordered_map，因此需要为自定义键类型提供哈希函数和KeyEqual，而不是仅由排序容器（例如set/map）或排序容器适配器（priority_queue）所需的键类型比较器。

在您的示例中，键类型为pair<string_view，string_view>。 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

- Peng