Soru C ++ unordered_map, anahtar olarak özel bir sınıf türü kullanarak


Unordered_map için aşağıdaki gibi özel bir sınıf kullanıyorum:

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

Sanırım C ++'ya nasıl bir nota sınıfına ihtiyacım var, ama nasıl yapacağımı tam olarak bilmiyordum. Bu tür görevlere örnek var mı?

Aşağıdaki g ++ hatasıdır:

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

199
2018-06-10 02:34


Menşei


üçüncü şablon argümanı Sağlamanız gereken karma işlevidir. - chrisaycock
cppreference, bunun nasıl yapılacağına dair basit ve pratik bir örneğe sahiptir: en.cppreference.com/w/cpp/container/unordered_map/unordered_map - jogojapan


Cevaplar:


Kullanabilmek std::unordered_map Kullanıcı tanımlı bir anahtar türüyle (veya diğer sırasız birleştirici kapsayıcılardan biri), iki şeyi tanımlamanız gerekir:

  1. bir Özet fonksiyonu; Bu geçersiz kılan bir sınıf olmalı operator() ve anahtar türünde bir nesne verilen karma değerini hesaplar. Bunu yapmak için özellikle düz ileri bir yol uzmanlaşmaktır std::hash Anahtar türünüz için şablon.

  2. bir eşitlik için karşılaştırma işlevi; Bu, karma'nın hash fonksiyonunun her bir farklı anahtar için her zaman benzersiz bir hash değeri sağlayacağına (yani, çarpışmalarla başa çıkabilmesi gerekir) güvenmesi gerektiğinden, bu gereklidir. Bu yüzden, verilen iki anahtarın karşılaştırılması için bir yönteme ihtiyaç vardır. tam bir eşleşme için. Bunu, geçersiz kılan bir sınıf olarak uygulayabilirsiniz. operator()ya da bir uzmanlık olarak std::equalya da - en kolay - aşırı yükleme operator==() Anahtar tipiniz için (zaten yaptığınız gibi).

Karma işleviyle ilgili zorluk, anahtar türünüz birkaç üyeden oluşuyorsa, genellikle hash işlevinin tek tek üyeler için karma değerlerini hesaplaması ve daha sonra bunları bir şekilde tüm nesne için bir karma değeriyle birleştirmenizdir. İyi performans için (yani, birkaç çarpışma), farklı çıktılar için aynı çıkışı elde etmekten kaçınmak için bireysel karma değerlerin nasıl birleştirileceği konusunda dikkatli düşünmelisiniz.

Bir hash işlevi için oldukça iyi bir başlangıç ​​noktası, bireysel karma değerlerini birleştirmek için bit kaydırması ve bitsel XOR kullanan birdir. Örneğin, böyle bir anahtar türü varsayarak:

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

İşte basit bir karma işlevi (kullanılan Kullanıcı tanımlı karma işlevleri için cppreference örneği):

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

}

Bu ile, bir std::unordered_map anahtar türü için:

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

Otomatik olarak kullanacak std::hash<Key> yukarıda hash değeri hesaplamaları için tanımlandığı gibi ve operator== üye işlevi olarak tanımlanır Key eşitlik kontrolleri için.

Şablonun içinde uzmanlaşmak istemiyorsanız std ad alanı (bu durumda tamamen yasal olmasına rağmen), karma işlevini ayrı bir sınıf olarak tanımlayabilir ve haritanın şablon argüman listesine ekleyebilirsiniz:

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

Daha iyi bir karma işlevi nasıl tanımlanır? Yukarıda da belirtildiği gibi, iyi bir karma işlev tanımlamak, çarpışmaları önlemek ve iyi bir performans elde etmek için önemlidir. Gerçekten iyi bir şey için, tüm alanların olası değerlerinin dağılımını hesaba katmalı ve bu dağılımı mümkün olduğunca geniş ve eşit bir şekilde dağıtılmış olası bir alana yansıtan bir karma işlev tanımlamanız gerekir.

Bu zor olabilir; Yukarıdaki XOR / bit değiştirme yöntemi muhtemelen kötü bir başlangıç ​​değildir. Biraz daha iyi bir başlangıç ​​için hash_valueve hash_combine Destek kütüphanesinden işlev şablonu. Eski benzer şekilde davranır std::hash Standart tipler için (yakın zamanda tuples ve diğer kullanışlı standart tipler de dahil); İkincisi, bireysel karma değerlerini bir araya getirmenize yardımcı olur. İşte Boost yardımcı işlevlerini kullanan karma işlevinin yeniden yazımıdır:

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

Ve bu, destek kullanmıyor, ancak karmaları birleştirmek için iyi bir yöntem kullanıyor:

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

340
2018-06-10 05:18



Lütfen bitlerin neden kaydırılmasının gerekli olduğunu açıklayabilir misiniz KeyHasher ? - Chani
Eğer bitleri değiştirmediyseniz ve iki dizge aynıysa, xor onların birbirlerini iptal etmelerine sebep olur. Yani hash ("a", "a", 1) karma ("b", "b", 1) ile aynı olacaktır. Ayrıca sipariş önemli değil, yani karma ("a", "b", 1) karma ("b", "a", 1) ile aynı olacaktır. - Buge
Ben sadece C ++ öğreniyorum ve her zaman mücadele ettiğim bir şey: Kodu nereye koyacağım? Bir uzman yazdım std::hash Yaptığın gibi benim anahtar için yöntem. Bunu, Key.cpp dosyamın altına koydum ama şu hatayı alıyorum: Error 57 error C2440: 'type cast' : cannot convert from 'const Key' to 'size_t' c:\program files (x86)\microsoft visual studio 10.0\vc\include\xfunctional. Derleyicinin karma yöntemimi bulamadığını mı tahmin ediyorum? Key.h dosyasına bir şey ekleyeyim mi? - Ben
@Ben .h dosyasına koymak doğrudur. std::hash aslında bir yapı değil, Bir struct için şablon (uzmanlık). Yani bu bir uygulama değil - derleyicinin buna ihtiyacı olduğunda bir uygulamaya dönüştürülecek. Şablonlar daima başlık dosyalarına gitmelidir. Ayrıca bakınız stackoverflow.com/questions/495021/... - jogojapan
@nightfury find() bir yineleyici döndürür ve yineleyici haritanın bir "girişine" işaret eder. Bir giriş std::pair anahtar ve değerden oluşur. Eğer yaparsan auto iter = m6.find({"John","Doe",12});, anahtarı alacaksın iter->first ve değer (yani dize "example") içinde iter->second. Dize doğrudan istiyorsanız, ya kullanabilirsiniz m6.at({"John","Doe",12}) (anahtar çıkmazsa bu bir istisna atar), veya m6[{"John","Doe",12}] (Bu anahtar yoksa, boş bir değer yaratacaktır). - jogojapan