std::set use of operator<

Question

This question is kinda related to my other question here: link (see the discussion in comments). Basically, I had the following problem:

I have a class node. Which has some fields, the most important: G, H and pos (pos is a Qt's QPoint, but I've rewritten it for the sake of example to my own class Point. See the example below:

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

class Point
{
public:
    int _x, _y;
    Point() : _x(0), _y(0) {}
    Point(int x, int y) : _x(x), _y(y) {}
    bool operator==(const Point& p) const { return _x == p._x && _y == p._y; }
    bool operator!=(const Point& p) const { return _x != p._x && _y != p._y; }
};

class node
{
public:
    node() {}
    node(const Point& p) : pos(p) {}
    bool operator==(const node& o) const { return pos == o.pos; }
    bool operator==(const Point& o) const { return pos == o; }
    bool operator!=(const node& o) const { return pos != o.pos; }
    bool operator<(const node& o) const { return G + H < o.G + o.H; }
    Point pos;
    std::shared_ptr<node> parent;
    int G = 0;
    int H = 0;
};

int main()
{
    node n1(Point(6, 7));
    n1.G = 1;
    n1.H = 1;
    node n2(Point(1, 1));
    n2.G = 2;
    n2.H = 2;
    node n3(Point(2, 2));
    n3.G = 1;
    n3.H = 1;
    std::set<node> nodes;
    nodes.insert(n1);
    nodes.insert(n2);
    nodes.insert(n3);
    auto min = (*std::min_element(nodes.begin(), nodes.end())).pos;
    std::cout << min._x << " " << min._y << '\n';
    std::cout << nodes.size() << '\n';
}

The output of this program is:

>main.exe
6 7
2

So the search for the lowest element was successful (using the operator<). So that's what I wanted. But as you can see, the three nodes I created have different .pos fields (basically, coordinates). So I would like all of them to be present in a set. In other words, you can say that the "uniqueness" of every node should be determined by .pos field (actually using this field's operator==, which I defined above). And one of the nodes is considered not unique, cuz std::set used operator< for comparing its elements. So n1 and n3 have the same G+H value and they are considered equal (the 2 in the second line of the output is the number of set`s elements -> 2, not 3).

Before I knew about the std::set's use of operator< to compare for equality, I've written operator== and operator!= thinking the set would use one of those to compare objects of my class. But it uses the operator<.

So my question here is why actually it uses this operator. Wouldn't it be easier to use operator== or operator!=?

For me, it kinda complicates the job, because I have to think of another way to write operator< or use a different container (therefore writing lambdas) or I can use .pos comparing in operator< and rewrite std::min_element myself (to take G and H sum in the account, not .pos field)

Answer 1

What you are attempting to achieve violates the Strict Weak Ordering requirement of std::set. Basically, if you have 2 numbers, and neither is less then the other, they must be the same! They can't also be different (when checked using some different syntax).

All of your comparison operators should be defined consistently, so that there is a clear idea of value for your type. Which members of your type are salient, i.e. contribute to the value? There might be other members, but they should never be checked in the comparison operators.

An example is std::vector. If two vectors both contain a, b, c, they are equal. They might have a different amount of storage space left unused (vector.capacity()), but this is not part of the value of either object.

If you have the time, John Lakos has presented about this, and Alexander Stepanov has written about it.