Difference between revisions of "cpp/algorithm/merge"
m (Update links.) |
m (Avoid -Wconversion warnings) |
||
| Line 100: | Line 100: | ||
// fill the vectors | // fill the vectors | ||
for (std::size_t idx = 0; idx < items; ++idx) { | for (std::size_t idx = 0; idx < items; ++idx) { | ||
| − | v1.push_back(std::rand()%items); | + | v1.push_back(static_cast<int>(std::rand()%items)); |
| − | v2.push_back(std::rand()%items); | + | v2.push_back(static_cast<int>(std::rand()%items)); |
} | } | ||
Revision as of 17:39, 19 December 2013
| 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.
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
Template:par req concept Template:par req concept Template:par req concept | ||
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(static_cast<int>(std::rand()%items)); v2.push_back(static_cast<int>(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
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) |
