Contents Index Search Related Documents Previous Next
A.18.2 The Package Containers.Vectors
1/2
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.
2/2
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.
3/2
Elements in a vector container can be refered
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.
4/2
A vector container may contain
empty elements. Empty elements do not have a specified value.
Static Semantics
5/2
The generic library
package Containers.Vectors has the following declaration:
6/2
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);
7/2
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;
8/2
type Vector is tagged private;
pragma Preelaborable_Initialization(Vector);
9/2
type Cursor is private;
pragma Preelaborable_Initialization(Cursor);
10/2
Empty_Vector : constant Vector;
11/2
No_Element : constant Cursor;
12/2
function "=" (Left, Right : Vector) return Boolean;
13/2
function To_Vector (Length : Count_Type) return Vector;
14/2
function To_Vector
(New_Item : Element_Type;
Length : Count_Type) return Vector;
15/2
function "&" (Left, Right : Vector) return Vector;
16/2
function "&" (Left : Vector;
Right : Element_Type) return Vector;
17/2
function "&" (Left : Element_Type;
Right : Vector) return Vector;
18/2
function "&" (Left, Right : Element_Type) return Vector;
19/2
function Capacity (Container : Vector) return Count_Type;
20/2
procedure Reserve_Capacity (Container : in out Vector;
Capacity : in Count_Type);
21/2
function Length (Container : Vector) return Count_Type;
22/2
procedure Set_Length (Container : in out Vector;
Length : in Count_Type);
23/2
function Is_Empty (Container : Vector) return Boolean;
24/2
procedure Clear (Container : in out Vector);
25/2
function To_Cursor (Container : Vector;
Index : Extended_Index) return Cursor;
26/2
function To_Index (Position : Cursor) return Extended_Index;
27/2
function Element (Container : Vector;
Index : Index_Type)
return Element_Type;
28/2
function Element (Position : Cursor) return Element_Type;
29/2
procedure Replace_Element (Container : in out Vector;
Index : in Index_Type;
New_Item : in Element_Type);
30/2
procedure Replace_Element (Container : in out Vector;
Position : in Cursor;
New_item : in Element_Type);
31/2
procedure Query_Element
(Container : in Vector;
Index : in Index_Type;
Process : not null access procedure (Element : in Element_Type));
32/2
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
33/2
procedure Update_Element
(Container : in out Vector;
Index : in Index_Type;
Process : not null access procedure (Element : in out Element_Type));
34/2
procedure Update_Element
(Container : in out Vector;
Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
35/2
procedure Move (Target : in out Vector;
Source : in out Vector);
36/2
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
New_Item : in Vector);
37/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector);
38/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector;
Position : out Cursor);
39/2
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
New_Item : in Element_Type;
Count : in Count_Type := 1);
40/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
41/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);
42/2
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
Count : in Count_Type := 1);
43/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
44/2
procedure Prepend (Container : in out Vector;
New_Item : in Vector);
45/2
procedure Prepend (Container : in out Vector;
New_Item : in Element_Type;
Count : in Count_Type := 1);
46/2
procedure Append (Container : in out Vector;
New_Item : in Vector);
47/2
procedure Append (Container : in out Vector;
New_Item : in Element_Type;
Count : in Count_Type := 1);
48/2
procedure Insert_Space (Container : in out Vector;
Before : in Extended_Index;
Count : in Count_Type := 1);
49/2
procedure Insert_Space (Container : in out Vector;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
50/2
procedure Delete (Container : in out Vector;
Index : in Extended_Index;
Count : in Count_Type := 1);
51/2
procedure Delete (Container : in out Vector;
Position : in out Cursor;
Count : in Count_Type := 1);
52/2
procedure Delete_First (Container : in out Vector;
Count : in Count_Type := 1);
53/2
procedure Delete_Last (Container : in out Vector;
Count : in Count_Type := 1);
54/2
procedure Reverse_Elements (Container : in out Vector);
55/2
procedure Swap (Container : in out Vector;
I, J : in Index_Type);
56/2
procedure Swap (Container : in out Vector;
I, J : in Cursor);
57/2
function First_Index (Container : Vector) return Index_Type;
58/2
function First (Container : Vector) return Cursor;
59/2
function First_Element (Container : Vector)
return Element_Type;
60/2
function Last_Index (Container : Vector) return Extended_Index;
61/2
function Last (Container : Vector) return Cursor;
62/2
function Last_Element (Container : Vector)
return Element_Type;
63/2
function Next (Position : Cursor) return Cursor;
64/2
procedure Next (Position : in out Cursor);
65/2
function Previous (Position : Cursor) return Cursor;
66/2
procedure Previous (Position : in out Cursor);
67/2
function Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'First)
return Extended_Index;
68/2
function Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
69/2
function Reverse_Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'Last)
return Extended_Index;
70/2
function Reverse_Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
71/2
function Contains (Container : Vector;
Item : Element_Type) return Boolean;
72/2
function Has_Element (Position : Cursor) return Boolean;
73/2
procedure Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
74/2
procedure Reverse_Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
75/2
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
package Generic_Sorting is
76/2
function Is_Sorted (Container : Vector) return Boolean;
77/2
procedure Sort (Container : in out Vector);
78/2
procedure Merge (Target : in out Vector;
Source : in out Vector);
79/2
end Generic_Sorting;
80/2
private
81/2
... -- not specified by the language
82/2
end Ada.Containers.Vectors;
83/2
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.
84/2
The type Vector is used to represent vectors.
The type Vector needs finalization (see
7.6).
85/2
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.
86/2
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.
87/2
The predefined "=" operator for type
Cursor should return True if both cursors or No_Element, or designate
the same element in the same container.
88/2
Execution of the default implementation of
the Input, Output, Read, or Write attribute of type Cursor raises Program_Error.
89/2
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.
90/2
Some
operations are assumed to work on a constant set of elements. During
the execution of such an operation, a subprogram is said to
tamper
with cursors of a vector object
V if:
91/2
- 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
92/2
93/2
- it calls the Move procedure with V
as a parameter.
94/2
Some
operations are assumed to not replace elements. During the execution
of such an operation, a subprogram is said to
tamper with elements
of a vector object
V if:
95/2
- it tampers with cursors of V;
or
96/2
- 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.
97/2
function "=" (Left, Right : Vector) return Boolean;
98/2
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 element equality returns
False, then the function returns False. If the function has not returned
a result after checking all of the elements, it returns True. Any exception
raised during evaluation of element equality is propagated.
99/2
function To_Vector (Length : Count_Type) return Vector;
100/2
Returns a vector
with a length of Length, filled with empty elements.
101/2
function To_Vector
(New_Item : Element_Type;
Length : Count_Type) return Vector;
102/2
Returns a vector
with a length of Length, filled with elements initialized to the value
New_Item.
103/2
function "&" (Left, Right : Vector) return Vector;
104/2
Returns a vector
comprising the elements of Left followed by the elements of Right.
105/2
function "&" (Left : Vector;
Right : Element_Type) return Vector;
106/2
Returns a vector
comprising the elements of Left followed by the element Right.
107/2
function "&" (Left : Element_Type;
Right : Vector) return Vector;
108/2
Returns a vector
comprising the element Left followed by the elements of Right.
109/2
function "&" (Left, Right : Element_Type) return Vector;
110/2
Returns a vector
comprising the element Left followed by the element Right.
111/2
function Capacity (Container : Vector) return Count_Type;
112/2
Returns the capacity
of Container.
113/2
procedure Reserve_Capacity (Container : in out Vector;
Capacity : in Count_Type);
114/2
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.
115/2
function Length (Container : Vector) return Count_Type;
116/2
Returns the number
of elements in Container.
117/2
procedure Set_Length (Container : in out Vector;
Length : in Count_Type);
118/2
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.
119/2
function Is_Empty (Container : Vector) return Boolean;
120/2
Equivalent to
Length (Container) = 0.
121/2
procedure Clear (Container : in out Vector);
122/2
Removes all the
elements from Container. The capacity of Container does not change.
123/2
function To_Cursor (Container : Vector;
Index : Extended_Index) return Cursor;
124/2
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.
125/2
function To_Index (Position : Cursor) return Extended_Index;
126/2
If Position is
No_Element, No_Index is returned. Otherwise, the index (within its containing
vector) of the element designated by Cursor is returned.
127/2
function Element (Container : Vector;
Index : Index_Type)
return Element_Type;
128/2
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.
129/2
function Element (Position : Cursor) return Element_Type;
130/2
If Position equals
No_Element, then Constraint_Error is propagated. Otherwise, Element returns
the element designated by Position.
131/2
procedure Replace_Element (Container : in out Vector;
Index : in Index_Type;
New_Item : in Element_Type);
132/2
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.
133/2
procedure Replace_Element (Container : in out Vector;
Position : in Cursor;
New_Item : in Element_Type);
134/2
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.
135/2
procedure Query_Element
(Container : in Vector;
Index : in Index_Type;
Process : not null access procedure (Element : in Element_Type));
136/2
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.
137/2
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
138/2
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.
139/2
procedure Update_Element
(Container : in out Vector;
Index : in Index_Type;
Process : not null access procedure (Element : in out Element_Type));
140/2
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.
141/2
If Element_Type is unconstrained and definite,
then the Element parameter of Process.all shall be unconstrained.
142/2
The element at
position Index is not an empty element after successful completion of
this operation.
143/2
procedure Update_Element
(Container : in out Vector;
Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
144/2
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.
145/2
If Element_Type is unconstrained and definite,
then the Element parameter of Process.all shall be unconstrained.
146/2
The element designated
by Position is not an empty element after successful completion of this
operation.
147/2
procedure Move (Target : in out Vector;
Source : in out Vector);
148/2
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.
149/2
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
New_Item : in Vector);
150/2
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.
151/2
If the current
vector capacity is less than or equal to 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.
152/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector);
153/2
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);
154/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector;
Position : out Cursor);
155/2
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).
156/2
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
New_Item : in Element_Type;
Count : in Count_Type := 1);
157/2
Equivalent to
Insert (Container, Before, To_Vector (New_Item, Count));
158/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
159/2
Equivalent to
Insert (Container, Before, To_Vector (New_Item, Count));
160/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);
161/2
Equivalent to
Insert (Container, Before, To_Vector (New_Item, Count), Position);
162/2
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
Count : in Count_Type := 1);
163/2
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.
164/2
If the current
vector capacity is less than or equal to
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 elements that are initialized
by default (see
3.3.1) in the positions starting
at Before.
165/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
166/2
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).
167/2
procedure Prepend (Container : in out Vector;
New_Item : in Vector;
Count : in Count_Type := 1);
168/2
Equivalent to
Insert (Container, First_Index (Container), New_Item).
169/2
procedure Prepend (Container : in out Vector;
New_Item : in Element_Type;
Count : in Count_Type := 1);
170/2
Equivalent to
Insert (Container, First_Index (Container), New_Item, Count).
171/2
procedure Append (Container : in out Vector;
New_Item : in Vector);
172/2
Equivalent to
Insert (Container, Last_Index (Container) + 1, New_Item).
173/2
procedure Append (Container : in out Vector;
New_Item : in Element_Type;
Count : in Count_Type := 1);
174/2
Equivalent to
Insert (Container, Last_Index (Container) + 1, New_Item, Count).
175/2
procedure Insert_Space (Container : in out Vector;
Before : in Extended_Index;
Count : in Count_Type := 1);
176/2
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.
177/2
If the current
vector capacity is less than or equal to 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.
178/2
procedure Insert_Space (Container : in out Vector;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
179/2
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).
180/2
procedure Delete (Container : in out Vector;
Index : in Extended_Index;
Count : in Count_Type := 1);
181/2
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.
182/2
procedure Delete (Container : in out Vector;
Position : in out Cursor;
Count : in Count_Type := 1);
183/2
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.
184/2
procedure Delete_First (Container : in out Vector;
Count : in Count_Type := 1);
185/2
Equivalent to
Delete (Container, First_Index (Container), Count).
186/2
procedure Delete_Last (Container : in out Vector;
Count : in Count_Type := 1);
187/2
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).
188/2
procedure Reverse_Elements (Container : in out List);
189/2
Reorders the
elements of Container in reverse order.
190/2
procedure Swap (Container : in out Vector;
I, J : in Index_Type);
191/2
If 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.
192/2
procedure Swap (Container : in out Vector;
I, J : in Cursor);
193/2
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.
194/2
function First_Index (Container : Vector) return Index_Type;
195/2
Returns the value
Index_Type'First.
196/2
function First (Container : Vector) return Cursor;
197/2
If Container
is empty, First returns No_Element. Otherwise, it returns a cursor that
designates the first element in Container.
198/2
function First_Element (Container : Vector) return Element_Type;
199/2
Equivalent to
Element (Container, First_Index (Container)).
200/2
function Last_Index (Container : Vector) return Extended_Index;
201/2
If Container
is empty, Last_Index returns No_Index. Otherwise, it returns the position
of the last element in Container.
202/2
function Last (Container : Vector) return Cursor;
203/2
If Container
is empty, Last returns No_Element. Otherwise, it returns a cursor that
designates the last element in Container.
204/2
function Last_Element (Container : Vector) return Element_Type;
205/2
Equivalent to
Element (Container, Last_Index (Container)).
206/2
function Next (Position : Cursor) return Cursor;
207/2
If Position equals
No_Element or designates the last element of the container, then Next
returns the value No_Element. Otherwise, returns a cursor that designates
the element with index To_Index (Position) + 1 in the same vector as
Position.
208/2
procedure Next (Position : in out Cursor);
209/2
Equivalent to
Position := Next (Position).
210/2
function Previous (Position : Cursor) return Cursor;
211/2
If Position equals
No_Element or designates the first element of the container, then Previous
returns the value No_Element. Otherwise, returns a cursor that designates
the element with index (To_Index (Position) – 1) in the same vector
as Position.
212/2
procedure Previous (Position : in out Cursor);
213/2
Equivalent to
Position := Previous (Position).
214/2
function Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'First)
return Extended_Index;
215/2
Searches the
elements of Container for an element equal to Item (in the sense of 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.
216/2
function Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
217/2
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 (in the sense of the generic formal
equality operator). The search starts at the first element if Cursor
equals No_Element, and at the element designated by Cursor 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.
218/2
function Reverse_Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'Last)
return Extended_Index;
219/2
Searches the
elements of Container for an element equal to Item (in the sense of 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.
220/2
function Reverse_Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
221/2
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 (in the sense of the generic
formal equality operator). The search starts at the last element if Cursor
equals No_Element, and at the element designated by Cursor 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.
222/2
function Contains (Container : Vector;
Item : Element_Type) return Boolean;
223/2
Equivalent to
Has_Element (Find (Container, Item)).
224/2
function Has_Element (Position : Cursor) return Boolean;
225/2
Returns True
if Position designates an element, and returns False otherwise.
226/2
procedure Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
227/2
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.
228/2
procedure Reverse_Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
229/2
Iterates over
the elements in Container as per Iterate, except that elements are traversed
in reverse index order.
230/2
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.
231/2
function Is_Sorted (Container : Vector) return Boolean;
232/2
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.
233/2
procedure Sort (Container : in out Vector);
234/2
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.
235/2
procedure Merge (Target : in out Vector;
Source : in out Vector);
236/2
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
237/2
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.
238/2
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.
239/2
A
Cursor value is
ambiguous if any of the following have occurred
since it was created:
240/2
- 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
241/2
- 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.
242/2
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:
243/2
- The cursor may be treated as if it
was No_Element;
244/2
- The cursor may designate some element
in the vector (but not necessarily the element that it originally designated);
245/2
- Constraint_Error may be raised; or
246/2
- Program_Error may be raised.
Erroneous Execution
247/2
A Cursor value
is
invalid if any of the following have occurred since it was
created:
248/2
- The vector that contains the element
it designates has been finalized;
249/2
- The vector that contains the element
it designates has been used as the Source or Target of a call to Move;
or
250/2
- The element it designates has been
deleted.
251/2
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.
Implementation Requirements
252/2
No storage associated with a vector object
shall be lost upon assignment or scope exit.
253/2
The execution of an assignment_statement
for a a vector shall have the effect of copying the elements from the
source vector object to the target vector object.
Implementation Advice
254/2
Containers.Vectors should be implemented similarly
to an array. In particular, if the length of a vector is N, then
255/2
- the worst-case time complexity of
Element should be O(log N); and
256
- 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
257/2
- the worst-case time complexity of
Prepend with Count=1 and Delete_First with Count=1 should be O(N
log N).
258/2
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).
259/2
Containers.Vectors.Generic_Sorting.Sort and
Containers.Vectors.Generic_Sorting.Merge should minimize copying of elements.
260/2
Move should not copy elements, and should
minimize copying of internal data structures.
261/2
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.
262/2
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.
263/2
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.
Contents Index Search Related Documents Previous Next Legal