Menu
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?
538
std::sort() is a built-in function in C++'s Standard Template Library. The function takes in a beginning iterator, an ending iterator, and (by default) sorts the iterable in ascending order. The function can also be used for custom sorting by passing in a comparator function that returns a boolean.
The std::sort is a sorting function that uses the Introsort algorithm and have the complexity of O(N log(N)) where N= std::distance(first, last) since C++11 and the order of equal elements is not guaranteed to be preserved[3]. The gcc-libstdc++ also uses Introsort algorithm.
In general, std::sort is indeed faster than qsort because of a couple of these things: qsort operates on void* , which first requires a dereference, and second requires the size of the data type to perform the swaps.
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.
197
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
