Cách sử dụng unordered_set với các loại tùy chỉnh?

Question

Tôi có cần tạo hàm băm của riêng mình cho các loại tùy chỉnh không? Không có mặc định tôi có thể sử dụng với unordered_set?

Answer 1

Thư viện chuẩn chứa các chuyên ngành của std::hash<T> cho các loại cơ bản, cho con trỏ và cho std::string (hoặc đúng hơn, cho tất cả các chuyên ngành của std::basic_string).

Đáng tiếc là thư viện không không chứa quan trọng chức năng mới như sau-từ-cũ kết hợp, tuy nhiên đó là một phần của Boost, và trong đó bạn nên sao chép vào mã của bạn:

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

Với chức năng này, bạn có thể băm cặp, bộ dữ liệu, mảng và bất kỳ loại nào của phạm vi của các phần tử mà chính chúng có thể băm. Duyệt các nguồn Boost cho nhiều ví dụ và triển khai hữu ích. Và rõ ràng là bạn có thể sử dụng hàm này để tạo hàm băm cho các kiểu của riêng bạn. Ví dụ: đây là băm một cặp:

template<typename S, typename T> struct pair_hash<std::pair<S, T>> 
{ 
    inline std::size_t operator()(const std::pair<S, T> & v) const 
    { 
     std::size_t seed = 0; 
     hash_combine(seed, v.first); 
     hash_combine(seed, v.second); 
     return seed; 
    } 
}; 

Xin lưu ý, mặc dù kết hợp băm không tạo ra giá trị băm tốt. Kết quả có chất lượng thống kê rất kém (ví dụ: rất dễ dàng để tạo ra các va chạm băm). Cần băm tốt để có thể xem tất cả các bit đầu vào thô, và không thể được thừa nhận thông qua các phần băm. (Đó là lý do tại sao không có giải pháp tốt hơn trong thư viện chuẩn hiện tại; không ai có thể đưa ra một thiết kế thỏa đáng.)

Answer 2

Có, bạn sẽ cần phải viết hàm băm của riêng bạn. Đây không phải là xấu như nó âm thanh: nếu lớp học của bạn có bất kỳ thành viên băm mà bạn biết sẽ được hợp lý duy nhất, bạn chỉ có thể trả về băm của thành viên đó.

Bạn có thể cung cấp băm này theo chuyên std::hash hoặc bằng cách chuyển lớp băm một cách rõ ràng làm thông số mẫu.