C++ std::sort 内省排序

C++ 详解 GNU libstdc++ std::sort 源码

Posted by Ciel's Paperplane on December 29, 2024

图片

GNU libstdc++ std::sort 的实现实际上是著名的内省排序，它由快速排序、堆排序与插入排序组成，其中快排作为复杂度常数最小的 O(NlogN) 排序算法被用作执行主体，而由于不平衡情况下快排会衰退到 O(N^2) 复杂度，所以用堆排序对此情况来做兜底（但这种情况实际上非常罕见，LLVM libc++ std::sort 在 2014 年就有一个 issue 指出其没有对 O(N^2) 情况做兜底：libc++ std::sort has O(n^2) worst case, standard mandates O(N log(N))，而这个 issue 在 2021 年才终于被处理掉。原因是只有 1% 的机会会执行到这个堆排兜底代码，几乎没有人在乎），最后插入排序由于其对接近有序的区间效果非常好所以被用作收尾。

插排是我认为这个混合排序算法中最精华的部分。

0. 入口：std::sort

函数有两个重载版本，接收一对迭代器作为前闭后开范围，如果没有提供排序器则默认用 std::less 即 < 作为排序器。

然后有一些编译时检查和 Debug 编译下的检查，不解释。

template<typename _RandomAccessIterator>
	_GLIBCXX20_CONSTEXPR
	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);
		__glibcxx_requires_irreflexive(__first, __last);

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

template<typename _RandomAccessIterator, typename _Compare>
	_GLIBCXX20_CONSTEXPR
	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);
		__glibcxx_requires_irreflexive_pred(__first, __last, __comp);

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

1. 实现：std::__sort

（GNU 的代码风格是真的丑。）

检查区间为空就直接返回，不过这个检查的真实目的是 std::__lg(__n) 的前提条件是 __n > 0。

因为快排的理论最小递归深度是 O(logN)，这里 std::__lg 计算了对数，限制了递归深度为 logN * 2。这样当超过这个深度时，内省排序就改用堆排兜底。

内省排序执行到一定程度后就会退出，最后用 std::__final_insertion_sort 收尾。

template<typename _RandomAccessIterator, typename _Compare>
	_GLIBCXX20_CONSTEXPR
	inline void
	__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
		_Compare __comp)
	{
		if (__first != __last)
{
	std::__introsort_loop(__first, __last,
			std::__lg(__last - __first) * 2,
			__comp);
	std::__final_insertion_sort(__first, __last, __comp);
}
	}

2. 内省排序：std::__introsort_loop

如果区间长度不大于 _S_threshold 即 16 时，就会直接退出，进入上一节提到的 std::__final_insertion_sort。因为快排对于 16 个元素来说最少会递归四次，却基本没干什么活，毫无经济性，改用插排效果会更好。

然后由于这个函数是一个递归函数，__depth_limit 每次都会递减，当它递减到 0 就代表已经到了 logN * 2 的深度，所以这里判断后直接改用 std::__partial_sort 堆排结束。

流程再往下走，std::__unguarded_partition_pivot 就是快排里的找出一个中点后以此为枢纽分别将大小元素交换到其两侧的部分。返回的 __cut 就是中点的迭代器。

这里用的是单侧递归，也就是说前半部分只要继续重复执行循环体即可，后半部分会再调用一层 std::__introsort_loop。

enum { _S_threshold = 16 };

template<typename _RandomAccessIterator, typename _Size, typename _Compare>
	_GLIBCXX20_CONSTEXPR
	void
	__introsort_loop(_RandomAccessIterator __first,
				_RandomAccessIterator __last,
				_Size __depth_limit, _Compare __comp)
	{
		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;
}
	}

3. 快排：std::__unguarded_partition_pivot

这边有两个工具函数。std::__move_median_to_first 会将区间的第二个、最中间和最后一个元素作比较，选出大小排中间的那个，与第一个元素交换。

这个操作的目的是，对于很多常见的数据模式，例如本来就已经有序的区间，直接将第一个元素当成中点那必然会导致 O(N^2) 的情形发生，所以三点选点可以有效避免这种情况。

选好中点后，调用 std::__unguarded_partition 执行快排的交换部分。这里的 unguarded 是有讲究的，因为第一个元素是中点，std::__move_median_to_first 已经确认了区间中至少有两点分别比它大和小，所以直接 while (__comp(__first, __pivot)) 是可以保证在某一点会停下来，绝对不越界的。而比较 naive 的教科书实现这里都会多一个越界检查，很影响性能。

template<typename _Iterator, typename _Compare>
	_GLIBCXX20_CONSTEXPR
	void
	__move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
				_Iterator __c, _Compare __comp)
	{
		if (__comp(__a, __b))
{
	if (__comp(__b, __c))
		std::iter_swap(__result, __b);
	else if (__comp(__a, __c))
		std::iter_swap(__result, __c);
	else
		std::iter_swap(__result, __a);
}
		else if (__comp(__a, __c))
std::iter_swap(__result, __a);
		else if (__comp(__b, __c))
std::iter_swap(__result, __c);
		else
std::iter_swap(__result, __b);
	}

template<typename _RandomAccessIterator, typename _Compare>
	_GLIBCXX20_CONSTEXPR
	_RandomAccessIterator
	__unguarded_partition(_RandomAccessIterator __first,
			_RandomAccessIterator __last,
			_RandomAccessIterator __pivot, _Compare __comp)
	{
		while (true)
{
	while (__comp(__first, __pivot))
		++__first;
	--__last;
	while (__comp(__pivot, __last))
		--__last;
	if (!(__first < __last))
		return __first;
	std::iter_swap(__first, __last);
	++__first;
}
	}

template<typename _RandomAccessIterator, typename _Compare>
	_GLIBCXX20_CONSTEXPR
	inline _RandomAccessIterator
	__unguarded_partition_pivot(_RandomAccessIterator __first,
			_RandomAccessIterator __last, _Compare __comp)
	{
		_RandomAccessIterator __mid = __first + (__last - __first) / 2;
		std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
				__comp);
		return std::__unguarded_partition(__first + 1, __last, __first, __comp);
	}

4. 最精华部分：std::__final_insertion_sort

（在我一年半前刚学 C++ 的时候看到这部分代码当场就忍不住拍手称赞了。）

在 std::__introsort_loop 执行结束即将进入这个函数时，整个区间的情况将会是，被快排递归切成了无数个长度小于 16 的小区间，其中可能有的小区间因为递归深度超了而已经被堆排排序完成了，有的则没有，小区间中还会是无序的。

但是可以确定的是，小区间们互相之间是有序的，即某个小区间里的任意元素，都肯定比左边的小区间们大，比右边的小区间们小。

所以当我们插排时，每个元素的最终位置绝不会远于当前位置的 16 个单位。在这种情况下，插排的时间复杂度就将会为 O(N * 16) 而不是 O(N^2)。

并且在此情况下，线性探测是更有优势的，二分插排由于分支预测差和复杂度常数大是不应该使用的。

不仅如此，这里的 unguarded 也非常精妙。只有第一段小区间是需要作越界检查的，之后的元素都必然比第一段小区间的元素大，那么就不需要担心找过界，结果就是 std::__unguarded_insertion_sort 的执行会非常快。

template<typename _RandomAccessIterator, typename _Compare>
	_GLIBCXX20_CONSTEXPR
	void
	__final_insertion_sort(_RandomAccessIterator __first,
				_RandomAccessIterator __last, _Compare __comp)
	{
		if (__last - __first > int(_S_threshold))
{
	std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
	std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
					__comp);
}
		else
std::__insertion_sort(__first, __last, __comp);
	}

5. 尾声

这个实现在实际使用中还有一些小缺点，例如没有对整数类型作特化，将其直接转入基数排序；还有就是没有尝试做模式匹配，对于本就有序的区间也会有 O(NlogN) 的复杂度。不过在泛化场景排序中，它的性能已经足够出色了。

Ciel's Paperplane

作诗中...
CATALOG