Figure 16.9 demonstrates algorithms inplace_merge
, unique_copy
and reverse_copy
.
1 // Fig. 16.9: fig16_09.cpp
2 // Algorithms inplace_merge, reverse_copy and unique_copy.
3 #include <iostream>
4 #include <algorithm> // algorithm definitions
5 #include <array> // array class-template definition
6 #include <vector> // vector class-template definition
7 #include <iterator> // back_inserter definition
8 using namespace std;
9
10 int main()
11 {
12 const int SIZE = 10;
13 array< int, SIZE > a1 = { 1, 3, 5, 7, 9, 1, 3, 5, 7, 9 };
14 ostream_iterator< int > output( cout, " " );
15
16 cout << "array a1 contains: ";
17 copy( a1.cbegin(), a1.cend(), output );
18
19 // merge first half of a1 with second half of a1 such that
20 // a1 contains sorted set of elements after merge
21 inplace_merge( a1.begin(), a1.begin() + 5, a1.end() );
22
23 cout << "
After inplace_merge, a1 contains: ";
24 copy( a1.cbegin(), a1.cend(), output );
25
26 vector< int > results1;
27
28 // copy only unique elements of a1 into results1
29 unique_copy( a1.cbegin(), a1.cend(), back_inserter( results1 ) );
30 cout << "
After unique_copy results1 contains: ";
31 copy( results1.cbegin(), results1.cend(), output );
32
33 vector< int > results2;
34
35 // copy elements of a1 into results2 in reverse order
36 reverse_copy( a1.cbegin(), a1.cend(), back_inserter( results2 ) );
37 cout << "
After reverse_copy, results2 contains: ";
38 copy( results2.cbegin(), results2.cend(), output );
39 cout << endl;
40 } // end main
array a1 contains: 1 3 5 7 9 1 3 5 7 9
After inplace_merge, a1 contains: 1 1 3 3 5 5 7 7 9 9
After unique_copy results1 contains: 1 3 5 7 9
After reverse_copy, results2 contains: 9 9 7 7 5 5 3 3 1 1
Line 21 uses the inplace_merge algorithm to merge two sorted sequences of elements in the same container. In this example, the elements from a1.begin()
up to, but not including, a1.begin() + 5
are merged with the elements from a1.begin() + 5
up to, but not including, a1.end()
. This algorithm requires its three iterator arguments to be at least bidirectional iterators. A second version of this algorithm takes as a fourth argument a binary predicate function for comparing elements in the two sequences.
Line 29 uses the unique_copy algorithm to make a copy of all the unique elements in the sorted sequence of values from a1.cbegin()
up to, but not including, a1.cend()
. The copied elements are placed into vector results1
. The first two arguments must be at least input iterators and the last must be at least an output iterator. In this example, we did not preallocate enough elements in results1
to store all the elements copied from a1
. Instead, we use function back_inserter
(defined in header <iterator>
) to add elements to the end of results1
. The back_inserter
uses vector
’s push_back
member function to insert elements at the end of the vector
. Because the back_inserter
inserts an element rather than replacing an existing element’s value, the vector
is able to grow to accommodate additional elements. A second version of the unique_copy
algorithm takes as a fourth argument a binary predicate function for comparing elements for equality.
Line 36 uses the reverse_copy algorithm to make a reversed copy of the elements in the range from a1.cbegin()
up to, but not including, a1.cend()
. The copied elements are inserted into results2
using a back_inserter
object to ensure that the vector
can grow to accommodate the appropriate number of elements copied. Algorithm reverse_copy
requires its first two iterator arguments to be at least bidirectional iterators and its third to be at least an output iterator.