CODEWITHSUNDEEP
c++structcompareoverloadingoperator-keyword
baronzo1
baronzo1

Reputation: 23

Overloading operator() for a new struct

I defined a new struct in c:

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

where ObjectType is an enum:

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

I would like to create a c++ set of TypedObject pointers and from previous questions I understood that I need to overload operator() in order to compare between TypedObject pointers inserted into the set.

Therefore I did it as follows:

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

Assume I define a set:

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

You can assume that I use an iterator to iterate though the set.

I want to insert TypedObject x into the set. I use mySet.insert(&x) to insert its address.. but once I use mySet.find(&x), it fails to find x. The call to operator() is made but the comparison is not made as expected.

Any idea what the problem might be with the way I overloaded operator()? what am I doing wrong? Also, Should I overload a different version of operator like < or ==?

Upvotes: 0

Views: 103

Answers (2)

Ap31
Ap31

Reputation: 3314

The Comparator class you provide should implement an order comparison, so that std::set could use it to build a binary search tree.

That means that your operator() should not be symmetrical - by default it is a "less than" comparison.

In general, operator() of Comparator class should represent a strict order relation for your class, so it should be

  • transitive - C(a,b) && C(b,c) means C(a,c)
  • antisymmetrical - C(a,b) means !C(b,a)
  • total - !C(a,b) && !C(b,a) means "a and b are equal"

The last definition of "equality" is what std::set uses when you call set::find.

Solution: While you surely can come up with some ordering that will satisfy the rules above, perhaps you can do with some refactoring instead.

If your TypedObjects have "address identity" (i.e. any object is only equal to itself), then you can just use the default comparison - it works perfectly for pointers: 

std::set<TypedObject *> mySet;

If you need to compare the members after all, the usual approach would be something like this: 

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

Notice how it only falls back on operator< for members. In fact, it would probably be better to define operator< to compare TypedObjects, and then call it from the pointer Comparator.

Finally, if your set owns the objects (i.e. objects are destroyed upon leaving the set) then perhaps it's better to just use 

std::set<TypedObject> mySet;

with the operator< overloaded for TypedObject. You will still be able to get pointers to objects from the set and use them in your C APIs, and you won't need to deal with extra comparator class and memory management.

Upvotes: 1

PapaDiHatti
PapaDiHatti

Reputation: 1921

Your order comparison is wrong as based on equality it will not be able to create BST so correct code should be like below (note < in comparator)

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

Upvotes: 0

Related Questions