EECS 311: STL Set Algorithms |
Home Course Info Links Grades |
Lectures Newsgroup Homework Exams |

Perhaps the most confusing thing to keep straight about sets in
the Standard Template Library is that the **generic set
algorithms** are independent of the **set container**. That is,
all the standard set operations, such as intersection, subset, and
union, are defined a generic algorithms, and can be used on any
**sorted** STL container. The set container just happens to be
useful with these algorithms because it sorts itself automatically
and cheaply.

The set container and its operations are summarized in the STL Summary.

Sets in mathematics have the following basic operations:

**Membership(X, S)**: Returns true if X is an element of a set S**Subset(S1, S2)**: Returns true if every element of S1 is a member of S2**Union(S1, S2)**: Returns the set containing all elements of S1 and S2**Intersection(S1, S2)**: Returns the set containing all elements of S1 that are also elements of S2

The mapping to the STL is pretty direct. Since "sets" for the generic set algorithms are really any sorted subrange of a container:

- Algorithms that "take sets" as arguments actually take a range for each set, i.e., a begin and end iterator for each set argument.
- Algorithms that "return sets" actually copy their answer into
an
`outputIterator`.

Membership can be handled by `set::find()` or with the
generic algorithm `binary_search()`, which is for sorted
vectors. Both are O(log n).

The remaining set algorithms have linear complexity. That is, an algorithm that takes two "sets" of size M and N will be O(M+N)

The generic set algorithms have two forms, one with just the
"sets," and another with an extra binary predicate argument. The
first form uses `operator=()` to determine element equality.
The second form uses the equality predicate you pass it.

**Caution**: the equality predicate is applied only to elments
deemed "equal" by the "less than" predicate used to sort the set,
that is to X and Y only if X is not less than Y and Y is not less
than X.

`includes` returns true if the first
"set" includes the second.

bool includes(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2); bool includes(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, Predicate pred);

`set_union` copies the union of both
input ranges into the ouput iterator and returns the end of the
result.

OutputIteratorset_union(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result); OutputIteratorset_union(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result, Predicate pred);

`set_intersection` copies the
intersection of both input ranges into the ouput iterator and returns
the end of the result.

OutputIteratorset_intersection(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result); OutputIteratorset_intersection(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result, Predicate pred);

`set_difference` copies the
elements in the first range not in the second range into the ouput
iterator and returns the end of the result.

OutputIteratorset_difference(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result); OutputIteratorset_difference(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result, Predicate pred);

`set_symmetric_difference` copies
the elements in each range not in the other range into the ouput
iterator and returns the end of the result.

OutputIteratorset_symmetric_difference(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result); OutputIteratorset_symmetric_difference(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result, Predicate pred);

*Comments? Send mail to
* c-riesbeck@northwestern.edu.