Finding a C++ object in the set by object comparision instead of using functors

Question

I want to populate a std::set of GraphNode objects and check if another GraphNode with the same value exists in the set. In Java, objects can be compared by overloading equals and compareTo methods, instead of creating some functor object. I implemented operator==(T& t) and expected to find the object in the set like this,

std::find(nodesSet->begin(),nodesSet->end(), new GraphNode<T>(1))!=nodesSet->end())

But I am not getting the break point in neither == nor ()() operator functions. Why is it so? Is there a way to find the object by object comparison?

template<class T>
class GraphNode
{
    friend class Graph<T>;
    friend bool operator==(GraphNode<T>& node1, GraphNode<T>& node2);

    private:
        T t;
        std::vector<GraphNode<T>*> adjNodes;

    public:
        bool operator==(T& t);
};

template<class T>
inline bool GraphNode<T>::operator==(T & t)
{
    return this->t == t ? true : false;
}

template<class T>
inline bool operator==(GraphNode<T>& node1, GraphNode<T>& node2)
{
    return node1.t == node2.t ? true : false;
}

void populate()
{
     std::set<GraphNode<T>*>* nodesSet = new set<GraphNode<T>*>;
     nodeSet->insert(new GraphNode<T>(1));
     nodeSet->insert(new GraphNode<T>(2));
     if ( std::find( nodesSet->begin(),nodesSet->end(),
                     new GraphNode<T>(1) ) != nodesSet->end() )
     {
         cout<<"found value";
     }
}

Answer 1

As aschepler pointed out, the problem with your code is that you end up comparing pointers, not objects. std::find (look at the possible implementations in the linked page), if called without a predicate, uses the == operator to compare what is returned when the iterators you give it are dereferenced. In your case, you have a std::set<GraphNode<T>*> nodesSet, so the type of *nodesSet.begin() is GraphNode<T>*, not GraphNode<T> (note the lack of star). In order for you to be able to use the == operator defined for your GraphNode, you need to have your set be std::set<GraphNode<T>>, that is of objects of your type rather than of pointers.

If you have to store pointers in your set (e.g. because you don't want to copy the objects), you can write a wrapper for pointers that uses the comparison operator for the underlying class of the pointers. Here's an example:

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

class obj {
  int i;
public:
  obj(int i): i(i) { }
  bool operator<(const obj& o) const { return i < o.i; }
  bool operator==(const obj& o) const { return i == o.i; }
  int get() const { return i; }
};

template <typename T>
class ptr_cmp {
  T* p;
public:
  ptr_cmp(T* p): p(p) { }
  template <typename U>
  bool operator<(const ptr_cmp<U>& o) const { return *o.p < *p; }
  template <typename U>
  bool operator==(const ptr_cmp<U>& o) const { return *o.p == *p; }
  T& operator*() const { return *p; }
  T* operator->() const { return p; }
};

int main(int argc, char* argv[])
{
  obj five(5), seven(7);

  std::set<ptr_cmp<obj>> s;
  s.insert(&five);
  s.insert(&seven);

  obj x(7);

  std::cout << (*std::find(s.begin(),s.end(), ptr_cmp<obj>(&x)))->get()
            << std::endl;

  return 0;
}

It turned out that my compiler (gcc 6.2.0) required both operator== and operator< for std::find to work without a predicate.

What is wrong with using a predicate though? It is a more generalizable approach. Here's an example:

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

class obj {
  int i;
public:
  obj(int i): i(i) { }
  bool operator==(const obj& o) const { return i == o.i; }
  int get() const { return i; }
};

template <typename T>
struct ptr_cmp {
  const T *l;
  ptr_cmp(const T* p): l(p) { }
  template <typename R>
  bool operator()(const R* r) { return *l == *r; }
};
template <typename T>
ptr_cmp<T> make_ptr_cmp(const T* p) { return ptr_cmp<T>(p); }

int main(int argc, char* argv[])
{
  obj five(5), seven(7);

  std::set<obj*> s;
  s.insert(&five);
  s.insert(&seven);

  obj x(7);

  std::cout << (*std::find_if(s.begin(),s.end(), make_ptr_cmp(&x)))->get()
            << std::endl;

  return 0;
}

Note, that make_ptr_cmp allows you to avoid explicitly stating the type, so you can write generic code.

If you can use C++11, use can just use a lambda function instead of ptr_cmp,

std::find_if(s.begin(),s.end(), [&x](const obj* p){ return *p == x; } )

Answer 2

As others have stated, you are comparing pointers, which won't work as expected, it's doing comparisons on addresses in memory. The operation a < b has a valid meaning for a pointer but will order the elements by their location in memory, not on their contained data elements and also no elements will be unique, as they will all have unique addresses. That is unless you try to insert the same element twice.

The above issue however will be hidden by using std::find, which iterates over all the elements in the container anyway. If you are using a set, you should be aspiring to get logarithmic time look ups for elements, so should use sets own find function, which knows that its a binary tree under the hood.

In C++, the equivalent of Object#equals is operator== (as you knew) and in the context of associative containers the equivalent of Object#compareTo is operator<. Object#equals and operator== work in the same way, exactly as you expect; If somethings equal its equal, simple to understand. Object#compareTo and operator< are used by algorithms in different ways, operator< is used to implement strict weak ordering to determine if one element is less than or greater than another.

So to allow your elements to be usable in a set you will need an overridden operator< in your GraphNode class. Once you have this you can use the std::set::find function to find elements in your set and it will find them in O(log n) time rather than linear time.

These algorithms are designed on the assumption they are working on value types, i.e not pointers but those things that are pointed to. So to use pointers you need to define a new comparison function that basically dereferences the pointers before applying the comparison (either == or <).

Some example code

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

template<typename>
class Graph
{
};

template<class T>
class GraphNode
{
    friend class Graph<T>;
    friend bool operator==(const GraphNode<T>& a, const GraphNode<T>& b);

    private:
        T t;
        std::vector<GraphNode<T>*> adjNodes;

    public:
        explicit GraphNode(const T& tval)
            :t(tval)
        {}
        T& getT(){ return t; }
        const T& getT() const { return t; }
        bool operator==(const T& t);

        friend bool operator<(const GraphNode& a, const GraphNode& b){
            return a.t < b.t;
        }
};

template<class T>
inline bool GraphNode<T>::operator==(const T& t)
{
    return (this->t == t);
}

template<class T>
inline bool operator==(const GraphNode<T>& a, const GraphNode<T>& b)
{
    return (a.t == b.t);
}

int main()
{
    using IntGraphNode = GraphNode<int>;

    std::set<IntGraphNode> nodesSet;

    nodesSet.insert(IntGraphNode(1));
    nodesSet.insert(IntGraphNode(2));

    auto findit = nodesSet.find(IntGraphNode(1));

    if(findit != nodesSet.end())
    {
        std::cout << "found value\n";
    }

    auto findit2 = std::find_if(
                        nodesSet.begin(),
                        nodesSet.end(),
                        [](IntGraphNode i) { return i.getT() == 1;});

    if(findit2 != nodesSet.end())
    {
        std::cout << "found value aswell\n";
    }
}

The first search uses sets own find function and the second uses std::find_if, which takes a predicate (function that returns either true or false) to test equality. The second example also removes the need to make a dummy object, by exposing the T object and using that in the comparison lambda function.

Also a comment about

std::find(nodesSet->begin(),nodesSet->end(), new GraphNode<T>(1))!=nodesSet->end())

There are quite a few conceptual misunderstandings in this line. Firstly std::find does not take a comparison function, that would be std::find_if, but the compiler will tell you that (in its own especially indirect and verbose way). Also the comparison function is evaluated in the algorithm, you are trying to evaluate it at the call site. The other thing is unlike java, you can't just fire off newed objects into oblivion. That's a memory leak, you no longer have any variable storing the newed value, so you can't delete it.

Answer 3

std::find compares the values pointed at by the iterators. These values are pointers, not objects. So none of them will be equal to new GraphNode<T>(1), which is a brand new pointer to a brand new object.