The Standard C++ 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 7 lists the container types that are not contained in the library, and the simple substitution.
Container type NOT given | Standard C++ 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 Standard C++ 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 the hash function to convert a value into an index. |
some set functionality |
In the Standard C++ Library, the set datatype is specifically ordered, and set operations (union, intersection, and so on) cannot be performed on a 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. |