I have an unordered_map
that uses a string-type as a key:
std::unordered_map<string, value> map;
A std::hash
specialization is provided for string
, as well as a
suitable operator==
.
Now I also have a "string view" class, which is a weak pointer into an existing string, avoiding heap allocations:
class string_view {
string *data;
size_t begin, len;
// ...
};
Now I'd like to be able to check if a key exists in the map using a string_view
object. Unfortunately, std::unordered_map::find
takes a Key
argument, not a generic T
argument.
(Sure, I can "promote" one to a string
, but that causes an allocation I'd like to avoid.)
What I would've liked instead was something like
template<class Key, class Value>
class unordered_map
{
template<class T> iterator find(const T &t);
};
which would require operator==(T, Key)
and std::hash<T>()
to be suitably defined, and would return an iterator to a matching value.
Is there any workaround?
P0919R2 Heterogeneous lookup for unordered containers has been merged in the C++2a's working draft!
The abstract seems a perfect match w.r.t. my original question :-)
Abstract
This proposal adds heterogeneous lookup support to the unordered associative containers in the C++ Standard Library. As a result, a creation of a temporary key object is not needed when different (but compatible) type is provided as a key to the member function. This also makes unordered and regular associative container interfaces and functionality more compatible with each other.
With the changes proposed by this paper the following code will work without any additional performance hits:
template<typename Key, typename Value> using h_str_umap = std::unordered_map<Key, Value, string_hash>; h_str_umap<std::string, int> map = /* ... */; map.find("This does not create a temporary std::string object :-)"sv);
Full example from cppreference
#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <string_view>
#include <unordered_map>
using namespace std::literals;
struct string_hash
{
using hash_type = std::hash<std::string_view>;
using is_transparent = void;
std::size_t operator()(const char* str) const { return hash_type{}(str); }
std::size_t operator()(std::string_view str) const { return hash_type{}(str); }
std::size_t operator()(std::string const& str) const { return hash_type{}(str); }
};
int main()
{
// simple comparison demo
std::unordered_map<int,char> example = {{1, 'a'}, {2, 'b'}};
if (auto search = example.find(2); search != example.end())
std::cout << "Found " << search->first << " " << search->second << '\n';
else
std::cout << "Not found\n";
// C++20 demo: Heterogeneous lookup for unordered containers (transparent hashing)
std::unordered_map<std::string, size_t, string_hash, std::equal_to<>> map{{"one"s, 1}};
std::cout << std::boolalpha
<< (map.find("one") != map.end()) << '\n'
<< (map.find("one"s) != map.end()) << '\n'
<< (map.find("one"sv) != map.end()) << '\n';
}