1245. std::hash<string> & co

Section: 22.10.19 [unord.hash] Status: C++11 Submitter: Paolo Carlini Opened: 2009-10-22 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [unord.hash].

View all issues with C++11 status.

Discussion:

In 22.10.19 [unord.hash], operator() is specified as taking the argument by value. Moreover, it is said that operator() shall not throw exceptions.

However, for the specializations for class types, like string, wstring, etc, the former requirement seems suboptimal from the performance point of view (a specific PR has been filed about this in the GCC Bugzilla) and, together with the latter requirement, hard if not impossible to fulfill. It looks like pass by const reference should be allowed in such cases.

[ 2009-11-18: Ganesh updates wording. ]

I've removed the list of types for which hash shall be instantiated because it's already explicit in the synopsis of header <functional> in 22.10 [function.objects]/2.

[ 2009-11-18: Original wording here: ]

Add to 22.10.19 [unord.hash]/2: 

namespace std {
  template <class T>
  struct hash : public std::unary_function<T, std::size_t> {
    std::size_t operator()(T val) const;
  };
}

The return value of operator() is unspecified, except that equal arguments shall yield the same result. operator() shall not throw exceptions. It is also unspecified whether operator() of std::hash specializations for class types takes its argument by value or const reference.

[ 2009-11-19 Moved to Tentatively Ready after 5 positive votes on c++std-lib. ]

[ 2009-11-24 Ville Opens: ]

I have received community requests to ask for this issue to be reopened. Some users feel that mandating the inheritance is overly constraining.

[ 2010-01-31 Alisdair: related to 978 and 1182. ]

[ 2010-02-07 Proposed resolution updated by Beman, Daniel and Ganesh. ]

[ 2010-02-09 Moved to Tentatively Ready after 5 positive votes on c++std-lib. ]

Proposed resolution:

Insert a new subclause either before or after the current 16.4.4.6 [allocator.requirements]:

Hash Requirements [hash.requirements]

This subclause defines the named requirement Hash, used in several clauses of the C++ standard library. A type H meets the Hash requirement if

Given Key is an argument type for function objects of type H, in the table below h is a value of type (possibly const) H, u is an lvalue of type Key,  and k is a value of a type convertible to (possibly const) Key:

Table ? — Hash requirements
Expression Return type Requirement
h(k) size_t Shall not throw exceptions. The value returned shall depend only on the argument k. [Note: Thus all evaluations of the expression h(k) with the same value for k yield the same result. — end note] [Note: For t1 and t2 of different values, the probability that h(t1) and h(t2) compare equal should be very small, approaching (1.0/numeric_limits<size_t>::max()). — end note] Comment (not to go in WP): The wording for the second note is based on a similar note in 28.3.4.5.1.3 [locale.collate.virtuals]/3
h(u) size_t Shall not modify u.

Change 22.10.19 [unord.hash] as indicated:

1 The unordered associative containers defined in Clause 23.5 [unord] use specializations of the class template hash as the default hash function. For all object types T for which there exists a specialization hash<T>, the instantiation hash<T> shall:

This class template is only required to be instantiable for integer types (6.8.2 [basic.fundamental]), floating-point types (6.8.2 [basic.fundamental]), pointer types (9.3.4.2 [dcl.ptr]), and std::string, std::u16string, std::u32string, std::wstring, std::error_code, std::thread::id, std::bitset, and std::vector<bool>. 

namespace std {
  template <class T>
  struct hash : public std::unary_function<T, std::size_t> {
    std::size_t operator()(T val) const;
  };
}

2 The return value of operator() is unspecified, except that equal arguments shall yield the same result. operator() shall not throw exceptions.

Change Unordered associative containers 23.2.8 [unord.req] as indicated:

Each unordered associative container is parameterized by Key, by a function object type Hash([hash.requirements]) that acts as a hash function for argument values of type Key, and by a binary predicate Pred that induces an equivalence relation on values of type Key. Additionally, unordered_map and unordered_multimap associate an arbitrary mapped type T with the Key.

A hash function is a function object that takes a single argument of type Key and returns a value of type std::size_t.

Two values k1 and k2 of type Key are considered equal if the container's equality function object returns true when passed those values. If k1 and k2 are equal, the hash function shall return the same value for both. [Note: Thus supplying a non-default Pred parameter usually implies the need to supply a non-default Hash parameter. — end note]