ceph/src/boost/libs/range/doc/reference/algorithm/inplace_merge.qbk

   1 [/
   2     Copyright 2010 Neil Groves
   3     Distributed under the Boost Software License, Version 1.0.
   4     (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5 /]
   6 [section:inplace_merge inplace_merge]
   7
   8 [heading Prototype]
   9
  10 ``
  11 template<class BidirectionalRange>
  12 BidirectionalRange&
  13 inplace_merge( BidirectionalRange& rng,
  14                typename range_iterator<BidirectionalRange>::type middle );
  15
  16 template<class BidirectionalRange>
  17 const BidirectionalRange&
  18 inplace_merge( const BidirectionalRange& rng,
  19                typename range_iterator<const BidirectionalRange>::type middle );
  20
  21 template<class BidirectionalRange, class BinaryPredicate>
  22 BidirectionalRange&
  23 inplace_merge( BidirectionalRange& rng,
  24                typename range_iterator<BidirectionalRange>::type middle,
  25                BinaryPredicate pred );
  26
  27 template<class BidirectionalRange, class BinaryPredicate>
  28 const BidirectionalRange&
  29 inplace_merge( const BidirectionalRange& rng,
  30                typename range_iterator<const BidirectionalRange>::type middle,
  31                BinaryPredicate pred );
  32 ``
  33
  34 [heading Description]
  35
  36 `inplace_merge` combines two consecutive sorted ranges `[begin(rng), middle)` and `[middle, end(rng))` into a single sorted range `[begin(rng), end(rng))`. That is, it starts with a range `[begin(rng), end(rng))` that consists of two pieces each of which is in ascending order, and rearranges it so that the entire range is in ascending order. `inplace_merge` is stable, meaning both that the relative order of elements within each input range is preserved.
  37
  38 [heading Definition]
  39
  40 Defined in the header file `boost/range/algorithm/inplace_merge.hpp`
  41
  42 [heading Requirements]
  43
  44 [*For the non-predicate version:]
  45
  46 * `BidirectionalRange` is a model of the __bidirectional_range__ Concept.
  47 * `BidirectionalRange` is mutable.
  48 * `range_value<BidirectionalRange>::type` is a model of `LessThanComparableConcept`
  49 * The ordering on objects of `range_type<BidirectionalRange>::type` is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
  50
  51 [*For the predicate version:]
  52 * `BidirectionalRange` is a model of the __bidirectional_range__ Concept.
  53 * `BidirectionalRange` is mutable.
  54 * `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
  55 * `BidirectionalRange`'s value type is convertible to both `BinaryPredicate`'s argument types.
  56
  57 [heading Precondition:]
  58
  59 [heading For the non-predicate version:]
  60
  61 * `middle` is in the range `rng`.
  62 * `[begin(rng), middle)` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `y < x` is `false`.
  63 * `[middle, end(rng))` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `y < x` is `false`.
  64
  65 [heading For the predicate version:]
  66
  67 * `middle` is in the range `rng`.
  68 * `[begin(rng), middle)` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `pred(y,x) == false`.
  69 * `[middle, end(rng))` is in ascending order. That is for each pair of adjacent elements `[x,y]`, `pred(y,x) == false`.
  70
  71 [heading Complexity]
  72
  73 Worst case: `O(N log(N))`
  74
  75 [endsect]
  76
  77