C++ Standard Set Algorithms

Chris Riesbeck
Last updated: July 3, 2009

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.

The Generic Set Algorithms

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.

Complexity

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)

Equality vs. Ordering

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.

Subset

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);
 

Union

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

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

Intersection

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

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

Difference

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.

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

Symmetric Difference

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.

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

Comments? Let me know!