Jak korzystać z unordered_set?

Question

próbuję zdefiniować unordered_set takiego:

unordered_set<Point> m_Points; 

Kiedy go skompilować, pojawia się następujący błąd:

The C++ Standard doesn't provide a hash for this type.

Class Point:

class Point{ 
    private: 
     int x, y; 
    public: 
     Point(int a_x, int a_y) 
      : x(a_x), y(a_y) 
     {} 
     ~Point(){} 

     int getX()const { return x; } 
     int getY()const { return y; } 

     bool operator == (const Point& rhs) const{ 
      return x == rhs.x && y == rhs.y; 
     } 

     bool operator != (const Point& rhs) const{ 
      return !(*this == rhs); 
     } 
}; 

• Jak/gdzie mogę zdefiniować funkcję skrótu dla Punkt?
• Jaka byłaby dobra funkcja skrótu dla punktu 2D?

Answer 1

std::unordered_set wymaga napisania hash functions, aby zapisać i znaleźć własne typy.

Typy baz i wiele typów w przestrzeni nazw std mają takie funkcje mieszania w zakresie std::hash<Key>. Funkcje te wynikają certain rules:

1. akceptuje jeden parametr typu Key.

2. Powoduje zwrócenie wartości typu size_t, która reprezentuje wartość skrótu parametru.

3. Nie wyrzuca wyjątków po wywołaniu.

4. Dla dwóch parametrów k1 i k2, które są równe, std::hash<Key>()(k1) == std::hash<Key>()(k2).

5. dla dwóch różnych parametrów k1 i k2 że nie są sobie równe, prawdopodobieństwo, że std::hash<Key>()(k1) == std::hash<Key>()(k2) powinny być bardzo małe, zbliża 1.0/std::numeric_limits<size_t>::max().

Teraz, gdy usunęliśmy definicje z drogi, zastanówmy się, jaka jest dobra funkcja skrótu dla twojej struktury punktów. Był request, który std::pair (który jest bardzo podobny do struktury punktowej) ma funkcję skrótu, ale, niestety, nie dostał się do standardu C++ 11.

Ale mamy szczęście: SO jest niesamowite i, oczywiście, można już w zasadzie już find the answer. Zauważ, że nie musisz samodzielnie mieszać liczb całkowitych, ponieważ std::hash ma już specjalizację. Warto więc kopać w naszej funkcji mieszającej, według this answer:

namespace std 
{ 
    template <> 
    struct hash<Point> 
    { 
     size_t operator()(Point const & x) const noexcept 
     { 
      return (
       (51 + std::hash<int>()(x.getX())) * 51 
       + std::hash<int>()(x.getY()) 
      ); 
     } 
    }; 
} 

I gotowe.