Name
merge function template — Merges sorted ranges
Synopsis
template<typename InIter1, typename InIter2, typename OutIter> OutIter merge(InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result); template<typename InIter1, typename InIter2, typename OutIter, typename Compare> OutIter merge(InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, OutIter result, Compare comp);
The merge
function template
merges the sorted ranges [first1
,
last1
) and [first2
, last2
), copying the results into the
sequence that starts with result
.
You must ensure that the destination has enough room for the entire
merged sequence.
The return value is the end value of the destination iterator,
that is, result
+ (last1
- first1
) + (last2
- first2
).
The destination range must not overlap either of the input ranges.
The merge is stable, so elements preserve their relative order. Equivalent elements are copied, so elements from the first range come before elements from the second range.
The first form compares values using the <
operator. The second form calls
comp(*iter1
, *iter2)
.
Technical Notes
Let length1 = last1 - first1 and length2 = last2 - first2.
Precondition: !(*(i + 1) < *i) for all i in [first1, last1 - 1) and !(*(j + 1) < *j) for all j in [first2, last2 - 1).
Postcondition: !(*(i + 1) < *i) for all i in [result, result + length1 + length2 - 1).
Complexity is linear: at most, length1 + length2 - 1 comparisons are performed.
Get C++ In a Nutshell now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.