16.3.10. Set Operations
Figure 16.10 demonstrates algorithms includes, set_difference, set_intersection, set_symmetric_difference and set_union for manipulating sets of sorted values.
1 // Fig. 16.10: fig16_10.cpp
2 // Algorithms includes, set_difference, set_intersection,
3 // set_symmetric_difference and set_union.
4 #include <iostream>
5 #include <array>
6 #include <algorithm> // algorithm definitions
7 #include <iterator> // ostream_iterator
8 using namespace std;
9
10 int main()
11 {
12 const size_t SIZE1 = 10, SIZE2 = 5, SIZE3 = 20;
13 array< int, SIZE1 > a1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
14 array< int, SIZE2 > a2 = { 4, 5, 6, 7, 8 };
15 array< int, SIZE2 > a3 = { 4, 5, 6, 11, 15 };
16 ostream_iterator< int > output( cout, " " );
17
18 cout << "a1 contains: ";
19 copy( a1.cbegin(), a1.cend(), output ); // display array a1
20 cout << "
a2 contains: ";
21 copy( a2.cbegin(), a2.cend(), output ); // display array a2
22 cout << "
a3 contains: ";
23 copy( a3.cbegin(), a3.cend(), output ); // display array a3
24
25 // determine whether a2 is completely contained in a1
26 if ( includes( a1.cbegin(), a1.cend(), a2.cbegin(), a2.cend() ) )
27 cout << "
a1 includes a2";
28 else
29 cout << "
a1 does not include a2";
30
31 // determine whether a3 is completely contained in a1
32 if ( includes( a1.cbegin(), a1.cend(), a3.cbegin(), a3.cend() ) )
33 cout << "
a1 includes a3";
34 else
35 cout << "
a1 does not include a3";
36
37 array< int, SIZE1 > difference;
38
39 // determine elements of a1 not in a2
40 auto result1 = set_difference( a1.cbegin(), a1.cend(),
41 a2.cbegin(), a2.cend(), difference.begin() );
42 cout << "
set_difference of a1 and a2 is: ";
43 copy( difference.begin(), result1, output );
44
45 array< int, SIZE1 > intersection;
46
47 // determine elements in both a1 and a2
48 auto result2 = set_intersection( a1.cbegin(), a1.cend(),
49 a2.cbegin(), a2.cend(), intersection.begin() );
50 cout << "
set_intersection of a1 and a2 is: ";
51 copy( intersection.begin(), result2, output );
52
53 array< int, SIZE1 + SIZE2 > symmetric_difference;
54
55 // determine elements of a1 that are not in a2 and
56 // elements of a2 that are not in a1
57 auto result3 = set_symmetric_difference( a1.cbegin(), a1.cend(),
58 a3.cbegin(), a3.cend(), symmetric_difference.begin() );
59 cout << "
set_symmetric_difference of a1 and a3 is: ";
60 copy( symmetric_difference.begin(), result3, output );
61
62 array< int, SIZE3 > unionSet;
63
64 // determine elements that are in either or both sets
65 auto result4 = set_union( a1.cbegin(), a1.cend(),
66 a3.cbegin(), a3.cend(), unionSet.begin() );
67 cout << "
set_union of a1 and a3 is: ";
68 copy( unionSet.begin(), result4, output );
69 cout << endl;
70 } // end main
a1 contains: 1 2 3 4 5 6 7 8 9 10
a2 contains: 4 5 6 7 8
a3 contains: 4 5 6 11 15
a1 includes a2
a1 does not include a3
set_difference of a1 and a2 is: 1 2 3 9 10
set_intersection of a1 and a2 is: 4 5 6 7 8
set_symmetric_difference of a1 and a3 is: 1 2 3 7 8 9 10 11 15
set_union of a1 and a3 is: 1 2 3 4 5 6 7 8 9 10 11 15
Fig. 16.10. Algorithms includes, set_difference, set_intersection, set_symmetric_difference and set_union.
includes Algorithm
Lines 26 and 32 call the includes algorithm, which compares two sets of sorted values to determine whether every element of the second set is in the first set. If so, includes returns true; otherwise, it returns false. The first two iterator arguments must be at least input iterators and must describe the first set of values. In line 26, the first set consists of the elements from a1.cbegin() up to, but not including, a1.cend(). The last two iterator arguments must be at least input iterators and must describe the second set of values. In this example, the second set consists of the elements from a2.cbegin() up to, but not including, a2.cend(). A second version of algorithm includes takes a fifth argument that’s a binary predicate function indicating the order in which the elements were originally sorted. The two sequences must be sorted using the same comparison function.
set_difference Algorithm
Lines 40–41 use the set_difference algorithm to find the elements from the first set of sorted values that are not in the second set of sorted values (both sets of values must be in ascending order). The elements that are different are copied into the fifth argument (in this case, the array difference). The first two iterator arguments must be at least input iterators for the first set of values. The next two iterator arguments must be at least input iterators for the second set of values. The fifth argument must be at least an output iterator indicating where to store a copy of the values that are different. The algorithm returns an output iterator positioned immediately after the last value copied into the set to which the fifth argument points. A second version of set_difference takes a sixth argument that’s a binary predicate function indicating the order in which the elements were originally sorted. The two sequences must be sorted using the same comparison function.
set_intersection Algorithm
Lines 48–49 use the set_intersection algorithm to determine the elements from the first set of sorted values that are in the second set of sorted values (both sets of values must be in ascending order). The elements common to both sets are copied into the fifth argument (in this case, array intersection). The first two iterator arguments must be at least input iterators for the first set of values. The next two iterator arguments must be at least input iterators for the second set of values. The fifth argument must be at least an output iterator indicating where to store a copy of the values that are the same. The algorithm returns an output iterator positioned immediately after the last value copied into the set to which the fifth argument points. A second version of set_intersection takes a sixth argument that’s a binary predicate function indicating the order in which the elements were originally sorted. The two sequences must be sorted using the same comparison function.
set_symmetric_difference Algorithm
Lines 57–58 use the set_symmetric_difference algorithm to determine the elements in the first set that are not in the second set and the elements in the second set that are not in the first set (both sets must be in ascending order). The elements that are different are copied from both sets into the fifth argument (the array symmetric_difference). The first two iterator arguments must be at least input iterators for the first set of values. The next two iterator arguments must be at least input iterators for the second set of values. The fifth argument must be at least an output iterator indicating where to store a copy of the values that are different. The algorithm returns an output iterator positioned immediately after the last value copied into the set to which the fifth argument points. A second version of set_symmetric_difference takes a sixth argument that’s a binary predicate function indicating the order in which the elements were originally sorted. The two sequences must be sorted using the same comparison function.
set_union Algorithm
Lines 65–66 use the set_union algorithm to create a set of all the elements that are in either or both of the two sorted sets (both sets of values must be in ascending order). The elements are copied from both sets into the fifth argument (in this case the array unionSet). Elements that appear in both sets are only copied from the first set. The first two iterator arguments must be at least input iterators for the first set of values. The next two iterator arguments must be at least input iterators for the second set of values. The fifth argument must be at least an output iterator indicating where to store the copied elements. The algorithm returns an output iterator positioned immediately after the last value copied into the set to which the fifth argument points. A second version of set_union takes a sixth argument that’s a binary predicate function indicating the order in which the elements were originally sorted. The two sequences must be sorted using the same comparison function.