opérateur Surcharge() pour une nouvelle struct

Question

I a défini une nouvelle struct dans c:

typedef struct TypedObject { 
    ObjectType type; 
    void * value; 
} TypedObject; 

où TypeObjet est un ENUM:

typedef enum ObjectType { 
    type_node, 
    type_int, 
    type_error, 
} ObjectType; 

Je voudrais créer un C++ ensemble de TypedObject pointeurs et à partir des questions précédentes j'ai compris que je dois surcharger operator() afin de comparer TypedObject pointeurs insérés dans l'ensemble.

donc je l'ai fait comme suit:

#ifdef __cplusplus 
typedef struct { 
    bool operator() (const TypedObject *lhs, const TypedObject *rhs){ 
     return (lhs->type==rhs->type) && (lhs->value==rhs->value); 
    } 
} ObjComparator; 
#endif 

On suppose que je définir un ensemble:

std::set<TypedObject *, ObjComparator> mySet; 

Vous pouvez supposer que j'utilise un itérateur pour itérer si l'ensemble. Je veux insérer TypedObject x dans l'ensemble. J'utilise mySet.insert(&x) pour insérer son adresse .. mais une fois que j'utilise mySet.find(&x), il ne parvient pas à trouver x. L'appel à operator() est effectué mais la comparaison n'est pas faite comme prévu.

Une idée de ce que le problème pourrait être avec la façon dont j'ai surchargé operator()? Qu'est-ce que je fais mal? En outre, devrais-je surcharger une version différente de l'opérateur comme < ou ==?

Answer 1

La classe Comparator vous fournissez doivent mettre en œuvre une comparaison d'ordre , de sorte que std::set pourrait l'utiliser pour construire un arbre de recherche binaire.

Cela signifie que votre operator() ne doit pas être symétrique - par défaut, il s'agit d'une comparaison "inférieure à".

En général, operator() de Comparator classe devrait représenter une stricte relation d'ordre pour votre classe, il devrait donc être

• transitive - C(a,b) && C(b,c) signifie C(a,c)
• antisymétrique - C(a,b) signifie !C(b,a)
• totale - !C(a,b) && !C(b,a) signifie "a et b sont égaux"

La dernière définition de «égalité» est ce que std::set utilise lorsque vous appelez set::find.

Solution: Alors que vous pouvez sûrement trouver un ordre qui satisfera les règles ci-dessus, peut-être vous pouvez faire avec un refactoring à la place.

Si vos TypedObject ont une "identité d'adresse" (c.-à-d.tout objet est seulement égal à lui-même), alors vous pouvez simplement utiliser la comparaison par défaut - il fonctionne parfaitement pour les pointeurs:

std::set<TypedObject *> mySet; 

Si vous avez besoin de comparer les membres après tout, l'approche habituelle serait quelque chose comme ceci:

bool operator() (const TypedObject *lhs, const TypedObject *rhs) 
{ 
    if(lhs->value < rhs->value) return true; 
    if(rhs->value < lhs->value) return false; 
    return (lhs->type < rhs->type) 
} 

Remarquez comment il ne retombe sur operator< pour les membres. En fait, il serait probablement préférable de définir operator< pour comparer TypedObject s, puis l'appeler à partir du pointeur Comparator.

Enfin, si votre set possède les objets (à savoir les objets sont détruits à la sortie du jeu) alors peut-être il vaut mieux simplement utiliser

std::set<TypedObject> mySet; 

avec le operator< surchargé pour TypedObject. Vous pourrez toujours obtenir des pointeurs vers des objets de l'ensemble et les utiliser dans vos API C, et vous n'aurez pas besoin de gérer la classe de comparateur supplémentaire et la gestion de la mémoire.

Answer 2

Votre comparaison de commande est erronée fondée sur l'égalité, il ne sera pas en mesure de créer BST le code si correct devrait être comme ci-dessous (note < dans comparateur)

typedef enum ObjectType { 
    type_node, 
    type_int, 
    type_error, 
} ObjectType; 

typedef struct { 
    ObjectType type; 
    void * value; 
} TypedObject; 



typedef struct { 
    bool operator() (const TypedObject *lhs, const TypedObject *rhs){ 
     return (lhs->type==rhs->type) && (lhs->value<rhs->value); 
    } 
} ObjComparator; 

int main() 
{ 
    std::set<TypedObject *, ObjComparator> mySet; 
    TypedObject obj; 
    obj.type=type_int; 
    obj.value=(void*)new int; 
    //*(obj.value)=4; 
    auto insert = mySet.insert(&obj); 
    std::cout<<insert.second<<std::endl; 
    if(mySet.find(&obj) == mySet.end()) 
    { 
     std::cout<<"Not Found..."<<std::endl; 
    } 
    else 
    { 
     std::cout<<"Found..."<<std::endl; 
    } 
    return 0; 
}