Rationale for Ada 2005
8.1 Organization of containers
A major enhancement to the predefined library in
Ada 2005 is the addition of a container library. This is quite extensive
and merits this separate chapter on its own. Other aspects of the predefined
library and the overall rationale for extending the library were described
in the previous chapter (see
7).
The main packages in the container library can be
grouped in various ways. One set of packages concerns the manipulation
of objects of definite types and another, essentially identical, set
concerns indefinite types. (Remember that an indefinite (sub)type is
one for which we cannot declare an object without giving a constraint.)
The reason for the duplication concerns efficiency. It is much easier
to manipulate definite types and although the packages for indefinite
types can be used for definite types, this would be rather inefficient.
We will generally only consider the definite packages.
These in turn comprise two groups.
Sequence containers –
these hold sequences of elements. There are packages for manipulating
vectors and for manipulating linked lists. These two packages have much
in common. But they have different behaviours in terms of efficiency
according to the pattern of use. In general (with some planning) it should
be possible to change from one to the other with little effort.
Associative containers –
these associate a key with each element and then store the elements in
order of the keys. There are packages for manipulating hashed maps, ordered
maps, hashed sets and ordered sets. These four packages also have much
in common and changing between hashed and ordered versions is usually
feasible.
There are also quite separate generic procedures
for sorting arrays which we will consider later.
package Ada.Containers is
pragma Pure(Containers);
type Hash_Type is mod implementation-defined;
type Count_Type is range 0 .. implementation-defined;
end Ada.Containers;
The type Hash_Type is
used by the associative containers and Count_Type
is used by both kinds of containers typically for the number of elements
in a container. Note that we talk about elements in a container rather
than the components in a container – components is the Ada term
for the items of an array or record as an Ada type and it is convenient
to use a different term since in the case of containers the actual data
structure is hidden.
Worst-case and average-case time complexity bounds
are given using the familiar O( ... ) notation. This encourages
implementations to use techniques that scale reasonably well and avoid
junk algorithms such as bubble sort.
Perhaps a remark about using containers from a multitasking
program would be helpful. The general rule is given in paragraph 3 of
Annex A which says "The implementation shall ensure that each language
defined subprogram is reentrant in the sense that concurrent calls on
the same subprogram perform as specified, so long as all parameters that
could be passed by reference denote nonoverlapping objects." So
in other words we have to protect ourselves by using the normal techniques
such as protected objects when container operations are invoked concurrently
on the same object from multiple tasks even if the operations are only
reading from the container.
© 2005, 2006 John Barnes Informatics.
Sponsored in part by:
