The set Abstract Data Type

Some of the newer textbooks on data structures may include a data structure called "set", or "bag", which is similar. The "set" class supports an "associative" container which provides efficient storage of keys.

The term "set" in this context is a bit unfortunate, actually, particularly if you are familiar with mathematical sets. In mathematics, sets are normally not ordered, but the elements in an STL set do have an order associated with them. In fact, if we store a simple type like int or char in a set, we have in effect a sorted list. We can also, of course, store class objects in a set, provided the class overloads operator<.

The following list of operations is typical of what a set might provide, and includes the STL versions of those operations. There are a number of other operations available in the STL set as well.

Set Operations
Generic (ADT) Specific (STL)
Construct a set
Default constructor set<T> s;
Copy constructor set<T> s(otherSet);
Construct a set from a range of elements set<T> s(inputIter1, inputIter2);
Test a set
Test for emptiness empty()
Add one or more elements to a set
Insert the element passed and return a pair struct containing the iterator position of that element (or of the previously existing element) and a boolean indicating whether the insertion succeeded insert(element)
Insert the element passed, with iter a "hint" at the location (for efficiency purposes) and return the iterator position of the inserted element (or of the previously existing element) insert(iter, element)
Insert elements from the given range insert(startIter, endIter)
Remove one or more elements from a set
Remove all elements clear()
Remove element which has key equal to keyVal erase(keyVal)
Remove element at the iterator position erase(iter)
Remove all elements in the given range erase(startIter, endIter)
Search operations
Return number of elements (0 or 1) having the given key value count(keyVal)
Return iterator position of element whose key is same as keyVal, or end() find(keyVal)
Return first iterator position where keyVal would be inserted (position of first element with key value >= keyVal) lower_bound(keyVal)
Return last iterator position where keyVal would be inserted (position of first element with key value > keyVal) upper_bound(keyVal)
Return the values of lower_bound(keyVal) and upper_bound(keyVal) as a pair struct, with lower_bound first and upper_bound second equal_range(keyVal)
Retrieve set size
Return the maximum size max_size()
Return the current size size()
Miscellaneous set operations
Exchange the contents of one set with another swap(otherSet)

What kind of iterator does the set container provide?

The set<T>::iterator and set<T>::reverse_iterator iterators are bidirectional iterators, the second-most powerful kind of STL iterator. The member function begin() returns the iterator position of the first element of the set, while end() is a member function returning the iterator position "one past the end" of the set. Analogously, rbegin() and rend() return the iterator positions of the last element, and "one before the first element", respectively.

When should a set container class be used?

The set container class is similar to the map, except that in sets the key and value are not separated like they are in maps. In other words, in a set the key is simply part of the data and in the case of simple data type like int or char, the key and the value are one and the same. Sets provide very efficient containers when there is no need to separate the key from the data.

The set class is one of the four "associative" container classes in the STL. The multiset, the map and the multimap are the other three.

The multiset Abstract Data Type

The multiset is like the set, except that it allows elements with duplicate keys. But because of this, one of the insert functions int the multiset interface has a different return value from the corresponding function in the set interface, and the count function may now return a value other than 0 or 1, as shown in the table below:

Multiset Operations
Generic (ADT) Specific (STL)
Insert the element passed and return the iterator position of that element insert(element)
Return number of elements having the given key value count(keyVal)