A.18 Containers
1/2
{
AI95-00302-03}
This clause presents the specifications of the
package Containers and several child packages, which provide facilities
for storing collections of elements.2/2
{
AI95-00302-03}
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.{cursor (for a container)
[partial]} {container
(cursor)} 2.a/2
Reason: The last
sentence is intended to clarify that operations that just use a cursor
are on the same footing as operations that use a container in terms of
the reentrancy rules of Annex A.
3/2
{
AI95-00302-03}
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. {Landau
symbol O(X)} {O(f(N))}
3.a/2
Discussion: Of
course, an implementation can do better than a specified O(f(N)):
for example, O(1) meets the requirements for O(log N).
3.b/2
This concept seems to
have as many names as there are authors. We used “Landau symbol”
because that's what our reference does. But we'd also seen this referred
as big-O notation{big-O notation} (sometimes
written as big-oh), and as Bachmann notation. Whatever the name,
it always has the above definition.
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.
Language Design Principles
4.a/2
{
AI95-00302-03}
This clause provides a number of useful containers
for Ada. Only the most useful containers are provided. Ones that are
relatively easy to code, redundant, or rarely used are omitted from this
set, even if they are generally included in containers libraries.4.b/2
The containers packages
are modeled on the Standard Template Library (STL), an algorithms and
data structure library popularized by Alexander Stepanov, and included
in the C++ standard library. The structure and terminology differ from
the STL where that better maps to common Ada usage. For instance, what
the STL calls “iterators” are called “cursors”
here.
4.c/2
The
following major nonlimited containers are provided:
4.d/2
- (Expandable)
Vectors of any nonlimited type;
4.e/2
- Doubly-linked
Lists of any nonlimited type;
4.f/2
- Hashed
Maps keyed by any nonlimited hashable type, and containing any nonlimited
type;
4.g/2
- Ordered
Maps keyed by any nonlimited ordered type, and containing any nonlimited
type;
4.h/2
- Hashed
Sets of any nonlimited hashable type; and
4.i/2
- Ordered
Sets of any nonlimited ordered type.
4.j/2
Separate versions for
definite and indefinite element types are provided, as those for definite
types can be implemented more efficiently.
4.k/2
Each container includes
a cursor, which is a reference to an element within a container. Cursors
generally remain valid as long as the container exists and the element
referenced is not deleted. Many operations on cursors are common to all
of the containers. This makes it possible to write generic algorithms
that work on any kind of container.
4.l/2
The containers packages
are structured so that additional packages can be added in the future.
Indeed, we hope that these packages provide the basis for a more extensive
secondary standard for containers.
4.m/2
If containers with similar
functionality (but different performance characteristics) are provided
(by the implementation or by a secondary standard), we suggest that a
prefix be used to identify the class of the functionality: "Ada.Containers.Bounded_Sets"
(for a set with a maximum number of elements); "Ada.Containers.Protected_Maps"
(for a map which can be accessed by multiple tasks at one time); "Ada.Containers.Persistent_Vectors"
(for a persistent vector which continues to exist between executions
of a program) and so on.
4.n/2
Note
that the language already includes several requirements that are important
to the use of containers. These include:
4.o/2
- Library
packages must be reentrant – multiple tasks can use the packages
as long as they operate on separate containers. Thus, it is only necessary
for a user to protect a container if a single container needs to be used
by multiple tasks.
4.p/2
- Language-defined
types must stream "properly". That means that the stream attributes
can be used to implement persistence of containers when necessary, and
containers can be passed between partitions of a program.
4.q/2
- Equality
of language-defined types must compose “properly”. This means
that the version of "=" directly used by users is the same
one that will be used in generics and in predefined equality operators
of types with components of the containers and/or cursors. This prevents
the abstraction from breaking unexpectedly.
4.r/2
If a container's element
type is controlled, the point at which the element is finalized will
depend on the implementation of the container. We do not specify precisely
where this will happen (it will happen no later than the finalization
of the container, of course) in order to give implementation's flexibility
to cache, block, or split the nodes of the container. In particular,
Delete does not necessarily finalize the element; the implementation
may (or may not) hold the space for reuse.
4.s/2
This is not likely to
be a hardship, as the element type has to be nonlimited. Types used to
manage scarce resources generally need to be limited. Otherwise, the
amount of resources needed is hard to control, as the language allows
a lot of variation in the number or order of adjusts/finalizations. For
common uses of nonlimited controlled types such as managing storage,
the types already have to manage arbitrary copies.
4.t/2
The use of controlled
type also brings up the possibility of failure of finalization (and thus
deallocation) of an element. This is a “serious bug”, as
AI-179 puts it, so we don't try to specify what happens in that case.
The implementation should propagate the exception.
4.u/2
Implementation Note:
It is expected that exceptions propagated from these operations do
not damage containers. That is, if Storage_Error is propagated because
of an allocation failure, or Constraint_Error is propagated by the assignment
of elements, the container can continue to be used without further exceptions.
The intent is that it should be possible to recover from errors without
losing data. We don't try to state this formally in most cases, because
it is hard to define precisely what is and is not allowed behavior.
4.v/2
Implementation Note:
When this clause says that the behavior of something is unspecified{unspecified
[partial]} , we really mean that any result of executing
Ada code short of erroneous execution is allowed. We do not mean that
memory not belonging to the parameters of the operation can be trashed.
When we mean to allow erroneous behavior, we specifically say that execution
is erroneous. All this means if the containers are written in Ada is
that checks should not be suppressed or removed assuming some behavior
of other code, and that the implementation should take care to avoid
creating internal dangling accesses by assuming behavior from generic
formals that can't be guaranteed. We don't try to say this normatively
because it would be fairly complex, and implementers are unlikely to
increase their support costs by fielding implementations that are unstable
if given buggy hash functions, et al.
Extensions to Ada 95
4.w/2
{
AI95-00302-03}
{extensions to Ada 95} This
clause is new. It just provides an introduction to the following subclauses.
Sponsored by Ada-Europe