c++c++11visual-studio-2012unordered-mapstdhash

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


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:

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

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


Solution

  • 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.