This clause presents the specifications of the package
Containers and several child packages, which provide facilities for storing
collections of elements.
A variety of sequence and associative containers
are provided. Each container package defines a cursor
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 itself.
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.
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.
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
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.
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.
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
for any values x
, then for all other
) or (z
Elements are in a smallest first
such an operator if, for every element y
with a predecessor x
in the order, (y
) is false.
Certain subprograms declared within instances of
some of the generic packages presented in this clause are said to perform
. 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.
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.
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
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.
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.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe