Связь между hasher и key_equal в std :: unordered_set

Question

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

Но нет такой вещи написаны либо на 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 
} 

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

Answer 1

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

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

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

---

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