std::merge
Defined in header
<algorithm>
|
||
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt merge( InputIt1 first1, InputIt1 last1, |
(1) | |
template< class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt merge( InputIt1 first1, InputIt1 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.
The behavior is undefined if the destination range overlaps either of the input ranges (the input ranges may overlap each other).
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 object (i.e. an object that satisfies the requirements of Compare ) which returns true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1 &a, const Type2 &b); The signature does not need to have const &, but the function object must not modify the objects passed to it. |
Type requirements | ||
-
InputIt1 must meet the requirements of InputIterator .
|
||
-
InputIt2 must meet the requirements of InputIterator .
|
||
-
OutputIt must meet the requirements of OutputIterator .
|
[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] 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); } |
[edit] Example
#include <iostream> #include <iterator> #include <algorithm> #include <vector> #include <random> int main() { // fill the vectors with random numbers std::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))); // 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::vector<int> dst; 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'; }
Possible output:
v1 : 0 1 3 4 4 5 5 8 8 9 v2 : 0 2 2 3 6 6 8 8 8 9 dst: 0 0 1 2 2 3 3 4 4 5 5 6 6 8 8 8 8 8 9 9
[edit] See also
merges two ordered ranges in-place (function template) |
|
sorts a range into ascending order (function template) |
|
sorts a range of elements while preserving order between equal elements (function template) |