A.18 Containers
1/2
This clause presents the specifications of the package
Containers and several child packages, which provide facilities for storing
collections of elements.
2/2
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.
3/2
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.
4/2
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.
5/3
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