C++/STL Algorithms Merge/merge

Материал из C\C++ эксперт
Перейти к: навигация, поиск

Demonstrating the generic merge algorithm with an array, a list, and a deque

<source lang="cpp">

  1. include <iostream>
  2. include <cassert>
  3. include <list>
  4. include <deque>
  5. include <algorithm> // For merge

using namespace std; int main() {

 char s[] = "aeiou";
 int len = strlen(s);
 list<char> list1(&s[0], &s[strlen(s)]);
 // Initialize deque1 with 26 copies of the letter x:
 deque<char> deque1(26, "x");
 // Merge array s and list1, putting result in deque1:
 merge(&s[0], &s[len], list1.begin(), list1.end(),deque1.begin());
 deque<char>::iterator i;
 cout.precision(10);
 for (i = deque1.begin(); i != deque1.end(); ++i)
   cout << *i << endl;
 return 0;

} /* a a e e i i o o u u x x x x x x x x x x x x x x x x

*/        
   
 </source>


Generic merge algorithm: merge parts of an array and a deque, putting the result into a list

<source lang="cpp">

  1. include <iostream>
  2. include <string>
  3. include <cassert>
  4. include <list>
  5. include <deque>
  6. include <algorithm> // For merge

using namespace std; int main() {

 char s[] = "acegikm";
 deque<char> deque1(&s[0], &s[strlen(s)]);
 // Initialize list1 with 26 copies of the letter x:
 list<char> list1(26, "x");
 // Merge first 5 letters in array s with first 10 in
 // deque1, putting result in list1:
 merge(&s[0], &s[5], deque1.begin(), deque1.begin() + 10,list1.begin());
 list<char>::iterator i;
 cout.precision(10);
 for (i = list1.begin(); i != list1.end(); ++i)
   cout << *i << endl;
 return 0;

}

/* a a c c e e g g i i k m S P x x x x x x x x x x x

*/
        
   
 </source>


Merge a vector with deque

<source lang="cpp">

  1. include <iostream>
  2. include <vector>
  3. include <deque>
  4. include <list>
  5. include <algorithm>

using namespace std; template<class InIter> void show_range(const char *msg, InIter start, InIter end); int main() {

 vector<char> v;
 deque<char> dq;
 list<char> result(26);
 list<char>::iterator res_end;
 for(int i=0; i < 26; i+=2) {
    v.push_back("A"+i);
 }
 for(int i=0; i < 26; i+=2) {
    dq.push_back("B"+i);
 }
 res_end = merge(v.begin(), v.end(),dq.begin(), dq.end(),result.begin());
 show_range("Result of merging v with dq:", result.begin(), res_end);
 return 0;

} template<class InIter> void show_range(const char *msg, InIter start, InIter end) {

 InIter itr;
 cout << msg << endl;
 for(itr = start; itr != end; ++itr)
   cout << *itr << endl;

}


 </source>


Merge in place

<source lang="cpp">

  1. include <iostream>
  2. include <vector>
  3. include <deque>
  4. include <list>
  5. include <algorithm>

using namespace std; template<class InIter> void show_range(const char *msg, InIter start, InIter end); int main() {

 vector<char> v;
 deque<char> dq;
 list<char> result(26);
 list<char>::iterator res_end;
 for(int i=0; i < 26; i+=2) {
    v.push_back("A"+i);
 }
 for(int i=0; i < 26; i+=2) {
    dq.push_back("B"+i);
 }
 vector<char> v2;
 for(int i=0; i < 26; i+=2) {
   v2.push_back("B"+i);
 }
 for(int i=0; i < 26; i+=2) {
   v2.push_back("A"+i);
 }
 show_range("Original contents of v2:", v2.begin(), v2.end());
 return 0;

} template<class InIter> void show_range(const char *msg, InIter start, InIter end) {

 InIter itr;
 cout << msg << endl;
 for(itr = start; itr != end; ++itr)
   cout << *itr << endl;

}


 </source>


Merge two containers

<source lang="cpp">

/* The following code example is taken from the book

* "The C++ Standard Library - A Tutorial and Reference"
* by Nicolai M. Josuttis, Addison-Wesley, 1999
*
* (C) Copyright Nicolai M. Josuttis 1999.
* Permission to copy, use, modify, sell and distribute this software
* is granted provided this copyright notice appears in all copies.
* This software is provided "as is" without express or implied
* warranty, and with no claim as to its suitability for any purpose.
*/
  1. include <iostream>
  2. include <vector>
  3. include <deque>
  4. include <list>
  5. include <set>
  6. include <map>
  7. include <string>
  8. include <algorithm>
  9. include <iterator>
  10. include <functional>
  11. include <numeric>

/* PRINT_ELEMENTS()

* - prints optional C-string optcstr followed by
* - all elements of the collection coll
* - separated by spaces
*/

template <class T> inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="") {

   typename T::const_iterator pos;
   std::cout << optcstr;
   for (pos=coll.begin(); pos!=coll.end(); ++pos) {
       std::cout << *pos << " ";
   }
   std::cout << std::endl;

} /* INSERT_ELEMENTS (collection, first, last)

* - fill values from first to last into the collection
* - NOTE: NO half-open range
*/

template <class T> inline void INSERT_ELEMENTS (T& coll, int first, int last) {

   for (int i=first; i<=last; ++i) {
       coll.insert(coll.end(),i);
   }

} using namespace std; int main() {

   list<int> coll1;
   set<int> coll2;
   // fill both collections with some sorted elements
   INSERT_ELEMENTS(coll1,1,6);
   INSERT_ELEMENTS(coll2,3,8);
   PRINT_ELEMENTS(coll1,"coll1:  ");
   PRINT_ELEMENTS(coll2,"coll2:  ");
   // print merged sequence
   cout << "merged: ";
   merge (coll1.begin(), coll1.end(),
          coll2.begin(), coll2.end(),
          ostream_iterator<int>(cout," "));
   cout << endl;

}

/* 

coll1: 1 2 3 4 5 6 coll2: 3 4 5 6 7 8 merged: 1 2 3 3 4 4 5 5 6 6 7 8

*/       
   
 </source>


Merge two ranges within a vector

<source lang="cpp">

  1. include <iostream>
  2. include <vector>
  3. include <deque>
  4. include <list>
  5. include <algorithm>

using namespace std; template<class InIter> void show_range(const char *msg, InIter start, InIter end); int main() {

 vector<char> v;
 deque<char> dq;
 list<char> result(26);
 list<char>::iterator res_end;
 for(int i=0; i < 26; i+=2) {
    v.push_back("A"+i);
 }
 for(int i=0; i < 26; i+=2) {
    dq.push_back("B"+i);
 }
 // Merge two ranges within v2.
 inplace_merge(v.begin(), v.begin()+13, v.end());
 show_range("Contents of v after in-place merge:", v.begin(),v.end());
 return 0;

} template<class InIter> void show_range(const char *msg, InIter start, InIter end) {

 InIter itr;
 cout << msg << endl;
 for(itr = start; itr != end; ++itr)
   cout << *itr << endl;

}


 </source>


sum the ranges by using merge()

<source lang="cpp">

/* The following code example is taken from the book

* "The C++ Standard Library - A Tutorial and Reference"
* by Nicolai M. Josuttis, Addison-Wesley, 1999
*
* (C) Copyright Nicolai M. Josuttis 1999.
* Permission to copy, use, modify, sell and distribute this software
* is granted provided this copyright notice appears in all copies.
* This software is provided "as is" without express or implied
* warranty, and with no claim as to its suitability for any purpose.
*/
  1. include <iostream>
  2. include <vector>
  3. include <deque>
  4. include <list>
  5. include <set>
  6. include <map>
  7. include <string>
  8. include <algorithm>
  9. include <iterator>
  10. include <functional>
  11. include <numeric>

/* PRINT_ELEMENTS()

* - prints optional C-string optcstr followed by
* - all elements of the collection coll
* - separated by spaces
*/

template <class T> inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="") {

   typename T::const_iterator pos;
   std::cout << optcstr;
   for (pos=coll.begin(); pos!=coll.end(); ++pos) {
       std::cout << *pos << " ";
   }
   std::cout << std::endl;

} /* INSERT_ELEMENTS (collection, first, last)

* - fill values from first to last into the collection
* - NOTE: NO half-open range
*/

template <class T> inline void INSERT_ELEMENTS (T& coll, int first, int last) {

   for (int i=first; i<=last; ++i) {
       coll.insert(coll.end(),i);
   }

} using namespace std; int main() {

   int c1[] = { 1, 2, 2, 4, 6, 7, 7, 9 };
   int num1 = sizeof(c1) / sizeof(int);
   int c2[] = { 2, 2, 2, 3, 6, 6, 8, 9 };
   int num2 = sizeof(c2) / sizeof(int);
   // print source ranges
   cout << "c1:                         " ;
   copy (c1, c1+num1, ostream_iterator<int>(cout," "));
   cout << endl;
   cout << "c2:                         " ;
   copy (c2, c2+num2, ostream_iterator<int>(cout," "));
   cout << "\n" << endl;
   // sum the ranges by using merge()
   cout << "merge():                    ";
   merge (c1, c1+num1, c2, c2+num2, ostream_iterator<int>(cout," "));
   cout << endl;

} /* c1: 1 2 2 4 6 7 7 9 c2: 2 2 2 3 6 6 8 9 merge(): 1 2 2 2 2 2 3 4 6 6 6 7 7 8 9 9

*/
       
   
 </source>


Use merge with back_inserter

<source lang="cpp">

  1. include <iostream>
  2. include <string>
  3. include <list>
  4. include <vector>
  5. include <algorithm>
  6. include <iterator>

using namespace std; int main( ) {

  vector<string> v1, v2, v3;
  v1.push_back("a");
  v1.push_back("c");
  v1.push_back("e");
  v2.push_back("b");
  v2.push_back("d");
  v2.push_back("f");
  v3.reserve(v1.size( ) + v2.size( ) + 1);
  merge(v1.begin( ), v1.end( ),
        v2.begin( ), v2.end( ),
        back_inserter<vector<string> >(v3));
  for(int i=0;i<6;i++){
     cout << v3[i];
  }

}

/* 

abcdef

*/       
   
 </source>


Use std::merge to merge elements in two elements into the third one in sorted order

<source lang="cpp">

  1. include <iostream>

using std::cout; using std::endl;

  1. include <algorithm>
  2. include <vector>
  3. include <iterator>

int main() {

  int a1[ 5 ] = { 1, 3, 5, 7, 9 };
  int a2[ 5 ] = { 2, 4, 5, 7, 9 };
  std::vector< int > v1( a1, a1 + 5 );
  std::vector< int > v2( a2, a2 + 5 );
  std::ostream_iterator< int > output( cout, " " );
  std::copy( v1.begin(), v1.end(), output ); // display vector output
  cout << "\n\n";
  std::copy( v2.begin(), v2.end(), output ); // display vector output
  std::vector< int > results2( v1.size() + v2.size() );
  std::merge( v1.begin(), v1.end(), v2.begin(), v2.end(), results2.begin() );
  cout << "\n\nAfter merge of v1 and v2 results2 contains:\n";
  std::copy( results2.begin(), results2.end(), output );
  cout << endl;
  return 0;

}

/* 

1 3 5 7 9 2 4 5 7 9 After merge of v1 and v2 results2 contains: 1 2 3 4 5 5 7 7 9 9

*/       
   
 </source>