Container types not found in the standard library – HP Integrity NonStop H-Series User Manual
Page 52
Click on the banner to return to the user guide home page.
©Copyright 1996 Rogue Wave Software
Container Types Not Found in the Standard
Library
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
There are no sparse arrays. A novel solution to this problem is to use the graph representation
discussed in
.
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
, 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.