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

Question

C ++ 14 introduces Compare::is_transparent for equivalent search 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 a key that compares with the value of x. This overload only participates in overload resolution if the valid Compare :: is_transparent identifier is valid and indicates the type. It allows you to call this function without constructing an instance of the key.

Since there is no longer a temporary instance of Key , it can be more efficient.

This seems to be the equivalent for unordered containers .

Why not Compare::key_equal / Compare::hash_equal ?

I believe that it would be relatively easy to effectively search, for example, 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

If you watch CppCon's Grill the Committee video, they explain why this happens: no one fought for it.

C ++ is standardized by a committee, but this committee requires community involvement. Someone has to write documents, respond to criticism, go to meetings, etc. You can then vote on this feature. The committee does not just sit inventing language and library functions. He only discusses and votes for those who are nominated for him.

Answer 2

Keys that compare the same must have the same hash value. Decoupling the hash function and the predicate and at the same time creating one or both heterogeneous ones may be too error prone.

A recent article, P0919r2 , provides the following example:

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

Although -1L and -1.0 compared equal, some heterogeneous hash function that does not match the selected equality comparison logic can produce different values. Heterogeneous function templates with search support have been added to the document - find , count , equal_range and contains - but makes them available when the [unord.req] / p17 requirements are met below:

If valid-id Hash::transparent_key_equal valid and indicates the type ([temp.deduct]), then the program is poorly formed if:

• qualified-id Hash::transparent_key_equal::is_transparent invalid or does not indicate a type, or
• Pred is a different type than equal_to<Key> or Hash::transparent_key_equal .

The member templates of the find , count , equal_range and contains functions should not participate in overload resolution, unless the valid Hash::transparent_key_equal identifier is valid and indicates the type ([temp.deduct]).

In this case, Hash::transparent_key_equal overwrites the default predicate ( std::equal_to<Key> ) and is used to (transparent) check equality with Hash itself for (transparent) hashing.

Under these conditions, the following transparent functional objects can be used to provide a heterogeneous search:

 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 .

The presence of this type alias (or the type definition itself) in the definition of the hash function class makes it clear that it is a valid predicate that works perfectly with this particular hashing logic, and they cannot 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; 

Or it will use string_hash and string_equal .