CODEWITHSUNDEEP
c++templatescomparisonoperator-overloadingavl-tree
Zakini
Zakini

Reputation: 23

Binary operator overloading in C++ with differing data types

I'm working on implementing an AVL tree in C++. To keep things concise (and for practice), I'm trying to overload the comparison operators for the nodes of the tree.

Here's how I'd like the find function of the tree to look:

node* find(int key)
{
    node* currentNode = root;

    while (currentNode)
    {
        if (key < *currentNode)
        {
            currentNode = currentNode.getLeftChild();
        }
        else if (key > *currentNode)
        {
            currentNode = currentNode.getRightChild();
        }
        else
        {
            return currentNode;
        }
    }

    return nullptr;
}

In this instance, I could just overload the operator to compare int to node like so:

bool operator<(const int& lhs, const node& rhs)    // friend of node
{
    return lhs < rhs.key;
}

But this only seems to work with int < node not with node < int. Do I need to define a separate function for node < int?

I'd also like to template this function so that I can compare anything (that itself has comparison operators) to nodes:

template<typename T> bool operator<(const T& lhs, const node& rhs)    // friend of node
{
    return lhs < rhs.key;
}

Again, this works for T < node but not for node < T. Do I need to define a function for node < T as well as the above function?

TL;DR

If I overload an operator as bool operator<(const foo& lhs, const bar& rhs), do I also need to define bool operator<(const bar& lhs, const foo& rhs) so that the operands can be either way around? Is this also the case with template functions like template<typename T> bool operator<(const foo& lhs, const T& rhs)?

Apologies if I've answered my own question here but the only resources I can find on operator overloading only show examples using the same type for both parameters. I'd just like to be sure I'm doing this right, and hopefully this post will come up the next time someone searches for this problem.

Upvotes: 2

Views: 506

Answers (2)

Rahul
Rahul

Reputation: 11

its considered good practice. Many library developers have done it the same way. boost is one such example, If you define both operations separately.

bool operator < (const foo& lhs, const bar& rhs);
bool operator < (const bar& lhs, const foo& rhs);

To be specific to your problem, if you wish to have just one template comparison function, you can do it following way:

template<typename T>
bool less(const T& lhs, const T& rhs)
{
    return lhs < rhs;
}

class node
{
private:
    int nodeValue;

public:
    explicit node(int i):nodeValue(i){}

Below conversion function defined for comparison with int, same can be defined for char or a user defined data type

    operator int()const
    {
        return nodeValue;
    }
};

void test()
{
    node tmp(75);

    std::cout<<"less<int>(tmp, 10):"<<less<int>(tmp, 10)<<std::endl;
    std::cout<<"less<int>(10, tmp):"<<less<int>(10, tmp)<<std::endl;
}

Building onto this, you can use this approach for two different user defined date types provided they have conversion functions defined to some data type which has operator < defined.

Upvotes: 1

NathanOliver
NathanOliver

Reputation: 180710

Lets look at you function and the naming you are using

bool operator<(const int& lhs, const node& rhs)

So the int is called lhs and the node is rhs. Thes names match what side of the operator the types lie. lhs is left hand side and rhs is right hand side. So 

bool operator<(const int& lhs, const node& rhs)

Will only work when you have

int < node

If you want to hadle

node < int

Then you would need another function where the node is the lhs and the int is the rhs

bool operator<(const node& lhs, const int& rhs)

Now you can template this like

template<typename T> bool operator<(const T& lhs, const node& rhs)    // friend of node
{
    return lhs < rhs.key;
}

template<typename T> bool operator<(const node& lhs, const T& rhs)    // friend of node
{
    return lhs.key < rhs;
}

And this will give you operator < for all types that T < node::key is defined where T and node appear on either side of <.

Upvotes: 2

Related Questions