Next: , Previous: A.18.1, Up: A.18


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 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.

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,      in     Index_Type);

56/2

        procedure Swap (Container in out Vector;
                        I,      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 returns True if both cursors are 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 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
A subprogram is said to tamper with cursors of a vector object V if:

92/2

93/2

94/2

95/2
A subprogram is said to tamper with elements of a vector object V if:

96/2

97/2

98/2

     function "=" (Left, Right Vector) return Boolean;

99/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 any such comparison returns False, the function returns False; otherwise it returns True. Any exception raised during evaluation of element equality is propagated.

100/2

     function To_Vector (Length Count_Type) return Vector;

101/2

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

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

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

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

Returns a vector comprising the element Left followed by the elements of Right.

110/2

     function "&" (Left, Right  Element_Type) return Vector;

111/2

Returns a vector comprising the element Left followed by the element Right.

112/2

     function Capacity (Container Vector) return Count_Type;

113/2

Returns the capacity of Container.

114/2

     procedure Reserve_Capacity (Container in out Vector;
                                 Capacity  in     Count_Type);

115/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.

116/2

     function Length (Container Vector) return Count_Type;

117/2

Returns the number of elements in Container.

118/2

     procedure Set_Length (Container in out Vector;
                           Length    in     Count_Type);

119/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.

120/2

     function Is_Empty (Container Vector) return Boolean;

121/2

Equivalent to Length (Container) = 0.

122/2

     procedure Clear (Container in out Vector);

123/2

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

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

If Position is No_Element, No_Index is returned. Otherwise, the index (within its containing vector) of the element designated by Position is returned.

128/2

     function Element (Container Vector;
                       Index     Index_Type)
        return Element_Type;

129/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.

130/2

     function Element (Position  Cursor) return Element_Type;

131/2

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/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.

134/2

     procedure Replace_Element (Container in out Vector;
                                Position  in     Cursor;
                                New_Item  in     Element_Type);

135/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.

136/2

     procedure Query_Element
       (Container in Vector;
        Index     in Index_Type;
        Process   not null access procedure (Element in Element_Type));

137/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.

138/2

     procedure Query_Element
       (Position in Cursor;
        Process  not null access procedure (Element in Element_Type));

139/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.

140/2

     procedure Update_Element
       (Container in out Vector;
        Index     in     Index_Type;
        Process   not null access procedure (Element in out Element_Type));

141/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.

142/2

If Element_Type is unconstrained and definite, then the actual Element parameter of Process.all shall be unconstrained.

143/2

The element at position Index is not an empty element after successful completion of this operation.

144/2

     procedure Update_Element
       (Container in out Vector;
        Position  in     Cursor;
        Process   not null access procedure (Element in out Element_Type));

145/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.

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.

148/2

     procedure Move (Target in out Vector;
                     Source in out Vector);

149/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.

150/2

     procedure Insert (Container in out Vector;
                       Before    in     Extended_Index;
                       New_Item  in     Vector);

151/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.

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.

153/2

     procedure Insert (Container in out Vector;
                       Before    in     Cursor;
                       New_Item  in     Vector);

154/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);

155/2

     procedure Insert (Container in out Vector;
                       Before    in     Cursor;
                       New_Item  in     Vector;
                       Position     out Cursor);

156/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).

157/2

     procedure Insert (Container in out Vector;
                       Before    in     Extended_Index;
                       New_Item  in     Element_Type;
                       Count     in     Count_Type := 1);

158/2

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

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

Equivalent to Insert (Container, Before, To_Vector (New_Item, Count), Position);

163/2

     procedure Insert (Container in out Vector;
                       Before    in     Extended_Index;
                       Count     in     Count_Type := 1);

164/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 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

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).

168/2

     procedure Prepend (Container in out Vector;
                        New_Item  in     Vector;
                        Count     in     Count_Type := 1);

169/2

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

Equivalent to Insert (Container, First_Index (Container), New_Item, Count).

172/2

     procedure Append (Container in out Vector;
                       New_Item  in     Vector);

173/2

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

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/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.

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

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/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.

183/2

     procedure Delete (Container in out Vector;
                       Position  in out Cursor;
                       Count     in     Count_Type := 1);

184/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.

185/2

     procedure Delete_First (Container in out Vector;
                             Count     in     Count_Type := 1);

186/2

Equivalent to Delete (Container, First_Index (Container), Count).

187/2

     procedure Delete_Last (Container in out Vector;
                            Count     in     Count_Type := 1);

188/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).

189/2

     procedure Reverse_Elements (Container in out List);

190/2

Reorders the elements of Container in reverse order.

191/2

     procedure Swap (Container in out Vector;
                     I,      in     Index_Type);

192/2

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.

193/2

     procedure Swap (Container in out Vector;
                     I,      in     Cursor);

194/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.

195/2

     function First_Index (Container Vector) return Index_Type;

196/2

Returns the value Index_Type'First.

197/2

     function First (Container Vector) return Cursor;

198/2

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

Equivalent to Element (Container, First_Index (Container)).

201/2

     function Last_Index (Container Vector) return Extended_Index;

202/2

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

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

Equivalent to Element (Container, Last_Index (Container)).

207/2

     function Next (Position Cursor) return Cursor;

208/2

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

Equivalent to Position := Next (Position).

211/2

     function Previous (Position Cursor) return Cursor;

212/2

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

Equivalent to Position := Previous (Position).

215/2

     function Find_Index (Container Vector;
                          Item      Element_Type;
                          Index     Index_Type := Index_Type'First)
        return Extended_Index;

216/2

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/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 (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

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/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 (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

Equivalent to Has_Element (Find (Container, Item)).

225/2

     function Has_Element (Position Cursor) return Boolean;

226/2

Returns True if Position designates an element, and returns False otherwise.

227/2

     procedure Iterate
       (Container in Vector;
        Process   not null access procedure (Position in Cursor));

228/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.

229/2

     procedure Reverse_Iterate
       (Container in Vector;
        Process   not null access procedure (Position in Cursor));

230/2

Iterates over the elements in Container as per Iterate, except that elements are traversed in reverse index order.

231/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.232/2

     function Is_Sorted (Container Vector) return Boolean;

233/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.

234/2

     procedure Sort (Container in out Vector);

235/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.

236/2

     procedure Merge (Target  in out Vector;
                      Source  in out Vector);

237/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

238/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.

239/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.

240/2
A Cursor value is ambiguous if any of the following have occurred since it was created:

241/2

242/2

243/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:

244/2

245/2

246/2

247/2

Erroneous Execution

248/2
A Cursor value is invalid if any of the following have occurred since it was created:249/2

250/2

251/2

252/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

253/2
No storage associated with a vector object shall be lost upon assignment or scope exit.

254/2
The execution of an assignment_statement for a vector shall have the effect of copying the elements from the source vector object to the target vector object.

Implementation Advice

255/2
Containers.Vectors should be implemented similarly to an array. In particular, if the length of a vector is N, then

256/2

257

258/2

259/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).

260/2
Containers.Vectors.Generic_Sorting.Sort and Containers.Vectors.Generic_Sorting.Merge should minimize copying of elements.

261/2
Move should not copy elements, and should minimize copying of internal data structures.

262/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.

     NOTES

263/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.

264/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.