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|
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.
Since vectors can hold other vectors as elements, such structures can be easily constructed.
A novel substitution is the graph representation discussed in Section 9.3.2.
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.
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.