Merges two sorted ranges[first1, last1) and[first2, last2) into one sorted range beginning atd_first.

This merge function is stable, which means that for equivalent elements in the original two ranges, the elements from the first range (preserving their original order) precede the elements from the second range (preserving their original order).

If the output range overlaps with[first1, last1) or[first2, last2), the behavior is undefined.

[edit]Parameters

[edit]Return value

An output iterator to element past the last element copied.

[edit]Complexity

Given\(\scriptsize N_1\)N1 asstd::distance(first1, last1) and\(\scriptsize N_2\)N2 asstd::distance(first2, last2):

[edit]Exceptions

The overloads with a template parameter namedExecutionPolicy report errors as follows:

• If execution of a function invoked as part of the algorithm throws an exception andExecutionPolicy is one of thestandard policies,std::terminate is called. For any otherExecutionPolicy, the behavior is implementation-defined.
• If the algorithm fails to allocate memory,std::bad_alloc is thrown.

[edit]Possible implementation

See also the implementations inlibstdc++ andlibc++.

template<class InputIt1,class InputIt2,class OutputIt>OutputIt merge(InputIt1 first1, InputIt1 last1,               InputIt2 first2, InputIt2 last2,               OutputIt d_first){for(; first1!= last1;++d_first){if(first2== last2)returnstd::copy(first1, last1, d_first); if(*first2<*first1){*d_first=*first2;++first2;}else{*d_first=*first1;++first1;}}returnstd::copy(first2, last2, d_first);}

template<class InputIt1,class InputIt2,class OutputIt,class Compare>OutputIt merge(InputIt1 first1, InputIt1 last1,               InputIt2 first2, InputIt2 last2,               OutputIt d_first, Compare comp){for(; first1!= last1;++d_first){if(first2== last2)returnstd::copy(first1, last1, d_first); if(comp(*first2,*first1)){*d_first=*first2;++first2;}else{*d_first=*first1;++first1;}}returnstd::copy(first2, last2, d_first);}

[edit]Notes

This algorithm performs a similar task asstd::set_union does. Both consume two sorted input ranges and produce a sorted output with elements from both inputs. The difference between these two algorithms is with handling values from both input ranges which compare equivalent (see notes onLessThanComparable). If any equivalent values appearedn times in the first range andm times in the second,std::merge would output alln+ m occurrences whereasstd::set_union would outputstd::max(n, m) ones only. Sostd::merge outputs exactlystd::distance(first1, last1)+std::distance(first2, last2) values andstd::set_union may produce fewer.

[edit]Example

#include <algorithm>#include <functional>#include <iostream>#include <iterator>#include <random>#include <vector> auto print=[](constauto rem,constauto& v){std::cout<< rem;std::copy(v.begin(), v.end(),std::ostream_iterator<int>(std::cout," "));std::cout<<'\n';}; int main(){// fill the vectors with random numbersstd::random_device rd;std::mt19937 mt(rd());std::uniform_int_distribution<> dis(0,9); std::vector<int> v1(10), v2(10);std::generate(v1.begin(), v1.end(),std::bind(dis,std::ref(mt)));std::generate(v2.begin(), v2.end(),std::bind(dis,std::ref(mt)));     print("Originally:\nv1: ", v1);    print("v2: ", v2); std::sort(v1.begin(), v1.end());std::sort(v2.begin(), v2.end());     print("After sorting:\nv1: ", v1);    print("v2: ", v2); // mergestd::vector<int> dst;    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),std::back_inserter(dst));     print("After merging:\ndst: ", dst);}

Originally:v1: 2 6 5 7 4 2 2 6 7 0v2: 8 3 2 5 0 1 9 6 5 0After sorting:v1: 0 2 2 2 4 5 6 6 7 7v2: 0 0 1 2 3 5 5 6 8 9After merging:dst: 0 0 0 1 2 2 2 2 3 4 5 5 5 6 6 6 7 7 8 9

[edit]Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

[edit]See also

• In other languages

• Deutsch
• Español
• Français
• Italiano
• 日本語
• Português
• Русский
• 中文