CODEWITHSUNDEEP
c++templatesoperator-overloadingbinary-search-tree
user2105982
user2105982

Reputation: 187

Operator Overloading with a Binary Search Tree

I believe that my operator overloading is not working for one of my two datatypes. MY program works with an int datatype but not with my defined class students. students is a tree of pointers so this might be my problem. I discovered this problem when my search function wasn't functioning as planned. I'm hoping to get some advice as to what I am doing wrong with my overloaded operators.

struct Students{

char lastName[20];
char firstName[20];
int IDnumber;
Students();
bool operator == (const Students);
bool operator > (const Students);
bool operator < (const Students);

friend ostream& operator << (ostream& stream, const Students* students);

};

template <class DataType>
TNode<DataType>* BST<DataType>::bstSearch(DataType search)
{
 TNode<DataType>* y = root;

  while (y!=NULL && search != y->data)
   {
      if (search < y->data)
    {
      y = y->left;
    }
      else
    {
      y = y->right;
      }
   }

  return y;
}

here is my overloader code

friend bool operator == (const Students& lh, const Students& rh);
friend bool operator > (const Students& lh, const Students& rh);
friend bool operator < (const Students& lh, const Students& rh);

bool operator ==(const Students& lh, const Students& rh)
{
    return lh.IDnumber == rh.IDnumber;
}

bool operator > (const Students& lh, const Students& rh)
{
    return lh.IDnumber > rh.IDnumber;
}

bool operator < (const Students& lh, const Students& rh)
{
    return lh.IDnumber < rh.IDnumber;
}

this is the tree objects I create

   BST<Students*> stree;              
   BST<int> itree;

Upvotes: 0

Views: 3596

Answers (2)

Nemanja Boric
Nemanja Boric

Reputation: 22157

If you use Students* for data-type, then this:

if (search < y->data)

is comparing pointers and not actual objects. Pass object of Student by value to BST:

BST<Students> stree;

Also, don't pass object by value to the operators and your search function:

bool Students::operator< (const Students& ob)
TNode<DataType>* BST<DataType>::bstSearch(const DataType& search)

Next thing you should note is that you don't need to implement all compare operators individually, it is sufficient to implement only operator<. For example:

bool operator==(const some_class& b){ return !(*this < b) && !(b < *this); }
bool operator>(const some_class& b){ return !(*this == b) && !(*this < b); } 
// and so on...

On the other hand, you could use templates, std::enable_if and std::is_pointer to dereference you pointer automatically:

#include <utility>
#include <iostream>

template<typename T>
T& dereference(T &v){return v;}

template<typename T>
const T& dereference(const T& v){return v;}

template<typename T>
typename std::enable_if<!std::is_pointer<T>::value, T&>::type dereference(T* v){return dereference(*v);}

// example usage:
template <typename T>
class A
{
public:
         bool compare(T a, T b){
                return dereference(a) < dereference(b);
        }


};

int main()
{

        int u = 10;
        int *v = &u;

        int i = 5;
        int *j = &i;


        A<int> a;
        A<int*> b;

        std::cout << a.compare(i, u) << std::endl;
        std::cout << b.compare(j, v) << std::endl;

        return 0;

}

So, just add dereference templates, and in your search function you can use it as:

template <class DataType>
TNode<DataType>* BST<DataType>::bstSearch(DataType search)
{
 TNode<DataType>* y = root;

  while (y!=NULL && dereference(search) != dereference(y->data))
   {
      if (dereference(search) < dereference(y->data))
    {
      y = y->left;
    }
      else
    {
      y = y->right;
      }
   }

  return y;
}

For more on dereference method, see excelent answers to my question here: Recursively dereference pointer

Upvotes: 2

Prashant Kumar
Prashant Kumar

Reputation: 22559

If you want to keep it a tree of pointers, you want to compare like this:

if (*search < *(y->data)) {

The way I see it, int is a non-pointer type, and Students* is of a pointer type.
If you use Students instead of Students* in your tree, it should work.
Alternatively, you can make a different implementation to handle pointer trees.

Upvotes: 0

Related Questions