C++ unordered_map sử dụng một loại lớp tùy chỉnh như là chìa khóa

Question

Tôi đang cố gắng sử dụng một lớp tùy chỉnh như là chìa khóa cho unordered_map, như sau,

#include <iostream> 
#include <algorithm> 
#include <unordered_map> 
//#include <map> 

using namespace std; 

class node; 
class Solution; 

class Node { 
    public: 
     int a; 
     int b; 
     int c; 
     Node(){} 
     Node(vector<int> v) { 
      sort(v.begin(), v.end()); 
      a = v[0];  
      b = v[1];  
      c = v[2];  
     } 

     bool operator==(Node i) { 
      if (i.a==this->a && i.b==this->b &&i.c==this->c) { 
       return true; 
      } else { 
       return false; 
      } 
     } 
}; 

int main() { 

    unordered_map<Node, int> m; 

    vector<int> v; 
    v.push_back(3); 
    v.push_back(8); 
    v.push_back(9); 
    Node n(v); 

    m[n] = 0; 

    return 0; 
} 

Tôi đoán tôi cần một câu nói C++ làm thế nào để băm lớp Node, tuy nhiên, tôi không hoàn toàn chắc chắn làm thế nào để làm điều đó. Có ví dụ nào cho loại nhiệm vụ này không?

Sau đây là lỗi từ g ++:

In file included from /usr/include/c++/4.6/string:50:0, 
       from /usr/include/c++/4.6/bits/locale_classes.h:42, 
       from /usr/include/c++/4.6/bits/ios_base.h:43, 
       from /usr/include/c++/4.6/ios:43, 
       from /usr/include/c++/4.6/ostream:40, 
       from /usr/include/c++/4.6/iostream:40, 
       from 3sum.cpp:4: 
/usr/include/c++/4.6/bits/stl_function.h: In member function ‘bool std::equal_to<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Node]’: 
/usr/include/c++/4.6/bits/hashtable_policy.h:768:48: instantiated from ‘bool std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_M_compare(const _Key&, std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_Hash_code_type, std::__detail::_Hash_node<_Value, false>*) const [with _Key = Node, _Value = std::pair<const Node, int>, _ExtractKey = std::_Select1st<std::pair<const Node, int> >, _Equal = std::equal_to<Node>, _H1 = std::hash<Node>, _H2 = std::__detail::_Mod_range_hashing, std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_Hash_code_type = long unsigned int]’ 
/usr/include/c++/4.6/bits/hashtable.h:897:2: instantiated from ‘std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node* std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_M_find_node(std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node*, const key_type&, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type) const [with _Key = Node, _Value = std::pair<const Node, int>, _Allocator = std::allocator<std::pair<const Node, int> >, _ExtractKey = std::_Select1st<std::pair<const Node, int> >, _Equal = std::equal_to<Node>, _H1 = std::hash<Node>, _H2 = std::__detail::_Mod_range_hashing, _Hash = std::__detail::_Default_ranged_hash, _RehashPolicy = std::__detail::_Prime_rehash_policy, bool __cache_hash_code = false, bool __constant_iterators = false, bool __unique_keys = true, std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node = std::__detail::_Hash_node<std::pair<const Node, int>, false>, std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::key_type = Node, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type = long unsigned int]’ 
/usr/include/c++/4.6/bits/hashtable_policy.h:546:53: instantiated from ‘std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::mapped_type& std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::operator[](const _Key&) [with _Key = Node, _Pair = std::pair<const Node, int>, _Hashtable = std::_Hashtable<Node, std::pair<const Node, int>, std::allocator<std::pair<const Node, int> >, std::_Select1st<std::pair<const Node, int> >, std::equal_to<Node>, std::hash<Node>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, false, false, true>, std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::mapped_type = int]’ 
3sum.cpp:149:5: instantiated from here 
/usr/include/c++/4.6/bits/stl_function.h:209:23: error: passing ‘const Node’ as ‘this’ argument of ‘bool Node::operator==(Node)’ discards qualifiers [-fpermissive] 
make: *** [threeSum] Error 1 

Answer 1

Để có thể sử dụng std::unordered_map (hoặc một trong các container kết hợp có thứ tự khác) với một chìa khóa kiểu người dùng định nghĩa, bạn cần xác định hai điều :

1. A hàm băm; đây phải là một lớp ghi đè operator() và tính toán giá trị băm cho một đối tượng của loại khóa. Một cách đặc biệt dễ hiểu là thực hiện mẫu std::hash cho loại khóa của bạn.

2. A chức năng so sánh cho sự bình đẳng; điều này là bắt buộc vì hàm băm không thể dựa vào thực tế là hàm băm sẽ luôn cung cấp giá trị băm duy nhất cho mỗi khóa riêng biệt (nghĩa là nó cần có khả năng đối phó với va chạm), vì vậy nó cần một cách để so sánh hai khóa đã cho cho một kết hợp chính xác. Bạn có thể thực hiện điều này hoặc là một lớp ghi đè operator() hoặc dưới dạng chuyên môn của std::equal hoặc – dễ dàng nhất của tất cả – bằng cách quá tải operator==() cho loại khóa của bạn (như bạn đã làm).

Khó khăn với hàm băm là nếu loại khóa của bạn bao gồm nhiều thành viên, bạn sẽ thường xuyên có hàm băm tính giá trị băm cho từng thành viên và sau đó kết hợp chúng thành một giá trị băm cho toàn bộ đối tượng. Để có hiệu suất tốt (nghĩa là, ít va chạm), bạn nên suy nghĩ cẩn thận về cách kết hợp các giá trị băm riêng lẻ để đảm bảo bạn tránh nhận được cùng một đầu ra cho các đối tượng khác nhau quá thường xuyên.

Điểm khởi đầu khá tốt cho hàm băm là một điểm sử dụng phép dịch bit và bit XOR để kết hợp các giá trị băm riêng lẻ. Ví dụ, giả sử một chìa khóa kiểu như thế này:

struct Key 
{ 
    std::string first; 
    std::string second; 
    int   third; 

    bool operator==(const Key &other) const 
    { return (first == other.first 
      && second == other.second 
      && third == other.third); 
    } 
}; 

Đây là một hàm băm đơn giản (chuyển thể từ một trong những sử dụng trong cppreference example for user-defined hash functions):

namespace std { 

    template <> 
    struct hash<Key> 
    { 
    std::size_t operator()(const Key& k) const 
    { 
     using std::size_t; 
     using std::hash; 
     using std::string; 

     // Compute individual hash values for first, 
     // second and third and combine them using XOR 
     // and bit shifting: 

     return ((hash<string>()(k.first) 
      ^(hash<string>()(k.second) << 1)) >> 1) 
      ^(hash<int>()(k.third) << 1); 
    } 
    }; 

} 

Với điều này tại chỗ, bạn có thể nhanh chóng một std::unordered_map cho phím kiểu:

int main() 
{ 
    std::unordered_map<Key,std::string> m6 = { 
    { {"John", "Doe", 12}, "example"}, 
    { {"Mary", "Sue", 21}, "another"} 
    }; 
} 

Nó sẽ tự động sử dụng std::hash<Key> như đã định nghĩa ở trên cho phép tính giá trị băm, và operator== được định nghĩa là chức năng thành viên của Key để kiểm tra bình đẳng.

Nếu bạn không muốn chuyên mẫu bên trong không gian tên std (mặc dù nó hoàn toàn hợp pháp trong trường hợp này), bạn có thể xác định hàm băm làm lớp riêng biệt và thêm nó vào danh sách đối số mẫu cho bản đồ:

struct KeyHasher 
{ 
    std::size_t operator()(const Key& k) const 
    { 
    using std::size_t; 
    using std::hash; 
    using std::string; 

    return ((hash<string>()(k.first) 
      ^(hash<string>()(k.second) << 1)) >> 1) 
      ^(hash<int>()(k.third) << 1); 
    } 
}; 

int main() 
{ 
    std::unordered_map<Key,std::string,KeyHasher> m6 = { 
    { {"John", "Doe", 12}, "example"}, 
    { {"Mary", "Sue", 21}, "another"} 
    }; 
} 

Cách xác định hàm băm tốt hơn? Như đã nói ở trên, việc xác định hàm băm tốt là quan trọng để tránh va chạm và có hiệu suất tốt. Để có một cái thực sự tốt, bạn cần phải tính đến sự phân bố các giá trị có thể có của tất cả các trường và định nghĩa hàm băm mà dự án phân phối tới một không gian có thể có kết quả rộng và phân bố đều nhất có thể.

Điều này có thể khó khăn; phương pháp XOR/bit-shift ở trên có lẽ không phải là một khởi đầu tồi. Để bắt đầu tốt hơn một chút, bạn có thể sử dụng mẫu chức năng hash_value và hash_combine từ thư viện Boost. Các hành vi cũ theo cách tương tự như std::hash đối với các loại tiêu chuẩn (gần đây cũng bao gồm bộ dữ liệu và các loại tiêu chuẩn hữu ích khác); sau này giúp bạn kết hợp các giá trị băm riêng lẻ thành một. Đây là một viết lại của hàm băm có sử dụng các chức năng Boost helper:

#include <boost/functional/hash.hpp> 

struct KeyHasher 
{ 
    std::size_t operator()(const Key& k) const 
    { 
     using boost::hash_value; 
     using boost::hash_combine; 

     // Start with a hash value of 0 . 
     std::size_t seed = 0; 

     // Modify 'seed' by XORing and bit-shifting in 
     // one member of 'Key' after the other: 
     hash_combine(seed,hash_value(k.first)); 
     hash_combine(seed,hash_value(k.second)); 
     hash_combine(seed,hash_value(k.third)); 

     // Return the result. 
     return seed; 
    } 
}; 

và đây là một viết lại mà không sử dụng tăng, nhưng sử dụng phương pháp tốt của việc kết hợp các băm:

namespace std 
{ 
    template <> 
    struct hash<Key> 
    { 
     size_t operator()(const Key& k) const 
     { 
      // Compute individual hash values for first, second and third 
      // http://stackoverflow.com/a/1646913/126995 
      size_t res = 17; 
      res = res * 31 + hash<string>()(k.first); 
      res = res * 31 + hash<string>()(k.second); 
      res = res * 31 + hash<int>()(k.third); 
      return res; 
     } 
    }; 
}