I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com
ComputingStlAlgorithmsSet

merge

Merges the elements of two ranges
+ View version details

Definition

The merge() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.

Interface

#include <algorithm>
template < class InputIterator1, class InputIterator2, class OutputIterator >
   OutputIterator merge(
      InputIterator1 first1, 
      InputIterator1 last1,
      InputIterator2 first2, 
      InputIterator2 last2, 
      OutputIterator result
   );
template < class InputIterator1, class InputIterator2, class OutputIterator, class BinaryPredicate >
   OutputIterator merge(
      InputIterator1 first1, 
      InputIterator1 last1,
      InputIterator2 first2, 
      InputIterator2 last2, 
      OutputIterator result
      BinaryPredicate comp
   );

Parameters:
Parameter Description
first1 An input iterator addressing the position of the first element in the first of two sorted source ranges to be combined and sorted into a single range
last1 An input iterator addressing the position one past the last element in the first of two sorted source ranges to be combined and sorted into a single range
first2 An input iterator addressing the position of the first element in second of two consecutive sorted source ranges to be combined and sorted into a single range
last2 An input iterator addressing the position one past the last element in second of two consecutive sorted source ranges to be combined and sorted into a single range
result An output iterator addressing the position of the first element in the destination range where the two source ranges are to be combined into a single sorted 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

Merge function merges two sorted ranges ( [first1, last1) and [first2, last2)) into a single sorted range beginng at result.

The first version uses operator< to compare the elements and the second version uses the given comparison function comp. The relative order of equivalent elements is preserved.

Return Value

Returns an output iterator to element past the last element copied.

Complexity

The complexity is linear; performs at most (last1 - first1) + (last2 - first2) - 1 comparisons.
Example:

Example - merge function
Problem
This program illustrates the use of the STL merge() algorithm (default version) to merge two sorted ranges of integer values from two different vectors of integers into a single sorted range of values in another vector of integers.
Workings
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
  int a1[] = {1, 2, 3, 5, 6, 9};
  vector<int> v1(a1, a1+6);
  cout <<"\nHere are the contents of v1:\n";
  for (vector<int>::size_type i=0; i<v1.size(); i++)
    cout <<v1.at(i)<<" ";
 
  int a2[] = {2, 4, 6, 8, 9, 10, 15};
  vector<int> v2(a2, a2+7);
  cout <<"\nHere are the contents of v2:\n";
  for (vector<int>::size_type i=0; i<v2.size(); i++)
    cout <<v2.at(i)<<" ";
 
  vector<int> v3(15);
  cout <<"\nHere are the contents of v3:\n";
  for (vector<int>::size_type i=0; i<v3.size(); i++)
    cout <<v3.at(i)<<" ";
 
  cout <<"\nNow merge the contents of v1 and v2 into v3.";
  merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
  cout <<"\nHere are the revised contents of v3:\n";
  for (vector<int>::size_type i=0; i<v3.size(); i++)
     cout <<v3.at(i)<<" ";
 
  return 0;
}
Solution
Output:

Here are the contents of v1:
1 2 3 5 6 9

Here are the contents of v2:
2 4 6 8 9 10 15

Here are the contents of v3:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Now merge the contents of v1 and v2 into v3.

Here are the revised contents of v3:
1 2 2 3 4 5 6 6 8 9 9 10 15 0 0
References