Function template adaptive_sort

boost::movelib::adaptive_sort

Synopsis

// 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 iterator_traits< RandIt >::size_type uninitialized_len);

Description

Effects: Sorts the elements in the range [first, last) in ascending order according to comparison functor "comp". The sort is stable (order of equal elements is guaranteed to be preserved). Performance is improved if additional raw storage is provided.

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, last: the range of elements to sort
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 ceil(std::distance(first, last)/2).

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

Complexity: Always K x O(Nxlog(N)) comparisons and move assignments/constructors/swaps. Comparisons are close to minimum even with no additional memory. Constant factor for data movement is minimized when uninitialized_len is ceil(std::distance(first, last)/2). Pretty good enough performance is achieved when ceil(sqrt(std::distance(first, last)))*2.

Caution: Experimental implementation, not production-ready.

Boost C++ Libraries