ADTSet and ADTMultiset
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) |
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.
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 is like the set, except that it allows elements with duplicate keys. But because of this, one of the insert functions in 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) |