std :: set avec le type défini par l’utilisateur, comment garantir l’absence de doublons

J’ai donc un std :: set qui doit conserver un ordre spécifique et ne pas autoriser les doublons d’un type défini par l’utilisateur. Maintenant, je peux faire en sorte que l’ordre fonctionne correctement en surchargeant l’opérateur ‘<' dans mon type. Cependant, l'ensemble ne détecte pas correctement les doublons et, pour être honnête, je ne suis pas tout à fait sûr de la manière dont cela se fait en interne. J'ai surchargé l'opérateur '==', mais je ne suis pas sûr que ce soit ce que le jeu utilise réellement? La question est donc de savoir comment l’ensemble détermine les doublons lorsque vous ajoutez des valeurs. Voici le code correspondant:

Le type défini par l’utilisateur:

//! An element used in the route calculation. struct RouteElem { int shortestToHere; // Shortest distance from the start. int heuristic; // The heuristic estimate to the goal. Coordinate position; bool operator<( const RouteElem& other ) const { return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere); } bool operator==( const RouteElem& other ) const { return (position.x == other.position.x && position.y == other.position.y); } }; 

Les éléments sont donc équivalents lorsque leur position est équivalente, et un élément est inférieur à un autre si sa fonctionnalité combinée est inférieure à celle de l’autre. Le sorting fonctionne, mais l’ensemble acceptera deux éléments de la même position.

    operator== n’est pas utilisé par std::set . Les éléments a et b sont considérés égaux iff !(a < b) && !(b < a)

    std::set prend std::set charge la spécification d’une fonction de comparaison. La valeur par défaut est less ce qui utilisera operator < pour vérifier l'égalité. Vous pouvez définir une fonction personnalisée pour vérifier l'égalité et utiliser celle-ci à la place:

     std::set myset; 

    Notez qu'il n'est pas possible de séparer la fonction de comparaison de la fonction de sorting. std::set est un arbre binary et si un élément dans un arbre binary n'est ni plus grand ni plus petit qu'un élément spécifique, il devrait être au même endroit. Il fait quelque chose comme ça dans l'algorithme de recherche de lieu:

     if (a < b) { // check the left subtree } else if (b < a) { // check the right subtree } else { // the element should be placed here. } 

    Le comparateur de rlbond n’empêche pas l’insertion d’éléments comparables. Apparemment, il est difficile de le prouver dans les commentaires, étant donné la limite de caractères, car rlbond semble penser que std :: set garantit qu’il ne contiendra jamais deux éléments avec !compare(a,b) && !compare(b,a) pour son comparateur. Cependant, le comparateur de rlbond ne définit pas un ordre ssortingct et n’est donc pas un paramètre valide pour std :: set.

     #include  #include  #include  #include  struct BrokenOrder { int order; int equality; public: BrokenOrder(int o, int e) : order(o), equality(e) {} bool operator<(const BrokenOrder &rhs) const { return order < rhs.order; } bool operator==(const BrokenOrder &rhs) const { return equality == rhs.equality; } }; std::ostream &operator<<(std::ostream &stream, const BrokenOrder &b) { return stream << b.equality; } // rlbond's magic comparator struct LessThan : public std::binary_function { bool operator()(const BrokenOrder& lhs, const BrokenOrder& rhs) const { return !(lhs == rhs) && (lhs < rhs); } }; int main() { std::set s; for (int i = 0; i < 5; ++i) { s.insert(BrokenOrder(i,i)); } for (int i = 0; i < 5; ++i) { s.insert(BrokenOrder(10-i,i)); } std::copy(s.begin(), s.end(), std::ostream_iterator(std::cout, "\n")); } 

    Sortie:

     0 1 2 3 4 3 2 1 0 

    Doublons. Le comparateur de magie a échoué. Différents éléments de l’ensemble ont la même valeur d’ equality et comparent donc la même chose avec l’ operator== , car pendant l’insertion, l’ensemble n’a jamais comparé le nouvel élément avec son duplicata. Le seul duplicata qui a été exclu était 4, car les deux 4 avaient des ordres de sorting 4 et 6. Cela les rapprochait suffisamment dans le jeu pour les comparer.

    A partir du standard C ++: 25.3: 3 “Pour que les algorithmes fonctionnent correctement, comp doit induire un ssortingct ordre faible sur les valeurs”.

    25.3: 4 “… les exigences sont que comp et equiv soient des relations transitives:

     comp(a,b) && comp(b,c) implies comp(a,c)" 

    Considérons maintenant les éléments a = BrokenOrder(1,1) , b = BrokenOrder(2,2) et c = BrokenOrder(9,1) , et comp bien sûr égal au comparateur magique. Alors:

    • comp(a,b) est vrai puisque 1! = 2 (égalité) et 1 <2 (ordre)
    • comp(b,c) est vrai puisque 2! = 1 (égalité) et 2 <9 (ordre)
    • comp(a,c) est faux puisque 1 == 1 (égalité)

    L’implémentation d’ensemble STL fait quelque chose de conceptuellement comme ceci pour détecter l’égalité:

     bool equal = !(a < b) && !(b < a); 

    Autrement dit, si deux éléments ne sont pas moins que l’autre, ils doivent être égaux. Vous pourrez peut-être vérifier cela en définissant un point d'arrêt sur votre méthode operator==() et en vérifiant s'il est appelé.

    Je me méfierais généralement des opérateurs de comparaison qui vérifient des choses complètement différentes. Votre opérateur < est défini par deux éléments distincts de la définition de votre opérateur == . En règle générale, vous souhaitez que ces comparaisons utilisent des informations cohérentes.

    Vous pourriez essayer quelque chose comme ceci:

     //! An element used in the route calculation. struct RouteElem { int shortestToHere; // Shortest distance from the start. int heuristic; // The heuristic estimate to the goal. Coordinate position; bool operator<( const RouteElem& other ) const { return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere); } bool operator==( const RouteElem& other ) const { return (position.x == other.position.x && position.y == other.position.y); } }; struct CompareByPosition { bool operator()(const RouteElem &lhs, const RouteElem &rhs) { if (lhs.position.x != rhs.position.x) return lhs.position.x < rhs.position.x; return lhs.position.y < rhs.position.y; } }; // first, use std::set to remove duplicates std::set routeset; // ... add each RouteElem to the set ... // now copy the RouteElems into a vector std::vector routevec(routeset.begin(), routeset.end()); // now sort via operator< std::sort(routevec.begin(), routevec.end()); 

    Évidemment, il y a la copie au milieu, qui semble lente. Mais toute structure qui indexe des articles selon deux critères différents va donc avoir une sorte de surcoût par article par rapport à un ensemble. La totalité du code ci-dessus est O (n log n), en supposant que votre implémentation de std :: sort utilise introsort.

    Si vous le possédez, sous ce schéma, vous pouvez utiliser unordered_set au lieu de set pour effectuer l’originalisation initiale. Comme le hachage ne devrait dépendre que de x et y, il devrait être plus rapide que les comparaisons O (log N) requirejses pour être insérées dans un ensemble.

    Edit: juste remarqué que vous avez dit que vous vouliez "garder" l'ordre de sorting, pas que vous vouliez tout traiter dans un lot. Désolé pour ça. Si vous souhaitez maintenir efficacement l'ordre et exclure les doublons lors de l'ajout d'éléments, je vous recommande d'utiliser le jeu défini ou non défini ci-dessus en fonction de la position, ainsi qu'un std::multiset qui maintiendra l' operator< order . Pour chaque nouvel élément, faites:

     if (routeset.insert(elem).second) { routemultiset.insert(elem); } 

    Bien méfiez-vous que cela n'offre aucune garantie d'exception. Si le deuxième insert lance, alors le chemin a été modifié, donc l'état n'est plus cohérent. Donc je suppose que vous avez vraiment besoin de:

     if (routeset.insert(elem).second) { try { routemultiset.insert(elem); // I assume strong exception guarantee } catch(...) { routeset.erase(elem); // I assume nothrow. Maybe should check those. throw; } } 

    Ou un équivalent avec RAII, qui sera plus verbeux s'il n'y a qu'une seule place dans votre code que vous utilisez la classe RAII, mais mieux s'il y a beaucoup de répétitions.

    Attention aux ramifications de ceci. On dirait que vous essayez de faire quelque chose comme A *, et si vous essayez d’insérer un “doublon”, il sera ignoré, même s’il ya une “meilleure” route.

    REMARQUE: cette solution ne fonctionne pas, voir ci-dessous l’explication de onebyone

     struct RouteElem { int shortestToHere; // Shortest distance from the start. int heuristic; // The heuristic estimate to the goal. Coordinate position; bool operator<( const RouteElem& other ) const { return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere); } bool operator==( const RouteElem& other ) const { return (position.x == other.position.x && position.y == other.position.y); } }; struct RouteElemLessThan : public std::binary_function { bool operator()(const RouteElem& lhs, const RouteElem& rhs) const { return !(lhs == rhs) && (lhs < rhs); } }; std::set my_set;