Container Types Not Found in the C++ Standard Library

Apache C++ Standard Library User's Guide

4.4 Container Types Not Found in the C++ Standard Library

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.

Table 8: Container types not given in the C++ Standard Library

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 vector*s as elements, such structures can be easily constructed.
graph	One representation for graphs can be easily constructed as a *map* that holds other *map*s. 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 *list*s.