HOME
LIBRARY
PRODUCTS
FORUMS
CART
LoginOr login with:
inplace_merge
Merges two consecutive sorted ranges
Definition
The inplace_merge() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.Interface
#include <algorithm> template < class BidirectionalIterator > void inplace_merge( BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last ); template < class BidirectionalIterator, class Predicate > void inplace_merge( BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Predicate comp );Parameters:
| Parameter | Description |
|---|---|
| first | A bidirectional iterator addressing the position of the first element in the first of two consecutive sorted ranges to be combined and sorted into a single range |
| middle | A bidirectional iterator addressing the position of the first element in the second of two consecutive sorted ranges to be combined and sorted into a single range |
| last | A bidirectional iterator addressing the position one past the last element in the second of two consecutive sorted ranges to be combined and sorted into a single range |
| comp | User-defined predicate function object that defines the sense in which one element is greater than another. The binary predicate takes two arguments and should return true when the first element is less than the second element and false otherwise |
Description
Inplace_merge function 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 compares objects using operator<, and the second compares objects using a function object comp.Complexity
The complexity is linear; performs(last - first) - 1 if enough additional memory is available.
Otherwise, is N log(N), where
N = last - first.Example:
Example - inplace_merge function
Problem
This program illustrates the use of the STL inplace_merge() algorithm
(default version) to merge two sorted ranges of integer values in the
same vector into a single sorted range of values within that same vector.
Workings
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int a[] = {1, 3 , 5, 7, 9, 11, 13, 2, 4, 6, 8, 10}; vector<int> v(a, a+12); cout <<"\nHere are the contents of v:\n"; for (vector<int>::size_type i=0; i<v.size(); i++) cout <<v.at(i)<<" "; inplace_merge(v.begin(), v.begin()+7, v.end()); cout <<"\nNow we perform the "in place merge"."; cout <<"\nHere are the revised contents of v:\n"; for (vector<int>::size_type i=0; i<v.size(); i++) cout <<v.at(i)<<" "; return 0; }
Solution
Output:
Here are the contents of v:
1 3 5 7 9 11 13 2 4 6 8 10 Now we perform the "in place merge".
Here are the revised contents of v:
1 2 3 4 5 6 7 8 9 10 11 13
1 3 5 7 9 11 13 2 4 6 8 10 Now we perform the "in place merge".
Here are the revised contents of v:
1 2 3 4 5 6 7 8 9 10 11 13
References
You must login to leave a messge