The following program is compiled with VC++ 2012.
#include <algorithm>
struct A
{
A()
: a()
{}
bool operator <(const A& other) const
{
return a <= other.a;
}
int a;
};
int main()
{
A coll[8];
std::sort(&coll[0], &coll[8]); // Crash!!!
}
If I change return a <= other.a; to return a < other.a; then the program runs as expected with no exception.
Why?
11
std::sort requires a sorter which satisfies the strict weak ordering rule, which is explained
here
So, your comparer says that a < bwhen a == b which doesn’t follow the strict weak ordering rule, it is possible that the algorithm will crash because it’ll enter in an infinite loop.
4
The answer for xorguy is pretty good.
I would just add some quote from the standard :
25.4 Sorting and related operations [alg.sorting]
For algorithms other than those described in 25.4.3 to work correctly, comp has to induce a strict weak ordering on the values.
The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering.
So xorguy explains it very well : You comp function says that a < b when a == b which doesn’t follow the strict weak ordering rule…
The problem with your code is that you are accessing invalid memory. Code
coll[8]
trying to access the element after the last array element (the last element index is 7).
I would suggest using std::array instead plain C arrays.
std::array<A, 8> a;
// fill it somehow
std::sort(a.begin(), a.end());
1