Heterogeneous lookup in unordered containers

Introduction

This proposal is aimed to add heterogeneous lookup functions to the unordered associative containers in Standard Library. These functions allow finding elements without actual construction of a temporary key object.

Motivation and Scope

Heterogeneous lookup functions are not new. C++14 introduced these functions in the ordered associative containers (std::map, std::set, etc).

C++17 has presented std::string_view class and now it is possible to search for elements in std::string-based associative container via std::string_view without construction of std::string instance. Consider the example:

std::set<std::string> s1 = {"hello"};
s1.find(std::string_view{"hello"}); // it won't compile
...
// explicitly provide transparent compare function
std::set<std::string, std::less<>> s2 = {"hello"}; 
s2.find(std::string_view{"hello"}); // now it's ok

But that's not working in unordered containers because of two reasons: there are no transparent hash function and heterogeneous lookup members overloads. Thus this proposal allows a programmer to enable heterogeneous lookup members by defining unordered container with both transparent hash and comparison function. For example:

std::unordered_set<std::string, std::hash<>, std::equal_to<>> s3 = {"hello"};
s3.find(std::string_view{"hello"});

Using an unordered container with std:string key is a widely used approach. So heterogeneous lookup would be very helpful for many users. The proposal is not about std::string and std::string_view only but is about any complex user defined type.

Impact On the Standard

This proposal can be implemented in terms of existing C++11 standard library components.

This proposal has no dependencies beyond a C++11 compiler and Standard Library implementation. Nothing depends on it.

It requires changes to the following standard components:

• unordered_set
• unordered_multiset
• unordered_map
• unordered_multimap
• introduce hash<void> specialization

Design Decisions

All decisions are made in contrast to the existing Mark Boyall's proposal N3573 [1].

Heterogeneous hash function object

Proposal N3573 defines the heterogeneous hash function object in the following way:

template<typename T = void> struct hash;
template<> struct hash<void> {
    template<typename T> std::size_t operator()(T&& t) {
        return std::hash<typename std::decay<T>::type>()(std::forward<T>(t));
    }
};

That's a dangerous approach because std::decay destroys initial type (remember array-to-pointer conversion). Also it doesn't have is_transaprent tag. This document proposes much more safer way:

template<class T = void> struct hash;
template <> struct hash<void> {
    template <class T>
    size_t operator()(T&& t) const noexcept {
        return hash<typename remove_cv<typename remove_reference<T>::type>::type>{}(t);
    }
    using is_transparent = void;
};

Heterogeneous member functions overloads

Proposal N3573 defines heterogeneous lookup functions in the following way:

template<typename T, typename Hash = std::hash<>, typename Eq = std::equal_to<>>
iterator find(T t, Hash h = Hash(), Eq e = Eq());
template<typename T, typename Hash = std::hash<>, typename Eq = std::equal_to<>>
const_iterator find(T t, Hash h = Hash(), Eq e = Eq()) const;

Here transparency is enabled by default that may break an old code like that:

std::unordered_set<std::string> s = {"aaa"};
s.find({'a', 'a', 'a'}); // it won't compile

This document proposes SFINAE approach similar to the ordered associative containers (see "Implementability" section for details).

template <class K> iterator find(const K& k);
template <class K> const_iterator find(const K& k) const;

Proposed wording

Make the following changes to the specified working paper:

23.14.1 Header <functional> synopsis [functional.syn]

template <class T = void>
  struct hash;
template <> struct hash<void>;

23.14.15 Class template hash [unord.hash]

template <> struct hash<void> {
  template <class T>
  size_t operator()(T&& t) const noexcept {
    return hash<typename remove_cv<typename remove_reference<T>::type>::type>{}(t);
  }
  using is_transparent = unspecified;
};

26.5.4.1 Class template unordered_­map overview [unord.map.overview]

// map operations:
iterator       find(const key_type& k);
const_iterator find(const key_type& k) const;
template <class K> iterator find(const K& k);
template <class K> const_iterator find(const K& k) const;
size_type      count(const key_type& k) const;
template <class K> size_type count(const K& k) const;
pair             equal_range(const key_type& k);
pair equal_range(const key_type& k) const;
template <class K> pair<iterator, iterator> equal_range(const K& k);
template <class K> pair<const_iterator, const_iterator> equal_range(const K& k) const;

26.5.5.1 Class template unordered_­multimap overview [unord.multimap.overview]

// map operations:
iterator       find(const key_type& k);
const_iterator find(const key_type& k) const;
template <class K> iterator find(const K& k);
template <class K> const_iterator find(const K& k) const;
size_type      count(const key_type& k) const;
template <class K> size_type count(const K& k) const;
pair             equal_range(const key_type& k);
pair equal_range(const key_type& k) const;
template <class K> pair<iterator, iterator> equal_range(const K& k);
template <class K> pair<const_iterator, const_iterator> equal_range(const K& k) const;

26.5.6.1 Class template unordered_­set overview [unord.set.overview]

// set operations:
iterator       find(const key_type& k);
const_iterator find(const key_type& k) const;
template <class K> iterator find(const K& k);
template <class K> const_iterator find(const K& k) const;
size_type      count(const key_type& k) const;
template <class K> size_type count(const K& k) const;
pair             equal_range(const key_type& k);
pair equal_range(const key_type& k) const;
template <class K> pair<iterator, iterator> equal_range(const K& k);
template <class K> pair<const_iterator, const_iterator> equal_range(const K& k) const;

26.5.7.1 Class template unordered_­multiset overview [unord.multiset.overview]

// set operations:
iterator       find(const key_type& k);
const_iterator find(const key_type& k) const;
template <class K> iterator find(const K& k);
template <class K> const_iterator find(const K& k) const;
size_type      count(const key_type& k) const;
template <class K> size_type count(const K& k) const;
pair             equal_range(const key_type& k);
pair equal_range(const key_type& k) const;
template <class K> pair<iterator, iterator> equal_range(const K& k);
template <class K> pair<const_iterator, const_iterator> equal_range(const K& k) const;

Implementability

Heterogeneous lookup functions may be enabled via SFINAE. It requires Hash and Pred function objects to be both transparent. Since C++14 Standard Library implementations already have facilities to test transparency of a single function object. Combine them by logical AND to build a complex metafunction enable_if_transparent.

template <class Key, class Hash = hash<Key>, class Pred = equal_to<Key>,
          class Allocator = allocator<Key>>
class unordered_set {
  ...
  template <class K, class T>
  using enable_if_transparent = typename enable_if<
    is_transparent<Hash, K>::value &&
    is_transparent<Pred, K>::value, T>::type;
  ...
  template <class K>
  enable_if_transparent<K, iterator> find(const K& k) { ... }
  template <class K>
  enable_if_transparent<K, const_iterator> find(const K& k) const { ... }
  ...
};

Possible implementation of heterogeneous lookup for std::unordered_set in libc++ may be found at https://github.com/compmaniak/libcxx/pull/1/files.

Acknowledgements

Antony Polukhin discussed and made corrections to the proposal.

References

1. Mark Boyall, "Heterogenous extensions to unordered containers" (N3573, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3573.html)