C++ Primer Plus

The STL set models several concepts. It is an associative set, it is reversible, it is sorted, and the keys are unique, so it can hold no more than one of any given value. Like vector and list, set uses a template parameter to provide the type stored:

set A;  // a set of string objects

An optional second template argument can be used to indicate a comparison function or object to be used to order the key. By default, the less<> template (discussed later) is used. Older C++ implementations may not provide a default value and thus require an explicit template parameter:

set > A;  // older implementation

Consider the following code:

const int N = 6;

string s1[N] = {"buffoon", "thinkers", "for", "heavy", "can", "for"};

set A(s1, s1 + N); // initialize set A using a range from array

ostream_iterator out(cout, " ");

copy(A.begin(), A.end(), out);

Like other containers, set has a constructor (refer to Table 16.6) that takes a range of iterators as arguments. This provides a simple way to initialize a set to the contents of an array. Remember that the last element of a range is one past-the-end, and s1 + N points to one position past-the-end of array s1. The output for this code fragment illustrates that keys are unique (the string "for" appears twice in the array but once in the set) and that the set is sorted:

buffoon can for heavy thinkers

Mathematics defines some standard operations for sets. For example, the union of two sets is a set that combines the contents of the two sets. If a particular value is common to both sets, it appears just once in the union because of the unique key feature. The intersection of two sets is a set that consists of the elements that are common to both sets. The difference between two sets is the first set minus the elements common to both sets.

The STL provides algorithms that support these operations. They are general functions rather than methods, so they aren’t restricted to set objects. However, all set objects automatically satisfy the precondition for using these algorithms—namely, that the container be sorted. The set_union() function takes five iterators as arguments. The first two define a range in one set, the second two define a range in a second set, and the final iterator is an output iterator that identifies a location to which to copy the resultant set. For example, to display the union of sets A and B, you can use this:

set_union(A.begin(), A.end(), B.begin(), B.end(),

           ostream_iterator out(cout, " "));

Suppose you want to place the result into a set C instead of displaying it. In this case, you would want the last argument to be an iterator into C. The obvious choice is C.begin(), but that doesn’t work for two reasons. The first reason is that associative sets treat keys as constant values, so the iterator returned by C.begin() is a constant iterator and can’t be used as an output iterator. The second reason not to use C.begin() directly is that set_union(), like copy(), overwrites existing data in a container and requires the container to have sufficient space to hold the new information. C, being empty, does not satisfy that requirement. But the insert_iterator template discussed earlier solves both problems. Earlier you saw that it converts copying to insertion. Also it models the output iterator concept, so you can use it to write to a container. So you can construct an anonymous insert_iterator to copy information to C. The constructor, recall, takes the name of the container and an iterator as arguments:

set_union(A.begin(), A.end(), B.begin(), B.end(),

           insert_iterator >(C, C.begin()));

The set_intersection() and set_difference() functions find the set intersection and set difference of two sets, and they have the same interface as set_union().

Two useful set methods are lower_bound() and upper_bound(). The lower_bound() method takes a key-type value as its argument and returns an iterator that points to the first member of the set that is not less than the key argument. Similarly, the upper_bound() method takes a key as its argument and returns an iterator that points to the first member of the set that is greater than the key argument. For example, if you had a set of strings, you could use these methods to identify a range encompassing all strings from "b" up to "f" in the set.

Because sorting determines where additions to a set go, the class has insertion methods that just specify the material to be inserted, without specifying a position. If A and B are sets of strings, for example, you can use this:

string s("tennis");

A.insert(s);                    // insert a value

B.insert(A.begin(), A.end());   // insert a range

Listing 16.13 illustrates these uses of sets.

Listing 16.13. setops.cpp

// setops.cpp -- some set operations

#include

#include

#include

#include

#include

int main()

{

    using namespace std;