## merge
## Prototype
template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp); ## Description
The two versions of ## DefinitionDefined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h. ## Requirements on typesFor the first version: -
`InputIterator1` is a model of InputIterator. -
`InputIterator2` is a model of InputIterator. -
`InputIterator1` 's value type is the same type as`InputIterator2` 's value type. -
`InputIterator1` 's value type is a model of LessThanComparable. -
The ordering on objects of
`InputIterator1` 's value type is a*strict weak ordering*, as defined in the LessThanComparable requirements. -
`InputIterator1` 's value type is convertible to a type in`OutputIterator` 's set of value types.
For the second version: -
`InputIterator1` is a model of InputIterator. -
`InputIterator2` is a model of InputIterator. -
`InputIterator1` 's value type is the same type as`InputIterator2` 's value type. -
`StrictWeakOrdering` is a model of StrictWeakOrdering. -
`InputIterator1` 's value type is convertible to`StrictWeakOrdering` 's argument type. -
`InputIterator1` 's value type is convertible to a type in`OutputIterator` 's set of value types.
## PreconditionsFor the first version: -
`[first1, last1)` is a valid range. -
`[first1, last1)` is in ascending order. That is, for every pair of iterators`i` and`j` in`[first1, last1)` such that`i` precedes`j` ,`*j < *i` is`false` . -
`[first2, last2)` is a valid range. -
`[first2, last2)` is in ascending order. That is, for every pair of iterators`i` and`j` in`[first2, last2)` such that`i` precedes`j` ,`*j < *i` is`false` . -
The ranges
`[first1, last1)` and`[result, result + (last1 - first1) + (last2 - first2))` do not overlap. -
The ranges
`[first2, last2)` and`[result, result + (last1 - first1) + (last2 - first2))` do not overlap. -
There is enough space to hold all of the elements being copied. More formally, the requirement is that
`[result, result + (last1 - first1) + (last2 - first2))` is a valid range.
For the second version: -
`[first1, last1)` is a valid range. -
`[first1, last1)` is in ascending order. That is, for every pair of iterators`i` and`j` in`[first1, last1)` such that`i` precedes`j` ,`comp(*j, *i)` is`false` . -
`[first2, last2)` is a valid range. -
`[first2, last2)` is in ascending order. That is, for every pair of iterators`i` and`j` in`[first2, last2)` such that`i` precedes`j` ,`comp(*j, *i)` is`false` . -
The ranges
`[first1, last1)` and`[result, result + (last1 - first1) + (last2 - first2))` do not overlap. -
The ranges
`[first2, last2)` and`[result, result + (last1 - first1) + (last2 - first2))` do not overlap. -
There is enough space to hold all of the elements being copied. More formally, the requirement is that
`[result, result + (last1 - first1) + (last2 - first2))` is a valid range.
## ComplexityLinear. No comparisons if both ## Exampleint main() { int A1[] = { 1, 3, 5, 7 }; int A2[] = { 2, 4, 6, 8 }; const int N1 = sizeof(A1) / sizeof(int); const int N2 = sizeof(A2) / sizeof(int); merge(A1, A1 + N1, A2, A2 + N2, ostream_iterator<int>(cout, " ")); // The output is "1 2 3 4 5 6 7 8" } ## Notes[1] Note that you may use an ordering that is a strict weak ordering but not a total ordering; that is, there might be values ## See also |