카테고리 보관물: C++

C++

사용자 정의 클래스 유형을 키로 사용하는 C ++ unorder_map from /usr/include/c++/4.6/ostream:40,

unordered_map다음과 같이 사용자 정의 클래스를 키로 사용하려고합니다 .

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

그러나 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

나는 C ++에게 클래스를 해시하는 방법을 알려 주어야 Node하지만 어떻게 해야할지 잘 모르겠습니다. 이 작업을 어떻게 수행 할 수 있습니까?

답변

std::unordered_map사용자 정의 키 유형으로 (또는 정렬되지 않은 다른 연관 컨테이너 중 하나) 를 사용하려면 다음 두 가지를 정의해야합니다.

  1. 해시 함수 ; operator()키 타입의 객체가 주어진 해시 값 을 재정의 하고 계산 하는 클래스 여야합니다 . 이 작업을 수행하는 가장 간단한 방법 중 하나는 std::hash키 유형에 맞게 템플릿 을 특수화하는 것 입니다.

  2. 같은지 비교 함수 ; 해시는 해시 함수가 항상 모든 고유 키에 대해 고유 한 해시 값을 제공한다는 사실 (예 : 충돌을 처리 할 수 ​​있어야 함)에 의존 할 수 없으므로 두 개의 지정된 키를 비교할 수있는 방법이 필요하기 때문에 필요합니다. 정확히 일치합니다. 키 유형에 대해 오버로드 (이미 수행 한대로)를 재정의하는 클래스 operator()또는 특수화 std::equal또는 가장 쉬운 클래스로이를 구현할 수 있습니다 operator==().

해시 함수의 어려움은 키 유형이 여러 멤버로 구성된 경우 일반적으로 해시 함수가 개별 멤버의 해시 값을 계산 한 다음 전체 오브젝트에 대해 하나의 해시 값으로 결합한다는 것입니다. 성능을 높이려면 (예 : 충돌이 거의 발생하지 않음) 개별 해시 값을 결합하여 다른 객체에 대해 동일한 출력을 너무 자주 얻지 않도록하는 방법에 대해 신중하게 고려해야합니다.

해시 함수의 시작점은 비트 이동 및 비트 XOR을 사용하여 개별 해시 값을 결합하는 것입니다. 예를 들어 다음과 같은 키 유형을 가정합니다.

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

다음은 간단한 해시 함수입니다 ( 사용자 정의 해시 함수 에 대한 cppreference 예제에서 사용 된 것 ).

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

}

이를 통해 std::unordered_map키 유형에 대한 a 를 인스턴스화 할 수 있습니다 .

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

std::hash<Key>해시 값 계산에 대해 위에 operator==정의 된대로 , Key동등 검사 에 대한 멤버 함수 로 정의 된대로 자동으로 사용 됩니다 .

std네임 스페이스 내에서 템플릿을 특수화하지 않으려면 (이 경우 완벽하게 합법적이지만) 해시 함수를 별도의 클래스로 정의하여 맵의 템플릿 인수 목록에 추가 할 수 있습니다.

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

더 나은 해시 함수를 정의하는 방법? 위에서 말했듯이 충돌을 피하고 성능을 높이려면 좋은 해시 함수를 정의하는 것이 중요합니다. 실제로 좋은 결과를 얻으려면 모든 필드의 가능한 값 분포를 고려하고 가능한 넓고 고르게 분포 된 가능한 결과 공간으로 분포를 투영하는 해시 함수를 정의해야합니다.

이것은 어려울 수 있습니다. 위의 XOR / 비트 시프 팅 방법은 아마도 나쁜 시작이 아닙니다. 약간 더 나은 시작 을 위해 Boost 라이브러리에서 hash_valueand hash_combine함수 템플릿을 사용할 수 있습니다 . 전자는 std::hash표준 유형 과 비슷한 방식으로 작동 합니다 (최근에는 튜플 및 기타 유용한 표준 유형 포함). 후자는 개별 해시 값을 하나로 결합하는 데 도움이됩니다. 다음은 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;
  }
};

다음은 부스트를 사용하지 않지만 해시를 결합하는 좋은 방법을 사용하는 다시 작성입니다.

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

답변

Jogojapan 은 매우 훌륭하고 철저한 답변을 했다고 생각 합니다. 내 게시물을 읽기 전에 결정적으로 살펴 봐야합니다. 그러나 다음을 추가하고 싶습니다.

  1. unordered_map항등 비교 연산자 ( operator==) 를 사용하는 대신 별도로 비교 함수를 정의 할 수 있습니다 . 예를 들어 후자를 사용하여 두 Node객체 의 모든 멤버 를 서로 비교 하지만 일부 특정 멤버 만 키의 키로 사용하려는 경우unordered_map .
  2. 해시 및 비교 함수를 정의하는 대신 람다 식을 사용할 수도 있습니다 .

전체적으로 Node클래스의 코드는 다음과 같이 작성할 수 있습니다.

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

노트:

  • jogojapan의 답변 끝에 해싱 방법을 재사용했지만 더 일반적인 솔루션에 대한 아이디어를 찾을 수 있습니다. (당신이 부스트를 사용하지 않는 경우).
  • 내 코드가 약간 축소되었을 수 있습니다. 약간 더 읽기 쉬운 버전 은 Ideone에서이 코드 를 참조하십시오 .

답변