**Apache C++ Standard Library User's Guide**

## 8.1 The set Data Abstraction

A *set* is a collection of values. Although the abstract concept of a set does not necessarily imply an ordered collection, the standard library *set* datatype is always ordered.

**
NOTE -- If necessary, a collection of values that cannot be ordered can be maintained in an alternative data structure, such as a ***list*.

Because the container used to implement the *set* data structure maintains values in an ordered representation, *set*s are optimized for insertion and removal of elements, and for testing to see whether a particular value is contained in the collection. Each of these operations can be performed in a logarithmic number of steps, whereas for a *list*, *vector*, or *deque*, each operation requires in the worst case an examination of every element held by the container. For this reason, *std::set* should be the data structure of choice in any problem that emphasizes insertion, removal, and test for inclusion of values. Like a *list*, a *set* is not limited in size, but rather expands and contracts as elements are added to or removed from the collection.

There are two varieties of *set*s provided by the C++ Standard Library. In the *set* container, every element is unique, and insertions of values that are already contained in the *set* are ignored. In the *multiset* container, on the other hand, multiple occurrences of the same value are permitted.

**
NOTE -- In other programming languages, a multiset is sometimes referred to as a bag.
**

### 8.1.1 Include Files

Whenever you use a *set* or a *multiset*, you must include the set header file:

#include <set>