The C++ Standard Library provides the containers used in the solution of most programming problems. However, there are a number of classic container types that are not included. In most cases, this is because the provided containers can be easily adapted to a wide variety of uses, including the uses traditionally provided by the omitted containers. Table 8 lists the container types that are not contained in the library, and the simple substitution.
Container type NOT given | C++ Standard Library substitution |
tree | The set datatype is internally implemented using a form of binary search tree. For most problems that would be solved using trees, the set datatype is an adequate substitute. |
multidimensional array | Since vectors can hold other vectors as elements, such structures can be easily constructed. |
graph | One representation for graphs can be easily constructed as a map that holds other maps. This type of structure is described in the sample problem discussed in Section 9.3.2. |
sparse array | A novel substitution is the graph representation discussed in Section 9.3.2. |
hash table | A hash table provides amortized constant time access, and insertion and removal of elements, by converting access and removal operations into indexing operations. In the C++ Standard Library, a hash table can be easily constructed as a vector (or deque) that holds lists (or even sets) as elements. A similar structure is described in the radix sort sample problem discussed in Section 7.3, although this example does not include invoking a hash function to convert a value into an index. maps and multimaps provide features similar to a hash table's, but inserts and searches are performed in log(N) time, with N being the size of the map or multimap. |
some set functionality | In the C++ Standard Library, the set datatype is specifically ordered, and set operations (union, intersection, and so on) cannot be performed on collections of unordered values (for example, a set of complex numbers). A list can be used as a substitute, although it is still necessary to write special set operation functions, as the generic algorithms cannot be used with lists. |