• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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``
11template<
12    class SinglePassRange1,
13    class SinglePassRange2,
14    class OutputIterator
15    >
16OutputIterator merge(const SinglePassRange1& rng1,
17                     const SinglePassRange2& rng2,
18                     OutputIterator          out);
19
20template<
21    class SinglePassRange1,
22    class SinglePassRange2,
23    class OutputIterator,
24    class BinaryPredicate
25    >
26OutputIterator 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
36The two versions of `merge` differ by how they compare the elements.
37
38The 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
42Defined 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
84Linear. 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
89