unordered_map::find with key std::pair of pointers with custom hash crashes in VS2012

Question

I needed a std::unordered_map with key a std::pair<T*, T*> so I "stole" the following code:

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

namespace std
{
  template<typename S, typename T> struct hash<pair<S, T>>
  {
    inline size_t operator()(const pair<S, T> & v) const
    {
      size_t seed = 0;
      ::hash_combine(seed, v.first);
      ::hash_combine(seed, v.second);
      return seed;
    }
  };
}

from this stackoverflow answer.

It works like a charm on linux machines with gcc 4.9.2. However in windows visual studio 2012 it crashes upon calling member function find() of my unordered_map. A friend of mine debugged the crash on windows machine and he reported that it breaks only in debug compilation mode by giving "vector subscript out of range".

Q:

Is the code posted valid for hashing a std::pair<T*, T*>?
Is there a more robust/better way of hashing a std::pair<T*, T*>?
What causes this strange behaviour?

P.S: Deeply sorry for not posting a mcve but It's impossible to do so.

Why is mcve impossible? How can you be sure that issue with hash_map without test? Maybe you corrupt memory somewhere else? — Slava, Jun 23 '15 at 14:11
@Slava It's impossible because I'm having this behaviour for a very large data-base. Thus, I can't post a 1.000.000 keys example. — 101010, Jun 23 '15 at 14:32
First of all, this is undefined behavior as it was pointed out by Yakk in the comments to that answer. — Anton Savin, Jun 23 '15 at 14:42

score 3 · Accepted Answer · edited May 23 '17 at 12:22

Specialization of templates in std for types also in std may or may not make your program ill-formed (the standard is ambiguous, it seems to use "user-defined type" in multiple different ways without ever defining it). See my question on the subject, and active working group defect on the issue.

So create your own hashing namespace:

namespace my_hash {
  template<class T=void,class=void>
  struct hasher:std::hash<T>{};

  template<class T, class=std::result_of_t< hasher<T>(T const&) >>
  size_t hash( T const& t ) {
    return hasher<T>{}(t);
  }
  template<>
  struct hasher<void,void> {
    template<class T>
    std::result_of_t<hasher<T>(T const&)>
    operator()(T const& t)const{
      return hasher<T>{}(t);
    }
  };

  // support for containers and tuples:
  template <class T>
  size_t hash_combine(std::size_t seed, const T & v) {
    seed ^= hash(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    return seed;
  }

  template<class Tuple, size_t...Is>
  size_t hash_tuple_like(Tuple const& t, size_t count, std::index_sequence<Is...>) {
    size_t seed = hash(count);
    using discard=int[];
    (void)discard{0,((
      seed = hash_combine(seed, std::get<Is>(t))
    ),void(),0)...};
    return seed;
  }
  template<class Tuple>
  size_t hash_tuple_like(Tuple const& t) {
    constexpr size_t count = std::tuple_size<Tuple>{};
    return hash_tuple_like(t, count, std::make_index_sequence<count>{} );
  }
  struct tuple_hasher {
    template<class Tuple>
    size_t operator()(Tuple const& t)const{
      return hash_tuple_like(t);
    }
  };
  template<class...Ts>
  struct hasher<std::tuple<Ts...>,void>:
    tuple_hasher
  {};
  template<class T, size_t N>
  struct hasher<std::array<T,N>,void>:
    tuple_hasher
  {};
  template<class...Ts>
  struct hasher<std::pair<Ts...>,void>:
    tuple_hasher
  {};
  template<class C>
  size_t hash_container( C const& c ) {
    size_t seed = hash(c.size());
    for( const auto& x:c ) {
      seed = hash_combine( seed, x );
    }
    return seed;
  }
  struct container_hasher {
    template<class C>
    size_t operator()(C const& c)const{ return hash_container(c); }
  };
  template<class...Ts>
  struct hasher< std::vector<Ts...>, void >:
    container_hasher
  {};
  // etc
};

now you pass my_hash::hasher<> as your hasher to a container, and you don't have to do the sketchy business of providing a std specialization for a type (mostly) in std.

my_hash::hasher<?,void> exists so you can do SFINAE testing (say, detect if a type is container-like, and forward to hash_container. my_hash::hash provides ADL overriding for types without having to fool around in the my_hash namespace.

As an example:

template<class T>
struct custom {
  std::vector<T> state;
  friend size_t hash( custom const& c ) {
    using my_hash::hash;
    return hash(state);
  }
};

and custom is now hashable. No messy specialization required.

@T.C. Added a link in the answer. This implies *user-defined* is (mostly?) used in the standard as program-defined. I'd be mildly curious if every use of *user-defined* was proposed to be changed, or just most. — Yakk - Adam Nevraumont, Jun 23 '15 at 17:47
Mostly in the library clauses. Core still uses "user-defined". — T.C., Jun 23 '15 at 19:10
Fair enough, indeed the code I posted introduces undefined behaviour, so sky is the limit in terms of outcome. However, even with your solution the VS2012 still breaks in debug mode. It works perfectly though in release mode. I'm going to give up the quest. — 101010, Jun 24 '15 at 13:04
@101010 It is possible that problems elsewhere are triggering your issue. Or VS2012 might be failing under C++11 (its support is very partial); an error in the library. I recall it had some issue with `{}` ctors and smart pointers, among other things. — Yakk - Adam Nevraumont, Jun 24 '15 at 13:46

unordered_map::find with key std::pair of pointers with custom hash crashes in VS2012

Q:

1 Answers1

Linked

Related