merge

Merges the elements of two ranges

View version details

Contents

Definition
Interface
Description
Return Value
Complexity
Page Comments

Key Facts

Gyroscopic Couple: The rate of change of angular momentum ( $\inline \tau$ ) = $\inline I\omega\Omega$ (In the limit).

$\inline I$ = Moment of Inertia.
$\inline \omega$ = Angular velocity
$\inline \Omega$ = Angular velocity of precession.

Blaise Pascal (1623-1662) was a French mathematician, physicist, inventor, writer and Catholic philosopher.

Leonhard Euler (1707-1783) was a pioneering Swiss mathematician and physicist.

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.

References

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

http://www.smu.ca/academic/science/compsci/

merge

Key Facts

Definition

Interface

Description

Return Value

Complexity

References

Example - merge function

See Also