A.18.2 The Generic 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.
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.
A vector container may contain
empty elements. Empty elements do not have a specified value.
Static Semantics
The generic library
package Containers.Vectors has the following declaration:
with Ada.Iterator_Interfaces;
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);
pragma Remote_Types(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
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
pragma Preelaborable_Initialization(Vector);
type Cursor
is private;
pragma Preelaborable_Initialization(Cursor);
Empty_Vector :
constant Vector;
No_Element :
constant Cursor;
function Has_Element (Position : Cursor)
return Boolean;
package Vector_Iterator_Interfaces
is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
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));
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
type Reference_Type (Element :
not null access Element_Type)
is private
with Implicit_Dereference => Element;
function Constant_Reference (Container :
aliased in Vector;
Index :
in Index_Type)
return Constant_Reference_Type;
function Reference (Container :
aliased in out Vector;
Index :
in Index_Type)
return Reference_Type;
function Constant_Reference (Container :
aliased in Vector;
Position :
in Cursor)
return Constant_Reference_Type;
function Reference (Container :
aliased in out Vector;
Position :
in Cursor)
return Reference_Type;
procedure Assign (Target :
in out Vector; Source :
in Vector);
function Copy (Source : Vector; Capacity : Count_Type := 0)
return Vector;
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;
This paragraph
was deleted.
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));
function Iterate (Container : in Vector)
return Vector_Iterator_Interfaces.Reversible_Iterator'Class;
function Iterate (Container : in Vector; Start : in Cursor)
return Vector_Iterator_Interfaces.Reversible_Iterator'Class;
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;
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.
The type Vector is used to represent vectors. The
type Vector needs finalization
(see
7.6).
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.
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.
The predefined "=" operator for type Cursor
returns True if both cursors are No_Element, or designate the same element
in the same container.
Execution of the default implementation of the Input,
Output, Read, or Write attribute of type Cursor raises Program_Error.
Vector'Write for a Vector object V writes
Length(V) elements of the vector to the stream. It also may write
additional information about the vector.
Vector'Read reads the representation of a vector
from the stream, and assigns to Item a vector with the same length
and elements as was written by Vector'Write.
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.
If an operation attempts to modify the vector such
that the position of the last element would be greater than Index_Type'Last,
then the operation propagates Constraint_Error.
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.
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
it finalizes V; or
it calls the Assign procedure with V as
the Target parameter; or
it calls the Move procedure with V as a
parameter.
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.
When tampering
with cursors is
prohibited for a particular vector object
V,
Program_Error is propagated by a call of any language-defined subprogram
that is defined to tamper with the cursors of
V, leaving
V
unmodified. Similarly, when tampering with elements is
prohibited
for a particular vector object
V, Program_Error is propagated
by a call of any language-defined subprogram that is defined to tamper
with the elements of
V (or tamper with the cursors of
V),
leaving
V unmodified. These checks are made before any other defined
behavior of the body of the language-defined subprogram.
function Has_Element (Position : Cursor) return Boolean;
Returns True if
Position designates an element, and returns False otherwise.
function "=" (Left, Right : Vector) return Boolean;
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.
function To_Vector (Length : Count_Type) return Vector;
Returns a vector
with a length of Length, filled with empty elements.
function To_Vector
(New_Item : Element_Type;
Length : Count_Type) return Vector;
Returns a vector
with a length of Length, filled with elements initialized to the value
New_Item.
function "&" (Left, Right : Vector) return Vector;
Returns a vector
comprising the elements of Left followed by the elements of Right.
function "&" (Left : Vector;
Right : Element_Type) return Vector;
Returns a vector
comprising the elements of Left followed by the element Right.
function "&" (Left : Element_Type;
Right : Vector) return Vector;
Returns a vector
comprising the element Left followed by the elements of Right.
function "&" (Left, Right : Element_Type) return Vector;
Returns a vector
comprising the element Left followed by the element Right.
function Capacity (Container : Vector) return Count_Type;
Returns the capacity
of Container.
procedure Reserve_Capacity (Container : in out Vector;
Capacity : in Count_Type);
If the capacity
of Container is already greater than or equal to Capacity, then Reserve_Capacity
has no effect. Otherwise, Reserve_Capacity allocates additional storage
as necessary to ensure 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, as necessary, moves elements into the new storage and deallocates
any storage no longer needed. Any exception raised during allocation
is propagated and Container is not modified.
function Length (Container : Vector) return Count_Type;
Returns the number
of elements in Container.
procedure Set_Length (Container : in out Vector;
Length : in Count_Type);
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.
function Is_Empty (Container : Vector) return Boolean;
Equivalent to Length
(Container) = 0.
procedure Clear (Container : in out Vector);
Removes all the
elements from Container. The capacity of Container does not change.
function To_Cursor (Container : Vector;
Index : Extended_Index) return Cursor;
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;
If Position is No_Element,
No_Index is returned. Otherwise, the index (within its containing vector)
of the element designated by Position is returned.
function Element (Container : Vector;
Index : Index_Type)
return Element_Type;
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;
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);
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);
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.
procedure Query_Element
(Container : in Vector;
Index : in Index_Type;
Process : not null access procedure (Element : in Element_Type));
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. Tampering with the
elements of Container is prohibited during the execution of the call
on Process.all. Any exception raised by Process.all is
propagated.
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
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. Tampering with the elements of the vector that contains the
element designated by Position is prohibited during the execution of
the call on Process.all. 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));
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. Tampering with the elements of Container is prohibited
during the execution of the call on Process.all. 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 at position
Index is not an empty element after successful completion of this operation.
procedure Update_Element
(Container : in out Vector;
Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
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. Tampering with
the elements of Container is prohibited during the execution of the call
on Process.all. 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.
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
The types Constant_Reference_Type
and Reference_Type need finalization.
The default initialization of an object of type
Constant_Reference_Type or Reference_Type propagates Program_Error.
function Constant_Reference (Container : aliased in Vector;
Index : in Index_Type)
return Constant_Reference_Type;
This function (combined
with the Constant_Indexing and Implicit_Dereference aspects) provides
a convenient way to gain read access to an individual element of a vector
given an index value.
If Index is not in the range First_Index (Container)
.. Last_Index (Container), then Constraint_Error is propagated. Otherwise,
Constant_Reference returns an object whose discriminant is an access
value that designates the element at position Index. Tampering with the
elements of Container is prohibited while the object returned by Constant_Reference
exists and has not been finalized.
function Reference (Container : aliased in out Vector;
Index : in Index_Type)
return Reference_Type;
This function (combined
with the Variable_Indexing and Implicit_Dereference aspects) provides
a convenient way to gain read and write access to an individual element
of a vector given an index value.
If Index is not in the range First_Index (Container)
.. Last_Index (Container), then Constraint_Error is propagated. Otherwise,
Reference returns an object whose discriminant is an access value that
designates the element at position Index. Tampering with the elements
of Container is prohibited while the object returned by Reference exists
and has not been finalized.
The element at position Index is not an empty
element after successful completion of this operation.
function Constant_Reference (Container : aliased in Vector;
Position : in Cursor)
return Constant_Reference_Type;
This function (combined
with the Constant_Indexing and Implicit_Dereference aspects) provides
a convenient way to gain read access to an individual element of a vector
given a cursor.
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, Constant_Reference returns
an object whose discriminant is an access value that designates the element
designated by Position. Tampering with the elements of Container is prohibited
while the object returned by Constant_Reference exists and has not been
finalized.
function Reference (Container : aliased in out Vector;
Position : in Cursor)
return Reference_Type;
This function (combined
with the Variable_Indexing and Implicit_Dereference aspects) provides
a convenient way to gain read and write access to an individual element
of a vector given a cursor.
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, Reference returns an object
whose discriminant is an access value that designates the element designated
by Position. Tampering with the elements of Container is prohibited while
the object returned by Reference exists and has not been finalized.
The element designated by Position is not an empty
element after successful completion of this operation.
procedure Assign (Target : in out Vector; Source : in Vector);
If Target denotes
the same object as Source, the operation has no effect. If the length
of Source is greater than the capacity of Target, Reserve_Capacity (Target,
Length (Source)) is called. The elements of Source are then copied to
Target as for an
assignment_statement
assigning Source to Target (this includes setting the length of Target
to be that of Source).
function Copy (Source : Vector; Capacity : Count_Type := 0)
return Vector;
Returns a vector
whose elements are initialized from the corresponding elements of Source.
If Capacity is 0, then the vector capacity is the length of Source; if
Capacity is equal to or greater than the length of Source, the vector
capacity is at least the specified value. Otherwise, the operation propagates
Capacity_Error.
procedure Move (Target : in out Vector;
Source : in out Vector);
If Target denotes
the same object as Source, then the operation has no effect. Otherwise,
Move first calls Reserve_Capacity (Target, Length (Source)) and then
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.
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
New_Item : in Vector);
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.
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector);
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);
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector;
Position : out Cursor);
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).
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
New_Item : in Element_Type;
Count : in Count_Type := 1);
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);
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);
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);
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);
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).
procedure Prepend (Container : in out Vector;
New_Item : in Vector);
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);
Equivalent to Insert
(Container, First_Index (Container), New_Item, Count).
procedure Append (Container : in out Vector;
New_Item : in Vector);
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);
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);
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);
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);
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.
procedure Delete (Container : in out Vector;
Position : in out Cursor;
Count : in Count_Type := 1);
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);
Equivalent to Delete
(Container, First_Index (Container), Count).
procedure Delete_Last (Container : in out Vector;
Count : in Count_Type := 1);
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 Vector);
Reorders the elements
of Container in reverse order.
procedure Swap (Container : in out Vector;
I, J : in Index_Type);
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.
procedure Swap (Container : in out Vector;
I, J : in Cursor);
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.
function First_Index (Container : Vector) return Index_Type;
Returns the value
Index_Type'First.
function First (Container : Vector) return Cursor;
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;
Equivalent to Element
(Container, First_Index (Container)).
function Last_Index (Container : Vector) return Extended_Index;
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;
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;
Equivalent to Element
(Container, Last_Index (Container)).
function Next (Position : Cursor) return Cursor;
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);
Equivalent to Position
:= Next (Position).
function Previous (Position : Cursor) return Cursor;
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);
Equivalent to Position
:= Previous (Position).
function Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'First)
return Extended_Index;
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;
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;
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;
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;
Equivalent to Has_Element
(Find (Container, Item)).
Paragraphs 225
and 226 were moved above.
procedure Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
Invokes Process.all
with a cursor that designates each element in Container, in index order.
Tampering with the cursors of Container is prohibited during the execution
of a call on Process.all. Any exception raised by Process.all
is propagated.
procedure Reverse_Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
Iterates over the
elements in Container as per procedure Iterate, except that elements
are traversed in reverse index order.
function Iterate (Container : in Vector)
return Vector_Iterator_Interfaces.Reversible_Iterator'Class;
Iterate returns
a reversible iterator object (see
5.5.1)
that will generate a value for a loop parameter (see
5.5.2)
designating each node in Container, starting with the first node and
moving the cursor as per the Next function when used as a forward iterator,
and starting with the last node and moving the cursor as per the Previous
function when used as a reverse iterator. Tampering with the cursors
of Container is prohibited while the iterator object exists (in particular,
in the
sequence_of_statements
of the
loop_statement
whose
iterator_specification
denotes this object). The iterator object needs finalization.
function Iterate (Container : in Vector; Start : in Cursor)
return Vector_Iterator_Interfaces.Reversible_Iterator'Class;
If Start is not
No_Element and does not designate an item in Container, then Program_Error
is propagated. If Start is No_Element, then Constraint_Error is propagated.
Otherwise, Iterate returns a reversible iterator object (see
5.5.1)
that will generate a value for a loop parameter (see
5.5.2)
designating each node in Container, starting with the node designated
by Start and moving the cursor as per the Next function when used as
a forward iterator, or moving the cursor as per the Previous function
when used as a reverse iterator. Tampering with the cursors of Container
is prohibited while the iterator object exists (in particular, in the
sequence_of_statements
of the
loop_statement
whose
iterator_specification
denotes this object). The iterator object needs finalization.
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 weak ordering relationship (see
A.18);
it should not modify Container. If the actual for "<" behaves
in some other manner, the behavior of the subprograms of Generic_Sorting
are unspecified. The number of times the subprograms of Generic_Sorting
call "<" is unspecified.
function Is_Sorted (Container : Vector) return Boolean;
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);
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.
procedure Merge (Target : in out Vector;
Source : in out Vector);
If Source is empty,
then Merge does nothing. If Source and Target are the same nonempty container
object, then Program_Error is propagated. Otherwise, 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.
Bounded (Run-Time) Errors
Reading the value of an empty
element by calling Element, Query_Element, Update_Element, Constant_Reference,
Reference, 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.
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.
It is a bounded error for the actual function
associated with a generic formal subprogram, when called as part of an
operation of this package, to tamper with elements of any Vector parameter
of the operation. Either Program_Error is raised, or the operation works
as defined on the value of the Vector either prior to, or subsequent
to, some or all of the modifications to the Vector.
It is a bounded error to call any subprogram declared
in the visible part of Containers.Vectors when the associated container
has been finalized. If the operation takes Container as an in out
parameter, then it raises Constraint_Error or Program_Error. Otherwise,
the operation either proceeds as it would for an empty container, or
it raises Constraint_Error or Program_Error.
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.
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.
Erroneous Execution
A Cursor value is
invalid if any of the following have occurred since it was created:
The vector that contains the element it designates
has been finalized;
The vector that contains the element it designates
has been used as the Target of a call to Assign, or as the target of
an
assignment_statement;
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 or removed
from the vector that previously contained the element.
The result of "=" or Has_Element is unspecified
if it is called with an invalid cursor parameter.
Execution is erroneous if any other subprogram declared in Containers.Vectors
is called with an invalid cursor parameter.
Execution is erroneous if the vector associated
with the result of a call to Reference or Constant_Reference is finalized
before the result object returned by the call to Reference or Constant_Reference
is finalized.
Implementation Requirements
No storage associated with a vector object shall
be lost upon assignment or scope exit.
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 and changing the length of
the target object to that of the source object.
Implementation Advice
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);
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
the worst-case time complexity of Prepend with
Count=1 and Delete_First with Count=1 should be O(N log
N).
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).
Containers.Vectors.Generic_Sorting.Sort and Containers.Vectors.Generic_Sorting.Merge
should minimize copying of elements.
Move should not copy elements, and should minimize
copying of internal data structures.
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.
48 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.
49 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.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
