Làm cách nào để sử dụng unordered_set?

Question

Tôi cố gắng để xác định một unordered_set như thế này:

unordered_set<Point> m_Points; 

Khi tôi biên dịch nó, tôi nhận được lỗi sau:

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

Lớp 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); 
     } 
}; 

• thế nào/Tôi xác định hàm băm ở đâu cho Điểm?
• Chức năng băm tốt cho điểm 2D là gì?

Answer 1

std::unordered_set yêu cầu bạn viết hash functions để lưu trữ và tìm các loại của riêng bạn.

Loại cơ sở và nhiều loại trong không gian tên std có hàm băm như vậy trong phạm vi std::hash<Key>. Các chức năng này tuân theo certain rules:

1. Chấp nhận một tham số đơn loại Key.

2. Trả về giá trị loại size_t đại diện cho giá trị băm của tham số.

3. Không ném ngoại lệ khi được gọi.

4. Đối với hai thông số k1 và k2 bằng nhau, std::hash<Key>()(k1) == std::hash<Key>()(k2).

5. Đối với hai thông số khác nhau k1 và k2 không bằng nhau, xác suất std::hash<Key>()(k1) == std::hash<Key>()(k2) phải rất nhỏ, tiếp cận 1.0/std::numeric_limits<size_t>::max().

Bây giờ, chúng tôi đã tìm ra định nghĩa, hãy nghĩ về hàm băm tốt cho cấu trúc điểm của bạn. Có một số request rằng std::pair (rất giống với một cấu trúc điểm) có hàm băm, nhưng thật không may, nó không được đưa vào tiêu chuẩn C++ 11.

Nhưng chúng tôi may mắn: SO là tuyệt vời và, tất nhiên, về cơ bản bạn đã có thể là find the answer. Lưu ý rằng bạn không phải tự băm số nguyên, bởi vì std::hash có một chuyên môn cho điều đó. Vì vậy, hãy tìm hiểu hàm băm của chúng tôi, theo số 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()) 
      ); 
     } 
    }; 
} 

Và chúng tôi đã hoàn tất.