C++ user-defined operator< not working properly

Question

I have a struct Node and I want to define operator< for it in order to use the Node in my Fibonacci Heap.

This is my simple Node:

struct Node {
    int key, data;
    Node* parent;
    Node(int aKey, int aData):key(aKey),data(aData),parent(nullptr) {}

    bool operator<(const Node* n) const {
        return n->key > key;
    }
}

To make sure operator< was working, I tested it out:

Node* n = new Node(100, 0);
Node* m = new Node(1, 1);

cout << (n < m) << endl;
cout << (n > m) << endl;

The answer I got was:

1
0

However, I suspected this was wrong so I modified my Node a bit:

struct Node {
    int key, data;
    Node* parent;
    Node(int aKey, int aData):key(aKey),data(aData),parent(nullptr) {}

    bool operator<(const Node* n) const {
        cout << "comparing.... " << endl;
        return n->key > key;
    }
}

Then I did the same test again, and "comparing.... " never printed out. So for some reason, when I try to compare Nodes, it doesn't use the comparator operator that I have defined. Instead, it appears to me comparing the pointers. How do I fix this? I know that the "alternative" would be to create something like:

struct NodeComp(Node* a, Node* b) {
     ....
}

However, that won't work for my implementation of the Fibonacci Heap, and ultimately I want to insert the Nodes into the Fibonacci Heap.

Thanks.

Answer 1

Normal use of operator< involves passing a const reference parameter, not a pointer:

bool operator<(const Node& n) const {  // Note the & instead of the *
    return n.key > key;
}

You can then compare Node pointers by first dereferencing them:

cout << (*n < *m) << endl;

Regardless, you're not going to get > to work if you've only defined < -- you'll need to also overload operator> if you want to be able to compile expressions like (*n > *m).

Answer 2

If you want to overload operator<() it needs to be made either a member of the class:

bool operator<(Node &n);

It can also be a stand-alone function:

// this function should be made a friend of you class if you need to
// access private class members
bool operator<(Node &left, Node &right);

Note that a reference to the object is passed to your function, not a pointer.

You will need to rewrite your code to:

cout << (*n < *m) << endl;
cout << (*n > *m) << endl;