ceph/src/boost/libs/move/include/boost/move/algo/adaptive_sort.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2015-2016.
   4 // Distributed under the Boost Software License, Version 1.0.
   5 // (See accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt)
   7 //
   8 // See http://www.boost.org/libs/move for documentation.
   9 //
  10 //////////////////////////////////////////////////////////////////////////////
  11
  12 #ifndef BOOST_MOVE_ADAPTIVE_SORT_HPP
  13 #define BOOST_MOVE_ADAPTIVE_SORT_HPP
  14
  15 #include <boost/move/detail/config_begin.hpp>
  16 #include <boost/move/algo/detail/adaptive_sort_merge.hpp>
  17
  18 namespace boost {
  19 namespace movelib {
  20
  21 //! <b>Effects</b>: Sorts the elements in the range [first, last) in ascending order according
  22 //!   to comparison functor "comp". The sort is stable (order of equal elements
  23 //!   is guaranteed to be preserved). Performance is improved if additional raw storage is
  24 //!   provided.
  25 //!
  26 //! <b>Requires</b>:
  27 //!   - RandIt must meet the requirements of ValueSwappable and RandomAccessIterator.
  28 //!   - The type of dereferenced RandIt must meet the requirements of MoveAssignable and MoveConstructible.
  29 //!
  30 //! <b>Parameters</b>:
  31 //!   - first, last: the range of elements to sort
  32 //!   - comp: comparison function object which returns true if the first argument is is ordered before the second.
  33 //!   - uninitialized, uninitialized_len: raw storage starting on "uninitialized", able to hold "uninitialized_len"
  34 //!      elements of type iterator_traits<RandIt>::value_type. Maximum performance is achieved when uninitialized_len
  35 //!      is ceil(std::distance(first, last)/2).
  36 //!
  37 //! <b>Throws</b>: If comp throws or the move constructor, move assignment or swap of the type
  38 //!   of dereferenced RandIt throws.
  39 //!
  40 //! <b>Complexity</b>: Always K x O(Nxlog(N)) comparisons and move assignments/constructors/swaps.
  41 //!   Comparisons are close to minimum even with no additional memory. Constant factor for data movement is minimized
  42 //!   when uninitialized_len is ceil(std::distance(first, last)/2). Pretty good enough performance is achieved when
  43 //!   ceil(sqrt(std::distance(first, last)))*2.
  44 //!
  45 //! <b>Caution</b>: Experimental implementation, not production-ready.
  46 template<class RandIt, class Compare>
  47 void adaptive_sort( RandIt first, RandIt last, Compare comp
  48                , typename iterator_traits<RandIt>::value_type* uninitialized = 0
  49                , std::size_t uninitialized_len = 0)
  50 {
  51    typedef typename iterator_traits<RandIt>::size_type  size_type;
  52    typedef typename iterator_traits<RandIt>::value_type value_type;
  53
  54    ::boost::movelib::detail_adaptive::adaptive_xbuf<value_type> xbuf(uninitialized, uninitialized_len);
  55    ::boost::movelib::detail_adaptive::adaptive_sort_impl(first, size_type(last - first), comp, xbuf);
  56 }
  57
  58 }  //namespace movelib {
  59 }  //namespace boost {
  60
  61 #include <boost/move/detail/config_end.hpp>
  62
  63 #endif   //#define BOOST_MOVE_ADAPTIVE_SORT_HPP