C++ std::inplace_merge with std::vector














































C++ std::inplace_merge with std::vector



Normal Merge algorithm is basically merging to sorted sequences but it has a time and space complexity of O(m+n) where m and n are the sizes of the corresponding sequences.


But std::inplace_merge is different, it does merging within the same container between two ranges [first,middle) and [middle,last) where the ranges must be sorted beforehand.

Since it is inplace that means no additional space is required.


SYNTAX:-


version 1


template <class IteratorLoc>
void inplace_merge (IteratorLoc first, IteratorLoc middle, IteratorLoc last);

version 2

template <class IteratorLoc, class Compare_function>
void inplace_merge (IteratorLoc first, IteratorLoc middle, IteratorLoc last, Compare_function function_name);



PARAMETERS-

first - iterator to the first position of the first range.
middle - iterator of the intial position of the second sorted sequence of the container.
last - iterator of the last position of the second sorted sequence of the container.
function_name - is the function pointer of the bool fucntion which returns true or false after comparision.


COMPLEXTY-

If enough extra memory is available, linear in the distance between first and last: Performs N-1 comparisons and up to twice that many element moves.
Otherwise, up to linearithmic: Performs up to N*log(N) element comparisons (where N is the distance above), and up to that many element swaps.


IN THIS ARTICLE WE ARE SEEING HOW TO USE THIS ALGORITH HEADER FUCNTION ON vector CONTAINER.


code example :-

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// inplace_merge example
#include <iostream>
#include <algorithm> // std::inplace_merge, std::sort, std::copy
#include <vector> // std::vector


//including this to able to use all the required things from standard namespace
using namespace std;

//bool function for comparison
bool myfunction (int i,int j) { return (i<j); }

int main () {

int first_half[] = {50,1,5,3,15};
int second_half[] = {0,-20,9,20,777};
vector<int> v1;
vector<int> v2;

sort (first_half,first_half+5);
sort (second_half,second_half+5);

//pushing values in the vector container v1
for (int i = 0; i <sizeof(first_half)/sizeof(int); i++)
{
v1.push_back(first_half[i]);
}
for (int i = 0; i <sizeof(second_half)/sizeof(int); i++)
{
v1.push_back(second_half[i]);
}


//using version 1
inplace_merge (v1.begin(),v1.begin()+5,v1.end());
cout << "The resulting vector contains: using version 1";
for (int i=0;i<10;i++)
{
cout << ' ' << v1[i];
}


//pushing values in the vector container v2
for (int i = 0; i <sizeof(first_half)/sizeof(int); i++)
{
v2.push_back(first_half[i]);
}
for (int i = 0; i <sizeof(second_half)/sizeof(int); i++)
{
v2.push_back(second_half[i]);
}


//using version 2
inplace_merge (v2.begin(),v2.begin()+5,v2.end(),myfunction);
cout << "\nThe resulting vector contains: using version 2";
for (int i=0;i<10;i++)
{
cout << ' ' << v2[i];
}

return 0;
}







NOTE :- cant be done with other container as there is no implementation of operator +.


Comments