qsort vs std::sort

朋友问我，qsort和std::sort有什么区别，我没有专门查过，但还是尝试答了几条：

1. qsort是C标准库函数，位于<stdlib.h>；sort是STL中的函数模板，位于<algorithm>
2. qsort的参数用指针表示范围；sort的参数用迭代器表示范围
3. qsort肯定是快排，sort应该是根据迭代器类型来判断是否采用快排，如果是前向迭代器的话应该就不是快排

第三条是我猜的，后来查过资料之后，发现我第三条确实答错了，事实上：

• sort的迭代器参数只能是Mutable RandomAccessIterator。
• sort的排序算法不是快排，而是IntroSort和InsertionSort的结合。（内省排序 和 插入排序）

下面说一下std::sort的源码，以及记录一下阅读中遇到的不懂的东西（不懂的实在有点多，可能有点啰嗦）。

std::sort

std::sort有两个重载：

  template<typename _RAIter>
    void 
    sort(_RAIter, _RAIter);

  template<typename _RAIter, typename _Compare>
    void 
    sort(_RAIter, _RAIter, _Compare);

分别点进去：

  template<typename _RandomAccessIterator>
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<
        typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);

      std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
    }

  template<typename _RandomAccessIterator, typename _Compare>
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     _Compare __comp)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>)
      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
        typename iterator_traits<_RandomAccessIterator>::value_type,
        typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);

      std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
    }

殊途同归，调用了同一个函数std::__sort，只是第三个参数不同。

接下来先不看std::__sort的源码，先搞懂调用该函数前的那一堆代码是什么。

__glibcxx_function_requires

上面代码里面，__glibcxx_function_requires是宏定义，涉及到c++ concept checking的概念。

显然concept checking不是C++11标准的一部分，它是Boost的一部分，是Boost Concept Checking Library的内容，然后GNU将其整合到了 GNU C++ library中。gcc里面，concept checking默认是关闭的，可以通过 #define _GLIBCXX_CONCEPT_CHECKS 来打开它，但是没有任何必要，因为C++11的特性会完成concept checking的功能。更具体的解释见文末的引用[6][7]。

简而言之，这个concept check的作用是“限制某类型的特定的操作是合法的”。比如说，__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIterator>)就是要限制你传入的迭代器类型得是Mutable RandomAccessIterator，得支持++ -- [] * += -= 等运算符操作。如果不满足的话，编译就不通过。

上面的sort(__first, __last)里的两条__glibcxx_function_requires就限制了：

• 迭代器类型得是Mutable RandomAccessIterator
• 迭代器所指类型得是支持<运算符的

之前我只清楚iterator的五种类型，即std::input_iterator_tag等代表的五种，然后我就有了以下疑问：

1. 为什么用concept check来检查迭代器类型？像std::advance那样用__iterator_traits检查迭代器类型不行吗？
2. 迭代器类型中有mutable iterator吗？五种迭代器类型好像没有提到啊？

针对问题查了cppreference.com [4]：

There are five (until C++17)six (since C++17) kinds of iterators: InputIterator, OutputIterator, ForwardIterator, BidirectionalIterator, RandomAccessIterator, and ContiguousIterator (since C++17).

All of the iterator categories (except OutputIterator and ContiguousIterator) can be organized into a hierarchy, where more powerful iterator categories (e.g. RandomAccessIterator) support the operations of less powerful categories (e.g. InputIterator). If an iterator falls into one of these categories and also satisfies the requirements of OutputIterator, then it is called a mutable iterator and supports both input and output. Non-mutable iterators are called constant iterators.

mutable iterator指的支持write和increment的迭代器。因此，iterator_catogory是random_access_iterator_tag的迭代器并不一定可写，random_access_iterator_tag并不能保证迭代器是mutable还是constant，只有mutable iterator才是可写的。所以上面的两个问题有答案了。

那么concept check是怎么实现的呢？接下来接着看源码。

点进去__glibcxx_function_requires：

#ifndef _GLIBCXX_CONCEPT_CHECKS
#define __glibcxx_function_requires(...)
#else // the checks are on
#define __glibcxx_function_requires(...)                                 \
            __gnu_cxx::__function_requires< __gnu_cxx::__VA_ARGS__ >();
#endif // enable/disable

因此，如果想要使用concept check，就需要自己在include相关头文件之前定义宏_GLIBCXX_CONCEPT_CHECKS，或者修改c++config.h中的宏定义。

接下来看 __gnu_cxx::__function_requires。

template <class _Concept>
inline void __function_requires()
{
  void (_Concept::*__x)() _IsUnused = &_Concept::__constraints;
}

_IsUnused是宏定义，展开后是__attribute__((unused))，表示该函数或变量可能不使用，这个属性可以避免编译器产生警告信息。如果看不懂__function_requires里面的语法，请参考引用[2][3]。

所以，最初std::sort里的第一个__glibcxx_function_requires展开之后就是：

__gnu_cxx::__function_requires< __gnu_cxx::_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>>();

然而这做了什么？

首先，这句话导致实例化并调用了__function_requires模板函数。该函数里，定义了一个函数指针，指向模板参数表示的类的__constraints成员函数，进而导致实例化了__gnu_cxx::_Mutable_RandomAccessIteratorConcept<_RandomAccessIterator>::__constraints。在__constraints函数中会对迭代器进行某些运算符操作，编译时编译器会检查这些操作的有效性，因此，就达到了检查迭代器性质的作用。

贴出来_Mutable_RandomAccessIteratorConcept的源码，加以印证：

  template <class _Tp>
  struct _Mutable_RandomAccessIteratorConcept
  {
    void __constraints() {
      __function_requires< _RandomAccessIteratorConcept<_Tp> >();
      __function_requires< _Mutable_BidirectionalIteratorConcept<_Tp> >();
      __i[__n] = *__i;                  // require element access and assignment
    }
    _Tp __i;
    typename std::iterator_traits<_Tp>::difference_type __n;
  };

现在std::__sort之前的那一大坨我们已经弄清楚了，接下来进入std::__sort。

std::__sort

接下来std::__sort的实现和侯捷的《STL源码剖析》中讲的std::sort的实现基本一样了。我看的这个STL版本是gcc 5.3.1使用的版本，其std::sort的实现只是在侯捷书中讲的版本上套了个壳子，加了concept checking（也就是前面大费周章讲的东西）。如果有这本书的话可以去看这本书，书上讲的详细多了，这里只简单介绍一下实现。

std::__sort的排序算法是IntroSort和InsertionSort的结合，先说一下什么是IntroSort。

这个排序算法类似于快排，在快排的基础上，当递归深度超过一定深度（深度为排序元素数量的对数值）时转为堆排序。伪代码如下：

procedure sort(A : array):
    let maxdepth = ⌊log(length(A))⌋ × 2
    introsort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
    if n ≤ 1:
        return  // base case
    else if maxdepth = 0:
        heapsort(A)
    else:
        introsort(A[0:p], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)

接下来贴出来std::__sort源码，我把代码加上了注释，不再单独解释代码了。

 template<typename _RandomAccessIterator, typename _Compare>
    inline void
    __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
       _Compare __comp)
    {
      if (__first != __last)
    {
      // __introsort_loop先进行一遍IntroSort，但是不是严格意义上的IntroSort。
      //因为执行完之后区间并不是完全有序的，而是基本有序的。
      //__introsort_loop和IntroSort不同的地方是，__introsort_loop会在一开始会判断区间的大小，当区间小于16的时候，就直接返回。
      std::__introsort_loop(__first, __last,
                std::__lg(__last - __first) * 2,
                __comp); 
      // 在区间基本有序的基础上再做一遍插入排序，使区间完全有序
      std::__final_insertion_sort(__first, __last, __comp);
    }
    }

__introsort_loop和__final_insertion_sort代码：

  enum { _S_threshold = 16 };

  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
    void
    __introsort_loop(_RandomAccessIterator __first,
             _RandomAccessIterator __last,
             _Size __depth_limit, _Compare __comp)
    {
      // 若区间大小<=16就不再排序。
      while (__last - __first > int(_S_threshold))
    {
      // 若递归次数达到限制，就改用堆排序
      if (__depth_limit == 0)
        {
          std::__partial_sort(__first, __last, __last, __comp);
          return;
        }
      --__depth_limit;
      _RandomAccessIterator __cut =
      std::__unguarded_partition_pivot(__first, __last, __comp); // 分割
      std::__introsort_loop(__cut, __last, __depth_limit, __comp); // 右半区间递归
      __last = __cut;
    // 回到while循环，对左半区间进行排序，这么做能显著减少__introsort_loop的调用的次数
    }
    }


  template<typename _RandomAccessIterator, typename _Compare>
    void
    __final_insertion_sort(_RandomAccessIterator __first,
               _RandomAccessIterator __last, _Compare __comp)
    {
      if (__last - __first > int(_S_threshold)) // 区间长度大于16
    {
      // 插入排序
      std::__insertion_sort(__first, __first + int(_S_threshold), __comp); 
      // 也是插入排序，只是在插入排序的内循环时，不再判断边界条件，因为已经保证了区间前面肯定有比待插入元素更小的元素
      std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, 
                      __comp);
    }
      else // 区间长度小于等于16的话
    std::__insertion_sort(__first, __last, __comp); // 插入排序
    }

__unguarded_insertion_sort和__insertion_sort和__unguarded_partition_pivot不再赘述。

总结

感觉讲了一堆废话，C++11中concept checking都不用了，感觉白看了......

Reference

1. how does __glibcxx_function_requires and __glibcxx_requires_valid_range macros work?
2. Function pointer to member function
3. function pointers in c++ : error: must use '.' or '->' to call pointer-to-member function in function
4. https://en.cppreference.com/w/cpp/iterator
5. https://en.wikipedia.org/wiki/Introsort
6. Compile Time Checks
7. Using Concept Checks