Previous fileTop of DocumentContentsIndex pageNext file
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


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.


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.

Previous fileTop of DocumentContentsIndex pageNext file