Date
2010-10-21.18:28:33
Message id
1295

Content

Proposed resolution:

Insert a new subclause either before or after the current [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

  • it is a function object type ([function.objects]).

  • it satisfies the requirements of CopyConstructible, and Destructible ([utility.arg.requirements]),

  • the expressions shown in the following table are valid and have the indicated semantics, and

  • it satisfies all other requirements of this subclause.

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 [locale.collate.virtuals]/3
h(u) size_t Shall not modify u.

Change [unord.hash] as indicated:

1 The unordered associative containers defined in Clause [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:

  • satisfy the Hash requirements([hash.requirements]), with T as the function call argument type, the DefaultConstructible requirements ([defaultconstructible]), the CopyAssignable requirements ([copyassignable]), and the Swappable requirements ([swappable]),
  • provide two nested types result_type and argument_type which shall be synonyms for size_t and T, respectively,
  • satisfy the requirement that if k1 == k2 is true, h(k1) == h(k2) is true, where h is an object of type hash<T>, and k1, k2 are objects of type T.

This class template is only required to be instantiable for integer types ([basic.fundamental]), floating-point types ([basic.fundamental]), pointer types ([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 [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]