浅谈std::list::sort()实现原理

GCC STL源自SGI STL, 其使用的std::sort()使用的算法为quick sort / insert sort / heap sort的综合体，而这些算法都有随机访问元素的需求，因此其要求的入参迭代器类型为RandomAccessIterator. 而list itertor为BidirectionalIterator, 因此不能满足std::sort()的需求。 list提供了一个成员版sort()算法，其本质上是一种bottom-up merge sort (侯捷STL源码剖析 P142中的quick sort说法有误), 本文接下来将对其GCC 12.2.0版代码进行分析，希望能对大家有所帮助。

1. 算法实现

GCC版list::sort()算法基本上和最初的SGI版完全一致（可见GCC代码注释），其本质上是一种bottom-up merge sort, 具体算法流程如下：

  1. 创建一个含64个元素的数组_tmp来存储merge sort过程的中间结果, _tmp[i]所存储的元素数量为2i, 因此最多可以容纳264 - 1个元素而可以满足任何实际排序需求。
  2. 取出list的第一个元素，将其和_tmp[0]开始合并。
  3. 若合并后_tmp[i]非空，则将_tmp[i]合并如_tmp[i+1], 直到_tmp[i]为空为止。 _tmp[0 -> i]的所有元素个数为2i+1 - 1, 加上第2步取出的链表头后元素总数刚好和_tmp[i+1]的元素个数2i+1相等, 因此合并流程和bottom-up merge sort完全一致。
  4. 重复2和3, 直到list为空为止。
  5. 合并所有非空_tmp[i]以得到排序好后的最终结果。

其具体代码如下： 

template<typename _Tp, typename _Alloc>
void list<_Tp, _Alloc>::sort() {
    // Do nothing if the list has length 0 or 1.
    if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
    {
using __detail::_Scratch_list;
_Scratch_list __carry;
_Scratch_list __tmp[64];  // __tmp[i]所存储的元素数量为2^i, 因此最多可以容纳2^64 - 1个元素而可以满足任何实际排序需求。
_Scratch_list* __fill = __tmp;
_Scratch_list* __counter;
_Scratch_list::_Ptr_cmp<iterator, void> __ptr_comp;

__try {
    do {
        __carry._M_take_one(begin()._M_node);  // 取出第一个元素
        for(__counter = __tmp;
            __counter != __fill && !__counter->empty();
            ++__counter)
        {
            // 将__carry和__tmp[i]逐项合并，直到__counter (tmp[i])为空或到达__fill为止
            __counter->merge(__carry, __ptr_comp);
            __carry.swap(*__counter);
        }
        __carry.swap(*__counter);
        if (__counter == __fill)
        ++__fill;
     } while ( !empty() );

    // 合并__tmp[0 -> __fill]以得到排序好后的最终结果
    for (__counter = __tmp + 1; __counter != __fill; ++__counter)
      __counter->merge(__counter[-1], __ptr_comp);
    __fill[-1].swap(this->_M_impl._M_node);
  }
__catch(...)
  {
    // Move all nodes back into *this.
    __carry._M_put_all(end()._M_node);
    for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
      __tmp[__i]._M_put_all(end()._M_node);
    __throw_exception_again;
  }
    }
  }

list元素是离散存储的，因此无需使用tmp buffer来存储merge sort中间结果，而这使得​list merge sort空间复杂度为O(1) (而非数组merge sort的O(N))​。