16.3.8. copy_backward, merge, unique and reverse
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
Fig. 16.8. Algorithms copy_backward, merge, unique and reverse.
copy_backward Algorithm
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.
merge Algorithm
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.
back_inserter, front_inserter and inserter Iterator Adapters
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 arrays 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).
unique Algorithm
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.
reverse Algorithm
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: copy_if and copy_n Algorithms
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).