unordered_map::find с ключом std:: пара указателей с пользовательскими хэш-сбоями в VS2012

Question

Мне нужен был std::unordered_map с ключом std::pair<T*, T*> поэтому я "украл" следующий код:

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;
    }
  };
}

из этого ответа stackru.

Это работает как шарм на машинах Linux с GCC 4.9.2. Однако в Windows Visual Studio 2012 происходит сбой при вызове функции-члена find() из моего unordered_map, Мой друг отладил сбой на машине с Windows, и он сообщил, что он ломается только в режиме отладочной компиляции, давая "векторный индекс вне диапазона".

Q:

1. Является ли опубликованный код действительным для хеширования std::pair<T*, T*>?
2. Есть ли более надежный / лучший способ хеширования std::pair<T*, T*>?
3. Что вызывает это странное поведение?

PS: глубоко сожалею, что не выложил mcve, но это невозможно сделать.

Answer 1

Специализация шаблонов в std для типов также в std может или не может сделать вашу программу плохо сформированной (стандарт неоднозначен, кажется, что он использует "определяемый пользователем тип" несколькими различными способами, даже не определяя его). Смотрите мой вопрос по этому вопросу, и активный дефект рабочей группы по этому вопросу.

Итак, создайте ваше собственное пространство хэширования:

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
};

теперь вы проходите my_hash::hasher<> в качестве хэша к контейнеру, и вам не нужно делать набросок std специализация для вида (в основном) в std,

my_hash::hasher<?,void> существует, так что вы можете выполнять тестирование SFINAE (скажем, определить, является ли тип контейнероподобным, и перейти к hash_container, my_hash::hash обеспечивает переопределение ADL для типов без необходимости дурачиться в my_hash Пространство имен.

В качестве примера:

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

а также custom теперь можно стирать Никакой грязной специализации не требуется.