C++/STL Algorithms Merge/merge
Содержание
- 1 Demonstrating the generic merge algorithm with an array, a list, and a deque
- 2 Generic merge algorithm: merge parts of an array and a deque, putting the result into a list
- 3 Merge a vector with deque
- 4 Merge in place
- 5 Merge two containers
- 6 Merge two ranges within a vector
- 7 sum the ranges by using merge()
- 8 Use merge with back_inserter
- 9 Use std::merge to merge elements in two elements into the third one in sorted order
Demonstrating the generic merge algorithm with an array, a list, and a deque
<source lang="cpp">
- include <iostream>
- include <cassert>
- include <list>
- include <deque>
- 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">
- include <iostream>
- include <string>
- include <cassert>
- include <list>
- include <deque>
- 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">
- include <iostream>
- include <vector>
- include <deque>
- include <list>
- 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">
- include <iostream>
- include <vector>
- include <deque>
- include <list>
- 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. */
- include <iostream>
- include <vector>
- include <deque>
- include <list>
- include <set>
- include <map>
- include <string>
- include <algorithm>
- include <iterator>
- include <functional>
- 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">
- include <iostream>
- include <vector>
- include <deque>
- include <list>
- 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. */
- include <iostream>
- include <vector>
- include <deque>
- include <list>
- include <set>
- include <map>
- include <string>
- include <algorithm>
- include <iterator>
- include <functional>
- 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">
- include <iostream>
- include <string>
- include <list>
- include <vector>
- include <algorithm>
- 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">
- include <iostream>
using std::cout; using std::endl;
- include <algorithm>
- include <vector>
- 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>