What are the principles of the 'insert' function of set in C++ STL?

Question

For this piece of code below：

int main()
{
    std::set<Node> s;
    for (int i = 0; i <= 5; i++)
        s.insert(Node(i));
    s.insert(Node(4));
    for (auto itor = s.begin(); itor != s.end(); itor++)
    {
        std::cout << itor->val << ' ';
    }
}

When the sign '<' is overwrote as below, the output is: '5 4 3 2 1 0'

struct Node
{
    int val;
    Node(int _val = -1) : val(_val) {}
    bool operator<(const Node &p) const
    {
        return val > p.val;
    }
};

When I change the function into this:

bool operator<(const Node &p) const
{
    return val >= p.val;
}

The output changes into: '5 4 4 3 2 1 0'. The difference confuses me, could someone explain why this happened and explain the principles of the 'insert' function?

Answer 1

std::set uses operator< on the key type by default, so in the first case, it uses the operator< defined for Node to compare the keys, which in turn uses > to compare the underlying integers, so you see a descending sequence of integers.

std::set expects that the order provided is a strict weak order as a precondition. In the second case, your operator< is not a strict weak order, thus you violate the precondition, triggering undefined behavior. Therefore, the implementation is confused. (Undefined behavior means anything can happen — the program can produce strange results, crash, put your computer on fire, produce nasal demons, etc.)

Answer 2

Custom comparison functions in STL containers must meet the requirements, i.e. they must induce a strict weak ordering relation. The second operator overload with val >= p.val fails to do exactly that, and the behavior is thus undefined.

From cppreference on std::set:

Everywhere the standard library uses the Compare requirements, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects a and b are considered equivalent if neither compares less than the other: !comp(a, b) && !comp(b, a).