This chapter is from the book
This chapter is from the book
This chapter is from the book
Using a Set
A set is a collection of key values. A set is used when we need to know whether a value is present. In a graph-traversal algorithm, for example, we might use a set to hold each visited node. Before we move to the next node, we query the set to see whether the node has already been visited.
The word occurrence program of the preceding section, for example, may choose not to count common words. To do this, we define a word-exclusion set of type string:
#include <set> #include <string> set<string> word_exclusion;
Before entering a word into our map, we check whether it is present within the word_exclusion set:
while ( cin >> tword )
{
if ( word_exclusion.count( tword ))
// present in the set of excluded words?
// then skip the rest of this iteration
continue;
// ok: if here, not an excluded word
words[ tword ]++;
}
The continue statement causes the loop to skip the remaining statements of the current loop iteration. In this case, if tword is within the word_exclusion set, the
words[ tword ]++;
statement is never executed. The while loop instead begins the next loop iteration by evaluating
while ( cin >> tword )
A set contains only one instance of each key value. (To store multiple key values, we must use a multiset.)
By default, the elements are ordered using the less-than operator of the underlying element type. For example, given
int ia[ 10 ] = { 1, 3, 5, 8, 5, 3, 1, 5, 8, 1 } ;
vector< int > vec( ia, ia+10 );
set<int> iset( vec.begin(), vec.end() );
the elements contained in iset are {1,3,5,8}.
Individual elements of a set are added using the single argument insert():
iset.insert( ival );
A range of elements is added using the insert() operation taking two iterators:
iset.insert( vec.begin(), vec.end() );
Iteration over a set is as you might expect:
set<int>::iterator it = iset.begin(); for ( ; it != iset.end(); ++it ) cout << *it << ' '; cout << endl;
The generic algorithms provide a number of set algorithms: set_intersection(), set_union(), set_difference(), and set_symmetric_difference().