Làm cách nào để chuyên std :: hash <Key> :: toán tử() cho loại do người dùng xác định trong vùng chứa không có thứ tự?

Question

Để hỗ trợ người dùng xác định loại quan trọng trong std::unordered_set<Key> và std::unordered_map<Key, Value> người ta phải cung cấp operator==(Key, Key) và một functor băm:

struct X { int id; /* ... */ }; 
bool operator==(X a, X b) { return a.id == b.id; } 

struct MyHash { 
    size_t operator()(const X& x) const { return std::hash<int>()(x.id); } 
}; 

std::unordered_set<X, MyHash> s; 

Nó sẽ là thuận tiện hơn để viết chỉ std::unordered_set<X> với một hash mặc định cho loại X , như đối với các loại đi kèm với trình biên dịch và thư viện. Sau khi tham khảo ý kiến ​​

• C++ chuẩn Draft N3242 §20.8.12 [unord.hash] và §17.6.3.4 [hash.requirements],
• Boost.Unordered
• g ++ include\c++\4.7.0\bits\functional_hash.h
• VC10 include\xfunctional
• khác nhau related question s trong Stack Overflow

it se ems thể chuyên std::hash<X>::operator():

namespace std { // argh! 
    template <> 
    inline size_t 
    hash<X>::operator()(const X& x) const { return hash<int>()(x.id); } // works for MS VC10, but not for g++ 
    // or 
    // hash<X>::operator()(X x) const { return hash<int>()(x.id); }  // works for g++ 4.7, but not for VC10 
}                    

Với trình biên dịch hỗ trợ cho C++ 11 vẫn chưa thực nghiệm --- Tôi không cố gắng Clang ---, đây là những câu hỏi của tôi:

1. Có hợp pháp để thêm chuyên môn như vậy vào không gian tên std? Tôi có cảm xúc lẫn lộn về điều đó.

2. Phiên bản std::hash<X>::operator() nào, nếu có, tuân thủ tiêu chuẩn C++ 11?

3. Có cách nào để di chuyển không?

Answer 1

Bạn được phép rõ ràng và khuyến khích thêm chuyên ngành đến không gian tên std *. (Chỉ và về cơ bản) cách chính xác để thêm một hàm băm là thế này:

namespace std { 
    template <> struct hash<Foo> 
    { 
    size_t operator()(const Foo & x) const 
    { 
     /* your code here, e.g. "return hash<int>()(x.value);" */ 
    } 
    }; 
} 

_{*) chừng nào (chuyên ngành phổ biến khác mà bạn có thể xem xét hỗ trợ được std::less, std::equal_to và std::swap.) một trong những loại có liên quan là do người dùng xác định, tôi giả sử.}

Answer 2

@Kerrek SB đã bao gồm 1) và 3).

2) Mặc dù g ++ và VC10 khai báo std::hash<T>::operator() với các chữ ký khác nhau, cả triển khai thư viện đều tuân thủ Tiêu chuẩn.

Tiêu chuẩn không chỉ định các thành viên của std::hash<T>. Nó chỉ nói rằng mỗi chuyên môn như vậy phải đáp ứng cùng một yêu cầu "băm" cần thiết cho đối số mẫu thứ hai của std::unordered_set và cứ tiếp tục như vậy.Cụ thể:

• Hash loại H là một đối tượng chức năng, với ít nhất một đối số kiểu Key.
• H là bản sao có thể cấu hình được.
• H có thể bị hủy.
• Nếu h là một biểu hiện của loại H hoặc const H, và k là một biểu hiện của một loại chuyển đổi thành (có thể const) Key, sau đó h(k) là một biểu thức có giá trị với loại size_t.
• Nếu h là một biểu hiện của loại H hoặc const H, và u là một vế trái của loại Key, sau đó h(u) là một biểu thức có giá trị với loại size_t mà không sửa đổi u.

Answer 3

đặt cược của tôi sẽ được trên Hash mẫu luận cho unordered_map/unorder_set/... lớp:

#include <unordered_set> 
#include <functional> 

struct X 
{ 
    int x, y; 
    std::size_t gethash() const { return (x*39)^y; } 
}; 

typedef std::unordered_set<X, std::size_t(*)(const X&)> Xunset; 
typedef std::unordered_set<X, std::function<std::size_t(const X&)> > Xunset2; 

int main() 
{ 
    auto hashX = [](const X&x) { return x.gethash(); }; 

    Xunset my_set (0, hashX); 
    Xunset2 my_set2(0, hashX); // if you prefer a more flexible set typedef 
} 

Tất nhiên

• hashX có thể cũng giống như cũng là một tĩnh toàn cầu chức năng
• trong trường hợp thứ hai, bạn có thể vượt qua điều đó
  • functor cũ fjtor vv (struct Xhasher { size_t operator(const X&) const; };)
  • std::hash<X>()
  • bất kỳ biểu hiện ràng buộc thỏa mãn chữ ký -