A.18.2 The Generic 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 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.
4/2
A vector
container may contain empty elements. Empty elements do not have
a specified value.
4.a/2
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).
4.b/2
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
5/2
{
AI95-00302-03}
The generic library package Containers.Vectors
has the following declaration: 6/3
{
AI05-0084-1}
{
AI05-0212-1}
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);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/3
{
AI05-0212-1}
type Vector is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
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;
11.1/3
{
AI05-0212-1}
function Has_Element (Position : Cursor) return Boolean;11.2/3
{
AI05-0212-1}
package Vector_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);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));
34.1/3
{
AI05-0212-1}
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;34.2/3
{
AI05-0212-1}
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;34.3/3
{
AI05-0212-1}
function Constant_Reference (Container : aliased in Vector;
Index : in Index_Type)
return Constant_Reference_Type;34.4/3
{
AI05-0212-1}
function Reference (Container : aliased in out Vector;
Index : in Index_Type)
return Reference_Type;34.5/3
{
AI05-0212-1}
function Constant_Reference (Container : aliased in Vector;
Position : in Cursor)
return Constant_Reference_Type;34.6/3
{
AI05-0212-1}
function Reference (Container : aliased in out Vector;
Position : in Cursor)
return Reference_Type;34.7/3
{
AI05-0001-1}
procedure Assign (Target : in out Vector; Source : in Vector);34.8/3
{
AI05-0001-1}
function Copy (Source : Vector; Capacity : Count_Type := 0)
return Vector;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/3
This paragraph
was deleted. {
AI05-0212-1}
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));
74.1/3
{
AI05-0212-1}
function Iterate (Container : in Vector)
return Vector_Iterator_Interfaces.Reversible_Iterator'Class;74.2/3
{
AI05-0212-1}
function Iterate (Container : in Vector; Start : in Cursor)
return Vector_Iterator_Interfaces.Reversible_Iterator'Class;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
{
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.83.a/2
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.
83.b/2
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.
84/2
{
AI95-00302-03}
The type Vector is used to represent vectors. The
type Vector needs finalization (see 7.6).85/2
{
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.86/2
{
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.87/2
{
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.88/2
{
AI95-00302-03}
Execution of the default implementation of the
Input, Output, Read, or Write attribute of type Cursor raises Program_Error.88.a/2
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.
88.1/3
{
AI05-0001-1}
{
AI05-0262-1}
Vector'Write writes exactly Length(Vector) elements
of the vector to the stream. It may write additional information about
the vector as well. Vector'Read reads exactly Length(Vector) elements
of Vector from the stream and consumes any additional information written
by Vector'Write.88.b/3
Implementation Note:
The Standard requires streaming of all language-defined non-limited
types (including containers) to "work" (see 13.13.2).
In addition, we do not want all of the elements that make up the capacity
of the vector streamed, as those beyond the length of the container have
undefined contents (and might cause bad things when read back in). This
will require a custom stream attribute implementation; the language-defined
default implementation will not work (even for a bounded form, as that
would most likely stream the entire capacity of the vector).
89/2
{
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.89.a/2
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).
89.1/3
{
AI05-0001-1}
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.89.b/3
Reason: We don't
want to require an implementation to go to heroic efforts to handle index
values larger than the base type of the index subtype.
90/2
{
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.]91/2
{
AI95-00302-03}
A subprogram is said to tamper
with cursors of a vector object V if:92/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.a/2
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.
93/2
it finalizes V; or
93.1/3
{
AI05-0001-1}
it calls the Assign procedure with V as
the Target parameter; or94/2
it calls the Move procedure
with V as a parameter.
94.a/2
Discussion: Swap,
Sort, and Merge copy elements rather than reordering them, so they don't
tamper with cursors.
95/2
{
AI95-00302-03}
A subprogram is said to tamper
with elements of a vector object V if:96/2
it tampers with cursors of
V; or
97/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.a/2
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.
97.1/3
{
AI05-0265-1}
If tampering
with cursors is prohibited for a particular vector object V,
Program_Error is propagated by any language-defined subprogram that is
defined to tamper with the cursors of V. Similarly, if tampering
with elements is prohibited for a particular vector object V,
Program_Error is propagated by any language-defined subprogram that is
defined to tamper with the elements of V.97.2/3
function Has_Element (Position : Cursor) return Boolean;
97.3/3
{
AI05-0212-1}
Returns True if Position designates an element,
and returns False otherwise.97.b/3
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).
98/2
function "=" (Left, Right : Vector) return Boolean;
99/3
{
AI95-00302-03}
{
AI05-0264-1}
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.99.a/2
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.
100/2
function To_Vector (Length : Count_Type) return Vector;
101/2
{
AI95-00302-03}
Returns a vector with a length of Length, filled
with empty elements.102/2
function To_Vector
(New_Item : Element_Type;
Length : Count_Type) return Vector;
103/2
{
AI95-00302-03}
Returns a vector with a length of Length, filled
with elements initialized to the value New_Item.104/2
function "&" (Left, Right : Vector) return Vector;
105/2
{
AI95-00302-03}
Returns a vector comprising the elements of Left
followed by the elements of Right.106/2
function "&" (Left : Vector;
Right : Element_Type) return Vector;
107/2
{
AI95-00302-03}
Returns a vector comprising the elements of Left
followed by the element Right.108/2
function "&" (Left : Element_Type;
Right : Vector) return Vector;
109/2
{
AI95-00302-03}
Returns a vector comprising the element Left followed
by the elements of Right.110/2
function "&" (Left, Right : Element_Type) return Vector;
111/2
{
AI95-00302-03}
Returns a vector comprising the element Left followed
by the element Right.112/2
function Capacity (Container : Vector) return Count_Type;
113/2
114/2
procedure Reserve_Capacity (Container : in out Vector;
Capacity : in Count_Type);
115/3
{
AI95-00302-03}
{
AI05-0001-1}
{
AI05-0264-1}
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 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,
as necessary, moves copies the elements into the new
storage data
structures and deallocates any
storage no longer needed the
old data structures. Any exception
raised during allocation is propagated and Container is not modified.115.a/2
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.
115.b/2
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.
115.c/2
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.
116/2
function Length (Container : Vector) return Count_Type;
117/2
118/2
procedure Set_Length (Container : in out Vector;
Length : in Count_Type);
119/3
{
AI95-00302-03}
{
AI05-0264-1}
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.a/2
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.
120/2
function Is_Empty (Container : Vector) return Boolean;
121/2
122/2
procedure Clear (Container : in out Vector);
123/2
{
AI95-00302-03}
Removes all the elements from Container. The capacity
of Container does not change.124/2
function To_Cursor (Container : Vector;
Index : Extended_Index) return Cursor;
125/2
{
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.126/2
function To_Index (Position : Cursor) return Extended_Index;
127/2
{
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.127.a/2
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).
128/2
function Element (Container : Vector;
Index : Index_Type)
return Element_Type;
129/2
{
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.130/2
function Element (Position : Cursor) return Element_Type;
131/2
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error
is propagated. Otherwise, Element returns the element designated by Position.132/2
procedure Replace_Element (Container : in out Vector;
Index : in Index_Type;
New_Item : in Element_Type);
133/3
{
AI95-00302-03}
{
AI05-0264-1}
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.134/2
procedure Replace_Element (Container : in out Vector;
Position : in Cursor;
New_Item : in Element_Type);
135/3
{
AI95-00302-03}
{
AI05-0264-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, 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.a/3
Ramification: {
AI05-0212-1}
Replace_Element, and Update_Element,
and Reference are the only ways that an
element can change from empty to non-empty. Also see the note following
Update_Element.
136/2
procedure Query_Element
(Container : in Vector;
Index : in Index_Type;
Process : not null access procedure (Element : in Element_Type));
137/3
{
AI95-00302-03}
{
AI05-0265-1}
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 Program_Error
is propagated if Process.all tampers with the elements of Container is prohibited
during the execution of Process.all.
Any exception raised by Process.all is propagated.137.a/2
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).
138/2
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
139/3
{
AI95-00302-03}
{
AI05-0021-1}
{
AI05-0265-1}
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 Program_Error
is propagated if Process.all tampers with the elements of the vector that contains
the element designated by Position is prohibited during the execution
of Process.all Container.
Any exception raised by Process.all is propagated.140/2
procedure Update_Element
(Container : in out Vector;
Index : in Index_Type;
Process : not null access procedure (Element : in out Element_Type));
141/3
{
AI95-00302-03}
{
AI05-0265-1}
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 Program_Error
is propagated if Process.all tampers with the elements of Container is prohibited
during the execution of Process.all.
Any exception raised by Process.all is propagated.142/2
If Element_Type is unconstrained
and definite, then the actual Element parameter of Process.all
shall be unconstrained.
142.a/2
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.
143/2
The
element at position Index is not an empty element after successful completion
of this operation.
143.a/2
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.
144/2
procedure Update_Element
(Container : in out Vector;
Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
145/3
{
AI95-00302-03}
{
AI05-0264-1}
{
AI05-0265-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, Update_Element calls Process.all with the element designated by
Position as the argument. Tampering Program_Error
is propagated if Process.all tampers with the elements of Container is prohibited
during the execution of Process.all.
Any exception raised by Process.all is propagated.146/2
If Element_Type is unconstrained
and definite, then the actual Element parameter of Process.all
shall be unconstrained.
147/2
The
element designated by Position is not an empty element after successful
completion of this operation.
147.1/3
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
147.2/3
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
147.3/3
{
AI05-0212-1}
The types Constant_Reference_Type and Reference_Type
need finalization.147.4/3
The default initialization
of an object of type Constant_Reference_Type or Reference_Type propagates
Program_Error.
147.a/3
Reason: It is expected
that Reference_Type (and Constant_Reference_Type) will be a controlled
type, for which finalization will have some action to terminate the tampering
check for the associated container. If the object is created by default,
however, there is no associated container. Since this is useless, and
supporting this case would take extra work, we define it to raise an
exception.
147.5/3
function Constant_Reference (Container : aliased in Vector;
Index : in Index_Type)
return Constant_Reference_Type;
147.6/3
{
AI05-0212-1}
This function (combined with the Constant_Indexing
and Implicit_Dereference aspects) provides a convenient way to gain read
access to the individual elements of a container starting with an index
value.147.7/3
{
AI05-0212-1}
{
AI05-0265-1}
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.147.8/3
function Reference (Container : aliased in out Vector;
Index : in Index_Type)
return Reference_Type;
147.9/3
{
AI05-0212-1}
This function (combined with the Variable_Indexing
and Implicit_Dereference aspects) provides a convenient way to gain read
and write access to the individual elements of a container starting with
an index value.147.10/3
{
AI05-0212-1}
{
AI05-0265-1}
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.147.11/3
The element at position
Index is not an empty element after successful completion of this operation.
147.12/3
function Constant_Reference (Container : aliased in Vector;
Position : in Cursor)
return Constant_Reference_Type;
147.13/3
{
AI05-0212-1}
This function (combined with the Constant_Indexing
and Implicit_Dereference aspects) provides a convenient way to gain read
access to the individual elements of a container starting with a cursor.147.14/3
{
AI05-0212-1}
{
AI05-0265-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, 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.147.15/3
function Reference (Container : aliased in out Vector;
Position : in Cursor)
return Reference_Type;
147.16/3
{
AI05-0212-1}
This function (combined with the Variable_Indexing
and Implicit_Dereference aspects) provides a convenient way to gain read
and write access to the individual elements of a container starting with
a cursor.147.17/3
{
AI05-0212-1}
{
AI05-0265-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, 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.147.18/3
The element designated by
Position is not an empty element after successful completion of this
operation.
147.19/3
procedure Assign (Target : in out Vector; Source : in Vector);
147.20/3
{
AI05-0001-1}
{
AI05-0248-1}
{
AI05-0262-1}
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). 147.b/3
Discussion: {
AI05-0005-1}
This routine exists for compatibility with the
bounded vector container. For an unbounded vector, Assign(A, B)
and A := B behave identically. For a bounded vector, := will
raise an exception if the container capacities are different, while Assign
will not raise an exception if there is enough room in the target.
147.21/3
function Copy (Source : Vector; Capacity : Count_Type := 0)
return Vector;
147.22/3
{
AI05-0001-1}
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.148/2
procedure Move (Target : in out Vector;
Source : in out Vector);
149/3
{
AI95-00302-03}
{
AI05-0001-1}
{
AI05-0248-1}
If Target denotes the same object as Source, then
the operation Move 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.149.a/2
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.
150/2
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
New_Item : in Vector);
151/3
{
AI95-00302-03}
{
AI05-0264-1}
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.152/2
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.
152.a/2
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).
153/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector);
154/3
{
AI95-00302-03}
{
AI05-0264-1}
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.a/2
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).
155/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector;
Position : out Cursor);
156/2
{
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).156.a/2
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.
157/2
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
New_Item : in Element_Type;
Count : in Count_Type := 1);
158/2
{
AI95-00302-03}
Equivalent to Insert (Container, Before, To_Vector
(New_Item, Count));159/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Element_Type;
Count : in Count_Type := 1);
160/2
{
AI95-00302-03}
Equivalent to Insert (Container, Before, To_Vector
(New_Item, Count));161/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Element_Type;
Position : out Cursor;
Count : in Count_Type := 1);
162/2
{
AI95-00302-03}
Equivalent to Insert (Container, Before, To_Vector
(New_Item, Count), Position);162.a/3
Ramification: {
AI05-0257-1}
If Count equals 0, Position will designate the
element designated by Before, rather than a newly inserted element. Otherwise,
Position will designate the first newly inserted element.
163/2
procedure Insert (Container : in out Vector;
Before : in Extended_Index;
Count : in Count_Type := 1);
164/3
{
AI95-00302-03}
{
AI05-0264-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.165/2
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.
166/2
procedure Insert (Container : in out Vector;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
167/2
{
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).167.a/2
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.
168/2
procedure Prepend (Container : in out Vector;
New_Item : in Vector;
Count : in Count_Type := 1);
169/2
{
AI95-00302-03}
Equivalent to Insert (Container, First_Index (Container),
New_Item).170/2
procedure Prepend (Container : in out Vector;
New_Item : in Element_Type;
Count : in Count_Type := 1);
171/2
{
AI95-00302-03}
Equivalent to Insert (Container, First_Index (Container),
New_Item, Count).172/2
procedure Append (Container : in out Vector;
New_Item : in Vector);
173/2
{
AI95-00302-03}
Equivalent to Insert (Container, Last_Index (Container)
+ 1, New_Item).174/2
procedure Append (Container : in out Vector;
New_Item : in Element_Type;
Count : in Count_Type := 1);
175/2
{
AI95-00302-03}
Equivalent to Insert (Container, Last_Index (Container)
+ 1, New_Item, Count).176/2
procedure Insert_Space (Container : in out Vector;
Before : in Extended_Index;
Count : in Count_Type := 1);
177/3
{
AI95-00302-03}
{
AI05-0264-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.178/2
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.
179/2
procedure Insert_Space (Container : in out Vector;
Before : in Cursor;
Position : out Cursor;
Count : in Count_Type := 1);
180/2
{
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).181/2
procedure Delete (Container : in out Vector;
Index : in Extended_Index;
Count : in Count_Type := 1);
182/3
{
AI95-00302-03}
{
AI05-0264-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.182.a/2
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).
183/2
procedure Delete (Container : in out Vector;
Position : in out Cursor;
Count : in Count_Type := 1);
184/2
{
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.185/2
procedure Delete_First (Container : in out Vector;
Count : in Count_Type := 1);
186/2
{
AI95-00302-03}
Equivalent to Delete (Container, First_Index (Container),
Count).187/2
procedure Delete_Last (Container : in out Vector;
Count : in Count_Type := 1);
188/3
{
AI95-00302-03}
{
AI05-0264-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).189/2
{
AI05-0092-1}
procedure Reverse_Elements (Container : in out Vector List);190/2
{
AI95-00302-03}
Reorders the elements of Container in reverse order.190.a/2
Discussion: This
can copy the elements of the vector — all cursors referencing the
vector are ambiguous afterwards and may designate different elements
afterwards.
191/2
procedure Swap (Container : in out Vector;
I, J : in Index_Type);
192/2
{
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.192.a/2
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.
193/2
procedure Swap (Container : in out Vector;
I, J : in Cursor);
194/2
{
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.194.a/2
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.
194.b/2
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.
195/2
function First_Index (Container : Vector) return Index_Type;
196/2
196.a/2
Discussion: We'd
rather call this “First”, but then calling most routines
in here with First (Some_Vect) would be ambiguous.
197/2
function First (Container : Vector) return Cursor;
198/2
{
AI95-00302-03}
If Container is empty, First returns No_Element.
Otherwise, it returns a cursor that designates the first element in Container.199/2
function First_Element (Container : Vector) return Element_Type;
200/2
{
AI95-00302-03}
Equivalent to Element (Container, First_Index (Container)).201/2
function Last_Index (Container : Vector) return Extended_Index;
202/2
{
AI95-00302-03}
If Container is empty, Last_Index returns No_Index.
Otherwise, it returns the position of the last element in Container.203/2
function Last (Container : Vector) return Cursor;
204/2
{
AI95-00302-03}
If Container is empty, Last returns No_Element.
Otherwise, it returns a cursor that designates the last element in Container.205/2
function Last_Element (Container : Vector) return Element_Type;
206/2
{
AI95-00302-03}
Equivalent to Element (Container, Last_Index (Container)).207/2
function Next (Position : Cursor) return Cursor;
208/2
{
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.209/2
procedure Next (Position : in out Cursor);
210/2
211/2
function Previous (Position : Cursor) return Cursor;
212/2
{
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.213/2
procedure Previous (Position : in out Cursor);
214/2
215/2
function Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'First)
return Extended_Index;
216/2
{
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.217/2
function Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
218/3
{
AI95-00302-03}
{
AI05-0264-1}
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.219/2
function Reverse_Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'Last)
return Extended_Index;
220/2
{
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.221/2
function Reverse_Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
222/3
{
AI95-00302-03}
{
AI05-0264-1}
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.223/2
function Contains (Container : Vector;
Item : Element_Type) return Boolean;
224/2
{
AI95-00302-03}
Equivalent to Has_Element (Find (Container, Item)).225/3
function Has_Element (Position : Cursor) return Boolean;
226/3
226.a/3
To be honest: {
AI05-0212-1}
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).
Paragraphs
225 and 226 were moved above.
227/2
procedure Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
228/3
{
AI95-00302-03}
{
AI05-0265-1}
Invokes Process.all with a cursor that designates
each element in Container, in index order. Tampering Program_Error
is propagated if Process.all tampers with the cursors of Container is prohibited
during the execution of Process.all.
Any exception raised by Process.all is propagated.228.a/2
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.
228.b/2
There is no check needed
if an attempt is made to insert or delete nothing (that is, Count = 0
or Length(Item) = 0).
228.c/2
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.
229/2
procedure Reverse_Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
230/3
{
AI95-00302-03}
{
AI05-0212-1}
Iterates over the elements in Container as per
procedure Iterate,
except that elements are traversed in reverse index order.230.1/3
function Iterate (Container : in Vector)
return Vector_Iterator_Interfaces.Reversible_Iterator'Class;
230.2/3
{
AI05-0212-1}
{
AI05-0265-1}
Iterate returns a reversible iterator object that
will generate a value for the loop parameter 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.230.3/3
function Iterate (Container : in Vector; Start : in Cursor)
return Vector_Iterator_Interfaces.Reversible_Iterator'Class;
230.4/3
{
AI05-0212-1}
{
AI05-0265-1}
If Start is not No_Element and does not designate
an item in Container, then Program_Error is propagated. If Start is No_Element,
the call is equivalent to Iterate (Container). Otherwise, Iterate returns
a reversible iterator object that will generate a value for the loop
parameter 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.230.a/3
Discussion:
Exits are allowed from the loops created using the iterator objects.
In particular, to stop the iteration at a particular cursor, just add
230.b/3
exit when Cur = Stop;
230.c/3
in
the body of the loop (assuming the Cur is the loop parameter
and Stop is the cursor that you want to stop at).
231/3
{
AI05-0044-1}
{
AI05-0262-1}
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),
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. The number of How
many times the subprograms of Generic_Sorting
call "<" is unspecified.232/2
function Is_Sorted (Container : Vector) return Boolean;
233/2
{
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.234/2
procedure Sort (Container : in out Vector);
235/2
{
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.235.a/2
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.
235.b/2
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.
236/2
procedure Merge (Target : in out Vector;
Source : in out Vector);
237/3
{
AI95-00302-03}
{
AI05-0021-1}
If Source is empty,
then Merge does nothing. If Source and Target are the same non-empty
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.237.a/2
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.
237.b/2
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
238/3
{
AI95-00302-03}
{
AI05-0212-1}
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.238.a/2
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).
238.b/2
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.
238.c/2
There are other operations
which are defined in terms of the operations listed above.
239/2
{
AI95-00302-03}
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.1/3
{
AI05-0022-1}
{
AI05-0248-1}
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.239.2/3
{
AI05-0027-1}
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.240/2
{
AI95-00302-03}
A Cursor
value is ambiguous if any of the following have occurred since
it was created:241/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
242/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.
243/2
{
AI95-00302-03}
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:244/2
The cursor may be treated
as if it were No_Element;
245/2
The cursor may designate
some element in the vector (but not necessarily the element that it originally
designated);
246/2
Constraint_Error may be raised;
or
247/2
Program_Error may be raised.
247.a/2
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.
247.b/2
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.
247.c/2
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
248/2
{
AI95-00302-03}
A Cursor value is invalid if any of the
following have occurred since it was created: 249/2
The vector that contains
the element it designates has been finalized;
249.1/3
{
AI05-0160-1}
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;250/2
[The vector that contains
the element it designates has been used as the Source or Target of a
call to Move;] or
250.a/3
Proof: {
AI05-0001-1}
Move has been reworded in terms of Assign and Clear,
which are covered by other bullets, so this text is redundant.
251/3
{
AI05-0160-1}
{
AI05-0262-1}
The element it designates has been deleted or removed from the vector that previously contained the element.
251.a/3
Ramification: {
AI05-0160-1}
An element can be removed via calls to Set_Length,
Clear, and Merge; and indirectly via calls to Assign and Move.
252/2
{
AI95-00302-03}
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.252.a/2
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.
252.1/3
{
AI05-0212-1}
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.252.b/3
Reason: Each object
of Reference_Type and Constant_Reference_Type probably contains some
reference to the originating container. If that container is prematurely
finalized (which is only possible via Unchecked_Deallocation, as accessibility
checks prevent passing a container to Reference that will not live as
long as the result), the finalization of the object of Reference_Type
will try to access a non-existent object. This is a normal case of a
dangling pointer created by Unchecked_Deallocation; we have to explicitly
mention it here as the pointer in question is not visible in the specification
of the type. (This is the same reason we have to say this for invalid
cursors.)
Implementation Requirements
253/2
{
AI95-00302-03}
No storage associated with a vector object shall
be lost upon assignment or scope exit.254/3
{
AI95-00302-03}
{
AI05-0262-1}
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.254.a/2
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
255/2
{
AI95-00302-03}
Containers.Vectors should be implemented similarly
to an array. In particular, if the length of a vector is N, then256/2
the worst-case time complexity
of Element should be O(log N);
256.a/2
Implementation Advice:
The worst-case time complexity of Element
for Containers.Vector should be O(log N).
257/2
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.a/2
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).
258/2
the worst-case time complexity
of Prepend with Count=1 and Delete_First with Count=1 should be O(N
log N).
258.a/2
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).
258.b/2
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.
259/2
{
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).
259.a/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).
259.b/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!
260/2
{
AI95-00302-03}
Containers.Vectors.Generic_Sorting.Sort and Containers.Vectors.Generic_Sorting.Merge
should minimize copying of elements. 260.a/2
Implementation Advice:
Containers.Vectors.Generic_Sorting.Sort
and Containers.Vectors.Generic_Sorting.Merge should minimize copying
of elements.
260.b/2
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.
261/2
{
AI95-00302-03}
Move should not copy elements, and should minimize
copying of internal data structures. 261.a/2
Implementation Advice:
Containers.Vectors.Move should not copy
elements, and should minimize copying of internal data structures.
261.b/2
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.
262/2
{
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. 262.a/2
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.
262.b/2
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.
263/2
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.
264/2
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.
264.a/2
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
264.b/2
Incompatibilities With Ada 2005
264.c/3
{
AI05-0001-1}
Subprograms Assign and Copy
are newly added to Containers.Vectors. If an instance of Containers.Vectors
is referenced in a use_clause,
and an entity E with the same defining_identifier
as a new entity in Containers.Vectors is defined in a package that is
also referenced in a use_clause,
the entity E may no longer be use-visible, resulting in errors.
This should be rare and is easily fixed if it does occur. Extensions to Ada 2005
264.d/3
{
AI05-0212-1}
Added iterator, reference,
and indexing support to make vector containers more convenient to use.
Wording Changes from Ada 2005
264.e/3
{
AI05-0001-1}
Generalized the definition of Reserve_Capacity
and Move. Specified which elements are read/written by stream attributes.264.f/3
{
AI05-0022-1}
Correction: Added a Bounded (Run-Time) Error
to cover tampering by generic actual subprograms.264.g/3
{
AI05-0027-1}
Correction: Added a Bounded (Run-Time) Error
to cover access to finalized Vector containers.264.h/3
{
AI05-0044-1}
Correction: Redefined "<" actuals
to require a strict weak ordering; the old definition allowed indeterminant
comparisons that would not have worked in a container.264.i/3
{
AI05-0084-1}
Correction: Added a pragma Remote_Types
so that containers can be used in distributed programs.264.j/3
{
AI05-0160-1}
Correction: Revised the definition of invalid
cursors to cover missing (and new) cases.264.k/3
{
AI05-0265-1}
Correction: Defined when a container prohibits
tampering in order to more clearly define where the check is made and
the exception raised.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
