A.18 Containers
{
AI95-00302-03}
This clause presents the specifications of the package Containers and
several child packages, which provide facilities for storing collections
of elements.
Glossary entry: A container is an object
that contain other objects all of the same type, which could be class-wide.
Several predefined container types are provided by the children of package
Ada.Containers (see
A.18.1).
{
AI95-00302-03}
A variety of sequence and associative containers are provided. Each container
includes a
cursor type. A cursor is a reference to an element
within a container. Many operations on cursors are common to all of the
containers. A cursor referencing an element in a container is considered
to be overlapping with the container object itself.
Reason: The last sentence is intended
to clarify that operations that just use a cursor are on the same footing
as operations that use a container in terms of the reentrancy rules of
Annex A.
{
AI95-00302-03}
Within this clause we provide Implementation Advice for the desired average
or worst case time complexity of certain operations on a container. This
advice is expressed using the Landau symbol
O(X). Presuming f
is some function of a length parameter N and t(N) is the time the operation
takes (on average or worst case, as specified) for the length N, a complexity
of
O(f(N)) means that there exists a finite A such that for any
N, t(N)/f(N) < A.
Discussion: Of course, an implementation
can do better than a specified O(f(N)): for example, O(1)
meets the requirements for O(log N).
This concept seems to have as many names as
there are authors. We used “Landau symbol” because that's
what our reference does. But we'd also seen this referred as big-O notation
(sometimes written as
big-oh), and as Bachmann notation. Whatever
the name, it always has the above definition.
If the advice suggests that the complexity should
be less than O(f(N)), then for any arbitrarily small positive
real D, there should exist a positive integer M such that for all N >
M, t(N)/f(N) < D.
{
AI05-0001-1}
{
AI05-0044-1}
When a formal function is used to provide an ordering for a container,
it is generally required to define a strict weak ordering. A function
"<" defines a
strict weak ordering
if it is irreflexive, asymmetric, transitive, and in addition, if
x
<
y for any values
x and
y, then for all other
values
z, (
x <
z) or (
z <
y).
Language Design Principles
{
AI95-00302-03}
{
AI05-0299-1}
This subclause provides a number of useful containers for Ada. Only the
most useful containers are provided. Ones that are relatively easy to
code, redundant, or rarely used are omitted from this set, even if they
are generally included in containers libraries.
The containers packages are modeled on the Standard
Template Library (STL), an algorithms and data structure library popularized
by Alexander Stepanov, and included in the C++ standard library. The
structure and terminology differ from the STL where that better maps
to common Ada usage. For instance, what the STL calls “iterators”
are called “cursors” here.
The following
major nonlimited containers are provided:
(Expandable) Vectors of any nonlimited type;
Doubly-linked Lists of any nonlimited type;
Hashed Maps keyed by any nonlimited hashable
type, and containing any nonlimited type;
Ordered Maps keyed by any nonlimited ordered
type, and containing any nonlimited type;
{
AI05-0136-1}
Hashed Sets of any nonlimited hashable type;
{
AI05-0136-1}
Ordered Sets of any nonlimited ordered type;
{
AI05-0069-1}
Holders of any (indefinite) nonlimited type;
{
AI05-0159-1}
Synchronized queues of any definite nonlimited type; and
{
AI05-0159-1}
Priority queues of any definite nonlimited type.
{
AI05-0001-1}
Separate versions for definite and indefinite element types are provided,
as those for definite types can be implemented more efficiently. Similarly,
a separate bounded version is provided in order to give more predictable
memory usage.
Each container includes a cursor, which is a
reference to an element within a container. Cursors generally remain
valid as long as the container exists and the element referenced is not
deleted. Many operations on cursors are common to all of the containers.
This makes it possible to write generic algorithms that work on any kind
of container.
The containers packages are structured so that
additional packages can be added in the future. Indeed, we hope that
these packages provide the basis for a more extensive secondary standard
for containers.
If containers with similar functionality (but
different performance characteristics) are provided (by the implementation
or by a secondary standard), we suggest that a prefix be used to identify
the class of the functionality: "Ada.Containers.Bounded_Sets"
(for a set with a maximum number of elements); "Ada.Containers.Protected_Maps"
(for a map which can be accessed by multiple tasks at one time); "Ada.Containers.Persistent_Vectors"
(for a persistent vector which continues to exist between executions
of a program) and so on.
Note that the
language already includes several requirements that are important to
the use of containers. These include:
Library packages must be reentrant –
multiple tasks can use the packages as long as they operate on separate
containers. Thus, it is only necessary for a user to protect a container
if a single container needs to be used by multiple tasks.
Language-defined types must stream "properly".
That means that the stream attributes can be used to implement persistence
of containers when necessary, and containers can be passed between partitions
of a program.
Equality of language-defined types must compose
“properly”. This means that the version of "="
directly used by users is the same one that will be used in generics
and in predefined equality operators of types with components of the
containers and/or cursors. This prevents the abstraction from breaking
unexpectedly.
{
AI05-0048-1}
Redispatching is not allowed (unless it is required). That means that
overriding a container operation will not change the behavior of any
other predefined container operation. This provides a stable base for
extensions.
If a container's element type is controlled,
the point at which the element is finalized will depend on the implementation
of the container. We do not specify precisely where this will happen
(it will happen no later than the finalization of the container, of course)
in order to give implementation's flexibility to cache, block, or split
the nodes of the container. In particular, Delete does not necessarily
finalize the element; the implementation may (or may not) hold the space
for reuse.
This is not likely to be a hardship, as the
element type has to be nonlimited. Types used to manage scarce resources
generally need to be limited. Otherwise, the amount of resources needed
is hard to control, as the language allows a lot of variation in the
number or order of adjusts/finalizations. For common uses of nonlimited
controlled types such as managing storage, the types already have to
manage arbitrary copies.
The use of controlled types also brings up the
possibility of failure of finalization (and thus deallocation) of an
element. This is a “serious bug”, as AI95-179 puts it, so
we don't try to specify what happens in that case. The implementation
should propagate the exception.
Implementation Note: It is expected that
exceptions propagated from these operations do not damage containers.
That is, if Storage_Error is propagated because of an allocation failure,
or Constraint_Error is propagated by the assignment of elements, the
container can continue to be used without further exceptions. The intent
is that it should be possible to recover from errors without losing data.
We don't try to state this formally in most cases, because it is hard
to define precisely what is and is not allowed behavior.
Implementation Note: When this clause
says that the behavior of something is unspecified
,
we really mean that any result of executing Ada code short of erroneous
execution is allowed. We do not mean that memory not belonging to the
parameters of the operation can be trashed. When we mean to allow erroneous
behavior, we specifically say that execution is erroneous. All this means
if the containers are written in Ada is that checks should not be suppressed
or removed assuming some behavior of other code, and that the implementation
should take care to avoid creating internal dangling accesses by assuming
behavior from generic formals that can't be guaranteed. We don't try
to say this normatively because it would be fairly complex, and implementers
are unlikely to increase their support costs by fielding implementations
that are unstable if given buggy hash functions, et al.
Static Semantics
{
AI12-0035-1}
Certain subprograms declared within instances of some of the generic
packages presented in this clause are said to
perform indefinite insertion.
These subprograms are those corresponding (in the sense of the copying
described in subclause
12.3) to subprograms
that have formal parameters of a generic formal indefinite type and that
are identified as performing indefinite insertion in the subclause defining
the generic package.
{
AI12-0035-1}
If a subprogram performs indefinite insertion, then certain run-time
checks are performed as part of a call to the subprogram; if any of these
checks fail, then the resulting exception is propagated to the caller
and the container is not modified by the call. These checks are performed
for each parameter corresponding (in the sense of the copying described
in
12.3) to a parameter in the corresponding
generic whose type is a generic formal indefinite type. The checks performed
for a given parameter are those checks explicitly specified in subclause
4.8 that would be performed as part of the
evaluation of an initialized allocator whose access type is declared
immediately within the instance, where:
the designated subtype of the access type is the
subtype of the parameter; and
finalization of the collection of the access type
has started if and only if the finalization of the instance has started.
Discussion: The phrase "explicitly
specified" means those checks for which subclause
4.8
includes the phrase "<some exception> is raised if ...".
It does not refer, for example, to any checks performed as part of any
subtype conversion. In particular, this wording includes the checks described
in subclause
4.8 to be performed in the case
of a class-wide designated type, and of a designated subtype that has
access discriminant parts. These checks are needed to prevent containers
from outliving their contained (Element_Type or Key_Type) values.
Implementation Note: These rules have
a dual purpose. Mainly, we are
requiring checks needed to prevent
dangling references. As a side effect, we are also
allowing checks
needed to permit an implementation of a container generic to make use
of access types in a straightforward way. As an example of the second
purpose, suppose that an implementation does declare such an access type
and suppose further that the finalization of the collection of the access
type has started. These rules allow Program_Error to be propagated in
this case (as specified in
4.8); this is necessary
to allow an all-Ada implementation of these packages.
Extensions to Ada 95
Wording Changes from Ada 2005
{
AI05-0044-1}
Correction: Added a definition of strict weak ordering.
Wording Changes from Ada 2012
{
AI05-0035-1}
Corrigendum: Added a definition of “performs indefinite
insertion”. This is used in other subclauses and any resulting
inconsistencies are documented there.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
