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
| This section is incomplete |
[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) | |
