I understand that std::sort
requires strict weak ordering.
However, it is not clear to me why the comparator must follow irreflexivity.
Some answers (here and here) suggest that the algorithm would crash/go in an infinite-loop, but I do not see how.
Here is my layman's implementation of qsort. I am unable to create an example where having "<=" causes issues. The only issue I see here is that the number of swaps increases as opposed to having a strict inequality.
So is the irreflexivity clause only because of inefficiencies, or can it also cause the program to crash as other answers suggest?
It is mostly a design choice, however it is one that makes the C++ standard simpler, and easier to use. The current implementations certainly take advantage1 of the status quo, but if the standard were to relax it, they would change.
std::binary_search
et.al. also requires a strict-weak comparison, and there the strictness is necessary. It defines equivalence, and therefor presence of the searched-for item, by saying that an item is in the range if there is an element that is not ordered before the item, and also the item is not ordered before that element.
One of the preconditions of binary_search
is that the range is sorted with respect to the given comparison. If there was a subtly different requirement for the comparison, then code like the following would be problematic:
template<typename Cont, typename Comp>
class Foo {
Cont container;
Comp comparison;
void bar() { // called whenever container changes
std::sort(std::begin(container), std::end(container), comparison);
}
bool has_item(T elem) {
return std::binary_search(std::begin(container), std::end(container), comparison);
}
};
quicksort
that does crash when you switch <
for <=
template<class ForwardIt>
void quicksort(ForwardIt first, ForwardIt last)
{
if (first == last)
return;
auto pivot = *std::next(first, std::distance(first, last) / 2);
auto middle1 = std::partition(first, last, [pivot](const auto& em)
{
return em < pivot;
});
auto middle2 = std::partition(middle1, last, [pivot](const auto& em)
{
return !(pivot < em);
});
quicksort(first, middle1);
quicksort(middle2, last);
}