A.18.2 The Generic Package Containers.Vectors

Implementation Note: Vectors are not intended to be sparse (that is, there are elements at all defined positions). Users are expected to use other containers (like a Map) when they need sparse structures (there is a Note to this effect at the end of this subclause).

The internal array is a conceptual model of a vector. There is no requirement for an implementation to be a single contiguous array. 

Discussion: {AI12-0112-1} For the Global aspect, any side-effects of the actual parameters of an instance are ignored. So Global => in out synchronized means that the only global side-effects allowed are associated with the actual generic parameters of the instance or with any synchronized state. Unsynchronized package state is not allowed for any container package, and pure packages do not allow any package state at all (they typically have Global => null).

{AI12-0112-1} Similarly, when Nonblocking is set to True for a generic unit, it still includes the blocking effects of the actual parameters to the instance. Thus, the only blocking allowed is that associated with the actual generic parameters. If none of the actual paramerters allow blocking, then no operation of the generic instance may block.

Ramification: {AI12-0112-1} The base type of a scalar type is always nonblocking and has Global => null. Therefore, so long as this type is used in the implementation, whether or not the actual type for Index_Type allows blocking or side-effects does not matter. Therefore, we require that operations that only operate on the container implementation be nonblocking and have Global => null regardless of the actual parameters. 

Discussion: {AI12-0112-1} Any operation that takes a cursor but no vector can read the vector associated with the cursor. We only know that there is some object of type Vector. Since we don't have a global specification that describes all objects of a specific type, we have to allow reading any object by specifying in all. For such functions, we don't allow writing any object, even those associated with generic formal parameters, thus we also specify Use_Formal => null. 

Discussion: {AI12-0112-1} For operations that do not depend on any of the operations of the generic formal parameters (including those of formal types), we specify that the operation has no side-effects of any kind. This requires specifying that there is no dependence on the generic formal parameters with Use_Formal => null in addition to no usual side-effects with null. We also specify Nonblocking on such operations in order that the operation never blocks even if some of the actual parameters allow blocking. 

Discussion: {AI12-0112-1} Here the Nonblocking and Global contracts are saying that Element depends on the properties of the actual for Element_Type, but not on the properties of the actuals for Index_Type or "=". This is necessary as copying the element may require calling Adjust and Finalize for the actual Element_Type, and those may have side-effects or block. 

Discussion: {AI12-0112-1} Finalization of this type will update the tampering counter of an associated container. We know this has to be an object of type Vector, but we don't have a way to specify that. We need this separate Global in case an object of this type is declared to exist separately from the short-lived object associated with a call of the Constant_Reference function. 

Discussion: {AI05-0112-1} The Global of null assumes that the user of a stable object is including effects associated with the access discriminant. For operations with in parameters (after any overriding), the object designated by the access discriminant is assumed to be read, and for other operations (including initialization and finalization) the object designated by the access discriminant is assumed to be read and updated. 

Ramification: The “functions defined to use it” are Find, Find_Index, Reverse_Find, Reverse_Find_Index, and "=" for Vectors. This list is a bit too long to give explicitly.

If the actual function for "=" is not symmetric and consistent, the result returned by any of the functions defined to use "=" cannot be predicted. The implementation is not required to protect against "=" raising an exception, or returning random results, or any other “bad” behavior. And it can call "=" in whatever manner makes sense. But note that only the results of the functions defined to use "=" are unspecified; other subprograms are not allowed to break if "=" is bad. 

To be honest: {AI12-0434-1} “The primitive "=" operator” is the one with two parameters of type Cursor which returns Boolean. We're not talking about some other (hidden) primitive function named "=". 

Reason: A cursor will probably be implemented in terms of one or more access values, and the effects of streaming access values is unspecified. Rather than letting the user stream junk by accident, we mandate that streaming of cursors raise Program_Error by default. The attributes can always be specified if there is a need to support streaming. 

Implementation Note: The Reference Manual requires streaming of all language-defined nonlimited types (including containers) to "work" (see 13.13.2). In addition, we do not want all of the elements that make up the capacity of the vector streamed, as those beyond the length of the container have undefined contents (and might cause bad things when read back in). This will require a custom stream attribute implementation; the language-defined default implementation will not work (even for a bounded form, as that would most likely stream the entire capacity of the vector). There is a separate requirement that the unbounded and Bounded form use the same streaming representation for the same element type, see A.18.19.

Discussion: We require the existence of Index_Type'First – 1, so that No_Index and Last_Index of an empty vector is well-defined. We don't require the existence of Index_Type'Last + 1, as it is only used as the position of insertions (and needs to be allowed only when inserting an empty vector). 

Reason: We don't want to require an implementation to go to heroic efforts to handle index values larger than the base type of the index subtype. 

To be honest: Operations which are defined to be equivalent to a call on one of these operations also are included. Similarly, operations which call one of these as part of their definition are included. 

Ramification: We don't need to explicitly mention assignment_statement, because that finalizes the target object as part of the operation, and finalization of an object is already defined as tampering with cursors.

Discussion: {AI12-0111-1} Swap, Sort, and Merge copy elements rather than reordering them, so they don't tamper with cursors. 

Reason: Complete replacement of an element can cause its memory to be deallocated while another operation is holding onto a reference to it. That can't be allowed. However, a simple modification of (part of) an element is not a problem, so Update_Element does not cause a problem. 

Proof: Tampering with elements includes tampering with cursors, so we mention it only from completeness in the second sentence. 

To be honest: {AI05-0005-1} {AI05-0212-1} This function might not detect cursors that designate deleted elements; such cursors are invalid (see below) and the result of calling Has_Element with an invalid cursor is unspecified (but not erroneous). 

Ramification: If Position is No_Element, Has_Element returns False. 

Implementation Note: This wording describes the canonical semantics. However, the order and number of calls on the formal equality function is unspecified for all of the operations that use it in this package, so an implementation can call it as many or as few times as it needs to get the correct answer. Specifically, there is no requirement to call the formal equality additional times once the answer has been determined. 

Reason: {AI12-0112-1} Prohibiting tampering with elements also needs to prohibit tampering with cursors, as deleting an element is similar to replacing it. 

Implementation Note: {AI12-0112-1} Various contracts elsewhere in this specification require that this function be implemented with synchronized data. Moreover, it is possible for tampering to be prohibited by multiple operations (sequentially or in parallel). Therefore, tampering needs to be implemented with an atomic or protected counter. The counter is initialized to zero, and is incremented when tampering is prohibited, and decremented when leaving an area that prohibited tampering. Function Tampering_With_Cursors_Prohibited returns True if the counter is nonzero. (Note that any case where the result is not well-defined for one task is incorrect use of shared variables and would be erroneous by the rules of 9.10, so no special protection is needed to read the counter.) 

Reason: {AI12-0111-1} A definite element cannot change size, so we allow operations that tamper with elements even when tampering with elements is prohibited. That's not true for the indefinite containers, which is why this kind of tampering exists. 

but since the inner calculation can overflow or the type conversion can fail, this can't be evaluated in general with an expression function. Note that if this expression raises Constraint_Error, then the result is Count_Type'Last, since the Capacity of a Vector cannot exceed Count_Type'Last.

Discussion: Expanding the internal array can be done by allocating a new, longer array, copying the elements, and deallocating the original array. This may raise Storage_Error, or cause an exception from a controlled subprogram. We require that a failed Reserve_Capacity does not lose any elements if an exception occurs, but we do not require a specific order of evaluations or copying.

This routine is used to preallocate the internal array to the specified capacity such that future Inserts do not require memory allocation overhead. Therefore, the implementation should allocate the needed memory to make that true at this point, even though the visible semantics could be preserved by waiting until the memory is needed. This doesn't apply to the indefinite element container, because elements will have to be allocated individually.

The implementation does not have to contract the internal array if the capacity is reduced, as any capacity greater than or equal to the specified capacity is allowed.

Ramification: No elements are moved by this operation; any new empty elements are added at the end. This follows from the rules that a cursor continues to designate the same element unless the routine is defined to make the cursor ambiguous or invalid; this operation does not do that. 

Reason: {AI12-0196-1} Without the preceding rule, concurrent calls to To_Cursor on the same container would interfere by the concurrent call rules in Annex A, since the container object of the concurrent calls would overlap with itself. We want these to not interfere, for example to allow the Vector elements to be split into separate “chunks” for parallel processing. 

Ramification: This implies that the index is determinable from a bare cursor alone. The basic model is that a vector cursor is implemented as a record containing an access to the vector container and an index value. This does constrain implementations, but it also allows all of the cursor operations to be defined in terms of the corresponding index operation (which should be primary for a vector).

Ramification: {AI05-0212-1} Replace_Element, Update_Element, and Reference are the only ways that an element can change from empty to nonempty. Also see the note following Update_Element. 

Reason: {AI05-0005-1} The “tamper with the elements” check is intended to prevent the Element parameter of Process from being replaced or deleted outside of Process. The check prevents data loss (if Element_Type is passed by copy) or erroneous execution (if Element_Type is an unconstrained type in an indefinite container). 

Ramification: This means that the elements cannot be directly allocated from the heap; it must be possible to change the discriminants of the element in place. 

Ramification: Since reading an empty element is a bounded error, attempting to use this procedure to replace empty elements may fail. Use Replace_Element to do that reliably. 

Reason: It is expected that Reference_Type (and Constant_Reference_Type) will be a controlled type, for which finalization will have some action to terminate the tampering check for the associated container. If the object is created by default, however, there is no associated container. Since this is useless, and supporting this case would take extra work, we define it to raise an exception. 

Discussion: {AI05-0005-1} This routine exists for compatibility with the bounded vector container. For an unbounded vector, Assign(A, B) and A := B behave identically. For a bounded vector, := will raise an exception if the container capacities are different, while Assign will not raise an exception if there is enough room in the target. 

Discussion: The idea is that the internal array is removed from Source and moved to Target. (See the Implementation Advice for Move). If Capacity (Target) /= 0, the previous internal array may need to be deallocated. We don't mention this explicitly, because it is covered by the "no memory loss" Implementation Requirement.

Ramification: Moving the elements does not necessarily involve copying. Similarly, since Reserve_Capacity does not require the copying of elements, it does not need to be explicitly called (the implementation can combine the operations if it wishes to).

Ramification: The check on Before checks that the cursor does not belong to some other Container. This check implies that a reference to the container is included in the cursor value. This wording is not meant to require detection of dangling cursors; such cursors are defined to be invalid, which means that execution is erroneous, and any result is allowed (including not raising an exception). 

Discussion: {AI12-0400-1} The messy wording is needed because Before is invalidated by Insert_Vector Insert, and we don't want Position to be invalid after this call. An implementation probably only needs to copy Before to Position. 

Ramification: {AI05-0257-1} If Count equals 0, Position will designate the element designated by Before, rather than a newly inserted element. Otherwise, Position will designate the first newly inserted element. 

Reason: This routine exists mainly to ease conversion between Vector and List containers. Unlike Insert_Space, this routine default initializes the elements it inserts, which can be more expensive for some element types. 

Ramification: If Index + Count >= Last_Index(Container), this effectively truncates the vector (setting Last_Index to Index – 1 and consequently sets Length to Index – Index_Type'First). 

Discussion: This can copy the elements of the vector — all cursors referencing the vector are ambiguous afterwards and may designate different elements afterwards. 

To be honest: The implementation is not required to actually copy the elements if it can do the swap some other way. But it is allowed to copy the elements if needed. 

Ramification: After a call to Swap, I designates the element value previously designated by J, and J designates the element value previously designated by I. The cursors do not become ambiguous from this operation. 

To be honest: The implementation is not required to actually copy the elements if it can do the swap some other way. But it is allowed to copy the elements if needed. 

Discussion: We'd rather call this “First”, but then calling most routines in here with First (Some_Vect) would be ambiguous. 

Discussion: The purpose of the “tamper with the cursors” check is to prevent erroneous execution from the Position parameter of Process.all becoming invalid. This check takes place when the operations that tamper with the cursors of the container are called. The check cannot be made later (say in the body of Iterate), because that could cause the Position cursor to be invalid and potentially cause execution to become erroneous -- defeating the purpose of the check.

There is no check needed if an attempt is made to insert or delete nothing (that is, Count = 0 or Length(Item) = 0).

The check is easy to implement: each container needs a counter. The counter is incremented when Iterate is called, and decremented when Iterate completes. If the counter is nonzero when an operation that inserts or deletes is called, Finalize is called, or one of the other operations in the list occurs, Program_Error is raised.

Discussion: Exits are allowed from the loops created using the iterator objects. In particular, to stop the iteration at a particular cursor, just add

in the body of the loop (assuming that Cur is the loop parameter and Stop is the cursor that you want to stop at). 

Ramification: This implies swapping the elements, usually including an intermediate copy. This means that the elements will usually be copied. (As with Swap, if the implementation can do this some other way, it is allowed to.) Since the elements are nonlimited, this usually will not be a problem. Note that there is Implementation Advice below that the implementation should use a sort that minimizes copying of elements.

The sort is not required to be stable (and the fast algorithm required will not be stable). If a stable sort is needed, the user can include the original location of the element as an extra "sort key". We considered requiring the implementation to do that, but it is mostly extra overhead -- usually there is something already in the element that provides the needed stability. 

Discussion: It is a bounded error if either of the vectors is unsorted, see below. The bounded error can be recovered by sorting Target after the merge call, or the vectors can be pretested with Is_Sorted. 

Implementation Note: The Merge operation will usually require copying almost all of the elements. One implementation strategy would be to extend Target to the appropriate length, then copying elements from the back of the vectors working towards the front. An alternative approach would be to allocate a new internal data array of the appropriate length, copy the elements into it in an appropriate order, and then replacing the data array in Target with the temporary. 

Ramification: The names Vector and Cursor mean the types declared in the nested package in these subprogram specifications. 

Reason: The omitted routines are those that tamper with cursors or elements (or test that state). The model is that it is impossible to tamper with cursors or elements of a stable view since no such operations are included. Thus tampering checks are not needed for a stable view, and we omit the operations associated with those checks. 

Proof: {AI12-0438-1} Initialization is required as the type is indefinite, see 3.3.1. 

Ramification: For instance, a default initialized element could be returned. Or some previous value of an element. But returning random junk is not allowed if the type has default initial value(s).

Assignment and streaming of empty elements are not bounded errors. This is consistent with regular composite types, for which assignment and streaming of uninitialized components do not cause a bounded error, but reading the uninitialized component does cause a bounded error.

There are other operations which are defined in terms of the operations listed above. 

Reason: Cursors are made ambiguous if an Insert or Delete occurs that moves the elements in the internal array including the designated ones. After such an operation, the cursor probably still designates an element (although it might not after a deletion), but it is a different element. That violates the definition of cursor — it designates a particular element.

For "=" or Has_Element, the cursor works normally (it would not be No_Element). We don't want to trigger an exception simply for comparing a bad cursor.

While it is possible to check for these cases or ensure that cursors survive such operations, in many cases the overhead necessary to make the check (or ensure cursors continue to designate the same element) is substantial in time or space. 

Proof: {AI05-0001-1} Move has been reworded in terms of Assign and Clear, which are covered by other bullets, so this text is redundant. 

Ramification: {AI05-0160-1} An element can be removed via calls to Set_Length, Clear, and Merge; and indirectly via calls to Assign and Move. 

Discussion: The list above (combined with the bounded error cases) is intended to be exhaustive. In other cases, a cursor value continues to designate its original element. For instance, cursor values survive the appending of new elements. 

Reason: Each object of Reference_Type and Constant_Reference_Type probably contains some reference to the originating container. If that container is prematurely finalized (which is only possible via Unchecked_Deallocation, as accessibility checks prevent passing a container to Reference that will not live as long as the result), the finalization of the object of Reference_Type will try to access a nonexistent object. This is a normal case of a dangling pointer created by Unchecked_Deallocation; we have to explicitly mention it here as the pointer in question is not visible in the specification of the type. (This is the same reason we have to say this for invalid cursors.) 

Implementation Note: {AI05-0298-1} {AI12-0005-1} An assignment of a Vector is a “deep” copy; that is the elements are copied as well as the data structures. We say “effect of” in order to allow the implementation to avoid copying elements immediately if it wishes. For instance, an implementation that avoided copying until one of the containers is modified would be allowed. (Note that such an implementation would be require care, as Query_Element and Constant_Reference both could be used to access an element which later needs to be reallocated while the parameter or reference still exists, potentially leaving the parameter or reference pointing at the wrong element.) 

Implementation Advice: The worst-case time complexity of Element for Containers.Vector should be O(log N).

Implementation Advice: The worst-case time complexity of Append with Count = 1 when N is less than the capacity for Containers.Vector should be O(log N).

Implementation Advice: The worst-case time complexity of Prepend with Count = 1 and Delete_First with Count=1 for Containers.Vectors should be O(N log N).

Reason: We do not mean to overly constrain implementation strategies here. However, it is important for portability that the performance of large containers has roughly the same factors on different implementations. If a program is moved to an implementation that takes O(N) time to access elements, that program could be unusable when the vectors are large. We allow O(log N) access because the proportionality constant and caching effects are likely to be larger than the log factor, and we don't want to discourage innovative implementations. 

Implementation Advice: The worst-case time complexity of a call on procedure Sort of an instance of Containers.Vectors.Generic_Sorting should be O(N**2), and the average time complexity should be better than O(N**2).

Ramification: In other words, we're requiring the use of a better than O(N**2) sorting algorithm, such as Quicksort. No bubble sorts allowed! 

Implementation Advice: Containers.Vectors.Generic_Sorting.Sort and Containers.Vectors.Generic_Sorting.Merge should minimize copying of elements.

To be honest: We do not mean “absolutely minimize” here; we're not intending to require a single copy for each element. Rather, we want to suggest that the sorting algorithm chosen is one that does not copy items unnecessarily. Bubble sort would not meet this advice, for instance. 

Implementation Advice: Containers.Vectors.Move should not copy elements, and should minimize copying of internal data structures.

Implementation Note: Usually that can be accomplished simply by moving the pointer(s) to the internal data structures from the Source vector to the Target vector. 

Implementation Advice: If an exception is propagated from a vector operation, no storage should be lost, nor any elements removed from a vector unless specified by the operation.

Reason: This is important so that programs can recover from errors. But we don't want to require heroic efforts, so we just require documentation of cases where this can't be accomplished.

Discussion: This property is the main reason why only integer types (as opposed to any discrete type) are allowed as the index type of a vector. An enumeration or modular type would require a subtype in order to meet this requirement. 

{AI95-00302-03} The package Containers.Vectors is new. 

{AI05-0001-1} Subprograms Assign and Copy are added to Containers.Vectors. If an instance of Containers.Vectors is referenced in a use_clause, and an entity E with the same defining_identifier as a new entity in Containers.Vectors is defined in a package that is also referenced in a use_clause, the entity E may no longer be use-visible, resulting in errors. This should be rare and is easily fixed if it does occur. 

{AI05-0212-1} Added iterator, reference, and indexing support to make vector containers more convenient to use. 

{AI05-0001-1} Generalized the definition of Reserve_Capacity and Move. Specified which elements are read/written by stream attributes.

{AI05-0022-1} Correction: Added a Bounded (Run-Time) Error to cover tampering by generic actual subprograms.

{AI05-0027-1} Correction: Added a Bounded (Run-Time) Error to cover access to finalized vector containers.

{AI05-0044-1} Correction: Redefined "<" actuals to require a strict weak ordering; the old definition allowed indeterminant comparisons that would not have worked in a container.

{AI05-0084-1} Correction: Added a pragma Remote_Types so that containers can be used in distributed programs.

{AI05-0160-1} Correction: Revised the definition of invalid cursors to cover missing (and new) cases.

{AI05-0265-1} Correction: Defined when a container prohibits tampering in order to more clearly define where the check is made and the exception raised.

{AI12-0111-1} Tampering with elements is now defined to be equivalent to tampering with cursors for ordinary containers. If a program requires tampering detection to work, it might fail in Ada 2022. Specifically, if a program requires Program_Error to be raised by a routine that (only) tampers with elements in Ada 2012 (such as Replace_Element) when called in a context that does not allow tampering with elements (such as Update_Element), the routine will work as defined instead of raising Program_Error in Ada 2022. Needless to say, this shouldn't happen outside of test programs. Note that such contexts still prohibit tampering with cursors, so routines like Insert and Delete will still raise Program_Error in this case.

{AI12-0112-1} Trying to insert or concatenate more than Count_Type'Last elements will now raise Constraint_Error rather than Capacity_Error. This is extremely unlikely to happen, as Count_Type'Last is typically at least 2**31-1, so most such vectors will exceed memory before reaching this error. 

{AI12-0111-1} {AI12-0112-1} {AI12-0339-1} A number of new subprograms, types, and even a nested package were added to Containers.Vectors to better support contracts and stable views. Therefore, a use clause conflict is possible; see the introduction of Annex A for more on this topic.

{AI12-0005-1} {AI12-0212-1} {AI12-0400-1} Vector objects now support aggregates. This introduces a potential incompatibility for overloaded routines, including the "&" operations defined in this package. If the Element_Type of the vector is a type that allows aggregates (such as a record type), then calls to the "&" operations with an aggregate element will become ambiguous in Ada 2022, while they would have been legal in Ada 2012. This can be fixed by qualifying the aggregate with the element type.

{AI12-0400-1} Correction: The Insert, Append, and Prepend operations that operate on two vectors have been renamed Insert_Vector, Append_Vector, and Prepend_Vector, respectively. This was done in order to eliminate the aggregate ambiguity for the commonly used single element Append and Insert routines. The renamed routines are rarely used in Ada 2012 code, so the impact should be minimal. 

{AI12-0196-1} Correction: To_Cursor and Replace_Element are now defined such that they can be used concurrently so long as they operate on different elements. This allows some container operations to be used in parallel without separate synchronization.

{AI12-0212-1} Vectors now support indexed container aggregates, so aggregate syntax can be used to create Vectors.

{AI12-0266-1} The iterator for the entire container now can return a parallel iterator which can be used to process the container in parallel.

{AI12-0110-1} Corrigendum: Clarified that tampering checks precede all other checks made by a subprogram (but come after those associated with the call).

{AI12-0112-1} Added contracts to this container. This includes describing some of the semantics with pre- and postconditions, rather than English text. Note that the preconditions can be Suppressed (see 11.5).

{AI12-0400-1} Correction: Split the Append routine into two routines rather than having a single routine with a default parameter, in order that a routine with the appropriate profile for the Aggregate aspect exists. This change should not change the behavior of any existing code.