4

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?

sinkinben
  • 55
  • 3
  • 5
    There is nothing wrong with `insert`, but by using `>=` you break the premise of "strict weak ordering". https://stackoverflow.com/questions/979759/operator-and-strict-weak-ordering/981299#981299 – R2RT Aug 30 '19 at 07:07
  • 1
    https://duckduckgo.com/?q=strict+weak+ordering+c%2B%2B&t=fpas&ia=about – Robert Andrzejuk Aug 30 '19 at 07:24
  • 2
    `val > p.val` not `val >= p.val`. 'Less than' should never return true for two equal elements. – john Aug 30 '19 at 07:45

2 Answers2

5

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.)

L. F.
  • 19,445
  • 8
  • 48
  • 82
5

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).

lubgr
  • 37,368
  • 3
  • 66
  • 117