A.18.2 The Package Containers.Vectors
The language-defined generic package Containers.Vectors
provides private types Vector and Cursor, and a set of operations for
each type. A vector container allows insertion and deletion at any position,
but it is specifically optimized for insertion and deletion at the high
end (the end with the higher index) of the container. A vector container
also provides random access to its elements.
{vector
container} {container
(vector)} {length (of a vector
container) [partial]} {capacity
(of a vector) [partial]} A vector container
behaves conceptually as an array that expands as necessary as items are
inserted. The
length of a vector is the number of elements that
the vector contains. The
capacity of a vector is the maximum number
of elements that can be inserted into the vector prior to it being automatically
expanded.
Elements in a vector container can be referred to
by an index value of a generic formal type. The first element of a vector
always has its index value equal to the lower bound of the formal type.
{empty element (of
a vector) [partial]} A vector container
may contain
empty elements. Empty elements do not have a specified
value.
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.
Static Semantics
{
AI95-00302-03}
The generic library package Containers.Vectors has the following declaration:
generic
type Index_Type
is range <>;
type Element_Type
is private;
with function "=" (Left, Right : Element_Type)
return Boolean
is <>;
package Ada.Containers.Vectors
is
pragma Preelaborate(Vectors);
subtype Extended_Index
is
Index_Type'Base
range
Index_Type'First-1 ..
Index_Type'Min (Index_Type'Base'Last - 1, Index_Type'Last) + 1;
No_Index :
constant Extended_Index := Extended_Index'First;
type Vector
is tagged private;
pragma Preelaborable_Initialization(Vector);
type Cursor
is private;
pragma Preelaborable_Initialization(Cursor);
Empty_Vector :
constant Vector;
No_Element :
constant Cursor;
function "=" (Left, Right : Vector) return Boolean;
function To_Vector (Length : Count_Type)
return Vector;
function To_Vector
(New_Item : Element_Type;
Length : Count_Type)
return Vector;
function "&" (Left, Right : Vector) return Vector;
function "&" (Left : Vector;
Right : Element_Type) return Vector;
function "&" (Left : Element_Type;
Right : Vector) return Vector;
function "&" (Left, Right : Element_Type) return Vector;
function Capacity (Container : Vector)
return Count_Type;
procedure Reserve_Capacity (Container :
in out Vector;
Capacity :
in Count_Type);
function Length (Container : Vector)
return Count_Type;
procedure Set_Length (Container :
in out Vector;
Length :
in Count_Type);
function Is_Empty (Container : Vector)
return Boolean;
procedure Clear (Container :
in out Vector);
function To_Cursor (Container : Vector;
Index : Extended_Index)
return Cursor;
function To_Index (Position : Cursor)
return Extended_Index;
function Element (Container : Vector;
Index : Index_Type)
return Element_Type;
function Element (Position : Cursor)
return Element_Type;
procedure Replace_Element (Container :
in out Vector;
Index :
in Index_Type;
New_Item :
in Element_Type);
procedure Replace_Element (Container :
in out Vector;
Position :
in Cursor;
New_item :
in Element_Type);
procedure Query_Element
(Container :
in Vector;
Index :
in Index_Type;
Process :
not null access procedure (Element :
in Element_Type));
procedure Query_Element
(Position :
in Cursor;
Process :
not null access procedure (Element :
in Element_Type));
procedure Update_Element
(Container :
in out Vector;
Index :
in Index_Type;
Process :
not null access procedure
(Element :
in out Element_Type));
procedure Update_Element
(Container :
in out Vector;
Position :
in Cursor;
Process :
not null access procedure
(Element :
in out Element_Type));
procedure Move (Target :
in out Vector;
Source :
in out Vector);
procedure Insert (Container :
in out Vector;
Before :
in Extended_Index;
New_Item :
in Vector);
procedure Insert (Container :
in out Vector;
Before :
in Cursor;
New_Item :
in Vector);
procedure Insert (Container :
in out Vector;
Before :
in Cursor;
New_Item :
in Vector;
Position :
out Cursor);
procedure Insert (Container :
in out Vector;
Before :
in Extended_Index;
New_Item :
in Element_Type;
Count :
in Count_Type := 1);
procedure Insert (Container :
in out Vector;
Before :
in Cursor;
New_Item :
in Element_Type;
Count :
in Count_Type := 1);
procedure Insert (Container :
in out Vector;
Before :
in Cursor;
New_Item :
in Element_Type;
Position :
out Cursor;
Count :
in Count_Type := 1);
procedure Insert (Container :
in out Vector;
Before :
in Extended_Index;
Count :
in Count_Type := 1);
procedure Insert (Container :
in out Vector;
Before :
in Cursor;
Position :
out Cursor;
Count :
in Count_Type := 1);
procedure Prepend (Container :
in out Vector;
New_Item :
in Vector);
procedure Prepend (Container :
in out Vector;
New_Item :
in Element_Type;
Count :
in Count_Type := 1);
procedure Append (Container :
in out Vector;
New_Item :
in Vector);
procedure Append (Container :
in out Vector;
New_Item :
in Element_Type;
Count :
in Count_Type := 1);
procedure Insert_Space (Container :
in out Vector;
Before :
in Extended_Index;
Count :
in Count_Type := 1);
procedure Insert_Space (Container :
in out Vector;
Before :
in Cursor;
Position :
out Cursor;
Count :
in Count_Type := 1);
procedure Delete (Container :
in out Vector;
Index :
in Extended_Index;
Count :
in Count_Type := 1);
procedure Delete (Container :
in out Vector;
Position :
in out Cursor;
Count :
in Count_Type := 1);
procedure Delete_First (Container :
in out Vector;
Count :
in Count_Type := 1);
procedure Delete_Last (Container :
in out Vector;
Count :
in Count_Type := 1);
procedure Reverse_Elements (Container :
in out Vector);
procedure Swap (Container :
in out Vector;
I, J :
in Index_Type);
procedure Swap (Container :
in out Vector;
I, J :
in Cursor);
function First_Index (Container : Vector)
return Index_Type;
function First (Container : Vector)
return Cursor;
function First_Element (Container : Vector)
return Element_Type;
function Last_Index (Container : Vector)
return Extended_Index;
function Last (Container : Vector)
return Cursor;
function Last_Element (Container : Vector)
return Element_Type;
function Next (Position : Cursor)
return Cursor;
procedure Next (Position :
in out Cursor);
function Previous (Position : Cursor)
return Cursor;
procedure Previous (Position :
in out Cursor);
function Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'First)
return Extended_Index;
function Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
function Reverse_Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'Last)
return Extended_Index;
function Reverse_Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
function Contains (Container : Vector;
Item : Element_Type)
return Boolean;
function Has_Element (Position : Cursor)
return Boolean;
procedure Iterate
(Container :
in Vector;
Process :
not null access procedure (Position :
in Cursor));
procedure Reverse_Iterate
(Container :
in Vector;
Process :
not null access procedure (Position :
in Cursor));
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
package Generic_Sorting
is
function Is_Sorted (Container : Vector)
return Boolean;
procedure Sort (Container :
in out Vector);
procedure Merge (Target :
in out Vector;
Source :
in out Vector);
end Generic_Sorting;
private
... -- not specified by the language
end Ada.Containers.Vectors;
{
AI95-00302-03}
The actual function for the generic formal function "=" on
Element_Type values is expected to define a reflexive and symmetric relationship
and return the same result value each time it is called with a particular
pair of values. If it behaves in some other manner, the functions defined
to use it return an unspecified value. The exact arguments and number
of calls of this generic formal function by the functions defined to
use it are unspecified.
{unspecified
[partial]} 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.
{
AI95-00302-03}
The type Vector is used to represent vectors. The type Vector needs finalization
(see
7.6).
{
AI95-00302-03}
Empty_Vector represents the empty vector object. It has a length of 0.
If an object of type Vector is not otherwise initialized, it is initialized
to the same value as Empty_Vector.
{
AI95-00302-03}
No_Element represents a cursor that designates no element. If an object
of type Cursor is not otherwise initialized, it is initialized to the
same value as No_Element.
{
AI95-00302-03}
The predefined "=" operator for type Cursor returns True if
both cursors are No_Element, or designate the same element in the same
container.
{
AI95-00302-03}
Execution of the default implementation of the Input, Output, Read, or
Write attribute of type Cursor raises Program_Error.
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.
{
AI95-00302-03}
No_Index represents a position that does not correspond to any element.
The subtype Extended_Index includes the indices covered by Index_Type
plus the value No_Index and, if it exists, the successor to the Index_Type'Last.
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).
{
AI95-00302-03}
[Some operations of this generic package have access-to-subprogram parameters.
To ensure such operations are well-defined, they guard against certain
actions by the designated subprogram. In particular, some operations
check for “tampering with cursors” of a container because
they depend on the set of elements of the container remaining constant,
and others check for “tampering with elements” of a container
because they depend on elements of the container not being replaced.]
{
AI95-00302-03}
{tamper with cursors (of a vector)}
A subprogram is said to
tamper with cursors
of a vector object
V if:
it inserts or deletes elements of V, that
is, it calls the Insert, Insert_Space, Clear, Delete, or Set_Length procedures
with V as a parameter; or
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.
it finalizes V; or
it calls the Move procedure with V as a
parameter.
Discussion: Swap, Sort, and Merge copy
elements rather than reordering them, so they don't tamper with cursors.
{
AI95-00302-03}
{tamper with elements (of a vector)}
A subprogram is said to
tamper with elements
of a vector object
V if:
it tampers with cursors of V; or
it replaces one or more elements of V, that
is, it calls the Replace_Element, Reverse_Elements, or Swap procedures
or the Sort or Merge procedures of an instance of Generic_Sorting with
V as a parameter.
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.
function "=" (Left, Right : Vector) return Boolean;
{
AI95-00302-03}
If Left and Right denote the same vector object, then the function returns
True. If Left and Right have different lengths, then the function returns
False. Otherwise, it compares each element in Left to the corresponding
element in Right using the generic formal equality operator. If any such
comparison returns False, the function returns False; otherwise it returns
True. Any exception raised during evaluation of element equality is propagated.
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.
function To_Vector (Length : Count_Type) return Vector;
{
AI95-00302-03}
Returns a vector with a length of Length, filled with empty elements.
function To_Vector
(New_Item : Element_Type;
Length : Count_Type) return Vector;
{
AI95-00302-03}
Returns a vector with a length of Length, filled with elements initialized
to the value New_Item.
function "&" (Left, Right : Vector) return Vector;
{
AI95-00302-03}
Returns a vector comprising the elements of Left followed by the elements
of Right.
function "&" (Left : Vector;
Right : Element_Type) return Vector;
{
AI95-00302-03}
Returns a vector comprising the elements of Left followed by the element
Right.
function "&" (Left : Element_Type;
Right : Vector) return Vector;
{
AI95-00302-03}
Returns a vector comprising the element Left followed by the elements
of Right.
function "&" (Left, Right : Element_Type) return Vector;
{
AI95-00302-03}
Returns a vector comprising the element Left followed by the element
Right.
function Capacity (Container : Vector) return Count_Type;
procedure Reserve_Capacity (Container : in out Vector;
Capacity : in Count_Type);
{
AI95-00302-03}
Reserve_Capacity allocates new internal data structures such that the
length of the resulting vector can become at least the value Capacity
without requiring an additional call to Reserve_Capacity, and is large
enough to hold the current length of Container. Reserve_Capacity then
copies the elements into the new data structures and deallocates the
old data structures. Any exception raised during allocation is propagated
and Container is not modified.
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.
function Length (Container : Vector) return Count_Type;
procedure Set_Length (Container : in out Vector;
Length : in Count_Type);
{
AI95-00302-03}
If Length is larger than the capacity of Container, Set_Length calls
Reserve_Capacity (Container, Length), then sets the length of the Container
to Length. If Length is greater than the original length of Container,
empty elements are added to Container; otherwise elements are removed
from Container.
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.
function Is_Empty (Container : Vector) return Boolean;
procedure Clear (Container : in out Vector);
{
AI95-00302-03}
Removes all the elements from Container. The capacity of Container does
not change.
function To_Cursor (Container : Vector;
Index : Extended_Index) return Cursor;
{
AI95-00302-03}
If Index is not in the range First_Index (Container) .. Last_Index (Container),
then No_Element is returned. Otherwise, a cursor designating the element
at position Index in Container is returned.
function To_Index (Position : Cursor) return Extended_Index;
{
AI95-00302-03}
If Position is No_Element, No_Index is returned. Otherwise, the index
(within its containing vector) of the element designated by Position
is returned.
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).
function Element (Container : Vector;
Index : Index_Type)
return Element_Type;
{
AI95-00302-03}
If Index is not in the range First_Index (Container) .. Last_Index (Container),
then Constraint_Error is propagated. Otherwise, Element returns the element
at position Index.
function Element (Position : Cursor) return Element_Type;
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Element returns the element designated by Position.
procedure Replace_Element (Container : in out Vector;
Index : in Index_Type;
New_Item : in Element_Type);
{
AI95-00302-03}
If Index is not in the range First_Index (Container) .. Last_Index (Container),
then Constraint_Error is propagated. Otherwise Replace_Element assigns
the value New_Item to the element at position Index. Any exception raised
during the assignment is propagated. The element at position Index is
not an empty element after successful call to Replace_Element.
procedure Replace_Element (Container : in out Vector;
Position : in Cursor;
New_Item : in Element_Type);
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error is propagated; if
Position does not designate an element in Container, then Program_Error
is propagated. Otherwise Replace_Element assigns New_Item to the element
designated by Position. Any exception raised during the assignment is
propagated. The element at Position is not an empty element after successful
call to Replace_Element.
Ramification: Replace_Element and Update_Element
are the only ways that an element can change from empty to non-empty.
Also see the note following Update_Element.
procedure Query_Element
(Container : in Vector;
Index : in Index_Type;
Process : not null access procedure (Element : in Element_Type));
{
AI95-00302-03}
If Index is not in the range First_Index (Container) .. Last_Index (Container),
then Constraint_Error is propagated. Otherwise, Query_Element calls Process.
all
with the element at position Index as the argument. Program_Error is
propagated if Process.
all tampers with the elements of Container.
Any exception raised by Process.
all is propagated.
Reason: The “tamper with the elements”
check is intended to prevent the Element parameter of Process from being
modified 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).
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Query_Element calls Process.
all with the element designated by
Position as the argument. Program_Error is propagated if Process.
all
tampers with the elements of Container. Any exception raised by Process.
all
is propagated.
procedure Update_Element
(Container : in out Vector;
Index : in Index_Type;
Process : not null access procedure (Element : in out Element_Type));
{
AI95-00302-03}
If Index is not in the range First_Index (Container) .. Last_Index (Container),
then Constraint_Error is propagated. Otherwise, Update_Element calls
Process.
all with the element at position Index as the argument.
Program_Error is propagated if Process.
all tampers with the elements
of Container. Any exception raised by Process.
all is propagated.
If Element_Type is unconstrained and definite,
then the actual Element parameter of Process.all shall be unconstrained.
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.
The element at position
Index is not an empty element after successful completion of this operation.
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.
procedure Update_Element
(Container : in out Vector;
Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error is propagated; if
Position does not designate an element in Container, then Program_Error
is propagated. Otherwise Update_Element calls Process.
all with
the element designated by Position as the argument. Program_Error is
propagated if Process.
all tampers with the elements of Container.
Any exception raised by Process.
all is propagated.
If Element_Type is unconstrained and definite,
then the actual Element parameter of Process.all shall be unconstrained.
The element designated
by Position is not an empty element after successful completion of this
operation.
procedure Move (Target : in out Vector;
Source : in out Vector);
{
AI95-00302-03}
If Target denotes the same object as Source, then Move has no effect.
Otherwise, Move first calls Clear (Target); then, each element from Source
is removed from Source and inserted into Target in the original order.
The length of Source is 0 after a successful call to Move.
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.
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
New_Item : in Vector);
{
AI95-00302-03}
If Before is not in the range First_Index (Container) .. Last_Index (Container)
+ 1, then Constraint_Error is propagated. If Length(New_Item) is 0, then
Insert does nothing. Otherwise, it computes the new length
NL
as the sum of the current length and Length (New_Item); if the value
of Last appropriate for length
NL would be greater than Index_Type'Last
then Constraint_Error is propagated.
If the current vector
capacity is less than NL, Reserve_Capacity (Container, NL)
is called to increase the vector capacity. Then Insert slides the elements
in the range Before .. Last_Index (Container) up by Length(New_Item)
positions, and then copies the elements of New_Item to the positions
starting at Before. Any exception raised during the copying is propagated.
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).
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector);
{
AI95-00302-03}
If Before is not No_Element, and does not designate an element in Container,
then Program_Error is propagated. Otherwise, if Length(New_Item) is 0,
then Insert does nothing. If Before is No_Element, then the call is equivalent
to Insert (Container, Last_Index (Container) + 1, New_Item); otherwise
the call is equivalent to Insert (Container, To_Index (Before), New_Item);
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).
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector;
Position : out Cursor);
{
AI95-00302-03}
If Before is not No_Element, and does not designate an element in Container,
then Program_Error is propagated. If Before equals No_Element, then let
T be Last_Index (Container) + 1; otherwise, let
T be To_Index
(Before). Insert (Container,
T, New_Item) is called, and then
Position is set to To_Cursor (Container,
T).
Discussion: The messy wording is needed
because Before is invalidated by Insert, and we don't want Position to
be invalid after this call. An implementation probably only needs to
copy Before to Position.
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
New_Item : in Element_Type;
Count : in Count_Type := 1);
{
AI95-00302-03}
Equivalent to Insert (Container, Before, To_Vector (New_Item, Count));
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
{
AI95-00302-03}
Equivalent to Insert (Container, Before, To_Vector (New_Item, Count));
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);
{
AI95-00302-03}
Equivalent to Insert (Container, Before, To_Vector (New_Item, Count),
Position);
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
Count : in Count_Type := 1);
{
AI95-00302-03}
If Before is not in the range First_Index (Container) .. Last_Index (Container)
+ 1, then Constraint_Error is propagated. If Count is 0, then Insert
does nothing. Otherwise, it computes the new length
NL as the
sum of the current length and Count; if the value of Last appropriate
for length
NL would be greater than Index_Type'Last then Constraint_Error
is propagated.
If the current vector
capacity is less than
NL, Reserve_Capacity (Container,
NL)
is called to increase the vector capacity. Then Insert slides the elements
in the range Before .. Last_Index (Container) up by Count positions,
and then inserts elements that are initialized by default (see
3.3.1)
in the positions starting at Before.
procedure Insert (Container : in out Vector;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
{
AI95-00302-03}
If Before is not No_Element, and does not designate an element in Container,
then Program_Error is propagated. If Before equals No_Element, then let
T be Last_Index (Container) + 1; otherwise, let
T be To_Index
(Before). Insert (Container,
T, Count) is called, and then Position
is set to To_Cursor (Container,
T).
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.
procedure Prepend (Container : in out Vector;
New_Item : in Vector;
Count : in Count_Type := 1);
{
AI95-00302-03}
Equivalent to Insert (Container, First_Index (Container), New_Item).
procedure Prepend (Container : in out Vector;
New_Item : in Element_Type;
Count : in Count_Type := 1);
{
AI95-00302-03}
Equivalent to Insert (Container, First_Index (Container), New_Item, Count).
procedure Append (Container : in out Vector;
New_Item : in Vector);
{
AI95-00302-03}
Equivalent to Insert (Container, Last_Index (Container) + 1, New_Item).
procedure Append (Container : in out Vector;
New_Item : in Element_Type;
Count : in Count_Type := 1);
{
AI95-00302-03}
Equivalent to Insert (Container, Last_Index (Container) + 1, New_Item,
Count).
procedure Insert_Space (Container : in out Vector;
Before : in Extended_Index;
Count : in Count_Type := 1);
{
AI95-00302-03}
If Before is not in the range First_Index (Container) .. Last_Index (Container)
+ 1, then Constraint_Error is propagated. If Count is 0, then Insert_Space
does nothing. Otherwise, it computes the new length
NL as the
sum of the current length and Count; if the value of Last appropriate
for length
NL would be greater than Index_Type'Last then Constraint_Error
is propagated.
If the current vector
capacity is less than NL, Reserve_Capacity (Container, NL)
is called to increase the vector capacity. Then Insert_Space slides the
elements in the range Before .. Last_Index (Container) up by Count positions,
and then inserts empty elements in the positions starting at Before.
procedure Insert_Space (Container : in out Vector;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
{
AI95-00302-03}
If Before is not No_Element, and does not designate an element in Container,
then Program_Error is propagated. If Before equals No_Element, then let
T be Last_Index (Container) + 1; otherwise, let
T be To_Index
(Before). Insert_Space (Container,
T, Count) is called, and then
Position is set to To_Cursor (Container,
T).
procedure Delete (Container : in out Vector;
Index : in Extended_Index;
Count : in Count_Type := 1);
{
AI95-00302-03}
If Index is not in the range First_Index (Container) .. Last_Index (Container)
+ 1, then Constraint_Error is propagated. If Count is 0, Delete has no
effect. Otherwise Delete slides the elements (if any) starting at position
Index + Count down to Index. Any exception raised during element assignment
is propagated.
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).
procedure Delete (Container : in out Vector;
Position : in out Cursor;
Count : in Count_Type := 1);
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error is propagated. If
Position does not designate an element in Container, then Program_Error
is propagated. Otherwise, Delete (Container, To_Index (Position), Count)
is called, and then Position is set to No_Element.
procedure Delete_First (Container : in out Vector;
Count : in Count_Type := 1);
{
AI95-00302-03}
Equivalent to Delete (Container, First_Index (Container), Count).
procedure Delete_Last (Container : in out Vector;
Count : in Count_Type := 1);
{
AI95-00302-03}
If Length (Container) <= Count then Delete_Last is equivalent to Clear
(Container). Otherwise it is equivalent to Delete (Container, Index_Type'Val(Index_Type'Pos(Last_Index
(Container)) – Count + 1), Count).
procedure Reverse_Elements (Container : in out List);
{
AI95-00302-03}
Reorders the elements of Container in reverse order.
Discussion: This can copy the elements
of the vector — all cursors referencing the vector are ambiguous
afterwards and may designate different elements afterwards.
procedure Swap (Container : in out Vector;
I, J : in Index_Type);
{
AI95-00302-03}
If either I or J is not in the range First_Index (Container) .. Last_Index
(Container), then Constraint_Error is propagated. Otherwise, Swap exchanges
the values of the elements at positions I and J.
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.
procedure Swap (Container : in out Vector;
I, J : in Cursor);
{
AI95-00302-03}
If either I or J is No_Element, then Constraint_Error is propagated.
If either I or J do not designate an element in Container, then Program_Error
is propagated. Otherwise, Swap exchanges the values of the elements designated
by I and J.
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.
function First_Index (Container : Vector) return Index_Type;
Discussion: We'd rather call this “First”,
but then calling most routines in here with First (Some_Vect) would be
ambiguous.
function First (Container : Vector) return Cursor;
{
AI95-00302-03}
If Container is empty, First returns No_Element. Otherwise, it returns
a cursor that designates the first element in Container.
function First_Element (Container : Vector) return Element_Type;
{
AI95-00302-03}
Equivalent to Element (Container, First_Index (Container)).
function Last_Index (Container : Vector) return Extended_Index;
{
AI95-00302-03}
If Container is empty, Last_Index returns No_Index. Otherwise, it returns
the position of the last element in Container.
function Last (Container : Vector) return Cursor;
{
AI95-00302-03}
If Container is empty, Last returns No_Element. Otherwise, it returns
a cursor that designates the last element in Container.
function Last_Element (Container : Vector) return Element_Type;
{
AI95-00302-03}
Equivalent to Element (Container, Last_Index (Container)).
function Next (Position : Cursor) return Cursor;
{
AI95-00302-03}
If Position equals No_Element or designates the last element of the container,
then Next returns the value No_Element. Otherwise, it returns a cursor
that designates the element with index To_Index (Position) + 1 in the
same vector as Position.
procedure Next (Position : in out Cursor);
function Previous (Position : Cursor) return Cursor;
{
AI95-00302-03}
If Position equals No_Element or designates the first element of the
container, then Previous returns the value No_Element. Otherwise, it
returns a cursor that designates the element with index To_Index (Position)
– 1 in the same vector as Position.
procedure Previous (Position : in out Cursor);
function Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'First)
return Extended_Index;
{
AI95-00302-03}
Searches the elements of Container for an element equal to Item (using
the generic formal equality operator). The search starts at position
Index and proceeds towards Last_Index (Container). If no equal element
is found, then Find_Index returns No_Index. Otherwise, it returns the
index of the first equal element encountered.
function Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
{
AI95-00302-03}
If Position is not No_Element, and does not designate an element in Container,
then Program_Error is propagated. Otherwise Find searches the elements
of Container for an element equal to Item (using the generic formal equality
operator). The search starts at the first element if Position equals
No_Element, and at the element designated by Position otherwise. It proceeds
towards the last element of Container. If no equal element is found,
then Find returns No_Element. Otherwise, it returns a cursor designating
the first equal element encountered.
function Reverse_Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'Last)
return Extended_Index;
{
AI95-00302-03}
Searches the elements of Container for an element equal to Item (using
the generic formal equality operator). The search starts at position
Index or, if Index is greater than Last_Index (Container), at position
Last_Index (Container). It proceeds towards First_Index (Container).
If no equal element is found, then Reverse_Find_Index returns No_Index.
Otherwise, it returns the index of the first equal element encountered.
function Reverse_Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
{
AI95-00302-03}
If Position is not No_Element, and does not designate an element in Container,
then Program_Error is propagated. Otherwise Reverse_Find searches the
elements of Container for an element equal to Item (using the generic
formal equality operator). The search starts at the last element if Position
equals No_Element, and at the element designated by Position otherwise.
It proceeds towards the first element of Container. If no equal element
is found, then Reverse_Find returns No_Element. Otherwise, it returns
a cursor designating the first equal element encountered.
function Contains (Container : Vector;
Item : Element_Type) return Boolean;
{
AI95-00302-03}
Equivalent to Has_Element (Find (Container, Item)).
function Has_Element (Position : Cursor) return Boolean;
{
AI95-00302-03}
Returns True if Position designates an element, and returns False otherwise.
To be honest: This function may 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).
procedure Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
{
AI95-00302-03}
Invokes Process.
all with a cursor that designates each element
in Container, in index order. Program_Error is propagated if Process.
all
tampers with the cursors of Container. Any exception raised by Process
is propagated.
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.
procedure Reverse_Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
{
AI95-00302-03}
Iterates over the elements in Container as per Iterate, except that elements
are traversed in reverse index order.
The actual function for the generic formal function
"<" of Generic_Sorting is expected to return the same value
each time it is called with a particular pair of element values. It should
define a strict ordering relationship, that is, be irreflexive, asymmetric,
and transitive; it should not modify Container. If the actual for "<"
behaves in some other manner, the behavior of the subprograms of Generic_Sorting
are unspecified. How many times the subprograms of Generic_Sorting call
"<" is unspecified.
{unspecified
[partial]} function Is_Sorted (Container : Vector) return Boolean;
{
AI95-00302-03}
Returns True if the elements are sorted smallest first as determined
by the generic formal "<" operator; otherwise, Is_Sorted
returns False. Any exception raised during evaluation of "<"
is propagated.
procedure Sort (Container : in out Vector);
{
AI95-00302-03}
Reorders the elements of Container such that the elements are sorted
smallest first as determined by the generic formal "<" operator
provided. Any exception raised during evaluation of "<"
is propagated.
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.
procedure Merge (Target : in out Vector;
Source : in out Vector);
{
AI95-00302-03}
Merge removes elements from Source and inserts them into Target; afterwards,
Target contains the union of the elements that were initially in Source
and Target; Source is left empty. If Target and Source are initially
sorted smallest first, then Target is ordered smallest first as determined
by the generic formal "<" operator; otherwise, the order
of elements in Target is unspecified. Any exception raised during evaluation
of "<" is propagated.
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.
Bounded (Run-Time) Errors
{
AI95-00302-03}
{bounded error (cause) [partial]}
Reading the value of an empty element by calling
Element, Query_Element, Update_Element, Swap, Is_Sorted, Sort, Merge,
"=", Find, or Reverse_Find is a bounded error. The implementation
may treat the element as having any normal value (see
13.9.1)
of the element type, or raise Constraint_Error or Program_Error before
modifying the vector.
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.
{
AI95-00302-03}
{bounded error (cause) [partial]}
Calling Merge in an instance of Generic_Sorting with
either Source or Target not ordered smallest first using the provided
generic formal "<" operator is a bounded error. Either Program_Error
is raised after Target is updated as described for Merge, or the operation
works as defined.
{
AI95-00302-03}
{ambiguous cursor (of a vector)}
{cursor (ambiguous)}
A Cursor value is
ambiguous if any of the
following have occurred since it was created:
Insert, Insert_Space, or Delete has been called
on the vector that contains the element the cursor designates with an
index value (or a cursor designating an element at such an index value)
less than or equal to the index value of the element designated by the
cursor; or
The vector that contains the element it designates
has been passed to the Sort or Merge procedures of an instance of Generic_Sorting,
or to the Reverse_Elements procedure.
{
AI95-00302-03}
{bounded error (cause) [partial]}
It is a bounded error to call any subprogram other
than "=" or Has_Element declared in Containers.Vectors with
an ambiguous (but not invalid, see below) cursor parameter. Possible
results are:
The cursor may be treated as if it were No_Element;
The cursor may designate some element in the vector
(but not necessarily the element that it originally designated);
Constraint_Error may be raised; or
Program_Error may be raised.
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.
Erroneous Execution
{
AI95-00302-03}
A Cursor value is
invalid if any of the following have occurred
since it was created:
{invalid cursor
(of a vector)} {cursor
(invalid) [partial]} The vector that contains the element it designates
has been finalized;
The vector that contains the element it designates
has been used as the Source or Target of a call to Move; or
The element it designates has been deleted.
{
AI95-00302-03}
The result of "=" or Has_Element is unspecified if it is called
with an invalid cursor parameter.
{unspecified
[partial]} Execution is erroneous if any
other subprogram declared in Containers.Vectors is called with an invalid
cursor parameter.
{erroneous execution
(cause) [partial]} 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.
Implementation Requirements
{
AI95-00302-03}
No storage associated with a vector object shall be lost upon assignment
or scope exit.
{
AI95-00302-03}
The execution of an
assignment_statement
for a vector shall have the effect of copying the elements from the source
vector object to the target vector object.
Implementation Note: 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.
Implementation Advice
{
AI95-00302-03}
Containers.Vectors should be implemented similarly to an array. In particular,
if the length of a vector is
N, then
the worst-case time complexity of Element should
be O(log N);
Implementation Advice: The worst-case
time complexity of Element for Containers.Vector should be O(log
N).
the worst-case time complexity of Append with Count=1
when N is less than the capacity of the vector should be O(log
N); and
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).
the worst-case time complexity of Prepend with
Count=1 and Delete_First with Count=1 should be O(N 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.
{
AI95-00302-03}
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).
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!
{
AI95-00302-03}
Containers.Vectors.Generic_Sorting.Sort and Containers.Vectors.Generic_Sorting.Merge
should minimize copying of elements.
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.
{
AI95-00302-03}
Move should not copy elements, and should minimize copying of internal
data structures.
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.
{
AI95-00302-03}
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.
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.
42 All elements of a vector occupy locations
in the internal array. If a sparse container is required, a Hashed_Map
should be used rather than a vector.
43 If Index_Type'Base'First = Index_Type'First
an instance of Ada.Containers.Vectors will raise Constraint_Error. A
value below Index_Type'First is required so that an empty vector has
a meaningful value of Last_Index.
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.
Extensions to Ada 95
{
AI95-00302-03}
{
extensions to Ada 95}
The package Containers.Vectors
is new.
Sponsored by Ada-Europe