HP C++ User Documentation

Standard C++ LibraryCopyright 1996, Rogue Wave Software, Inc.

NAME

  inplace_merge  - Merge two sorted sequences into one.

SYNOPSIS

  #include <algorithm>
  template <class BidirectionalIterator>
   void inplace_merge(BidirectionalIterator first,
                      BidirectionalIterator middle,
                      BidirectionalIterator last);

  template <class BidirectionalIterator, class Compare>
   void inplace_merge(BidirectionalIterator first,
                      BidirectionalIterator middle,
                      BidirectionalIterator last, Compare comp);

DESCRIPTION

  The inplace_merge algorithm merges two sorted consecutive ranges [first,
  middle) and [middle, last), and puts the result of the merge into the range
  [first, last).  The merge is stable, that is, if the two ranges contain
  equivalent elements, the elements from the first range always precede the
  elements from the second.

  There are two versions of the inplace_merge algorithm.  The first version
  uses the less than operator (operator<) as the default for comparison, and
  the second version accepts a third argument that specifies a comparison
  operator.

COMPLEXITY

  When enough additional memory is available, inplace_merge does at most
  (last - first) - 1  comparisons. If no additional memory is available, an
  algorithm with O(NlogN) complexity (where N is equal to last-first) may be
  used.

EXAMPLE

  //
  // merge.cpp
  //
   #include <algorithm>
   #include <vector>
   #include <iostream.h>

  int main()
   {
    int d1[4] = {1,2,3,4};
    int d2[8] = {11,13,15,17,12,14,16,18};

     // Set up two vectors
    vector<int> v1(d1,d1 + 4), v2(d1,d1 + 4);

     // Set up four destination vectors
    vector<int> v3(d2,d2 + 8),v4(d2,d2 + 8),
                v5(d2,d2 + 8),v6(d2,d2 + 8);
     // Set up one empty vector
    vector<int> v7;
     // Merge v1 with v2
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());
     // Now use comparator
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v4.begin(),
          less<int>());
     // In place merge v5
    vector<int>::iterator mid = v5.begin();
    advance(mid,4);
     inplace_merge(v5.begin(),mid,v5.end());
     // Now use a comparator on v6
    mid = v6.begin();
    advance(mid,4);
     inplace_merge(v6.begin(),mid,v6.end(),less<int>());
     // Merge v1 and v2 to empty vector using insert iterator
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(),
          back_inserter(v7));
     // Copy all cout
    ostream_iterator<int,char> out(cout," ");
    copy(v1.begin(),v1.end(),out);
    cout << endl;
    copy(v2.begin(),v2.end(),out);
    cout << endl;
    copy(v3.begin(),v3.end(),out);
    cout << endl;
    copy(v4.begin(),v4.end(),out);
    cout << endl;
    copy(v5.begin(),v5.end(),out);
    cout << endl;
    copy(v6.begin(),v6.end(),out);
    cout << endl;
    copy(v7.begin(),v7.end(),out);
    cout << endl;

     // Merge v1 and v2 to cout
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(),
          ostream_iterator<int,char>(cout," "));
    cout << endl;
    return 0;
   }

  Output:
  1 2 3 4
  1 2 3 4
  1 1 2 2 3 3 4 4
  1 1 2 2 3 3 4 4
  11 12 13 14 15 16 17 18
  11 12 13 14 15 16 17 18
  1 1 2 2 3 3 4 4
  1 1 2 2 3 3 4 4

WARNINGS

  If your compiler does not support default template parameters, then you
  need to always supply the Allocator template argument.  For instance,
  you'll have to write :

  vector<int, allocator,int> >

  instead of

  vector<int>

SEE ALSO

  merge

STANDARDS CONFORMANCE

  ANSI X3J16/ISO WG21 Joint C++ Committee