La définition d'une classe personnalisée à utiliser avec un élément set non ordonné ne peut pas être trouvée dans l'ensemble

Question

Ce que j'essaie de faire est de rendre possible l'utilisation de std :: unordered_set avec ma classe personnalisée Vector2 - incluant la possibilité pour rechercher des objets de cette classe qui sont déjà dans un ensemble.

Permettez-moi de donner plus de détails. L'en-tête de ma classe Vector2, y compris la table de hachage personnalisé, est la suivante:

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

La mise en œuvre des fonctions de memeber de cette catégorie est trivial:

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

Ensuite, mes fonctions principales ressemble les éléments suivants:

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

Cependant, alors que je pense que la sortie soit Found it!, il est en fait Nothing found. Cela signifie que tandis que les objets Vector2 Vector2(1, 2), Vector2(3, 11) et Vector2(-5, 0) sont insérés dans mySet, ils ne sont plus trouvés lors d'une recherche dans un tel ensemble.

Qu'est-ce que je fais mal?

Answer 1

Les opérations de recherche dans un unordered_set dépendent en grande partie de la valeur de hachage des éléments, ce qui nécessite que, compte tenu de la fonction de hachage h: si A == B, puis h(A) == h(B).

Lorsqu'une recherche est effectuée, la fonction de hachage est utilisée pour déterminer le compartiment auquel appartient l'élément. Après cela, s'il y a plusieurs éléments dans le compartiment, des vérifications supplémentaires sont effectuées pour comparer ces éléments entre eux. Cela peut être fait en comparant directement les éléments, en les refaisant à nouveau ou en utilisant d'autres techniques.

Votre classe a deux membres de données, et apparemment vous vous attendez à "trouver" un élément par ces membres exacts (c'est-à-dire que vous attendez que A.x == B.x && A.y == B.y, puis A == B et vice versa). Cependant, votre fonction de hachage ne se base que sur les id éléments, en ignorant leurs autres membres, c'est pourquoi cela ne fonctionne pas comme prévu.

La solution serait de réécrire votre fonction de hachage pour utiliser la valeur des champs. Vous pouvez également vérifier la page de documentation this.