Less or less_equal using set

Question

We can pass the function as a < (less) operator into STL data structures such as set , multiset , map , priority_queue , ...

Is there a problem if our function acts like <= (less_equal)?

Answer 1

From Effective STL → Clause 21. Always have comparison functions that return false for equal values.

Create a set where less_equal is the type of comparison, then insert 10 into the set:

 set<int, less_equal<int> > s; // s is sorted by "<=" s.insert(10); //insert the value 10 

Now try pasting 10 again:

 s.insert(10); 

To insert this call, the set must find out if there is 10. We know what it is. but the set is dumb like a toast, so he has to check. To make it easier to understand what will happen when the kit does this, we will call 10 originally inserted 10A and 10, which we are trying to insert 10B. The set goes through its internal data structures, looking for a place to insert 10B. Ultimately, you need to check 10B to make sure it is 10A. Defining “the same” for associative containers is equivalence, so established tests show 10B is equivalent to 10A. When performing this test, he naturally uses a set of comparison function. In this example, this operator is <=, because we specified less_equal as a comparison function, and less_equal as operators. The set thus checks whether this expression is true:

 !(10A<= 10B)&&!(10B<= 10A) //test 10Aand 10B for equivalence 

Well, 10A and 10B are 10, so it’s clear that 10A <10V. It is equally clear that 10B <= 10A. Thus, the above expression simplifies to

 !!(true)&&!(true) 

and it simplifies to

 false && false 

which is simply false. That is, the kit concludes that 10A and 10B are not equivalent, therefore, not the same, and thus we are talking about inserting 10B into a container next to 10A. Technically, this action gives undefined behavior, but the almost universal result is that the set ends with two copies of the value 10, which means that it is not a set anymore. Using less_equal as our comparison type, we messed up the container! In addition, any comparison function in which equal values ​​return true will do the same. Equal values ​​are by definition not equivalent!

Answer 2

Yes, there is a problem.

Formally, the comparison function should determine a strict weak order, but <= does not.

more specifically, < also used to determine equivalence ( x and y equivalent if f !(x < y) && !(y < x) ). This fails for <= (with this operator, your set assumes objects are never equivalent)

Answer 3

There is really a problem.

The comparison function must satisfy strict weak ordering , which <= does not support.