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.
Return Value
None.
Complexity
The complexity is linear; performs (last - first) - 1 if enough additional memory is available.
Otherwise, is N log(N), where N = last - first.
References
Example 1
ProblemThis 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;
}
SolutionOutput:
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
Example 2
ProblemThis program illustrates the use of the STL inplace_merge() algorithm (extended version) to merge two ordered ranges of integer values in the same vector into a single ordered range of values within that same vector. The order of values is determined by one value preceding another if and only if the first has a smaller digit sum than the second.
Workings#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* Tests if one integer has a smaller digit sum than another.
i1 and i2 have been initialized and i1, i2 are both > 0.
Returns true if sum of the digits in i1 is < sum of digits in i2, and otherwise returns false. */
bool hasSmallerDigitSum (int i1, int i2)
{
int digitSum1 = 0;
while (i1 != 0)
{
digitSum1 += i1 % 10;
i1 /= 10;
}
int digitSum2 = 0;
while (i2 != 0)
{
digitSum2 += i2 % 10;
i2 /= 10;
}
return digitSum1 < digitSum2;
}
int main()
{
int a[] = {11, 41 , 36, 59, 98, 21, 13, 6, 52, 44, 28, 69};
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)<<" ";
cout <<"\nNote that the first five values form the first range, "
"\nand the rest of the values form the second range.";
inplace_merge(v.begin(), v.begin()+5, v.end(), hasSmallerDigitSum);
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;
}
SolutionOutput:
Here are the contents of v:
11 41 36 59 98 21 13 6 52 44 28 69
Note that the first five values form the first range,
and the rest of the values form the second range.
Now we perform the "in place merge".
Here are the revised contents of v:
11 21 13 41 6 52 44 36 28 59 69 98
See Also
