用std::sort替换qsort

简单说明

qsort的原型为：

void qsort(void *base, size_t nmemb, size_t size,
        int(*compar)(const void *, const void *));

实际实现为glibc/stdlib/msort.c中的qsort_r函数。compar函数取大于时，排序结果为递增。

std::sort为模板函数，原型为：

template<typename _RandomAccessIterator>
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{...}

和

template<typename _RandomAccessIterator, typename _Compare>
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{...}

函数inline，仿函数也inline，less<T>()时，排序结果为递增。

qsort和std::sort大体都是快排加插入，做了很多防止算法退化的优化。但不管什么情况下，都请使用std::sort代替qsort。

性能方面

由于qsort是传递函数指针，代码是早已编译好，使用是链接stdlib库。 而std::sort是模板函数，模板函数会被特化并参与重新编译，编译时inline就能发挥作用。 所以在性能方面std::sort比qsort能快10倍至20倍。

不要以为将函数实现写在头文件里，并加上inline就能使qsort提速。摒弃C++比C慢观念的又一力证。

简洁方面

使用qsort，无论如何你都得实现一个比较函数，以及恶心的void*类型转换。

int Comp(const void *a, const void *b)
{
    return *((const int*)a) > *((const int*)b);
}

而std::sort大多数情况下使用less<T>()和greater<T>()就足够，哪怕使用仿函数也优雅得多。

struct Comp
{
    bool operator()(const Node &a, const Node &b)
    {
        return a.x > b.x;
    }
};

多线程方面

qsort考虑了当需要排序的序列比较小，或者比较大的时候使用不同的排序算法， 以及临时使用内存小时，使用栈内存，大时，使用堆内存。在这个过程中，有两个问题值得一提。

第一，qsort计算过程中需要获取页大小，即pagesize，老版本的glibc中的qsort在获取pagesize时有线程安全的Bug。

第二，如果内存分配由tcmalloc托管，在线程中qsort会带来内存消耗上涨， 尽管该线程中再次需要分配内存时会重复利用这部分内存，但std::sort就没有这些闹心的事。