std::inplace_merge
Defined in header
<algorithm>
|
||
template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last ); |
(1) | |
template< class BidirIt, class Compare>
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last, Compare comp ); |
(2) | |
Merges two consecutive sorted ranges [first, middle)
and [middle, last)
into one sorted range [first, last)
. The order of equal elements is guaranteed to be preserved. The first version uses operator< to compare the elements, the second version uses the given comparison function comp
.
Contents |
[edit] Parameters
first | - | the beginning of the first sorted range |
middle | - | the end of the first sorted range and the beginning of the second |
last | - | the end of the second sorted 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 | ||
-
BidirIt must meet the requirements of ValueSwappable and BidirectionalIterator .
|
||
-The type of dereferenced BidirIt must meet the requirements of MoveAssignable and MoveConstructible .
|
[edit] Return value
(none)
[edit] Complexity
Exactly N-1 comparisons if enough additional memory is available, otherwise N·log(N) where N = std::distance(first, last).
[edit] Notes
This function attempts to allocate a temporary buffer, typically by calling std::get_temporary_buffer. If the allocation fails, the less efficient algorithm is chosen.
[edit] Example
The following code is an implementation of merge sort.
#include <vector> #include <iostream> #include <algorithm> template<class Iter> void merge_sort(Iter first, Iter last) { if (last - first > 1) { Iter middle = first + (last - first) / 2; merge_sort(first, middle); merge_sort(middle, last); std::inplace_merge(first, middle, last); } } int main() { std::vector<int> v{8, 2, -2, 0, 11, 11, 1, 7, 3}; merge_sort(v.begin(), v.end()); for(auto n : v) { std::cout << n << ' '; } std::cout << '\n'; }
Output:
-2 0 1 2 3 7 8 11 11
[edit] See also
merges two sorted ranges (function template) |
|
sorts a range into ascending order (function template) |
|
sorts a range of elements while preserving order between equal elements (function template) |
|
(parallelism TS)
|
parallelized version of std::inplace_merge (function template) |