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

Question

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.

https://stackoverflow.com/questions/20317413/what-are-transparent-comparators — NathanOliver, Jun 23 '22 at 12:27
@Enlico the key is the only argument provided in my example... it's just that the key itself is a pair. — not an alien, Jun 23 '22 at 12:36
@notanalien, oh crap, I've misread the declaration of `myMap` :D — Enlico, Jun 23 '22 at 12:37
Found a related post... https://stackoverflow.com/questions/34596768/stdunordered-mapfind-using-a-type-different-than-the-key-type/53530846#53530846 Sounds like there's no easy approach to this for unordered_map prior to C++20. — not an alien, Jun 23 '22 at 12:48
This should be the answer. https://stackoverflow.com/questions/58944520/how-to-define-a-custom-key-equivalence-predicate-for-an-stdunordered-set/58945096#58945096 but I can't get it to work. Here is the proposal on what to do: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0919r3.html — Homer512, Jun 23 '22 at 13:41

score 4 · Accepted Answer · answered Jun 23 '22 at 19:12

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

score 0 · Answer 2 · answered Jun 23 '22 at 15:02

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

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

2 Answers2