The set class implements an ordered collection of elements with
no duplicates. Internally this is implemented as a balanced tree. If an
item that is already present is inserted into the set, nothing happens.
Some of the key functions are:
-
set<T> S : creates an empty set S.
-
S.size() : returns the number of elements in S.
-
S.insert( const T& ) : adds an item to the set. Nothing is done if
the item is already present in the set (this is not an error).
-
S.count( const T& t ) : returns the number of times that the item t
is found in the set. This will be either 0 or 1.
-
S.erase( const T& t ) : removes the item t from the set.
-
S.find( const T& t ) : returns an iterator that points to the item
t, or S.end() if the item could not be found.
-
S.begin() : returns an iterator that points to the first element of S.
Note that this is the smallest item in the set, because the set is always
stored in sorted order.
-
S.end() : returns an iterator that points just past the last element of
S.
Note that this is the largest item in the set, because the set is always
stored in sorted order.
The header file for set also defines a multiset. This is
an ordered collection of items, where the items may occur 0 or more times.
Internally this is implemented as a balanced tree. If an item that is already
present is inserted into the set, nothing happens. Some of the key functions
are:
-
multiset<T> S : creates an empty multiset S.
-
S.size() : returns the number of elements in S.
-
S.insert( const T& ) : adds an item to the set. If the item is already
present, there will be multiple copies in the multiset..
-
S.count( const T& t ) : returns the number of times that the item t
is found in the set. This will be 0 if the item is not found.
-
S.erase( const T& t ) : removes the all items equal to t from
the multiset.
-
S.erase( multiset<T>::iterator i ) : removes the item pointed to by
i.
-
reverse( iterator begin, iterator end ) : reverses the order of the items:
S.erase( v ); // ALL: removes all of items == v from the multiset
S.erase( S.find( v ) ); // ONE: removes the first item == v from the multiset
-
S.find( const T& t ) : returns an iterator that points to the first
item == t, or S.end() if the item could not be found.
-
S.begin() : returns an iterator that points to the first element of S.
Note that this is the smallest item in the multiset, because the multiset
is always stored in sorted order.
-
S.end() : returns an iterator that points just past the last element of
S.
Note that this is the largest item in the multiset, because the multiset
is always stored in sorted order.