unordered_map: Lookup pair of std::string with a pair of std::string_view

user_7830114 0
Viewed 128

Given a hashmap that is keyed on a pair of strings, e.g:

std::unordered_map<std::pair<String, String>, int> myMap;

How could one do a lookup with a pair of std::string_view, e.g:

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));

I guess that I need to define my own comparator somewhere, but I'm not sure where to begin.

c++
2 Answers

With C++20's heterogeneous lookups this can be done (see documentation of unordered_map::find()). For this to work a hash functor and a equality functor have to be defined, e.g.:

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
};

The type of the map then has to be changed to std::unordered_map<std::pair<std::string, std::string>, int, hash, equal> in order to use the defined functors.

find() now works as intended:

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

The implementation can be played with here

user_11302700

Since you are using unordered_map, then you need to provide Hash function and KeyEqual for your custom key type, not the comparator for the key type which is needed only by sorted containers (such as set/map) or sorted container adapter (priority_queue).

In your example, the key type is pair<string_view, string_view>. The std::pair type already defines its == operator, but it provides no hash function. So we only need to define a hash function for the std::pair type. Fortunately, STL already provides the hash template specialization for std::string_view, which makes our task much easier. Here is the code:

#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;
}

output is:

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