一道面试题引起的...

引言--面试题

有个结构体如下:

struct AdItem {
  std::string ad_id; // 广告id
  int priority; // 优先级
  int score; // 得分
};

现在有一个AdItem类型的verctor，要求对其排序

排序规则如下:

1、按照priority升序排列

2、如果priority一样大，则按照score降序排列

3、如果score也一样，则随机排序

void ad_sort(vector<AdItem> &ad_items) {

std::sort(ad_items.begin(), ad_items.end(), [](const AdItem &item1, const AdItem &item2) {
  if (item1.priority < item2.priorty) {
      return true;
    } else if (item1.priority > item2.priorty) {
      return false;
    } else {
    if (item1.score > item2.score) {
      return true;
    } else if (item1.score < item2.score) {
      return false;
    } else {
      return rand() % 2 == 0 ? true : false;
    }
    }
} );
}

STL中sort实现

我们先说结论：

在STL的sort中，在数据量大时候，采用快排，分段递归排序。一旦分段后的数据量小于某个阈值，为了避免快排的递归调用引起的额外开销，此时就采用插入排序。如果递归层次过深，还会采用堆排序。

下面我们将对STL中的sort实现进行深入讲解。

template <class _RandomAccessIter, class _Compare>

inline void sort(_RandomAccessIter __first, _RandomAccessIter __last,
                 _Compare __comp) {
 ...
  if (__first != __last) {
    __introsort_loop(__first, __last,
                     __VALUE_TYPE(__first),
                     __lg(__last - __first) * 2,
                     __comp);
    __final_insertion_sort(__first, __last, __comp);
  }
}

它是一个模板函数，只接受随机访问迭代器。if语句先判断区间有效性，接着调用__introsort_loop，它就是STL的Introspective Sort（内省式排序）实现。在该函数结束之后，最后调用插入排序。

在此，我们需要注意的一点是，在STL的内省式排序中，depth_limit 的初始值是__lg(__last - __first) * 2,即 2 * lg(__last - __first)

下面我们来详细分析该函数。

__introsort_loop

template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>

void __introsort_loop(_RandomAccessIter __first,
                      _RandomAccessIter __last, _Tp*,
                      _Size __depth_limit, _Compare __comp)
{
  while (__last - __first > __stl_threshold) {
    if (__depth_limit == 0) {
      partial_sort(__first, __last, __last, __comp);
      return;
    }
    --__depth_limit;
    _RandomAccessIter __cut =
      __unguarded_partition(__first, __last,
                            _Tp(__median(*__first,
                                         *(__first + (__last - __first)/2),
                                         *(__last - 1), __comp)),
       __comp);
    __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
    __last = __cut;
  }
}

为了更清楚的理解该函数的功能，我们先将该函数中的调用子函数讲解，最后，通过逐个将子函数串起来，进行讲解该函数。

全局变量__stl_threshold

其定义如下：

const int __stl_threshold = 16;

数据最小分段阈值。当数据长度小于该阈值时，再使用递归来排序显然不划算，递归的开销相对来说太大。而此时整个区间内部有多个元素个数少于16的子序列，每个子序列都有相当程度的排序，但又尚未完全排序，过多的递归调用是不可取的。而这种情况刚好插入排序最拿手，它的效率能够达到O(N)。因此这里中止快速排序，sort会接着调用外部的__final_insertion_sort，即插入排序来处理未排序完全的子序列。

__lg

template <class _Size>

inline _Size __lg(_Size __n) {
  _Size __k;
  for (__k = 0; __n != 1; __n >>= 1) ++__k;
  return __k;
}

该函数主要功能是找出2^k <= n的最大k。当n = 7的时候，k = 2；当n = 20的时候，k = 4；当n = 8的时候，k = 3。

参数 depth_limit 由该函数获取。每次都会自减一次；当该参数为 0 时，意味着递归深度已经很深，很可能快排掉入了陷阱，因此调用堆排，并退出递归。

partial_sort

堆排序。

前面有提到，由depth_limit来决定是否进入堆排序。当递归次数超过depth_limit时，函数调用partial_sort。此时采用堆排序可以将快速排序的效率从O(N2)提升到O(N logN)，杜绝了过度递归所带来的开销。堆排序结束之后直接结束当前递归。

template <class _RandomAccessIter, class _Compare>

inline void partial_sort(_RandomAccessIter __first,
                         _RandomAccessIter __middle,
                         _RandomAccessIter __last, _Compare __comp) {
  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  __STL_BINARY_FUNCTION_CHECK(_Compare, bool, 
      typename iterator_traits<_RandomAccessIter>::value_type,
      typename iterator_traits<_RandomAccessIter>::value_type);
  __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first), __comp);
}
template <class _RandomAccessIter, class _Tp, class _Compare>

void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
                    _RandomAccessIter __last, _Tp*, _Compare __comp) {
  make_heap(__first, __middle, __comp);
  for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
    if (__comp(*__i, *__first))
      __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
                 __DISTANCE_TYPE(__first));
  sort_heap(__first, __middle, __comp);
}

快排

当去掉递归恶化的处理，introsort_loop函数，其实就是一个快排。快排的伪代码如下：

qsort(first, last):

    cut = partition(first, last, pivot)  // pivot is picked in [first, last)
    qsort(cut + 1, last)
    qsort(first, cut)

而去掉递归恶化处理之后的introsort_loop为：

template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>

void __introsort_loop(_RandomAccessIter __first,
                      _RandomAccessIter __last, _Tp*,
                      _Size __depth_limit, _Compare __comp)
{
  while (__last - __first > __stl_threshold) {
    // 去掉了递归恶化处理
    _RandomAccessIter __cut =
      __unguarded_partition(__first, __last,
                            _Tp(__median(*__first,
                                         *(__first + (__last - __first)/2),
                                         *(__last - 1), __comp)),
       __comp); // 获取pivot
    __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp); //执行右侧
    __last = __cut; // 执行左侧
  }
}

pivot的获取

此处用的__median函数来实现。这个函数基本就是选择a、b和c中间的一个
template <class _Tp>

inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
  __STL_REQUIRES(_Tp, _LessThanComparable);
  if (__a < __b)
    if (__b < __c)
      return __b;
    else if (__a < __c)
      return __c;
    else
      return __a;
  else if (__a < __c)
    return __a;
  else if (__b < __c)
    return __c;
  else
    return __b;
}

__unguarded_partition

template <class _RandomAccessIter, class _Tp>

_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, 
                                        _RandomAccessIter __last, 
                                        _Tp __pivot) 
{
  while (true) {
    while (*__first < __pivot)// 1
      ++__first; 
    --__last; // 2
    while (__pivot < *__last) // 3
      --__last;
    if (!(__first < __last)) // 4
      return __first;
    iter_swap(__first, __last); // 5
    ++__first; // 6
  }
}    

快排的核心，是对pivot进行分割。小于pivot的在左边，大于pivot的在右边。STL中使用__unguarded_partition进行该操作。

1和6都是将 first 迭代器后移，指向第一个不小于pivot的元素。2和3都是将 last 迭代器前移，指向第一个不大于pivot的元素。在4处的判断，若第一个不小于主元的元素不先序于第一个不大于pivot的元素，则说明分割已经完毕，返回第一个不小于pivot的元素的位置，即 first 的当前值；否则，在5处交换 first 和 last 指向元素的值。参考《STL 源码剖析》的图示：

分割图示例一

分割图示例二

__introsort_loop总结

1、在__introsort_loop函数中，首先会判断数据量大小，即如果last - first <= 16，则退出该函数。否则

2、判断__depth_limit是否为0。当该参数为 0 时，意味着递归深度已经很深，很可能快排掉入了陷阱，因此调用堆排，并退出递归。

3、每执行一次循环，depth_limit递减一次。

4、通过__unguarded_partition进行快排核心操作。

5、执行有半部分

6、通过__last = __cut;操作，下一步对左半部分进行排序。

__final_insertion_sort

代码实现如下：

template <class _RandomAccessIter, class _Compare>

void __final_insertion_sort(_RandomAccessIter __first, 
                            _RandomAccessIter __last, _Compare __comp) {
  if (__last - __first > __stl_threshold) {
    __insertion_sort(__first, __first + __stl_threshold, __comp);
    __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
  }
  else
    __insertion_sort(__first, __last, __comp);
}

该函数内有一个if分支，判定数据量是否大于阈值16，

1、如果大于16，则对数据的第一个到第十六个进行插入排序，剩下的部分，进行__unguarded_insertion_sort排序

2、如果小于16，则直接进行插入排序

__linear_insert

template <class _RandomAccessIter, class _Tp, class _Compare>
inline void __linear_insert(_RandomAccessIter __first, 
                            _RandomAccessIter __last, _Tp*, _Compare __comp) {
  _Tp __val = *__last;
  if (__comp(__val, *__first)) {
    copy_backward(__first, __last, __last + 1);
    *__first = __val;
  }
  else
    __unguarded_linear_insert(__last, __val, __comp);
}

该函数的目的是将 last 所指向的元素插入到正确位置，这里蕴含的前提假设是[first, last) 区间的元素是已经排好序的。在这一假设下，若 *last < *first，则毫无疑问，last 指向的元素应当插入在上述区间的最前面，因此有 std::copy_backward；若不满足条件判断，则在 [first, last) 之间必然存在不大于 value 的元素（比如至少 *first 是这样），因此可以调用 __unguarded_linear_insert 来解决问题，而不必担心在 __unguarded_linear_insert 中 next 迭代器向左越界。对于 *last < *first 的情况，__linear_insert 将 last - first - 1 次比较和交换操作变成了一次 std::copy_backward 操作，相当于节省了 last - first - 1 次比较操作。

__insertion_sort

template <class _RandomAccessIter, class _Compare>

void __insertion_sort(_RandomAccessIter __first,
                      _RandomAccessIter __last, _Compare __comp) {
  if (__first == __last) return;
  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp);
}

在该函数中 ，通过循环调用__linear_insert，从first之后的第一个元素开始，将该元素插入正确的位置。而这就是标准的插入排序了，此处不再赘述。

__unguarded_insertion_sort

template <class _RandomAccessIter, class _Tp, class _Compare>
void __unguarded_insertion_sort_aux(_RandomAccessIter __first, 
                                    _RandomAccessIter __last,
                                    _Tp*, _Compare __comp) {
  for (_RandomAccessIter __i = __first; __i != __last; ++__i)
    __unguarded_linear_insert(__i, _Tp(*__i), __comp);
}


template <class _RandomAccessIter, class _Compare>
inline void __unguarded_insertion_sort(_RandomAccessIter __first, 
                                       _RandomAccessIter __last,
                                       _Compare __comp) {
  __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first),
                                 __comp);
}

__unguarded_insertion_sort 没有边界检查，因此它一定比 __insertion_sort 要快。但由于 __unguarded_insertion_sort_aux 会从 first 开始调用 __unguarded_linear_insert；因此使用 __unguarded_insertion_sort 的条件比 __unguarded_linear_insert 更加严格。它必须保证以下假设成立：在 first 左边的有效位置上，存在不大于 [first, last) 中所有元素的元素。

__unguarded_linear_insert

template <class _RandomAccessIter, class _Tp>
void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
  _RandomAccessIter __next = __last;
  --__next;
  while (__val < *__next) {
    *__last = *__next;
    __last = __next;
    --__next;
  }
  *__last = __val;
}

这里仅仅挨个判断是否需要调换，找到位置之后就将其插入到适当位置。

它根本无需输入左边界，而只需输入右边界迭代器和带插入元素的值即可；这也意味着，__unguarded_linear_insert 不是完整的插入排序的实现。

显然，这种情况下，为了保证函数执行的正确性，函数必然有额外的前提假设。此处假设应当是：while 循环会在 next 迭代器向左越界之前停止；这也就是说，在 [first, last) 之间必然存在不大于 value 的元素。因此，为防止越界，在调用该函数模板之前，我们必须要保证这一假设成立。

__final_insertion_sort总结

1、数据量与__stl_threshold对比。

2、如果大于__stl_threshold，则对前16个进行插入排序。对后16个进行__unguarded_insertion_sort 排序

3、如果小于__stl_threshold，则直接进行插入排序

写在最后

一直都对std::sort的函数实现很好奇。工作中经常用到，之前也只是大概了解到用到了快排 插入等，但是没有想到其为了效率，做了如此多的工作。c++的道路，漫长且困难。