std::merge
From Cppreference
| Defined in header <algorithm>
|
||
| template< class InputIterator1, class InputIterator2, class OutputIterator >
OutputIterator merge( InputIterator1 first1, InputIterator1 last1, |
(1) | |
| template< class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator merge( InputIterator1 first1, InputIterator1 last1, |
(2) | |
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 |
[edit] 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 which returns true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following:
The signature does not need to have const &, but the function must not modify the objects passed to it. |
|||||||||
[edit] Return value
an output iterator to element past the last element copied.
[edit] Complexity
At most std::distance(first1, last1) + std::distance(first2, last2) + 1 comparisons.
[edit] Equivalent function
| First version |
|---|
template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2 OutputIterator 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 InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2 OutputIterator 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); } |
[edit] 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
[edit] See also
|
sorts the first N elements of a range (function template) |
|
|
sorts a range into ascending order (function template) |
|
|
sorts a range of elements while preserving order between equal elements (function template) |
|