Why is there no std::is_transparent equivalent for unordered containers?

Question

C++14 introduces Compare::is_transparent for equivalent find operations in associative containers.

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

Finds an element with key that compares equivalent to the value x. This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. It allows calling this function without constructing an instance of Key

Since there is no longer temporary instance of Key constructed, these can be more efficient.

There does not seem to be an equivalent for unordered containers.

Why is there no Compare::key_equal / Compare::hash_equal?

I imagine it would be relatively simple to allow efficiently looking up of, eg, string literals in unordered containers?

template<>
struct hash<string>
{
    std::size_t operator()(const string& s) const 
    {
        return ...;
    }
    // hash_equal=true allows hashing string literals
    std::size_t operator()(const char* s) const
    {
        return ...;
    }
};

Answer 1

Keys that compare equal should produce the same hash value. Decoupling the hash function and the predicate, and at the same time making one or both heterogeneous, could be too much error prone.

Recent paper, P0919r2, brings up the following example:

std::hash<long>{}(-1L) == 18446744073709551615ULL
std::hash<double>{}(-1.0) == 11078049357879903929ULL

Although -1L and -1.0 compare equal, some heterogeneous hash function, not in line with the selected equality comparison logic, could produce different values. The paper adds heterogeneous lookup-enabled function templates -- find, count, equal_­range, and contains -- but makes them available when the below requirements are met [unord.req]/p17:

If the qualified-id Hash::transparent_­key_­equal is valid and denotes a type ([temp.deduct]), 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 ([temp.deduct]).

In such a case, Hash::transparent_­key_­equal overwrites the default predicate (std::equal_to<Key>) and is used for (transparent) equality checking, together with Hash itself for (transparent) hashing.

Under these conditions, the below transparent function objects could be used to enable heterogeneous lookup:

struct string_equal
{
    using is_transparent = void;

    bool operator()(const std::string& l, const std::string& r) const
    {
        return l.compare(r) == 0; 
    }

    bool operator()(const std::string& l, const char* r) const 
    {
        return l.compare(r) == 0; 
    }

    bool operator()(const char* l, const std::string& r) const
    {
        return r.compare(l) == 0; 
    }
};

struct string_hash
{
    using transparent_key_equal = string_equal; // or std::equal_to<>

    std::size_t operator()(const std::string& s) const
    {
        return s.size();
    }

    std::size_t operator()(const char* s) const
    {
        return std::strlen(s);
    }
};

Both -- string_equal and std::equal_to<> -- are transparent comparators and can be used as transparent_key_equal for string_hash.

Having this type alias (or a type definition itself) within the hash function class definition makes it clear that it is a valid predicate that works fine with that particular hashing logic and the two can't diverge. Such an unordered set can be declared as:

std::unordered_set<std::string, string_hash> u;

or:

std::unordered_set<std::string, string_hash, string_hash::transparent_key_equal> u;

Either will use string_hash and string_equal.

Answer 2

If you watch the Grill the committee video from CppCon, they explain why stuff like this happens: nobody fought for it.

C++ is standardized by committee but that committee requires input from the community. Someone has to write papers, respond to criticism, go to the meetings, etc... Then the feature can be voted on. The committee doesn't just sit there inventing language and library features. It only discusses and votes on those that are brought forward to it.