merge

Prototype

template<
    class SinglePassRange1,
    class SinglePassRange2,
    class OutputIterator
    >
OutputIterator merge(const SinglePassRange1& rng1,
                     const SinglePassRange2& rng2,
                     OutputIterator          out);

template<
    class SinglePassRange1,
    class SinglePassRange2,
    class OutputIterator,
    class BinaryPredicate
    >
OutputIterator merge(const SinglePassRange1& rng1,
                     const SinglePassRange2& rng2,
                     OutputIterator          out,
                     BinaryPredicate         pred);

Description

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).

The two versions of merge differ by how they compare the elements.

The non-predicate version uses the operator<() for the range value type. The predicate version uses the predicate instead of operator<().

Definition

Defined in the header file boost/range/algorithm/merge.hpp

Requirements

For the non-predicate version:

SinglePassRange1 is a model of the Single Pass Range Concept.
SinglePassRange2 is a model of the Single Pass Range Concept.
range_value<SinglePassRange1>::type is the same as range_value<SinglePassRange2>::type.
range_value<SinglePassRange1>::type is a model of the LessThanComparableConcept.
The ordering on objects of range_value<SinglePassRange1>::type is a strict weak ordering, as defined in the LessThanComparableConcept requirements.
range_value<SinglePassRange1>::type is convertible to a type in OutputIterator's set of value types.

For the predicate version:

SinglePassRange1 is a model of the Single Pass Range Concept.
SinglePassRange2 is a model of the Single Pass Range Concept.
range_value<SinglePassRange1>::type is the same as range_value<SinglePassRange2>::type.
BinaryPredicate is a model of the StrictWeakOrderingConcept.
SinglePassRange1's value type is convertible to both BinaryPredicate's argument types.
range_value<SinglePassRange1>::type is convertible to a type in OutputIterator's set of value types.

Precondition:

For the non-predicate version:

The elements of rng1 are in ascending order. That is, for each adjacent element pair [x,y] of rng1, y < x == false.
The elements of rng2 are in ascending order. That is, for each adjacent element pair [x,y] of rng2, y < x == false.
The ranges rng1 and [out, out + distance(rng1) + distance(rng2)) do not overlap.
The ranges rng2 and [out, out + distance(rng1) + distance(rng2)) do not overlap.
[out, out + distance(rng1) + distance(rng2)) is a valid range.

For the predicate version:

The elements of rng1 are in ascending order. That is, for each adjacent element pair [x,y], of rng1, pred(y, x) == false.
The elements of rng2 are in ascending order. That is, for each adjacent element pair [x,y], of rng2, pred(y, x) == false.
The ranges rng1 and [out, out + distance(rng1) + distance(rng2)) do not overlap.
The ranges rng2 and [out, out + distance(rng1) + distance(rng2)) do not overlap.
[out, out + distance(rng1) + distance(rng2)) is a valid range.

Complexity

Linear. There are no comparisons if both rng1 and rng2 are empty, otherwise at most distance(rng1) + distance(rng2) - 1 comparisons.