Function template adaptive_merge

boost::movelib::adaptive_merge

Synopsis

// 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, 
                      std::size_t uninitialized_len = 0);

Description

Effects: Merges two consecutive sorted ranges [first, middle) and [middle, last) into one sorted range [first, last) according to the given comparison function comp. The algorithm is stable (if there are equivalent elements in the original two ranges, the elements from the first range (preserving their original order) precede the elements from the second range (preserving their original order).

Requires:

RandIt must meet the requirements of ValueSwappable and RandomAccessIterator.
The type of dereferenced RandIt must meet the requirements of MoveAssignable and MoveConstructible.

Parameters:

first: the beginning of the first sorted range.
middle: the end of the first sorted range and the beginning of the second
last: the end of the second sorted range
comp: comparison function object which returns true if the first argument is is ordered before the second.
uninitialized, uninitialized_len: raw storage starting on "uninitialized", able to hold "uninitialized_len" elements of type iterator_traits<RandIt>::value_type. Maximum performance is achieved when uninitialized_len is min(std::distance(first, middle), std::distance(middle, last)).

Throws: If comp throws or the move constructor, move assignment or swap of the type of dereferenced RandIt throws.

Complexity: Always K x O(N) comparisons and move assignments/constructors/swaps. Constant factor for comparisons and data movement is minimized when uninitialized_len is min(std::distance(first, middle), std::distance(middle, last)). Pretty good enough performance is achieved when uninitialized_len is ceil(sqrt(std::distance(first, last)))*2.

Caution: Experimental implementation, not production-ready.

Boost C++ Libraries