P1690R1
Refinement Proposal for P0919 Heterogeneous lookup for unordered containers

1. Motivation and Scope

2. Design Concerns

2.1. Consistency with Prior Art and Existing Practices

[P0919R3] does not standardize existing practice. [SwissTables] and [F14] Hash Tables, two of the most widely used C++ hash table implementations in Google and Facebook, both use the conjunction of is_transparent tags: heterogeneous lookup is only enabled when both Hash::is_transparent and Pred::is_transparent denote a type. See the Implementation Experiences Section for more details.

2.2. Compatibility of Hash and Pred

[P0919R3] tries to address the compatibility concern by stipulating compilation failures for containers with incompatible Hash and Pred types. However, using transparent_key_equal does not preclude the possibility of incompatibility--the user could still specify an incompatible key equality comparator as transparent_key_equal. In this case, the heterogeneous lookup methods would be unavailable (via SFINAE) or fall back to creating a temporary key_type object, which exhibits exactly the same behavior as R0.

We argue that the compatibility concern can be addressed by the implementation via good defaults, compiler warnings, and existing compilation rules. In our experience, this has not posed a problem.

2.3. Minimizing User Confusion

struct MyEqualTo {
  using is_transparent = ...;
  ...
};
struct MyHash {
  using is_transparent = ...;
  using transparent_key_equal = MyEqualTo;
  ...
};
// The user explicitly uses std::equal_to<K> as the 4th template parameter, but
// in fact that type is NEVER used:
std::unordered_map<K, V, MyHash, std::equal_to<K>> m;

In addition, allowing the Hash and Pred to operate on different sets of types can be useful. It is conceivable and useful for a hashing library to have a hasher that could operate on a wide variety of key types, e.g., absl::Hash<T> for string-like types or pointer types, folly::Hash for most common types. Pred, on the other hand, may not care about the entirety of the set of types the hasher could hash.

struct CommonEqualTo {...};
struct CommonHasher {
  using is_transparent = void;
  using transparent_key_equal = CommonEqualTo;
  ...
};
std::unordered_set<K, CommonHasher> s1; // works just fine

struct MyEqualTo {...};
std::unordered_set<K, CommonHasher, MyEqualTo> s2; // fails to compile

3. Impact On The Standard

There are no language changes.

Almost all existing C++17 code is unaffected because new member functions are disabled from overload resolution process unless both the Hash template parameter and the Pred template parameters have is_transparent property.

4. Proposed Wording

The proposed changes are relative to the working draft of the standard as of [N4810].

Modify 22.2.7 [unord.req] paragraph 11.7 as follows:

(11.7) a_tran denotes a possibly const value of type X when the the qualified-id X::hasher::transparent_key_equal is valid and denotes a type (13.9.2), qualified-ids X::key_equal::is_transparent and X::hasher::is_transparent are both valid and denote types (13.9.2),

Modify table 70 in section 22.2.7 [unord.req] as follows:

Expression	Return type	Assertion/note pre-/post-condition	Complexity
X::key_equal	Hash::transparent_key_equal if such a qualified-id is valid and denotes a type (13.9.2); otherwise, Pred. Pred	Requires: key_equal is CopyConstructible. key_equal shall be a binary predicate that takes two arguments of type Key. key_equal is an equivalence relation.	compile time

Modify paragraph 17 in 22.2.7 [unord.req]:

If the qualified-id Hash::transparent_key_equal is valid and denotes a type (12.9.2), then the program is ill-formed if either:

• qualified-id Hash::transparent_key_equal::is_transparent is not valid or does not denote a type, or

• Pred is a different type than equal_to<Key> or Hash::transparent_key_equal.

The member function templates find, count, equal_range, and contains shall not participate in overload resolution unless the qualified-id Hash::transparent_key_equal is valid and denotes a type qualified-ids Pred::is_transparent and Hash::is_transparent are both valid and denote types (13.9.2).

Modify paragraph 3 of 22.5.4.1 [unord.map.overview] as follows:

namespace std {
  template<class Key,
           class T,
           class Hash = hash<Key>,
           class Pred = equal_to<Key>,
           class Allocator = allocator<pair<const Key, T>>>
  class unordered_map {
  public:
    // types
    using key_type         = Key;
    using mapped_type      = T;
    using value_type       = pair<const Key, T>;
    using hasher           = Hash;
    using key_equal        = see 22.2.7;
    using key_equal        = Pred;
    using allocator_type   = Allocator;

Modify paragraph 3 of 22.5.5.1 [unord.multimap.overview] as follows:

namespace std {
  template<class Key,
           class T,
           class Hash = hash<Key>,
           class Pred = equal_to<Key>,
           class Allocator = allocator<pair<const Key, T>>>
  class unordered_multimap {
  public:
    // types
    using key_type         = Key;
    using mapped_type      = T;
    using value_type       = pair<const Key, T>;
    using hasher           = Hash;
    using key_equal        = see 22.2.7;
    using key_equal        = Pred;
    using allocator_type   = Allocator;

Modify paragraph 3 of 22.5.6.1 [unord.set.overview] add:

namespace std {
  template<class Key,
           class Hash = hash<Key>,
           class Pred = equal_to<Key>,
           class Allocator = allocator<pair<const Key, T>>>
  class unordered_set {
  public:
    // types
    using key_type         = Key;
    using value_type       = Key;
    using hasher           = Hash;
    using key_equal        = see 22.2.7;
    using key_equal        = Pred;
    using allocator_type   = Allocator;

Modify paragraph 3 of 22.5.7.1 [unord.multiset.overview] add:

namespace std {
  template<class Key,
           class Hash = hash<Key>,
           class Pred = equal_to<Key>,
           class Allocator = allocator<pair<const Key, T>>>
  class unordered_multiset {
  public:
    // types
    using key_type         = Key;
    using value_type       = Key;
    using hasher           = Hash;
    using key_equal        = see 22.2.7;
    using key_equal        = Pred;
    using allocator_type   = Allocator;

5. Possible Future Extensions

6. Implementation Experiences

7. Acknowledgements

8. Revision History

8.1. r0 -> r1

| SF | F | N | A | SA |
| 5  | 6 | 7 | 0 | 0  |

R1 adds the §8 Revision History section and includes a typo fix in the first paragraph of §4 Proposed Wording.