14.5 Merge Ordered Sequences

The algorithm std::merge() combines two ordered sequences to form a new ordered sequence. The size of the result is the sum of the sizes of the two argument sequences. This should be contrasted with the std::set_union() operation, which eliminates elements that are duplicated in both sets. The std::set_union() function is described later in this chapter.

The merge operation is stable. This means, for equal elements in the two ranges, not only is the relative ordering of values from each range preserved, but the values from the first range always precede the elements from the second. The two ranges are described by a pair of iterators, whereas the result is defined by a single output iterator. The arguments are shown in the following declaration:

namespace std {
  OutputIterator merge
     (InputIterator first1, InputIterator last1,
      InputIterator first2, InputIterator last2,
      OutputIterator result [, Compare ]);
}

The example program illustrates a simple merge, the use of a merge with an inserter, and the use of a merge with an output stream iterator.

void merge_example()
// illustrates the use of the merge algorithm
// see alg7.cpp for complete source code

{
  // make a list and vector of 10 random integers
  std::vector<int> aVec(10);
  std::list<int> aList(10, 0);
  std::generate(aVec.begin(), aVec.end(), randomValue);
  std::sort(aVec.begin(), aVec.end());
  std::generate_n(aList.begin(), 10, randomValue);
  aList.sort();

  // merge into a vector
  std::vector<int> vResult(aVec.size() + aList.size());
  std::merge(aVec.begin(), aVec.end(), 
             aList.begin(), aList.end(), vResult.begin());

  // merge into a list
  std::list<int> lResult;
  std::merge(aVec.begin(), aVec.end(), aList.begin(), 
             aList.end(), inserter(lResult, lResult.begin()));

  // merge into the output
  std::merge(aVec.begin(), aVec.end(), aList.begin(), aList.end(),
             std::ostream_iterator<int,char> (std::cout, " "));
  std::cout << std::endl;
}

The algorithm std::inplace_merge() (Section 12.4.6, "Merge Two Adjacent Sequences into One,") can be used to merge two sections of a single sequence into one sequence.

Copyright (c) 1994-2006 Rogue Wave Software, a Quovadx Division.
Licensed under the Apache License, Version 2.0.
Contact Rogue Wave about documentation or support issues. You can also seek help from other developers through the Apache stdcxx community (see below).