A.18 Containers

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