• Choose a category
• All
• Classic-Fiction

Set Algorithms

The final class of algorithms in the STL is five functions for performing set operations that work on any sorted iterator range. They do not work on unordered associative containers.

The includes() function implements standard subset determination, checking if all the elements of one sorted range are included in another sorted range, in any order.

The set_union(), set_intersection(), set_difference(), and set_symmetric_difference() algorithms implement the standard semantics of those operations. In set theory, the result of union is all the elements in either set. The result of intersection is all the elements which are in both sets. The result of difference is all the elements in the first set but not the second. The result of symmetric difference is the “exclusive or” of sets: all the elements in one, but not both, sets.

Make sure that your result range is large enough to hold the result of the operations. For set_union() and set_symmetric_difference(), the result is at most the sum of the sizes of the two input ranges. For set_intersection() and set_difference() it’s at most the maximum of the two sizes.

You can’t use iterator ranges from associative containers, including sets, to store the results because they don’t allow changes to their keys.

Here is an example of how to use these algorithms:

// The populateContainer() function is identical to the one shown earlier

// for comparison algorithms, so it is omitted here.

vector vec1, vec2, result;

cout << "Enter elements for set 1:" << endl;

populateContainer(vec1);

cout << "Enter elements for set 2:" << endl;

populateContainer(vec2);

// set algorithms work on sorted ranges

sort(vec1.begin(), vec1.end());

sort(vec2.begin(), vec2.end());

cout << "Set 1: ";

for_each(vec1.cbegin(), vec1.cend(), [](int i){cout << i << " ";});

cout << endl;

cout << "Set 2: ";

for_each(vec2.cbegin(), vec2.cend(), [](int i){cout << i << " ";});

cout << endl;

if (includes(vec1.cbegin(), vec1.cend(), vec2.cbegin(), vec2.cend())) {

cout << "The second set is a subset of the first." << endl;

}

if (includes(vec2.cbegin(), vec2.cend(), vec1.cbegin(), vec1.cend())) {

cout << "The first set is a subset of the second" << endl;

}

result.resize(vec1.size() + vec2.size());

auto newEnd = set_union(vec1.cbegin(), vec1.cend(), vec2.cbegin(),

vec2.cend(), result.begin());

cout << "The union is: ";

for_each(result.begin(), newEnd, [](int i){cout << i << " ";});

cout << endl;

newEnd = set_intersection(vec1.cbegin(), vec1.cend(), vec2.cbegin(),

vec2.cend(), result.begin());

cout << "The intersection is: ";

for_each(result.begin(), newEnd, [](int i){cout << i << " ";});

cout << endl;

newEnd = set_difference(vec1.cbegin(), vec1.cend(), vec2.cbegin(),

vec2.cend(), result.begin());

cout << "The difference between set 1 and set 2 is: ";

for_each(result.begin(), newEnd, [](int i){cout << i << " ";});

cout << endl;

newEnd = set_symmetric_difference(vec1.cbegin(), vec1.cend(),

vec2.cbegin(), vec2.cend(), result.begin());

cout << "The symmetric difference is: ";

for_each(result.begin(), newEnd, [](int i){cout << i << " ";});

cout << endl;

Code snippet from SetAlgorithms\Sets.cpp

Here is a sample run of the program:

Enter elements for set 1:

Enter a number (0 to quit): 5

Enter a number (0 to quit): 6

Enter a number (0 to quit): 7

Enter a number (0 to quit): 8

Enter a number (0 to quit): 0

Enter elements for set 2:

Enter a number (0 to quit): 8

Enter a number (0 to quit): 9

Enter a number (0 to quit): 10

Enter a number (0 to quit): 0

Set 1: 5 6 7 8

Set 2: 8 9 10

The union is: 5 6 7 8 9 10

The intersection is: 8

The difference between set 1 and set 2 is: 5 6 7

The symmetric difference is: 5 6 7 9 10

ALGORITHMS EXAMPLE: AUDITING VOTER REGISTRATIONS

Voter fraud can be a problem everywhere. People sometimes attempt to register and vote in two or more different voting districts. Additionally, some people, for example