1317. make_hash

Section: 23.14.15 [unord.hash] Status: LEWG Submitter: Nicolai M. Josuttis Opened: 2010-02-10 Last modified: 2016-02-10

Priority: Not Prioritized

View other active issues in [unord.hash].

View all other issues in [unord.hash].

View all issues with LEWG status.

Discussion:

Currently, the library lacks a convenient way to provide a hash function that can be used with the provided unordered containers to allow the usage of non trivial element types.

While we can easily declare an

std::unordered_set<int>

or

std::unordered_set<std::string>

we have no easy way to declare an unordered_set for a user defined type. IMO, this is a big obstacle to use unordered containers in practice. Note that in Java, the wide usage of HashMap is based on the fact that there is always a default hash function provided.

Of course, a default hash function implies the risk to provide poor hash functions. But often even poor hash functions are good enough.

While I really would like to see a default hash function, I don't propose it here because this would probably introduce a discussion that's too big for this state of C++0x.

However, I strongly suggest at least to provide a convenience variadic template function make_hash<>() to allow an easy definition of a (possibly poor) hash function.

As a consequence for a user-defined type such as

class Customer {
   friend class CustomerHash;
   private:
     string firstname;
     string lastname;
     long   no;
   ...
 };

would allow to specify:

class CustomerHash : public std::unary_function<Customer, std::size_t>
{
  public:
    std::size_t operator() (const Customer& c) const  {
       return make_hash(c.firstname,c.lastname,c.no);
    }
};

instead of:

class CustomerHash : public std::unary_function<Customer, std::size_t>
{
  public:
    std::size_t operator() (const Customer& c) const  {
       return std::hash<std::string>()(c.firstname) +
              std::hash<std::string>()(c.lastname) +
              std::hash<long>()(c.no);
    }
};

Note that, in principle, we can either specify that

make_hash returns the sum of a call of std::hash<T>()(x) for each argument x of type T

or we can specify that

make_hash provides a hash value for each argument, for which a std::hash() function is provided

with the possible note that the hash value may be poor or only a good hash value if the ranges of all passed arguments is equally distributed.

For my convenience, I propose wording that describes the concrete implementation.

[ 2010 Pittsburgh: Moved to NAD Editorial, rationale added below. ]

Rationale:

There is no consensus to make this change at this time.

Proposed resolution:

In Function objects 23.14 [function.objects] in paragraph 2 at the end of the Header <functional> synopsis insert:

// convenience functions
template <class T>
  size_t make_hash (const T&);
template <class T, class... Types>
  size_t make_hash (const T&, const Types&...);

In Class template hash 23.14.15 [unord.hash] add:

20.7.16.1 Hash creation functions [hash.creation]

template <class T>
  size_t make_hash (const T& val);

Returns: hash<T>()(val);

template <class T, class... Types>
  size_t make_hash (const T& val, const Types&... args);

Returns: hash<T>()(val) + std::make_hash(args...)