函数模板 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”开始的原始存储空间，能够容纳类型为 iterator_traits<RandIt>::value_type 的“uninitialized_len”个元素。当 uninitialized_len 为 ceil(std::distance(first, last)/2) 时，可获得最佳性能。

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

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

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

Boost C++ 库

函数模板 adaptive_sort

提要

描述