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 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.

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.

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*
< *y* for any values *x* and *y*, then for all other
values *z*, (*x* < *z*) or (*z* < *y*).

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.

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 value of the qualified_expression
is that of the parameter; and

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.

Ada 2005 and 2012 Editions sponsored in part by **Ada-Europe**