less or less_equal using set
c++, set, stl
Solution
From Effective STL -> Item 21. Always have comparison functions return false for equal values.
Create a set where less_equal is the comparison type, 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 inserting 10 again:
s.insert(10);
For this call to insert, the set has to figure out whether 10 is already present. We know that it is. but the set is dumb as toast, so it has to check. To make it easier to understand what happens when the set does this, we'll call the 10 that was initially inserted 10A and the 10 that we're trying to insert 10B.The set runs through its internal data structures looking for the place to insert 10B. It ultimately has to check 10B to see if it's the same as 10A. The definition of "the same" for associative containers is equivalence, so the set tests to see whether 10B is equivalent to 10A. When performing this test, it naturally uses the set's comparison function. In this example, that's operator<=, because we specified less_equal as the set's comparison function, and less_equal means operators. The set thus checks to see whether this expression is true:
!(10A<= 10B)&&!(10B<= 10A) //test 10Aand 10B for equivalence
Well, 10A and 10B are both 10, so it's clearly true that 10A <= 10B. Equally clearly, 10B <= 10A. The above expression thus simplifies to
!!(true)&&!(true)
and that simplifies to
false && false
which is simply false. That is, the set concludes that 10A and 10B are not equivalent, hence not the same, and it thus goes about inserting 10B into the container alongside 10A. Technically, this action yields undefined behavior, but the nearly universal outcome is that the set ends up with two copies of the value 10, and that means it's not a set any longer. By using less_equal as our comparison type, we've corrupted the container! Furthermore, any comparison function where equal values return true will do the same thing. Equal values are, by definition, not equivalent!
Problem
We can pass a function as `<`(less) operator to STL data structures such as `set`, `multiset`, `map`, `priority_queue`, ... Is there a problem if our function acts like `<=`(less_equal)?