std::merge
Template:ddcl list begin <tr class="t-dsc-header">
<td><algorithm>
<td></td> <td></td> </tr> <tr class="t-dcl ">
<td >OutputIt merge( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
<td > (1) </td> <td class="t-dcl-nopad"> </td> </tr> <tr class="t-dcl ">
<td >OutputIt merge( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
<td > (2) </td> <td class="t-dcl-nopad"> </td> </tr> Template:ddcl list end
Merges two sorted ranges [first1, last1) and [first2, last2) into one sorted range beginning at d_first. The first version uses operator< to compare the elements, the second version uses the given comparison function comp. The relative order of equivalent elements is preserved.
Contents |
Parameters
| first1, last1 | - | the first range of elements to merge |
| first2, last2 | - | the second range of elements to merge |
| d_first | - | the beginning of the destination range |
| comp | - | comparison function object (i.e. an object that satisfies the requirements of Compare) which returns true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1& a, const Type2& b); While the signature does not need to have const&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) |
| Type requirements | ||
-InputIt1 must meet the requirements of LegacyInputIterator.
| ||
-InputIt2 must meet the requirements of LegacyInputIterator.
| ||
-OutputIt must meet the requirements of LegacyOutputIterator.
| ||
Return value
An output iterator to element past the last element copied.
Complexity
At most std::distance(first1, last1) + std::distance(first2, last2) + 1 comparisons.
Possible implementation
| First version |
|---|
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) { return std::copy(first1, last1, d_first); } if (*first2 < *first1) { *d_first = *first2; ++first2; } else { *d_first = *first1; ++first1; } } return std::copy(first2, last2, d_first); } |
| Second version |
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) { return std::copy(first1, last1, d_first); } if (comp(*first2, *first1)) { *d_first = *first2; ++first2; } else { *d_first = *first1; ++first1; } } return std::copy(first2, last2, d_first); } |
Example
#include <iostream> #include <iterator> #include <cstdlib> #include <algorithm> #include <vector> int main() { const std::size_t items = 10; std::vector<int> v1, v2, dst; // fill the vectors for (std::size_t idx = 0; idx < items; ++idx) { v1.push_back(std::rand()%items); v2.push_back(std::rand()%items); } // sort std::sort(v1.begin(), v1.end()); std::sort(v2.begin(), v2.end()); // output v1 std::cout << "v1 : "; std::copy(v1.begin(), v1.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; // output v2 std::cout << "v2 : "; std::copy(v2.begin(), v2.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; // merge std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst)); // output std::cout << "dst: "; std::copy(dst.begin(), dst.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; }
Output:
v1 : 0 0 2 2 3 3 3 6 7 9 v2 : 1 2 5 5 6 6 6 6 7 9 dst: 0 0 1 2 2 2 3 3 3 5 5 6 6 6 6 6 7 7 9 9
