std :: set avec le type défini par l'utilisateur, comment éviter les doublons

Question

Donc j'ai un std::set qui doit rester spécifique de la commande ainsi que de ne pas permettre la présence de doublons de défini par l'utilisateur (par moi) de type. Maintenant, je peux obtenir l'ordre de fonctionner correctement en raison d'une surcharge de l' '<' opérateur dans mon genre. Cependant, l'ensemble n'est pas correctement détecter les doublons, et pour être honnête, je ne suis pas entièrement sûr de savoir comment il le fait à l'interne. J'ai surchargé le '==' opérateur, mais de toute façon je ne suis pas sûr que c'est ce que le jeu est fait à l'aide? Donc, la question est de savoir comment l'ensemble de déterminer 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);
    }
};

Ainsi, les éléments sont équivalents lorsque leur position est équivalent, et d'un élément est inférieure à une autre si son fonctionnement est inférieure à celle de l'autre. Le tri fonctionne, mais l'ensemble va accepter les deux éléments de la même position.

Answer 1

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

std::set<RouteElem, mycomparefunction> myset;

Notez qu'il n'est pas possible de séparer la fonction de comparaison de fonction de tri. std::set est un arbre binaire et si un élément dans un arbre binaire n'est pas plus grand ni plus petit qu'un élément spécifique, il doit être dans le même endroit. Il fait quelque chose comme cela dans la place algorithme de recherche de:

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

Answer 2

rlbond du comparateur de ne pas empêcher l'insertion d'éléments qui permettent de comparer l'égalité. Apparemment, il est difficile de le prouver dans les commentaires, compte tenu de la limite de caractères, parce que rlbond semble pense que std::set garantit qu'il ne sera jamais contenir deux éléments avec !compare(a,b) && !compare(b,a) de son comparateur. Cependant, rlbond du comparateur ne permet pas de définir un ordre strict, et n'est donc pas un paramètre valide pour std::set.

#include <set>
#include <iostream>
#include <iterator>
#include <algorithm>

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<BrokenOrder, BrokenOrder, bool> {
    bool operator()(const BrokenOrder& lhs, const BrokenOrder& rhs) const
    {
        return !(lhs == rhs) && (lhs < rhs);
    }
};

int main() {
    std::set<BrokenOrder,LessThan> 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<BrokenOrder>(std::cout, "\n"));
}

Sortie:

0
1
2
3
4
3
2
1
0

Les doublons. La magie comparateur a échoué. Les différents éléments de l'ensemble ont la même valeur de equality, et donc de comparer la même chose avec operator==, parce que lors de l'insertion, le jeu jamais par rapport à l'élément nouveau contre son double. Le seul double, qui a été exclu était de 4, parce que les deux 4 avait ordres de tri 4 et 6. Ce faisant, ils ont suffisamment rapprochés dans le jeu pour être comparés les uns contre les autres.

À partir de la norme C++: 25.3:3 "Pour les algorithmes de travailler correctement, comp a pour induire une faible stricte de la commande sur les valeurs".

25.3:4 "... les exigences de comp et eq à la fois être transitive des relations:

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

Maintenant, prendre en considération les éléments a = BrokenOrder(1,1), b = BrokenOrder(2,2), et c = BrokenOrder(9,1), et comp évidemment égale à la magie de comparaison. Alors:

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

Answer 3

La STL ensemble de la mise en œuvre fait quelque chose de conceptuellement comme cela pour détecter l'égalité:

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

C'est, si deux éléments sont à la fois pas moins que les autres, alors ils doivent être égaux. Vous pouvez être en mesure de vérifier ce fait en créant un point d'arrêt sur votre operator==() méthode et de vérifier si elle n'est jamais appelée à tous.

Je voudrais généralement se méfier des opérateurs de comparaison que l'enregistrement choses complètement différentes. Votre < opérateur est défini en termes de deux choses qui sont distinctes de la façon dont votre == opérateur est défini. En général, vous voulez de telles comparaisons à l'utilisation de l'information cohérente.

Answer 4

Vous pouvez essayer quelque chose comme ce qui suit:

//! 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<RouteElem,CompareByPosition> routeset;
// ... add each RouteElem to the set ...

// now copy the RouteElems into a vector
std::vector<RouteElem> routevec(routeset.begin(), routeset.end());

// now sort via operator<
std::sort(routevec.begin(), routevec.end());

Évidemment il y a le copier dans le milieu, qui semble ralentir. Mais toute la structure qui les index des articles par deux critères différents va donc avoir une sorte de surcharge par poste par rapport à un ensemble. L'ensemble du code ci-dessus est O(n log n), en supposant que votre implémentation de std::sort utilise introsort.

Si vous l'avez, dans ce schéma, vous pouvez utiliser unordered_set au lieu de set de faire les premiers uniqueifying. Depuis le hachage ne devrait dépend de x et de y, il devrait être plus rapide que l'O(log N) comparaisons nécessaires pour les insérer dans un ensemble.

Edit: viens de remarquer que vous avez dit vouloir "maintenir" l'ordre de tri, pas ce que vous voulais processus tout en un lot. Désolé à ce sujet. Si vous voulez efficacement à maintenir l'ordre et d'exclure les doublons tout en ajoutant des éléments, alors je vous recommande d'utiliser l'ensemble ou non ordonnée ensemble je l'ai défini ci-dessus, basée sur la position, et aussi un std::multiset<RouteElem>, ce qui permettra de maintenir l' operator< commande. Pour chaque nouvel élément, faites:

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

Mais attention, que cela n'offre pas une exception de garantie. Si l'insertion du deuxième lancers, puis le routeset a été modifié, de sorte que l'etat n'est plus cohérente. Donc je suppose que vraiment vous avez 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 détaillé si il n'y a qu'un seul endroit dans votre code, vous n'utiliserez jamais le RAII classe, mais c'est mieux si il y a beaucoup de répétitions.