[ новости /+++ | форум | теги | ]

                       Standard C++ Library
             Copyright 1998, Rogue Wave Software, Inc.


NAME
     merge

      - Merges two sorted sequences into a third sequence.



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

     template <class InputIterator1, class InputIterator2,
              class OutputIterator, class Compare>
      OutputIterator
       merge(InputIterator1 first1, InputIterator1 last1,
            InputIterator2 first2, InputIterator last2,
            OutputIterator result, Compare comp);



DESCRIPTION
     The merge algorithm merges two sorted  sequences,  specified
     by  [first1,  last1)  and [first2, last2), into the sequence
     specified by [result, result + (last1 - first1) +  (last2  -
     first2)).  The first version of the merge algorithm uses the
     less than operator  (<)  to  compare  elements  in  the  two
     sequences.  The  second version uses the comparison function
     included in the function call. If a comparison  function  is
     included,  merge  assumes  that  both  sequences were sorted
     using that comparison function.

     The merge is stable. This means that  if  the  two  original
     sequences contain equivalent elements, the elements from the
     first sequence always precede the matching elements from the
     second  in the resulting sequence. The size of the result of
     a merge is equal to the sum of the sizes of the two argument
     sequences.  merge returns an iterator that points to the end
     of the resulting sequence (in other words, result + (last1 -
     first1) + (last2 -first2)). The result of merge is undefined
     if the resulting range overlaps with either of the  original
     ranges.
     merge assumes that there are at least  (last1  -  first1)  +
     (last2  -  first2)  elements following result, unless result
     has been adapted by an insert iterator.



COMPLEXITY
     At most (last - first1) + (last2 - first2) -  1  comparisons
     are performed.



EXAMPLE
     //
     // merge.cpp
     //
      #include <algorithm>
      #include <vector>
      #include <iostream>
     using namespace std;

     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;
      }

     Program 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  parame-
     ters,  then you always need to supply the Allocator template
     argument. For instance, you have to write:

     vector<int,allocator<int> >
     instead of:

     vector<int>

     If your compiler does not support namespaces,  then  you  do
     not need the using declaration for std.



SEE ALSO
     Containers, inplace_merge

Партнёры:

Хостинг: