struct Object
{
int x;
int y;
bool isXValid()
{
return x > 0;
}
};
bool mySort(const Object& lhs, const Object& rhs)
{
// Note the short-circuit here
bool isValidForCheck = lhs.isXValid() && rhs.isXValid();
// rhs may be valid because short-circuit, or both may be invalid
if (isValidForCheck)
{
return lhs.x < rhs.x;
}
return lhs.y < rhs.y;
}
int main()
{
std::vector<Object> myVec;
// random populating of myVec
std::sort(myVec.begin(), myVec.end(), mySort);
return 0;
}
My comparison function is irreflexive but does not respect transitivity.
stl ordering - strict weak ordering
Thus, if:
(a < b) == true, (b < a) must be false.
Additionally, if:
a == b, then (a < b) and (b < a) are false.
However, it is not transitive. For example, with the following values:
(1, 3) (-1, 2), (3, 1)
Then it is possible to produce a sorted container where:
a < b, and b < c, but c < a.
This answer : What causes std::sort() to access address out of range explains why std::sort will address out-of-bounds when the comparison function doesn't respect irreflexibility (for example, quicksort where we do comp(pivot, pivot) and get true, thus the left pointer keeps walking right off the end of the array).
However, I am seeing crashes with comparisons that are irreflexive but non-transitive. I also believe I am going off the end of the array.
I cannot provide the exact code here as it is proprietary. The example above will not crash in my tests, but I am aware that std::sort will select different algorithms based upon the container and elements to be sorted.
What I'd like to know is if anybody knows why std::sort would crash under GNU C++ when the comparison is non-transitive? I know that non-transitive comparisons break the contract and it's undefined behaviour, but I was hoping for a similar answer to the one in the linked question - i.e. precisely why it can crash.
