C tuşu olarak özel bir sınıf türü kullanarak unordered_map

SORU

10 HAZİRAN 2013, PAZARTESİ

C tuşu olarak özel bir sınıf türü kullanarak unordered_map

Özel bir sınıf aşağıdaki gibi unordered_map için anahtar olarak kullanmaya çalışı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;
}

Karma nasıl söyle C sınıfı Düğüm ihtiyacım var sanırım, ancak oldukça nasıl emin değilim. Görevleri bu tür için herhangi bir örnek var mı?

Çok teşekkürler!

Aşağıdaki g: hata

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

CEVAP

10 HAZİRAN 2013, PAZARTESİ

Kullanıcı tanımlı anahtar tipi ile std::unordered_map (veya diğer sırasız ilişkilendirilebilir kapları bir) kullanabilmek için, iki şey tanımlamak gerekir:

Birkarma işlevi; operator() geçersiz kılan bir sınıf olmalı ve hesaplar karma değeri anahtar tipi bir nesne verilir. Özellikle düz ileri bir şekilde bu işi anahtar tipi sizin için std::hash şablon uzmanlaşmak.
Bireşitlik için karşılaştırma işlevi; bu gereklidir, çünkü karma edemiyor güveniyor aslında karma çalışmaz her zaman benzersiz bir karma değer için her ayrı bir anahtar (yani, ihtiyacı olmak üzere anlaşma ile çarpışmalar), bu kadar ihtiyacı olan bir şekilde karşılaştırmak için iki belirli anahtarlar için tam bir eşleşme. Sen-ebilmek uygulamak bu da bir sınıf geçersiz kılar operator() veya bir uzmanlık std::equal ya da-en kolay, tüm-tarafından aşırı operator==() anahtarınızı yazın sen de öyle zaten).

Güçlükle karma işlevi olduğunu Eğer anahtarınızı yazın oluşur bazı üyeleri, genellikle var olan hash fonksiyonu hash değerlerini hesaplamak için tek tek üyeleri, ve sonra bir yerde birleştirmek onları bir karma değer için tüm nesne. İyi performans (yani, birkaç çarpışmalar) için dikkatli bir şekilde tek tek hash değerleri farklı nesneler için aynı çıktıyı çok sık almamak sağlamak için birleştirmek için nasıl düşünmek gerekir.

Karma işlevi için oldukça iyi bir başlangıç noktası bit kayması ve bit seviyesinde XOR tek tek hash değerleri birleştirmek için kullanır. Örneğin, anahtar tipi varsayarak bu gibi:

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

Burada basit bir hash fonksiyonu (cppreference example for user-defined hash functions kullanılan uyarlanmıştır):

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, anahtar türü için std::unordered_map: bir başlatılamadı

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

Otomatik olarak yukarıda tanımlanan std::hash<Key> karma değer hesaplamaları için kullanır, ve operator== eşitlik kontrolleri için Key üye fonksiyonu olarak tanımlanmış.

Eğer istemiyorsan bir uzman şablonu içinde std ad (rağmen gayet yasal olarak bu durumda) tanımlayabilirsiniz hash fonksiyonu olarak ayrı bir sınıf ve eklemek için şablon argüman listesini göster:

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

Nasıl daha iyi bir karma işlev tanımlamak için? İyi bir karma işlev tanımlama önemli çarpışmaları önlemek ve iyi bir performans elde etmek için, yukarıdaki " dedi. Bir gerçek iyi bir ihtiyacın için hesaba dağılımı olası değerleri tüm alanları tanımlamak ve karma işlevi olan projeler dağıtım için bir boşluk olası sonuçları olarak geniş ve eşit olarak dağıtılmış olarak mümkün.

Bu zor olabilir; bit kaydırma yöntemi yukarıda/XOR muhtemelen kötü bir başlangıç değil. Biraz daha iyi bir başlangıç için Destek hash_value hash_combine işlev şablon kitaplığı kullanabilirsiniz. Eski standart tip std::hash benzer bir şekilde (yakın zamanda dizilerini ve diğer yararlı standart türleri de dahil olmak üzere) hareket eder; ikincisi, bir tek tek hash değerleri birleştirmek yardımcı olur. İşte Artırmaya yardımcı işlevlerini kullanan karma yeniden bir fonksiyonu

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

Bunu Paylaş: