--- ais/ai-20302.txt 2004/11/03 00:47:46 1.12 +++ ais/ai-20302.txt 2004/12/09 19:55:41 1.13 @@ -1,4 +1,21 @@ -!standard A.17 04-11-01 AI95-00302-03/08 +!standard A.18 (00) 04-11-01 AI95-00302-03/08 +!standard A.18.1 (00) +!standard A.18.2 (00) +!standard A.18.3 (00) +!standard A.18.4 (00) +!standard A.18.5 (00) +!standard A.18.6 (00) +!standard A.18.7 (00) +!standard A.18.8 (00) +!standard A.18.9 (00) +!standard A.18.10 (00) +!standard A.18.11 (00) +!standard A.18.12 (00) +!standard A.18.13 (00) +!standard A.18.14 (00) +!standard A.18.15 (00) +!standard A.18.16 (00) +!standard A.4.9 (00) !class amendment 04-01-14 !status work item 04-01-14 !status received 04-01-14 @@ -139,7 +156,7 @@ [This gives us Wide_ versions of these functions.] -A.4.8 String Hashing +A.4.9 String Hashing Static Semantics @@ -166,7 +183,7 @@ a wide spread of values for different string values. It should be unlikely for similar strings to return the same value. -A.17 Containers +A.18 Containers This clause presents the specifications of the package Containers and several child packages, which provide facilities for storing collections @@ -178,7 +195,7 @@ Within this clause we provide Implementation Advice for the desired average or worst case time complexity of certain operations on a -container. This advice is expressed using a big-O notation. +container. This advice is expressed using a big-O notation. A complexity of O(f(N)), presuming f is some function of a length parameter N and t(N) is the time the operation takes (on average or worst case, as specified) for the length N, @@ -298,7 +315,7 @@ implementations that are unstable if given buggy hash functions, et. al. End AARM Text -A.17.1 The Package Containers +A.18.1 The Package Containers The package Containers is the root of the containers subsystem. @@ -327,7 +344,7 @@ properly on machines with native sizes that are not 32 bits. For instance, a 24-bit target could use 2**24 for Hash_Type'Modulus. -A.17.2 The Package Containers.Vectors +A.18.2 The Package Containers.Vectors The language-defined package Containers.Vectors provides a private type Vector and a set of operations. A vector container allows insertion and deletion at @@ -1389,7 +1406,7 @@ or modular type would require a subtype in order to meet this requirement. -A.17.3 The Package Containers.Doubly_Linked_Lists +A.18.3 The Package Containers.Doubly_Linked_Lists The language-defined package Containers.Doubly_Linked_Lists provides private types List and Cursor, and a set of operations for each type. A @@ -1981,7 +1998,7 @@ vector, which may need to copy elements, and is probably not a stable sort. -A.17.4 Maps +A.18.4 Maps The language-defined packages Containers.Hashed_Maps and Containers.Ordered_Maps provide private types Map and Cursor, and a set of operations for each type. @@ -1990,8 +2007,8 @@ the keys, while an ordered map orders the keys per a specified relation. This section describes the declarations that are common to both kinds of maps. -See A.17.5 for a description of the semantics specific to Containers.Hashed_Maps -and A.17.6 for a description of the semantics specific to +See A.18.5 for a description of the semantics specific to Containers.Hashed_Maps +and A.18.6 for a description of the semantics specific to Containers.Ordered_Maps. The type Map is used to represent maps. The type Map needs finalization (see @@ -2292,7 +2309,7 @@ No storage associated with a Map object shall be lost upon assignment or scope exit. -A.17.5 The Package Containers.Hashed_Maps +A.18.5 The Package Containers.Hashed_Maps Static Semantics @@ -2502,7 +2519,7 @@ Which nodes are the first node and the last node of a map, and which node is the successor of a given node, are unspecified, other than the general semantics -described in A.17.4. +described in A.18.4. AARM Note Typically the first node will be the first node in the first bucket, the last @@ -2512,7 +2529,7 @@ procedure Clear (Container : in out Map); -In addition to the semantics described in A.17.4, Clear does not affect the +In addition to the semantics described in A.18.4, Clear does not affect the capacity of Container. AARM Note: @@ -2530,7 +2547,7 @@ Position : out Cursor; Inserted : out Boolean); -In addition to the semantics described in A.17.4, if Length (Container) equals +In addition to the semantics described in A.18.4, if Length (Container) equals Capacity (Container), then Insert first calls Reserve_Capacity to increase the capacity of Container to some larger value. @@ -2605,7 +2622,7 @@ (Container : in Map; Process : not null access procedure (Position : in Cursor)); -In addition to the semantics described in A.17.4, Program_Error is propagated +In addition to the semantics described in A.18.4, Program_Error is propagated if Process.all calls Reserve_Capacity. AARM Note: @@ -2660,7 +2677,7 @@ we don't want to discourage innovative implementations. -A.17.6 The Package Containers.Ordered_Maps +A.18.6 The Package Containers.Ordered_Maps Static Semantics @@ -2971,7 +2988,7 @@ log factor, and we don't want to discourage innovative implementations. -A.17.7 Sets +A.18.7 Sets The language-defined packages Containers.Hashed_Sets and Containers.Ordered_Sets provide private types Set and Cursor, and a set of @@ -2980,8 +2997,8 @@ elements, while an ordered set orders its element per a specified relation. This section describes the declarations that are common to both kinds of sets. -See A.17.8 for a description of the semantics specific to -Containers.Hashed_Sets and A.17.9 for a description of the semantics specific +See A.18.8 for a description of the semantics specific to +Containers.Hashed_Sets and A.18.9 for a description of the semantics specific to Containers.Ordered_Sets. The type Set is used to represent sets. The type Set needs finalization (see @@ -3348,7 +3365,7 @@ No storage associated with a Set object shall be lost upon assignment or scope exit. -A.17.8 The Package Containers.Hashed_Sets +A.18.8 The Package Containers.Hashed_Sets Static Semantics @@ -3576,11 +3593,11 @@ Which elements are the first element and the last element of a set, and which element is the successor of a given element, are unspecified, other than the -general semantics described in A.17.7. +general semantics described in A.18.7. procedure Clear (Container : in out Set); -In addition to the semantics described in A.17.7, Clear does not affect the +In addition to the semantics described in A.18.7, Clear does not affect the capacity of Container. procedure Insert (Container : in out Set; @@ -3588,7 +3605,7 @@ Position : out Cursor; Inserted : out Boolean); -In addition to the semantics described in A.17.7, if Length (Container) equals +In addition to the semantics described in A.18.7, if Length (Container) equals Capacity (Container), then Insert first calls Reserve_Capacity to increase the capacity of Container to some larger value. @@ -3616,7 +3633,7 @@ (Container : in Set; Process : not null access procedure (Position : in Cursor)); -In addition to the semantics described in A.17.7, Program_Error is propagated +In addition to the semantics described in A.18.7, Program_Error is propagated if Process.all calls Reserve_Capacity. function Capacity (Container : Set) return Count_Type; @@ -3671,7 +3688,7 @@ this package. -A.17.9 The Package Containers.Ordered_Sets +A.18.9 The Package Containers.Ordered_Sets Static Semantics @@ -4021,7 +4038,7 @@ unspecified. Which subprograms of this package call Key, Generic_Keys."<" and Generic_Keys.">", and how many times the functions are called, is unspecified. -In addition to the semantics described in A.17.7, the subprograms in package +In addition to the semantics described in A.18.7, the subprograms in package Generic_Keys named Floor, Ceiling, "<", and ">", are equivalent to the corresponding subprograms in the parent package, with the difference that the Key subprogram parameter is compared to elements in the container using the @@ -4040,7 +4057,7 @@ this package. -A.17.10 The Package Containers.Indefinite_Vectors +A.18.10 The Package Containers.Indefinite_Vectors The language-defined package Containers.Indefinite_Vectors provides a private type Vector and a set of operations. It provides the same @@ -4058,7 +4075,7 @@ may be constrained even if Element_Type is unconstrained. -A.17.11 The Package Containers.Indefinite_Doubly_Linked_Lists +A.18.11 The Package Containers.Indefinite_Doubly_Linked_Lists The language-defined package Containers.Indefinite_Doubly_Linked_Lists provides private types List and Cursor, and a set of operations for each @@ -4094,7 +4111,7 @@ may be constrained even if Element_Type is unconstrained. -A.17.12 The Package Containers.Indefinite_Hashed_Maps +A.18.12 The Package Containers.Indefinite_Hashed_Maps The language-defined package Containers.Indefinite_Hashed_Maps provides a map with the same operations as the package Hashed_Maps, with the @@ -4130,7 +4147,7 @@ may be constrained even if Element_Type is unconstrained. -A.17.13 The Package Containers.Indefinite_Ordered_Maps +A.18.13 The Package Containers.Indefinite_Ordered_Maps The language-defined package Containers.Indefinite_Ordered_Maps provides a map with the same operations as the package Ordered, with the @@ -4166,7 +4183,7 @@ may be constrained even if Element_Type is unconstrained. -A.17.14 The Package Containers.Indefinite_Hashed_Sets +A.18.14 The Package Containers.Indefinite_Hashed_Sets The language-defined package Containers.Indefinite_Hashed_Sets provides a set with the same operations as the package Hashed_Sets, with the @@ -4184,7 +4201,7 @@ unconstrained. -A.17.15 The Package Containers.Indefinite_Ordered_Sets +A.18.15 The Package Containers.Indefinite_Ordered_Sets The language-defined package Containers.Indefinite_Ordered_Sets provides a set with the same operations as the package Ordered_Sets, with the @@ -4202,7 +4219,7 @@ unconstrained. -A.17.16 Array Sorting +A.18.16 Array Sorting The language-defined procedures Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort provide sorting on @@ -4277,7 +4294,7 @@ !example -A.17.2 The Package Containers.Vectors +A.18.2 The Package Containers.Vectors Append is the canonical method for inserting items into a vector container: @@ -4554,7 +4571,7 @@ having to allocate a new one. This is exactly how Assign works. -A.17.3 The Package Containers.Doubly_Linked_Lists +A.18.3 The Package Containers.Doubly_Linked_Lists You can use a doubly-linked list to implement a queue in the traditional way: @@ -4678,7 +4695,7 @@ end Op; -A.17.5 The Package Containers.Hashed_Maps +A.18.5 The Package Containers.Hashed_Maps It's often the case that you know apriori the total number of elements you intend to insert into the map. Under these circumstances you should @@ -5488,7 +5505,7 @@ operation does a search anyway. -A.17.9 The Package Containers.Ordered_Sets +A.18.9 The Package Containers.Ordered_Sets Suppose we have a set and want to copy the elements from the set into an array. Here's one way to do it: @@ -6102,7 +6119,7 @@ same. The only real difference is where the key lives. ---!corrigendum A.17 +--!corrigendum A.18 !ACATS Test @@ -9508,7 +9525,7 @@ 4) The definition of *cursor* was buried in the introductory AARM text. I moved - that into the introductory paragraphs of A.17, so that it appears in the + that into the introductory paragraphs of A.18, so that it appears in the normative text. Readers of the standard should be presented the basic model of the containers. @@ -9581,7 +9598,7 @@ wording to make it equal to Before. 10) Added an AARM note to the effect that when we say "unspecified" in this -clause (A.17), we don't mean "erroneous". If we meant "erroneous", we said +clause (A.18), we don't mean "erroneous". If we meant "erroneous", we said that. And included some ramifications of that (checking must not be suppressed; don't create dangling pointers by assuming behavior of generic formals).

Questions? Ask the ACAA Technical Agent