
ALINK="#ff0000">
merge
PrototypeMerge is an overloaded name: there are actually two merge functions.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); DescriptionMerge combines two sorted ranges [first1, last1) and [first2, last2) into a single sorted range. That is, it copies elements from [first1, last1) and [first2, last2) into [result, result + (last1  first1) + (last2  first2)) such that the resulting range is in ascending order. Merge is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent [1] elements in both input ranges the element from the first range precedes the element from the second. The return value is result + (last1  first1) + (last2  first2).The two versions of merge differ in how elements are compared. The first version uses operator<. That is, the input ranges and the output range satisfy the condition that for every pair of iterators i and j such that i precedes j, *j < *i is false. The second version uses the function object comp. That is, the input ranges and the output range satisfy the condition that for every pair of iterators i and j such that i precedes j, comp(*j, *i) is false. DefinitionDefined in the standard header algorithm, and in the nonstandard backwardcompatibility header algo.h.Requirements on typesFor the first version:
PreconditionsFor the first version:
ComplexityLinear. No comparisons if both [first1, last1) and [first2, last2) are empty ranges, otherwise at most (last1  first1) + (last2  first2)  1 comparisons.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 x and y such that x < y, x > y, and x == y are all false. (See the LessThan Comparable requirements for a more complete discussion.) Two elements x and y are equivalent if neither x < y nor y < x. If you're using a total ordering, however (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same. See alsoinplace_merge, set_union, sortCopyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation
