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.
Term entry: container
— structured object that represents a collection of elements all
of the same (potentially class-wide) type, such as a vector or a tree
Note: Several predefined container types are provided by the children
of package Ada.Containers (see A.18.1).
{
AI95-00302-03}
{
AI12-0196-1}
{
AI12-0416-1}
A variety of sequence and associative containers are provided. Each container
package defines includes a
cursor
type
as well as a container 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
only
with the
element container
object itself.
Reason: {
AI12-0005-1}
{
AI12-0196-1}
The last sentence is intended to clarify that operations that just use
a cursor
do not interfere if the cursor objects
designated different elements of the container are
on the same footing as operations that use a container in terms
of the
concurrent call reentrancy
rules of
Annex A.
Ramification: {
AI12-0196-1}
A cursor is not considered to overlap with other
elements of the associated container, thus parallel operations involving
a set of cursors each operating on mutually exclusive sets of elements
from the same container are expected to work.
Discussion: {
AI12-0416-1}
We use the term “container” alone when
it is clear from context what kind of entity (package, type, or object)
that we are talking about. Otherwise, we use “container package”,
“container type”, or “container object”. Note
that "container type" is defined in 4.3.5
for a different usage; in all of A.18 we mean
“container type” to be one of the primary types declared
in the child packages of package Containers, such as Vector, List, or
Map.
{
AI12-0111-1}
{
AI12-0439-1}
Some operations of the language-defined child units
of Ada.Containers have access-to-subprogram parameters. To ensure such
operations are well-defined, they guard against certain actions by the
designated subprogram. An action on a container that can add or remove
an element is considered to tamper with cursors,
and these are prohibited during all such operations. An action on a container
that can replace an element with one of a different size is considered
to tamper with elements, and these are prohibited during certain
of such operations. The details of the specific actions
that are considered to tamper with cursors or elements are defined for
each child unit of Ada.Containers.
{
AI12-0111-1}
Several of the language-defined child units of
Ada.Containers include a nested package named Stable, which provides
a view of a container that prohibits any operations that would tamper
with elements. By using a Stable view for manipulating a container, the
number of tampering checks performed while performing the operations
can be reduced. The details of the Stable subpackage are defined separately
for each child unit of Ada.Containers that includes such a nested package.
{
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}
{
AI12-0416-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).
Elements are in a smallest first order using
such an operator if, for every element y with a predecessor x
in the order, (y < x) is false.
Reason: {
AI12-0416-1}
Given a "<" operator that provides
a strict weak ordering, knowing that (y < x) is false
is enough to know that (x <= y) is true. For a strict
weak ordering, (x = y) when both (x < y)
and (y < x) are false. Therefore, it is not necessary
to use the "=" operator or test (x < y). We
only need to discuss adjacent elements since a strict weak ordering is
transitive.
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:
{
AI12-0196-1}
Library packages must
allow concurrent calls 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
and concurrent calls to operations
of the container have overlapping parameters.
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.
{
AI12-0258-1}
If a container's element type is controlled, the point at which the element
is finalized will depend on the implementation of the container.
For
certain kinds of containers, we require finalization behavior based on
the canonical implementation of the container (see the Implementation
Requirements below). For the "normal" containers, we 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 implementations
flexibility to cache, block,
or split
,
or reuse 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 paragraph
was deleted.{
AI12-0258-1}
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: {
AI12-0005-1}
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
that, 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}
{
AI12-0449-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}
{
AI12-0449-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: {
AI12-0449-1}
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.
Implementation Requirements
{
AI12-0258-1}
For an indefinite container (one whose type is
defined in an instance of a child package of Containers whose defining_identifier
contains "Indefinite"), each element of the container shall
be created when it is inserted into the container and finalized when
it is deleted from the container (or when the container object is finalized
if the element has not been deleted). For a bounded container (one whose
type is defined in an instance of a child package of Containers whose
defining_identifier
starts with "Bounded") that is not an indefinite container,
all of the elements of the capacity of the container shall be created
and default initialized when the container object is created; the elements
shall be finalized when the container object is finalized. [For other
kinds of containers, when elements are created and finalized is unspecified.]
Ramification: This
allows a user to be able to reason about the behavior of elements that
have controlled parts. In most cases, such elements need to be stored
in an indefinite container.
Implementation Note:
If the containers are implemented in Ada, this implies that elements
for an indefinite container are allocated individually, and that a bounded
container contains an array of elements or other data structure that
is initialized for the entire capacity of the container when it is created.
There is no such restriction on the implementation of the "normal"
containers; these can be handled in any way convenient to the implementation
— in particular, node reuse is allowed.
{
AI12-0112-1}
For an instance I of a container package
with a container type, the specific type T of the object returned
from a function that returns an object of an iterator interface, as well
as the primitive operations of T, shall be nonblocking. The Global
aspect specified for T and the primitive operations of T
shall be (in all, out synchronized) or a specification
that allows access to fewer global objects.
Implementation Note:
This requires that the traversal and iteration operations of a container
do not create, destroy, or assign any objects of a formal type of I,
nor call any formal subprograms of I. Those objects and subprograms
might be blocking (depending on the actual parameters). We put similar
requirements on the individual traversal operations in the container
package definitions.
Reason: These requirements
allows users to use container iterators inside of parallel constructs,
regardless of the actual parameters to the instantiation. If such an
iterator allowed blocking, it would be illegal inside of a parallel construct
(see 9.5). If such an iterator allowed writing
of unsynchronized global objects, it would be illegal when the default
conflict checking policy is in effect (see 9.10.1).
These requirements include sequential iterators; the iterator does not
need to appear in a parallel loop to trigger these requirements.
Discussion: We
have to give these requirements as a text rule, as there is no place
to declare suitable aspects. The specific type of a container iterator
is declared by the implementation and is not part of the visible specification
(iterator functions just return a value of a class-wide type). The iterator
interface itself cannot impose such a requirement since it needs to be
able to work with user-defined types that do need to allow blocking.
We give this as a global requirement to avoid duplication.
Extensions to Ada 95
Wording Changes from Ada 2005
{
AI05-0044-1}
Correction: Added a definition of strict weak ordering.
Extensions to Ada 2012
{
AI12-0196-1}
Correction: We now say
that a cursor only overlaps with the element it designates, rather than
with the whole container. This allows some reading operations to operate
on the container in parallel without separate synchronization.
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.
{
AI12-0111-1}
Moved the basic description of tampering checks
here, to cut duplication in description of the individual containers.
Added a description of stable views of containers.
{
AI12-0112-1}
Added a global requirement that iterators returned
from containers are nonblocking if the instance is nonblocking.
{
AI12-0258-1}
Correction: Defined when objects are created
and finalized for Bounded and Indefinite containers, so that these can
be used reliably with controlled element types. This is not incompatible
as this behavior was previously unspecified; code depending on specific
behavior was wrong.
{
AI12-0005-1}
{
AI12-0416-1}
Added a definition of “smallest first”
ordering, so that the behavior of the Sort procedures when elements are
equal is well-defined.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe