Set of pointers to object with custom comparator-CodePudding

I want to overload the left-hand operator (<) for class Node. Note that, the elements won't be the class objects it will be a pointer to them. Please see the set<Node*> defined in the main class.

The one I have written right now doesn't work. I have also tried the friend function, declaring overloading outside the class as a non member function, but it doesn't work either. Doesn't work mean elements are randomly ordered in the set, and the comparator is not called. Whereas, it should be ordered as per the defination of my comparator.

#include <iostream>
#include <set>
using namespace std;

class Node {
public:
    int x, y;
    Node *prev, *next;

    Node(int x, int y) {
        this->x = x; this->y = y;
        this->prev = this->next = nullptr;
    }

    bool operator<(const Node& node) const {
        return this->x < node.x;
    }
};

int main() {
    set<Node*> S;

    S.insert(new Node(2, 4));
    S.insert(new Node(3, 2));
    S.insert(new Node(1, 4));
    S.insert(new Node(5, 1));
    S.insert(new Node(4, 3));

    for (auto itr : S)
        cout << itr-> x << endl;

    return 0;
}

CodePudding user response：

The problem is, that per default the std::set uses std::less for comparison. Please read here.

And std::less is able to compare Node*. Your comparison function will never be called. Instead. Everything will be sorted according to a (for your random) pointer value. This is the value, that is returned by new.

What you need is a Functor that compares your values in the following form:

    bool operator ()(const Node* n1, const Node* n2) const {
        return (n1->x == n2->x) ? n1->y < n2->y : n1->x < n2->x;
    }

You can use a separate Functor, a Lambda, a free function, or, you can add this function to your Node and, with that, make it a Functor. Then you add this as the 2nd parameter to the std::setdefinition.

So, you have really several ways. Let me use the last option as an example.

Please see:

#include <iostream>
#include <set>
using namespace std;

class Node {
public:
    int x{}, y{};
    Node* prev{}, * next{};

    Node() {};
    Node(int x, int y) {
        this->x = x; this->y = y;
        this->prev = this->next = nullptr;
    }
    
    bool operator ()(const Node* n1, const Node* n2) const {
        return (n1->x == n2->x) ? n1->y < n2->y : n1->x < n2->x;
    }
};

int main() {
    set<Node*, Node> S;

    S.insert(new Node(2, 4));
    S.insert(new Node(3, 2));
    S.insert(new Node(1, 4));
    S.insert(new Node(5, 1));
    S.insert(new Node(4, 3));

    for (auto itr : S)
        cout << itr->x << endl;

    return 0;
}