函数模板 adaptive_sort

boost::movelib::adaptive_sort

提要

// In header: <boost/move/algo/adaptive_sort.hpp>


template<typename RandIt, typename RandRawIt, typename Compare> 
  void adaptive_sort(RandIt first, RandIt last, Compare comp, 
                     RandRawIt uninitialized, 
                     typename iter_size< RandIt >::type uninitialized_len);

描述

效果：根据比较函数对象“comp”对范围 [first, last) 中的元素进行升序排序。排序是稳定的（相等元素的顺序被保证保持）。如果提供了额外的原始存储空间，性能将得到提高。

要求:

RandIt 必须满足 ValueSwappable 和 RandomAccessIterator 的要求。
解引用的 RandIt 的类型必须满足 MoveAssignable 和 MoveConstructible 的要求。

参数:

first, last：要排序的元素范围
comp：比较函数对象，如果第一个参数在第二个参数之前，则返回 true。
uninitialized, uninitialized_len：从“uninitialized”开始的原始存储空间，能够容纳“uninitialized_len”个类型为 iterator_traits<RandIt>::value_type 的元素。当 uninitialized_len 为 ceil(std::distance(first, last)/2) 时，可以获得最佳性能。

抛出：如果 comp 抛出异常，或者解引用的 RandIt 类型的移动构造函数、移动赋值运算符或 swap 操作抛出异常。

复杂度：始终需要 K x O(Nxlog(N)) 次比较和移动赋值/构造/交换操作。即使没有额外的内存，比较次数也接近最小值。当 uninitialized_len 为 ceil(std::distance(first, last)/2) 时，数据移动的常数因子被最小化。当 uninitialized_len 为 ceil(sqrt(std::distance(first, last)))*2 时，可以获得足够好的性能。

注意：实验性实现，尚未用于生产环境。

Boost C++ 库

函数模板 adaptive_sort

提要

描述