Связь между хешером и key_equal в std :: unordered_set

Я бы сказал, что между hasher и key_equal должна быть связь. Если два элемента одинаковы (вызов равенства возвращает истину), они должны иметь один и тот же хэш, иначе будет выполняться поиск элемента в неправильном сегменте.

Но ничего подобного нет и на http://www.cplusplus.com/reference/unordered_set/unordered_set/ или http://en.cppreference.com/w/cpp/container/unordered_set

Но это явно не работает правильно. См. Пример, когда я пытаюсь фильтровать пары независимо от порядка элементов (1,2 == 2,1)

#include <iostream>
#include <functional>
#include <unordered_set>

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

int main() 
{
   typedef std::pair<int, int> Pair;
    Pair pa = std::make_pair(7,5);
    Pair pb = std::make_pair(5,7);
    Pair pc = std::make_pair(5,1);
    Pair pd = std::make_pair(4,3);
    Pair pe = std::make_pair(5,7);

    struct PairEq
    {
        inline bool operator()(const Pair & p1, const Pair & p2) const
        {
            return (p1.first == p2.first && p1.second == p2.second)
                || (p1.first == p2.second && p1.second == p2.first);
        }
    };

    std::unordered_set<Pair, std::hash<Pair>> h;

    h.insert(pa);
    h.insert(pb);
    h.insert(pc);
    h.insert(pd);
    h.insert(pe);

   for(auto & p : h)
   {
      std::cout << p.first << " " << p.second << "\n";
   }

   // note 5,7 AND 7,5 is outputted
}

Безопасно ли использовать обычные свойства хэша: если два элемента равны, у них одинаковый хеш. Два одинаковых хэша не означают одинаковые элементы?


person relaxxx    schedule 28.08.2014    source источник


Ответы (1)


Да, это отношение требуется в соответствии со стандартом C ++, раздел § 23.2.5 / 5 [unord.req] - (Неупорядоченные ассоциативные контейнеры, выделено мной)

Объект контейнера типа Hash, обозначаемый хешем, называется хеш-функцией контейнера. Объект контейнера типа Pred, обозначаемый словом pred, называется предикатом равенства ключей контейнера.

Два значения k1 и k2 типа Key считаются эквивалентными, если предикат равенства ключей контейнера возвращает true при передаче этих значений. Если k1 и k2 эквивалентны, хеш-функция контейнера должна возвращать одинаковое значение для обоих.


Обратите внимание, что это требование относится ко всем неупорядоченным ассоциативным контейнерам, а не только к std::unordered_set.

person quantdev    schedule 28.08.2014