ceph/src/boost/libs/range/doc/reference/algorithm/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:merge merge]
   7
   8 [heading Prototype]
   9
  10 ``
  11 template<
  12     class SinglePassRange1,
  13     class SinglePassRange2,
  14     class OutputIterator
  15     >
  16 OutputIterator merge(const SinglePassRange1& rng1,
  17                      const SinglePassRange2& rng2,
  18                      OutputIterator          out);
  19
  20 template<
  21     class SinglePassRange1,
  22     class SinglePassRange2,
  23     class OutputIterator,
  24     class BinaryPredicate
  25     >
  26 OutputIterator merge(const SinglePassRange1& rng1,
  27                      const SinglePassRange2& rng2,
  28                      OutputIterator          out,
  29                      BinaryPredicate         pred);
  30 ``
  31
  32 [heading Description]
  33
  34 `merge` combines two sorted ranges `rng1` and `rng2` into a single sorted range by copying elements. `merge` is stable. The return value is `out + distance(rng1) + distance(rng2)`.
  35
  36 The two versions of `merge` differ by how they compare the elements.
  37
  38 The non-predicate version uses the `operator<()` for the range value type. The predicate version uses the predicate instead of `operator<()`.
  39
  40 [heading Definition]
  41
  42 Defined in the header file `boost/range/algorithm/merge.hpp`
  43
  44 [heading Requirements]
  45
  46 [*For the non-predicate version:]
  47
  48 * `SinglePassRange1` is a model of the __single_pass_range__ Concept.
  49 * `SinglePassRange2` is a model of the __single_pass_range__ Concept.
  50 * `range_value<SinglePassRange1>::type` is the same as `range_value<SinglePassRange2>::type`.
  51 * `range_value<SinglePassRange1>::type` is a model of the `LessThanComparableConcept`.
  52 * The ordering on objects of `range_value<SinglePassRange1>::type` is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
  53 * `range_value<SinglePassRange1>::type` is convertible to a type in `OutputIterator`'s set of value types.
  54
  55 [*For the predicate version:]
  56
  57 * `SinglePassRange1` is a model of the __single_pass_range__ Concept.
  58 * `SinglePassRange2` is a model of the __single_pass_range__ Concept.
  59 * `range_value<SinglePassRange1>::type` is the same as `range_value<SinglePassRange2>::type`.
  60 * `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
  61 * `SinglePassRange1`'s value type is convertible to both `BinaryPredicate`'s argument types.
  62 * `range_value<SinglePassRange1>::type` is convertible to a type in `OutputIterator`'s set of value types.
  63
  64 [heading Precondition:]
  65
  66 [heading For the non-predicate version:]
  67
  68 * The elements of `rng1` are in ascending order. That is, for each adjacent element pair `[x,y]` of `rng1`, `y < x == false`.
  69 * The elements of `rng2` are in ascending order. That is, for each adjacent element pair `[x,y]` of `rng2`, `y < x == false`.
  70 * The ranges `rng1` and `[out, out + distance(rng1) + distance(rng2))` do not overlap.
  71 * The ranges `rng2` and `[out, out + distance(rng1) + distance(rng2))` do not overlap.
  72 * `[out, out + distance(rng1) + distance(rng2))` is a valid range.
  73
  74 [heading For the predicate version:]
  75
  76 * The elements of `rng1` are in ascending order. That is, for each adjacent element pair `[x,y]`, of `rng1`, `pred(y, x) == false`.
  77 * The elements of `rng2` are in ascending order. That is, for each adjacent element pair `[x,y]`, of `rng2`, `pred(y, x) == false`.
  78 * The ranges `rng1` and `[out, out + distance(rng1) + distance(rng2))` do not overlap.
  79 * The ranges `rng2` and `[out, out + distance(rng1) + distance(rng2))` do not overlap.
  80 * `[out, out + distance(rng1) + distance(rng2))` is a valid range.
  81
  82 [heading Complexity]
  83
  84 Linear. There are no comparisons if both `rng1` and `rng2` are empty, otherwise at most `distance(rng1) + distance(rng2) - 1` comparisons.
  85
  86 [endsect]
  87
  88