C ++ unordered_map menggunakan tipe kelas khusus sebagai kuncinya

Saya mencoba menggunakan kelas khusus sebagai kunci untuk unordered_map, seperti berikut:

#include <iostream>
#include <algorithm>
#include <unordered_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;
}

Namun, g ++ memberi saya kesalahan berikut:

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

Saya kira, saya perlu memberitahu C ++ bagaimana cara hash class Node, namun, saya tidak yakin bagaimana melakukannya. Bagaimana saya bisa menyelesaikan tugas ini?

Agar dapat menggunakan std::unordered_map(atau salah satu wadah asosiatif tidak berurutan lainnya) dengan tipe kunci yang ditentukan pengguna, Anda perlu mendefinisikan dua hal:

1. Sebuah fungsi hash ; ini harus kelas yang menimpa operator()dan menghitung nilai hash yang diberikan objek tipe kunci. Salah satu cara yang paling mudah untuk melakukan ini adalah dengan mengkhususkan std::hashtemplate untuk tipe kunci Anda.

2. Sebuah fungsi perbandingan untuk kesetaraan ; ini diperlukan karena hash tidak dapat bergantung pada fakta bahwa fungsi hash akan selalu memberikan nilai hash yang unik untuk setiap kunci yang berbeda (yaitu, ia harus dapat menangani tabrakan), sehingga dibutuhkan cara untuk membandingkan dua kunci yang diberikan untuk pencocokan tepat. Anda dapat mengimplementasikan ini baik sebagai kelas yang menimpa operator(), atau sebagai spesialisasi std::equal, atau - paling mudah dari semuanya - dengan kelebihan beban operator==()untuk jenis kunci Anda (seperti yang sudah Anda lakukan).

Kesulitan dengan fungsi hash adalah bahwa jika tipe kunci Anda terdiri dari beberapa anggota, Anda biasanya akan memiliki fungsi hash menghitung nilai hash untuk masing-masing anggota, dan kemudian menggabungkannya menjadi satu nilai hash untuk seluruh objek. Untuk kinerja yang baik (yaitu, beberapa tabrakan), Anda harus berpikir dengan hati-hati tentang cara menggabungkan nilai hash individu untuk memastikan Anda menghindari mendapatkan output yang sama untuk objek yang berbeda terlalu sering.

Titik awal yang cukup baik untuk fungsi hash adalah titik yang menggunakan bit shifting dan bitwise XOR untuk menggabungkan nilai hash individu. Misalnya, dengan asumsi tipe kunci seperti ini:

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

Berikut adalah fungsi hash sederhana (diadaptasi dari yang digunakan dalam contoh cppreference untuk fungsi hash yang ditentukan pengguna ):

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

}

Dengan ini, Anda bisa instantiate std::unordered_mapuntuk tipe kunci:

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

Ini akan secara otomatis digunakan std::hash<Key>sebagaimana didefinisikan di atas untuk perhitungan nilai hash, dan yang operator==didefinisikan sebagai fungsi anggota Keyuntuk pemeriksaan kesetaraan.

Jika Anda tidak ingin mengkhususkan templat di dalam stdnamespace (meskipun dalam hal ini legal), Anda dapat mendefinisikan fungsi hash sebagai kelas terpisah dan menambahkannya ke daftar argumen templat untuk peta:

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

Bagaimana cara mendefinisikan fungsi hash yang lebih baik? Seperti dikatakan di atas, mendefinisikan fungsi hash yang baik adalah penting untuk menghindari tabrakan dan mendapatkan kinerja yang baik. Untuk yang benar-benar bagus, Anda perlu memperhitungkan distribusi nilai-nilai yang mungkin dari semua bidang dan mendefinisikan fungsi hash yang memproyeksikan distribusi tersebut ke ruang hasil yang mungkin selebar dan sebagi mungkin didistribusikan.

Ini bisa sulit; metode XOR / bit-shifting di atas mungkin bukan awal yang buruk. Untuk awal yang sedikit lebih baik, Anda dapat menggunakan hash_valuedan hash_combineberfungsi template dari perpustakaan Boost. Yang pertama bertindak dengan cara yang sama seperti std::hashuntuk tipe standar (baru-baru ini juga termasuk tupel dan tipe standar berguna lainnya); yang terakhir membantu Anda menggabungkan nilai hash individu menjadi satu. Berikut adalah penulisan ulang fungsi hash yang menggunakan fungsi pembantu Boost:

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

Dan inilah penulisan ulang yang tidak menggunakan boost, namun menggunakan metode yang baik untuk menggabungkan hash:

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

Saya pikir, jogojapan memberikan yang sangat baik dan lengkap jawaban . Anda harus melihatnya sebelum membaca posting saya. Namun, saya ingin menambahkan yang berikut ini:

1. Anda dapat menentukan fungsi perbandingan untuk secara unordered_mapterpisah, alih-alih menggunakan operator perbandingan kesetaraan ( operator==). Ini mungkin berguna, misalnya, jika Anda ingin menggunakan yang terakhir untuk membandingkan semua anggota dari dua Nodeobjek satu sama lain, tetapi hanya beberapa anggota tertentu sebagai kunci dari sebuah unordered_map.
2. Anda juga dapat menggunakan ekspresi lambda alih-alih mendefinisikan fungsi hash dan perbandingan.

Secara keseluruhan, untuk Nodekelas Anda , kode dapat ditulis sebagai berikut:

using h = std::hash<int>;
auto hash = [](const Node& n){return ((17 * 31 + h()(n.a)) * 31 + h()(n.b)) * 31 + h()(n.c);};
auto equal = [](const Node& l, const Node& r){return l.a == r.a && l.b == r.b && l.c == r.c;};
std::unordered_map<Node, int, decltype(hash), decltype(equal)> m(8, hash, equal);

Catatan:

• Saya hanya menggunakan kembali metode hashing pada akhir jawaban jogojapan, tetapi Anda dapat menemukan ide untuk solusi yang lebih umum di sini (jika Anda tidak ingin menggunakan Boost).
• Kode saya mungkin agak terlalu kecil. Untuk versi yang sedikit lebih mudah dibaca, silakan lihat kode ini di Ideone .