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