정렬되지 않은 set 요소에 사용할 사용자 정의 클래스를 설정하는 것이 집합에서 찾을 수 없습니다

Question

내가하려는 것은 std :: unordered_set을 사용자 정의 클래스 Vector2 - 과 함께 사용하는 것이 가능하도록하는 것입니다 이미 집합에 속한 클래스의 객체를 검색하려면.

좀 더 자세히 알려 드리겠습니다. 사용자 정의 해시 테이블을 포함하여 내 수업 Vector2의 헤더는 다음과 같다 :

Class Vector2 
{ 
private: 
    static int lastID; 
    const int id; 
    int x; 
    int y; 

public: 
    Vector2(int _x, int _y); 
    ~Vector2(); 

    bool Vector2::operator==(const Vector2& other) const; 

    int getId() const; 
    int getX() const; 
    int getY() const; 
}; 

namespace std 
{ 
    template<> 
    struct hash<Vector2> 
    { 
     size_t 
      operator()(const Vector2& obj) const 
     { 
      return hash<int>()(obj.getId()); 
     } 
    }; 
} 

같은 클래스의 일원이 기능의 구현은 간단하다 :

이

int Vector2::lastID = 0; 

Vector2::Vector2(int _x, int _y) : id(lastID++) 
{ 
    x = _x; 
    y = _y; 
} 

int Vector2::getId() const 
{ 
    return id; 
} 

int Vector2::getX() const 
{ 
    return x; 
} 

int Vector2::getY() const 
{ 
    return y; 
} 

bool Vector2::operator==(const Vector2& other) const 
{ 
    if (x != other.x || y != other.y) return false; 
    return true; 
} 

그런 다음 내 주요 기능의 모습 다음

std::unordered_set<Vector2> mySet; 
mySet.insert(Vector2(1, 2)); 
mySet.insert(Vector2(3, 11)); 
mySet.insert(Vector2(-5, 0)); 

Vector2 whatToLookFor(1, 2); 
if (mySet.find(whatToLookFor) != mySet.end()) 
{ 
    std::cout << "Found it!" << std::endl; 
} 
else 
{ 
    std::cout << "Nothing found." << std::endl; 
} 

을하지만, 내가 출력이 Found it! 것으로 기대하면서, 실제로 Nothing found입니다. 즉, Vector2 객체 Vector2(1, 2), Vector2(3, 11) 및 Vector2(-5, 0)은 mySet에 삽입되지만 나중에 해당 세트 내에서 검색 할 때 발견되지 않습니다.

내가 뭘 잘못하고 있니? 다음 h(A) == h(B)A == B 경우, 일 : unordered_set에

Answer 1

검색 작업은 해쉬 함수 h 주어진 것을 요하는 요소의 해시 값에 크게 의존한다.

검색을 수행 할 때 해시 함수를 사용하여 요소가 속한 버킷을 결정합니다. 그런 다음 버킷에 여러 요소가있는 경우 이러한 요소를 서로 비교하기 위해 추가 검사가 수행됩니다. 이는 요소를 직접 비교하거나, 다시 해싱하거나, 다른 기법을 사용하여 수행 할 수 있습니다.

클래스에는 두 개의 데이터 멤버가 있으며, 정확한 멤버로 요소를 "찾을"것으로 예상됩니다 (즉, A.x == B.x && A.y == B.y이면 A == B, 그 반대의 경우). 그러나 해시 함수는 요소의 id을 기반으로 해시 함수 만 해시합니다. 다른 멤버를 무시하면 해시 함수가 예상대로 작동하지 않습니다.

해결 방법은 해시 함수를 다시 작성하여 필드 값을 활용하는 것입니다. this 설명서 페이지를 확인할 수도 있습니다.