By René Richter


2011-11-16 20:05:42 8 Comments

To support user-defined key types in std::unordered_set<Key> and std::unordered_map<Key, Value> one has to provide operator==(Key, Key) and a hash functor:

struct X { int id; /* ... */ };
bool operator==(X a, X b) { return a.id == b.id; }

struct MyHash {
  size_t operator()(const X& x) const { return std::hash<int>()(x.id); }
};

std::unordered_set<X, MyHash> s;

It would be more convenient to write just std::unordered_set<X> with a default hash for type X, like for types coming along with the compiler and library. After consulting

  • C++ Standard Draft N3242 §20.8.12 [unord.hash] and §17.6.3.4 [hash.requirements],
  • Boost.Unordered
  • g++ include\c++\4.7.0\bits\functional_hash.h
  • VC10 include\xfunctional
  • various related questions in Stack Overflow

it seems possible to specialize std::hash<X>::operator():

namespace std { // argh!
  template <>
  inline size_t 
  hash<X>::operator()(const X& x) const { return hash<int>()(x.id); } // works for MS VC10, but not for g++
  // or
  // hash<X>::operator()(X x) const { return hash<int>()(x.id); }     // works for g++ 4.7, but not for VC10 
}                                                                             

Given compiler support for C++11 is yet experimental---I did not try Clang---, these are my questions:

  1. Is it legal to add such a specialization to namespace std? I have mixed feelings about that.

  2. Which of the std::hash<X>::operator() versions, if any, is compliant with C++11 standard?

  3. Is there a portable way to do it?

3 comments

@sehe 2011-11-16 20:36:29

My bet would be on the Hash template argument for the unordered_map/unorder_set/... classes:

#include <unordered_set>
#include <functional>

struct X 
{
    int x, y;
    std::size_t gethash() const { return (x*39)^y; }
};

typedef std::unordered_set<X, std::size_t(*)(const X&)> Xunset;
typedef std::unordered_set<X, std::function<std::size_t(const X&)> > Xunset2;

int main()
{
    auto hashX = [](const X&x) { return x.gethash(); };

    Xunset  my_set (0, hashX);
    Xunset2 my_set2(0, hashX); // if you prefer a more flexible set typedef
}

Of course

  • hashX could just as well be a global static function
  • in the second case, you could pass that
    • the oldfashioned functor object (struct Xhasher { size_t operator(const X&) const; };)
    • std::hash<X>()
    • any bind expression satisfying the signature -

@Kerrek SB 2011-11-16 21:49:41

I appreciate that you can write something that doesn't have a default constructor, but I always find that requiring each map construction to remember the additional argument is a bit of a burden -- quite a bit too much of a burden for my taste. I'm OK with an explicit template argument, though specialising std::hash is still the nicest way out :-)

@Kerrek SB 2011-11-16 22:12:37

user-defined types to the rescue :-) More seriously, I hope we'd slap them on the wrists already at the stage where their class contains a char*!

@Kerrek SB 2011-11-16 22:16:49

Hmm... do you have an example of how a hash specialization interferes via ADL? I mean, it's entirely plausible, but I have a hard time coming up with a problem case.

@sehe 2011-11-16 22:19:23

@Brian Gordon 2014-04-11 11:32:55

It's all fun and games until you need a std::unordered_map<Whatever, Xunset> and it doesn't work because your Xunset hasher type isn't default constructible.

@aschepler 2011-11-16 20:24:50

@Kerrek SB has covered 1) and 3).

2) Even though g++ and VC10 declare std::hash<T>::operator() with different signatures, both library implementations are Standard compliant.

The Standard does not specify the members of std::hash<T>. It just says that each such specialization must satisfy the same "Hash" requirements needed for the second template argument of std::unordered_set and so on. Namely:

  • Hash type H is a function object, with at least one argument type Key.
  • H is copy constructible.
  • H is destructible.
  • If h is an expression of type H or const H, and k is an expression of a type convertible to (possibly const) Key, then h(k) is a valid expression with type size_t.
  • If h is an expression of type H or const H, and u is an lvalue of type Key, then h(u) is a valid expression with type size_t which does not modify u.

@ildjarn 2011-11-16 20:27:36

No, neither implementation is standard compliant, since they attempt to specialize std::hash<X>::operator() rather than std::hash<X> as a whole, and the signature of std::hash<T>::operator() is implementation-defined.

@aschepler 2011-11-16 20:31:17

@ildjarn: Clarified - I was talking about the library implementations, not the attempted specializations. Not sure which exactly the OP meant to ask.

@Kerrek SB 2011-11-16 20:07:56

You are expressly allowed and encouraged to add specializations to namespace std*. The correct (and basically only) way to add a hash function is this:

namespace std {
  template <> struct hash<Foo>
  {
    size_t operator()(const Foo & x) const
    {
      /* your code here, e.g. "return hash<int>()(x.value);" */
    }
  };
}

(Other popular specializations that you might consider supporting are std::less, std::equal_to and std::swap.)

*) as long as one of the involved types is user-defined, I suppose.

@sehe 2011-11-16 20:11:28

while this is possible, would you in general recommend doing it this way? I'd prefer instantiation unorder_map<eltype, hash, equality> instead, to avoid ruining someone's day with funny ADL business. (Edit Pete Becker's advice on this topic)

@Kerrek SB 2011-11-16 20:13:24

@sehe: If you have a hash functor lying around that is default-constructible, perhaps, but why? (Equality is easier, since you'd just implement member-operator==.) My general philosophy is that if the function is natural and essentially the only "correct" one (like lexicographic pair comparison), then I add it to std. If it's something peculiar (like unordered pair comparison), then I make it specific to a container type.

@aschepler 2011-11-16 20:13:55

Should be size_t operator()(const Foo & x) const.

@René Richter 2011-11-16 20:14:20

It works on both compilers when adding a const modifier for the method. Thanks!

@sehe 2011-11-16 21:26:39

FWIW, I posted my lightweight take on this (which, incidentally, in no way requires a function object; even if you chose to use one, it didn't need to be default constructible, AFAICT)

@Virus721 2014-02-14 13:45:03

@KerrekSB (or anyone else) I don't understand the "template<> struct hash<Foo>". Could you explain what it means and why you're doing this please ? Thx

@Kerrek SB 2014-02-14 14:25:17

@Virus721: That's the syntax for template specialization.

@razeh 2014-07-02 13:18:28

I am not disagreeing, but where in the standard are we allowed and encouraged to add specializations to std?

@Kerrek SB 2014-07-02 13:24:50

@razeh: all over the place, e.g. hash, but also all sorts of traits... allocator_traits, pointer_traits, iterator_traits...

@razeh 2014-07-02 14:30:51

@Kerrek, I agree, but I was hoping for a chapter and verse reference to a place in the standard. I found the wording allowing the injection at 17.6.4.2.1 where it says it is not allowed "unless otherwise specified", but I haven't been able to find the "otherwise specified" part amid the 4000+ page specification.

@Marek R 2018-09-04 11:42:05

@razeh here you can read "A program may add a template specialization for any standard library template to namespace std only if the declaration depends on a user-defined type and the specialization meets the standard library requirements for the original template and is not explicitly prohibited.". So this solution is ok.

Related Questions

Sponsored Content

2 Answered Questions

[SOLVED] Why can't I store my objects in an unordered_set?

1 Answered Questions

4 Answered Questions

[SOLVED] How to specialize std::hash<T> for user defined types?

3 Answered Questions

2 Answered Questions

[SOLVED] error C2784 ,class in key map

2 Answered Questions

[SOLVED] When should we provide our own Hash function for `std::unordered_set`

  • 2013-07-17 16:33:03
  • q0987
  • 1052 View
  • 6 Score
  • 2 Answer
  • Tags:   c++ c++11 stl

2 Answered Questions

[SOLVED] Specializing a template class as a struct

Sponsored Content