boost::movelib::adaptive_merge
// In header: <boost/move/algo/adaptive_merge.hpp> template<typename RandIt, typename Compare> void adaptive_merge(RandIt first, RandIt middle, RandIt last, Compare comp, typename iterator_traits< RandIt >::value_type * uninitialized = 0, typename iter_size< RandIt >::type uninitialized_len = 0);
效果: 根据给定的比较函数 comp,将两个连续的已排序范围 [first, middle) 和 [middle, last) 合并为一个已排序范围 [first, last)。 该算法是稳定的(如果原始两个范围中存在等效元素,则来自第一个范围的元素(保持其原始顺序)将先于来自第二个范围的元素(保持其原始顺序)。
要求:
RandIt 必须满足 ValueSwappable 和 RandomAccessIterator 的要求。
解引用 RandIt 的类型必须满足 MoveAssignable 和 MoveConstructible 的要求。
参数:
first: 第一个已排序范围的起始迭代器。
middle: 第一个已排序范围的结束迭代器,也是第二个已排序范围的起始迭代器
last: 第二个已排序范围的结束迭代器
comp: 比较函数对象,如果第一个参数在第二个参数之前排序,则返回 true。
uninitialized, uninitialized_len: 原始存储起始于 "uninitialized",能够容纳 "uninitialized_len" 个 iterator_traits<RandIt>::value_type 类型的元素。 当 uninitialized_len 为 min(std::distance(first, middle), std::distance(middle, last)) 时,性能最佳。
抛出: 如果 comp 抛出异常,或者解引用 RandIt 的类型的移动构造函数、移动赋值运算符或 swap 操作抛出异常。
复杂度: 始终为 K x O(N) 次比较和移动赋值/构造/交换。 当 uninitialized_len 为 min(std::distance(first, middle), std::distance(middle, last)) 时,比较和数据移动的常数因子最小。 当 uninitialized_len 为 ceil(sqrt(std::distance(first, last)))*2 时,可以获得相当不错的性能。
注意: 实验性实现,尚未准备好用于生产环境。