Figure 16.8 demonstrates algorithms copy_backward
, merge
, unique
and reverse
.
1 // Fig. 16.8: fig16_08.cpp
2 // Algorithms copy_backward, merge, unique and reverse.
3 #include <iostream>
4 #include <algorithm> // algorithm definitions
5 #include <array> // array class-template definition
6 #include <iterator> // ostream_iterator
7 using namespace std;
8
9 int main()
10 {
11 const size_t SIZE = 5;
12 array< int, SIZE > a1 = { 1, 3, 5, 7, 9 };
13 array< int, SIZE > a2 = { 2, 4, 5, 7, 9 };
14 ostream_iterator< int > output( cout, " " );
15
16 cout << "array a1 contains: ";
17 copy( a1.cbegin(), a1.cend(), output ); // display a1
18 cout << "
array a2 contains: ";
19 copy( a2.cbegin(), a2.cend(), output ); // display a2
20
21 array< int, SIZE > results;
22
23 // place elements of a1 into results in reverse order
24 copy_backward( a1.cbegin(), a1.cend(), results.end() );
25 cout << "
After copy_backward, results contains: ";
26 copy( results.cbegin(), results.cend(), output );
27
28 array< int, SIZE + SIZE > results2;
29
30 // merge elements of a1 and a2 into results2 in sorted order
31 merge( a1.cbegin(), a1.cend(), a2.cbegin(), a2.cend(),
32 results2.begin() );
33
34 cout << "
After merge of a1 and a2 results2 contains: ";
35 copy( results2.cbegin(), results2.cend(), output );
36
37 // eliminate duplicate values from results2
38 auto endLocation = unique( results2.begin(), results2.end() );
39
40 cout << "
After unique results2 contains: ";
41 copy( results2.begin(), endLocation, output );
42
43 cout << "
array a1 after reverse: ";
44 reverse( a1.begin(), a1.end() ); // reverse elements of a1
45 copy( a1.cbegin(), a1.cend(), output );
46 cout << endl;
47 } // end main
array a1 contains: 1 3 5 7 9
array a2 contains: 2 4 5 7 9
After copy_backward, results contains: 1 3 5 7 9
After merge of a1 and a2 results2 contains: 1 2 3 4 5 5 7 7 9 9
After unique results2 contains: 1 2 3 4 5 7 9
array a1 after reverse: 9 7 5 3 1
Line 24 uses the copy_backward algorithm to copy elements in the range from a1.cbegin()
up to, but not including, a1.cend()
, placing the elements in results
by starting from the element before results.end()
and working toward the beginning of the array
. The algorithm returns an iterator positioned at the last element copied into the results
(i.e., the beginning of results
, because of the backward copy). The elements are placed in results
in the same order as a1
. This algorithm requires three bidirectional iterator arguments (iterators that can be incremented and decremented to iterate forward and backward through a sequence, respectively). One difference between copy_backward
and copy
is that the iterator returned from copy
is positioned after the last element copied and the one returned from copy_backward
is positioned at the last element copied (i.e., the first element in the sequence). Also, copy_backward
can manipulate overlapping ranges of elements in a container as long as the first element to copy is not in the destination range of elements.
In addition to the copy
and copy_backward
algorithms, C++11 now includes the move and move_backward algorithms. These use C++11’s new move semantics (discussed in Chapter 24, C++11: Additional Features) to move, rather than copy, objects from one container to another.
Lines 31–32 use the merge algorithm to combine two sorted ascending sequences of values into a third sorted ascending sequence. The algorithm requires five iterator arguments. The first four must be at least input iterators and the last must be at least an output iterator. The first two arguments specify the range of elements in the first sorted sequence (a1
), the second two arguments specify the range of elements in the second sorted sequence (a2
) and the last argument specifies the starting location in the third sequence (results2
) where the elements will be merged. A second version of this algorithm takes as its sixth argument a binary predicate function that specifies the sorting order.
Line 28 creates the array results2
with the number of elements in a1
and a2
. Using the merge
algorithm requires that the sequence where the results are stored be at least the size of the sequences being merged. If you do not want to allocate the number of elements for the resulting sequence before the merge
operation, you can use the following statements:
vector< int > results2;
merge( a1.begin(), a1.end(), a2.begin(), a2.end(),
back_inserter( results2 ) );
The argument back_inserter(results2)
uses function template back_inserter (header <iterator>
) for the vector results2
. A back_inserter
calls the container’s default push_back
function to insert an element at the end of the container. If an element is inserted into a container that has no more space available, the container grows in size—which is why we used a vector
in the preceding statements, because array
s are fixed size. Thus, the number of elements in the container does not have to be known in advance. There are two other inserters—front_inserter (uses push_front
to insert an element at the beginning of a container specified as its argument) and inserter (uses insert
to insert an element at the iterator supplied as its second argument in the container supplied as its first argument).
Line 38 uses the unique algorithm on the sorted sequence of elements in the range from results2.begin()
up to, but not including, results2.end()
. After this algorithm is applied to a sorted sequence with duplicate values, only a single copy of each value remains in the sequence. The algorithm takes two arguments that must be at least forward iterators. The algorithm returns an iterator positioned after the last element in the sequence of unique values. The values of all elements in the container after the last unique value are undefined. A second version of this algorithm takes as a third argument a binary predicate function specifying how to compare two elements for equality.
Line 44 uses the reverse algorithm to reverse all the elements in the range from a1.begin()
up to, but not including, a1.end()
. The algorithm takes two arguments that must be at least bidirectional iterators.
C++11 now includes the new copy algorithms copy_if
and copy_n
. The copy_if algorithm copies each element from a range if the unary predicate function in its fourth argument returns true
for that element. The iterators supplied as the first two arguments must be input iterators. The iterator supplied as the third argument must be an output iterator so that the element being copied can be assigned to the copy location. This algorithm returns an iterator positioned after the last element copied.
The copy_n algorithm copies the number of elements specified by its second argument from the location specified by its first argument (an input iterator). The elements are output to the location specified by its third argument (an output iterator).