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

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