Containers

Term entry: container — structured object that represents a collection of elements all of the same (potentially class-wide) type, such as a vector or a tree
Note: Several predefined container types are provided by the children of package Ada.Containers (see A.18.1).

{AI95-00302-03} {AI12-0196-1} {AI12-0416-1} A variety of sequence and associative containers are provided. Each container package defines a cursor type as well as a container 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 only with the element itself.

Reason: {AI12-0005-1} {AI12-0196-1} The last sentence is intended to clarify that operations that just use a cursor do not interfere if the cursor objects designated different elements of the container in terms of the concurrent call rules of Annex A.

Ramification: {AI12-0196-1} A cursor is not considered to overlap with other elements of the associated container, thus parallel operations involving a set of cursors each operating on mutually exclusive sets of elements from the same container are expected to work.

Discussion: {AI12-0416-1} We use the term “container” alone when it is clear from context what kind of entity (package, type, or object) that we are talking about. Otherwise, we use “container package”, “container type”, or “container object”. Note that "container type" is defined in 4.3.5 for a different usage; in all of A.18 we mean “container type” to be one of the primary types declared in the child packages of package Containers, such as Vector, List, or Map.

{AI12-0111-1} {AI12-0439-1} Some operations of the language-defined child units of Ada.Containers have access-to-subprogram parameters. To ensure such operations are well-defined, they guard against certain actions by the designated subprogram. An action on a container that can add or remove an element is considered to tamper with cursors, and these are prohibited during all such operations. An action on a container that can replace an element with one of a different size is considered to tamper with elements, and these are prohibited during certain of such operations. The details of the specific actions that are considered to tamper with cursors or elements are defined for each child unit of Ada.Containers.

{AI12-0111-1} Several of the language-defined child units of Ada.Containers include a nested package named Stable, which provides a view of a container that prohibits any operations that would tamper with elements. By using a Stable view for manipulating a container, the number of tampering checks performed while performing the operations can be reduced. The details of the Stable subpackage are defined separately for each child unit of Ada.Containers that includes such a nested package.

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

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

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 (sometimes written as big-oh), and as Bachmann notation. Whatever the name, it always has the above definition.

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.

{AI05-0001-1} {AI05-0044-1} {AI12-0416-1} 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). Elements are in a smallest first order using such an operator if, for every element y with a predecessor x in the order, (y < x) is false.

Reason: {AI12-0416-1} Given a "<" operator that provides a strict weak ordering, knowing that (y < x) is false is enough to know that (x <= y) is true. For a strict weak ordering, (x = y) when both (x < y) and (y < x) are false. Therefore, it is not necessary to use the "=" operator or test (x < y). We only need to discuss adjacent elements since a strict weak ordering is transitive.

Language Design Principles

{AI95-00302-03} {AI05-0299-1} This subclause 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.

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.

The following major nonlimited containers are provided:

{AI05-0001-1} Separate versions for definite and indefinite element types are provided, as those for definite types can be implemented more efficiently. Similarly, a separate bounded version is provided in order to give more predictable memory usage.

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.

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.

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.

Note that the language already includes several requirements that are important to the use of containers. These include:

{AI12-0196-1} Library packages must allow concurrent calls – 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 and concurrent calls to operations of the container have overlapping parameters.

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.

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.

{AI05-0048-1} Redispatching is not allowed (unless it is required). That means that overriding a container operation will not change the behavior of any other predefined container operation. This provides a stable base for extensions.

{AI12-0258-1} If a container's element type is controlled, the point at which the element is finalized will depend on the implementation of the container. For certain kinds of containers, we require finalization behavior based on the canonical implementation of the container (see the Implementation Requirements below). For the "normal" containers, 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 implementations flexibility to cache, block, split , or reusethe nodes of the container.

This paragraph was deleted.{AI12-0258-1}

The use of controlled types also brings up the possibility of failure of finalization (and thus deallocation) of an element. This is a “serious bug”, as AI95-179 puts it, so we don't try to specify what happens in that case. The implementation should propagate the exception.

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.

Implementation Note: {AI12-0005-1} When this clause says that the behavior of something is unspecified, 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 that, if the containers are written in Ada, 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.

Static Semantics

{AI12-0035-1} {AI12-0449-1} Certain subprograms declared within instances of some of the generic packages presented in this clause are said to perform indefinite insertion. These subprograms are those corresponding (in the sense of the copying described in 12.3) to subprograms that have formal parameters of a generic formal indefinite type and that are identified as performing indefinite insertion in the subclause defining the generic package.

{AI12-0035-1} {AI12-0449-1} If a subprogram performs indefinite insertion, then certain run-time checks are performed as part of a call to the subprogram; if any of these checks fail, then the resulting exception is propagated to the caller and the container is not modified by the call. These checks are performed for each parameter corresponding (in the sense of the copying described in 12.3) to a parameter in the corresponding generic whose type is a generic formal indefinite type. The checks performed for a given parameter are those checks explicitly specified in 4.8 that would be performed as part of the evaluation of an initialized allocator whose access type is declared immediately within the instance, where:

Discussion: {AI12-0449-1} The phrase "explicitly specified" means those checks for which 4.8 includes the phrase "<some exception> is raised if ...". It does not refer, for example, to any checks performed as part of any subtype conversion. In particular, this wording includes the checks described in 4.8 to be performed in the case of a class-wide designated type, and of a designated subtype that has access discriminant parts. These checks are needed to prevent containers from outliving their contained (Element_Type or Key_Type) values.

Implementation Note: These rules have a dual purpose. Mainly, we are requiring checks needed to prevent dangling references. As a side effect, we are also allowing checks needed to permit an implementation of a container generic to make use of access types in a straightforward way. As an example of the second purpose, suppose that an implementation does declare such an access type and suppose further that the finalization of the collection of the access type has started. These rules allow Program_Error to be propagated in this case (as specified in 4.8); this is necessary to allow an all-Ada implementation of these packages.

Implementation Requirements

{AI12-0258-1} For an indefinite container (one whose type is defined in an instance of a child package of Containers whose defining_identifier contains "Indefinite"), each element of the container shall be created when it is inserted into the container and finalized when it is deleted from the container (or when the container object is finalized if the element has not been deleted). For a bounded container (one whose type is defined in an instance of a child package of Containers whose defining_identifier starts with "Bounded") that is not an indefinite container, all of the elements of the capacity of the container shall be created and default initialized when the container object is created; the elements shall be finalized when the container object is finalized. [For other kinds of containers, when elements are created and finalized is unspecified.]

Ramification: This allows a user to be able to reason about the behavior of elements that have controlled parts. In most cases, such elements need to be stored in an indefinite container.

Implementation Note: If the containers are implemented in Ada, this implies that elements for an indefinite container are allocated individually, and that a bounded container contains an array of elements or other data structure that is initialized for the entire capacity of the container when it is created. There is no such restriction on the implementation of the "normal" containers; these can be handled in any way convenient to the implementation — in particular, node reuse is allowed.

{AI12-0112-1} For an instance I of a container package with a container type, the specific type T of the object returned from a function that returns an object of an iterator interface, as well as the primitive operations of T, shall be nonblocking. The Global aspect specified for T and the primitive operations of T shall be (in all, out synchronized) or a specification that allows access to fewer global objects.

Implementation Note: This requires that the traversal and iteration operations of a container do not create, destroy, or assign any objects of a formal type of I, nor call any formal subprograms of I. Those objects and subprograms might be blocking (depending on the actual parameters). We put similar requirements on the individual traversal operations in the container package definitions.

Reason: These requirements allows users to use container iterators inside of parallel constructs, regardless of the actual parameters to the instantiation. If such an iterator allowed blocking, it would be illegal inside of a parallel construct (see 9.5). If such an iterator allowed writing of unsynchronized global objects, it would be illegal when the default conflict checking policy is in effect (see 9.10.1). These requirements include sequential iterators; the iterator does not need to appear in a parallel loop to trigger these requirements.

Discussion: We have to give these requirements as a text rule, as there is no place to declare suitable aspects. The specific type of a container iterator is declared by the implementation and is not part of the visible specification (iterator functions just return a value of a class-wide type). The iterator interface itself cannot impose such a requirement since it needs to be able to work with user-defined types that do need to allow blocking. We give this as a global requirement to avoid duplication.

Extensions to Ada 95

{AI95-00302-03} {AI05-0299-1} This subclause is new. It just provides an introduction to the following subclauses.

Wording Changes from Ada 2005

{AI05-0044-1} Correction: Added a definition of strict weak ordering.

Extensions to Ada 2012

{AI12-0196-1} Correction: We now say that a cursor only overlaps with the element it designates, rather than with the whole container. This allows some reading operations to operate on the container in parallel without separate synchronization.

Wording Changes from Ada 2012

{AI05-0035-1} Corrigendum: Added a definition of “performs indefinite insertion”. This is used in other subclauses and any resulting inconsistencies are documented there.

{AI12-0111-1} Moved the basic description of tampering checks here, to cut duplication in description of the individual containers. Added a description of stable views of containers.

{AI12-0112-1} Added a global requirement that iterators returned from containers are nonblocking if the instance is nonblocking.

{AI12-0258-1} Correction: Defined when objects are created and finalized for Bounded and Indefinite containers, so that these can be used reliably with controlled element types. This is not incompatible as this behavior was previously unspecified; code depending on specific behavior was wrong.