Rationale for Ada 2005

John Barnes
Contents   Index   References   Search   Previous   Next 

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.
The root package is
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.

Contents   Index   References   Search   Previous   Next 
© 2005, 2006, 2007 John Barnes Informatics.
Sponsored in part by:
The Ada Resource Association and its member companies: ARA Members AdaCore Polyspace Technologies Praxis Critical Systems IBM Rational Sofcheck and   Ada-Europe:
Ada-Europe