C++ Algorithm merge
The merge function in C++ Algorithm is employed to combine two sorted intervals [first1, last1) and [first2, last2) into a single sorted range that starts at the specified result position.
Elements can be compared using the < operator in the initial version or by utilizing the specified binary comparison function comp in the alternate version.
Syntax
default(1) template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result);
custom (2) template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
Parameter
An input iterator pointing to the initial element in the initial sorted origin sequence that will be combined.
last: An input iterator indicating the element just beyond the last in the initial sorted source sequence intended for merging.
The iterator named first2 points to the initial element within the subsequent sorted origin sequence that will be merged.
An input iterator pointing to the element preceding the final element in the second sorted origin sequence to be merged.
The comp function is a custom binary predicate that evaluates two arguments and outputs true if they are in the correct order, otherwise false. This function adheres to the strict weak ordering principle for arranging the elements.
val : A value representing the maximum limit for comparing the elements within the specified range.
An output iterator points to the initial element in the target range where the two input ranges are merged to form a unified sorted range.
Return value
It yields an iterator that points to the element just before the first one in the generated sequence.
Complexity
Complexity follows a linear pattern: it executes a maximum of (last1-first1) + (last2 - first2) - comparisons and assignments for all elements.
Data races
The elements within the intervals [first1, last1) and [first2, last2) are being retrieved.
The items within the range from the outcome to the value that is given back are modified.
Exceptions
This function will raise an exception if an error occurs during comparison of elements or while performing an operation on an iterator.
Please be aware that providing invalid parameters can lead to unpredictable behavior.
Example 1
Let's explore a straightforward example to showcase the functionality of the merge method:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void printVector(vector<int>& v)
{
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
cout << ' ' << *it;
cout << '\n';
}
int main () {
vector<int> v1 = {5,1,4,2,6}, v2 = {50,40,30,20,10}, v3(10);
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());
cout << "Vector v1 : ";
printVector(v1);
cout << "Vector v2 : ";
printVector(v2);
cout << "Vector v3 : ";
printVector(v3);
return 0;
}
Output:
Vector v1 : 1 2 4 5 6
Vector v2 : 10 20 30 40 50
Vector v3 : 1 2 4 5 6 10 20 30 40 50
Example 2
Let's explore another straightforward illustration demonstrating the implementation of the merge function utilizing the < operator.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
// initializing 1st container
vector<int> arr1 = { 1, 4, 6, 3, 2 };
// initializing 2nd container
vector<int> arr2 = { 60, 20, 50, 70, 10 };
// declaring resultant container
vector<int> arr3(10);
// sorting initial containers
sort(arr1.begin(), arr1.end());
sort(arr2.begin(), arr2.end());
// using merge() to merge the initial containers
merge(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), arr3.begin());
// printing the resultant merged container
cout << "The container after merging initial containers is: ";
for (int i = 0; i < arr3.size(); i++)
cout << arr3[i] << " ";
return 0;
}
Output:
The container after merging initial containers is: 1 2 3 4 6 10 20 50 60 70
Example 3
Let's explore another straightforward illustration to showcase the merge function using a comparison callback.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// comparator function to reverse merge sort
struct greaters {
bool operator()(const long& a, const long& b) const
{
return a > b;
}
};
int main()
{
// initializing 1st container
vector<int> arr1 = { 1, 4, 6, 3, 2 };
// initializing 2nd container
vector<int> arr2 = { 60, 20, 50, 70, 10 };
// declaring resultant container
vector<int> arr3(10);
// sorting initial containers
// in descending order
sort(arr1.rbegin(), arr1.rend());
sort(arr2.rbegin(), arr2.rend());
// using merge() to merge the initial containers
// returns descended merged container
merge(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), arr3.begin(), greaters());
// printing the resultant merged container
cout << "The container after reverse merging initial containers is : ";
for (int i = 0; i < arr3.size(); i++)
cout << arr3[i] << " ";
return 0;
}
Output:
The container after reverse merging initial containers is : 70 60 50 20 10 6 4 3 2 1
Example 4
Let's see another simple exampl
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
// initializing 1st container
// containing denominations
vector<int> stack1 = { 50, 20, 10, 100, 200 };
// initializing 2nd container
// containing demonitions
vector<int> stack2 = { 500, 2000, 5000, 1000, 10000 };
// declaring resultant stack
vector<int> stack3(10);
cout << "The original 1st stack: ";
for (int i = 0; i < 5; i++)
cout << stack1[i] << " ";
cout << endl;
cout << "The original 2nd stack: ";
for (int i = 0; i < 5; i++)
cout << stack2[i] << " ";
cout << endl;
// sorting initial stacks of notes
// in descending order
sort(stack1.begin(), stack1.end());
sort(stack2.begin(), stack2.end());
// using merge() to merge the initial stacks
// of notes
merge(stack1.begin(), stack1.end(), stack2.begin(), stack2.end(), stack3.begin());
// printing the resultant stack
cout << "The resultant stack of notes is: ";
for (int i = 0; i < stack3.size(); i++)
cout << stack3[i] << " ";
return 0;
}
Output:
The original 1st stack: 50 20 10 100 200
The original 2nd stack: 500 2000 5000 1000 10000
The resultant stack of notes is: 10 20 50 100 200 500 1000 2000 5000 10000
