C++ Algorithm merge()

C++ Algorithm merge() function is used to merge two sorted ranges [first1, last1) and [first2, last2) into one sorted range beginning at result.

Elements are compared using operator < for the first version or using the given binary comparison function comp for the second 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

first1: An input iterator pointing to the first element in the first sorted source sequence to be merged.

last: A input iterator pointing to the past last element in the first sorted source sequence to be merged.

first2: An input iterator pointing to the first element in the second sorted source sequence to be merged.

last2: An input iterator pointing to the past last element in the second sorted source sequence to be merged.

comp: A user-defined binary predicate function that accepts two arguments and returns true if the two arguments are in order and false otherwise. It follows the strict weak ordering to order the elements.

val: A value of the upper bound to compare the elements in the range.

result: An output iterator pointing to the first element in the destination range where the two source ranges are to be combined into a single sorted range.

Return value

It returns an iterator pointing to the past last element in the resulting sequence.

Complexity

Complexity is linear: performs at most (last1-first1) + (last2 – first2) – compares and assigns all elements.

Data races

The object in the range [first1, last1) and [first2, last2) are accessed.

The object in the range between result and the returned value are altered.

Exceptions

This function throws an exception if either an element comparisons or an operation on iterator throws an exception.

Please note that invalid parameters cause an undefined behavior.

Example 1

Let’s see the simple example to demonstrate the use of merge():

  #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 see another simple example to implement merge() function using 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 see another simple example to demonstrate merge() using comparison function

  #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

Next TopicC++ Algorithm

adjacent_find()algorithm any_of()beginners copy_if()copy()count_if()count()cpp equal()find_end()find_first_of()find_if_not() for_each()find_if()find()professionals tutorial

C++ algorithm merge() function

C++ Algorithm merge()

Syntax

Parameter

Return value

Complexity

Data races

Exceptions

Example 1

Example 2

Example 3

Example 4

Underwriting of Shares

C++ Math abs() Functions

You may also like