C++ algorithm merge() function

C++ algorithm merge() function with c++ tutorial for beginners and professionals with examples on adjacent_find(),any_of(), copy(), copy_if(), count(), count_if(), equal(), find(), find_end(), find_first_of(), find_if(), find_if_not(), for_each() etc.

<< Back to CPP

next → ← prev

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

← prev next →

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C++ algorithm merge() function

C++ Algorithm merge()

Syntax

Parameter

Return value

Complexity

Data races

Exceptions

Example 1

Example 2

Example 3

Example 4

Related Links:

.Net

Java

Related Links