std :: map ne supprime pas les doublons avec l'objet personnalisé

Question

tous. J'ai donc créé une classe de base comparable (a la Java) qui fait le travail de surcharger les opérateurs de comparaison en C++. Le voici:

template <class T> 
class Comparable { 
public: 
    bool operator== (const T& rhs) const { return this->compare(rhs) == 0; } 
    bool operator!= (const T& rhs) const { return !(*this == rhs); } 
    bool operator< (const T& rhs) const { return this->compare(rhs) < 0; } 
    bool operator<= (const T& rhs) const { return (*this == rhs) || (*this < rhs); } 
    bool operator> (const T& rhs) const { return this->compare(rhs) > 0; } 
    bool operator>= (const T& rhs) const { return (*this == rhs) || (*this > rhs); } 
protected: 
    virtual int compare (const T& rhs) const = 0; 
}; 

Les objets de la sous-classe ont à la fois un ID et des données qui doivent être une clé pour le tri. J'ai implémenté chacun pour que les objets avec le même ID retournent 0, et s'ils ne sont pas le même ID, ils trient en fonction de leurs données. Voici un exemple:

int Foo::compare(const Foo& rhs) const 
{ 
    if (_id == rhs._id) 
     return 0; 
    // _value is integer data; comparison should sort on this 
    if (_value == rhs._value) 
    { 
     // OK, same data, now sort on ID's 
     return _id.compare(rhs._id); 
    } 
    // Sort on value 
    return _value - rhs._value; 
} 

Jusqu'ici, tout va bien, je pense.

Cependant, lorsque je tente de stocker des objets Foo dans un conteneur std :: set, l'ensemble n'éliminera PAS les doublons. Autrement dit, il y aura toujours des objets qui contiennent le même ID, même si cela doit être considéré comme égal.

Quelqu'un a-t-il une idée de ce qui se passe?

EDIT: Il y a beaucoup de questions sur la raison pour laquelle le code est conçu de cette façon.

Il y a deux conditions que je dois satisfaire:

1. objets avec le même ID doit être l'objet « même », quelle que soit la valeur.
2. Les objets qui n'ont pas le même ID doivent être triés en fonction de leur valeur (cette valeur dépend du type de l'objet).

Cela est dû au fait que les données qui créent ces objets proviennent d'une source non vérifiée. Si cette source donne des données avec le même ID mais une valeur différente, c'est une donnée invalide.

EDIT 2: En ce qui concerne la commande stricte faible pour std :: map. Disons que vous avez deux objets Foo, A et B.

Si leurs ID sont égaux, alors A < B est faux, et B < A est faux. Si leur carte d'identité de ne sont pas égaux, alors A < B est vrai ou faux en fonction de leurs valeurs, et B < A est à l'opposé de A < B.

Si cela ne satisfait pas aux règles de classement strictes?

Dans tous les cas, si std :: set utilise l'opérateur less-than (comme c'est le cas par défaut), ne devrait-il pas fonctionner comme prévu?

EDIT 3: std::set, et non std::map. C'était vraiment stupide de ma part. Excuses.

Answer 1

std::map ne détermine pas les doublons via operator==. Il utilise operator< , puisqu'il doit quand même l'utiliser pour déterminer l'ordre. Votre operator< est cassé. Il doit appliquer un strict weak ordering.

La façon dont votre comparaison échoue est dans la propriété suivante (appelée transitivité). Pour 3 objets, si A < B et B < C, alors il doit être le cas que A < C.Par conséquent, considérons trois objets, A, B et C. A.id != B.id, mais A.value < B.value, donc A < B. Maintenant, C.id == B.id (donc C.id != A.id), mais C.value < A.value. Donc C < A, et A < B. Par conséquent, C doit être < B. Mais ce n'est pas, parce que C.id == B.id.

Une façon de le faire serait de définir votre fonction compare comme ceci:

int Foo::compare(const Foo& rhs) const 
{ 
    if (_id < rhs._id) 
     return -1; 
    if (rhs._id < _id) 
     return 1; 

    return _value - rhs._value; 
} 

Si vous ne pouvez pas l'utiliser, et vous ne pouvez pas trouver un autre moyen de faire respecter un ordre approprié, alors vous ne pouvez pas utiliser vos objets en tant que clés dans un std::map.

_{1. Si rhs n'est pas inférieur à lhs, et lhs n'est pas inférieur à rhs, alors il est implicite qu'ils sont égaux. Vous pouvez également fournir un autre foncteur à condition qu'il applique également un ordre faible strict.}

Answer 2

Si vous n'avez pas un ordre strict faible, vous ne pouvez pas utiliser map, et vous ne pouvez pas vous plaindre si vous le faites et cela ne fonctionne pas. C'est une condition préalable de map.

ÉDITÉ:

Votre compare n'implémente pas la sémantique que vous spécifiez - vous devez retourner 0 si _value == rhs._value dans votre deuxième test.

Mais avec ce correctif, vous n'avez toujours pas un ordre cohérent - voir l'exemple donné par Benjamin Lindley dans les commentaires. Essentiellement, votre commande n'a pas de sens - vous devez soit corriger votre sémantique, soit arrêter d'utiliser des composants de bibliothèque standard qui nécessitent une commande cohérente.