There are a number of "classic" container types that are not found in the standard library. In most cases, the reason is that the containers that have been provided can easily be adapted to a wide variety of uses, including those traditionally solved by these alternative collections.
There is no tree collection that is described as such. However, the set data type is internally implemented using a form of binary search tree. For most problems that would be solved using trees, the set data type is an adequate substitute.
The set data type is specifically ordered, and there is no provision for performing set operations (union, intersection, and so on) on a collection of values that cannot be ordered (for example, a set of complex numbers). In such cases 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 in this case.
There are no multidimensional arrays. However, vectors can hold other vectors as elements, so such structures can be easily constructed.
There are no graphs. However, 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.
There are no sparse arrays. A novel solution to this problem is to use the graph representation discussed in Section 9.3.2.
There are no hash tables. A hash table provides amortized constant time access, insertion and removal of elements, by converting access and removal operations into indexing operations. However, hash tables 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.
In short, while not providing every conceivable container type, the containers in the standard library represent those used in the solution of most problems, and a solid foundation from which further structures can be constructed.
©Copyright 1996, Rogue Wave Software, Inc.