According to Scott Meyers, in his Effective STL book - item 46. He claimed that std::sort
is about 670% faster than std::qsort
due to the fact of inline. I tested myself, and I saw that qsort is faster :( ! Could anyone help me to explain this strange behavior?
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
const size_t LARGE_SIZE = 100000;
struct rnd {
int operator()() {
return rand() % LARGE_SIZE;
}
};
int comp( const void* a, const void* b ) {
return ( *( int* )a - *( int* )b );
}
int main() {
int ary[LARGE_SIZE];
int ary_copy[LARGE_SIZE];
// generate random data
std::generate( ary, ary + LARGE_SIZE, rnd() );
std::copy( ary, ary + LARGE_SIZE, ary_copy );
// get time
std::time_t start = std::clock();
// perform quick sort C using function pointer
std::qsort( ary, LARGE_SIZE, sizeof( int ), comp );
std::cout << "C quick-sort time elapsed: " << static_cast<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";
// get time again
start = std::clock();
// perform quick sort C++ using function object
std::sort( ary_copy, ary_copy + LARGE_SIZE );
std::cout << "C++ quick-sort time elapsed: " << static_cast<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";
}
This is my result:
C quick-sort time elapsed: 0.061
C++ quick-sort time elapsed: 0.086
Press any key to continue . . .
Update
Effective STL 3rd Edition ( 2001 )
Chapter 7 Programming with STL
Item 46: Consider function objects instead of functions as algorithm parameters.
qsort
orsort
will use a quicksort implementation that breaks on reverse-sorted inputs. The most common STLsort
implementation uses introsort, which introspects on the quicksort routine to ensure it never degrades to worse than O(n lg n), and I'm fairly confident that the Cqsort
routine uses something similar (or at least a heuristic like median-of-three) to prevent this.