Annotated Ada Reference ManualLegal Information
Contents   Index   References   Search   Previous   Next 

 A.18.6 The Generic Package Containers.Ordered_Maps

Static Semantics

1/2
{AI95-00302-03} The generic library package Containers.Ordered_Maps has the following declaration: 
2/3
{AI05-0084-1} {AI05-0212-1} with Ada.Iterator_Interfaces;
generic
   type Key_Type is private;
   type Element_Type is private;
   with function "<" (Left, Right : Key_Type) return Boolean is <>;
   with function "=" (Left, Right : Element_Type) return Boolean is <>;
package Ada.Containers.Ordered_Maps is
   pragma Preelaborate(Ordered_Maps);

   pragma Remote_Types(Ordered_Maps);
3/2
   function Equivalent_Keys (Left, Right : Key_Type) return Boolean;
4/3
{AI05-0212-1}    type Map is tagged private
      with Constant_Indexing => Constant_Reference,
           Variable_Indexing => Reference,
           Default_Iterator  => Iterate,
           Iterator_Element  => Element_Type
;
   pragma Preelaborable_Initialization(Map);
5/2
   type Cursor is private;
   pragma Preelaborable_Initialization(Cursor);
6/2
   Empty_Map : constant Map;
7/2
   No_Element : constant Cursor;
7.1/3
{AI05-0212-1}    function Has_Element (Position : Cursor) return Boolean;
7.2/3
{AI05-0212-1}    package Map_Iterator_Interfaces is new
       Ada.Iterator_Interfaces (Cursor, Has_Element);
8/2
   function "=" (Left, Right : Map) return Boolean;
9/2
   function Length (Container : Map) return Count_Type;
10/2
   function Is_Empty (Container : Map) return Boolean;
11/2
   procedure Clear (Container : in out Map);
12/2
   function Key (Position : Cursor) return Key_Type;
13/2
   function Element (Position : Cursor) return Element_Type;
14/2
   procedure Replace_Element (Container : in out Map;
                              Position  : in     Cursor;
                              New_Item  : in     Element_Type);
15/2
   procedure Query_Element
     (Position : in Cursor;
      Process  : not null access procedure (Key     : in Key_Type;
                                            Element : in Element_Type));
16/2
   procedure Update_Element
     (Container : in out Map;
      Position  : in     Cursor;
      Process   : not null access procedure
                      (Key     : in     Key_Type;
                       Element : in out Element_Type));
16.1/3
{AI05-0212-1}    type Constant_Reference_Type
         (Element : not null access constant Element_Type) is private
      with Implicit_Dereference => Element;
16.2/3
{AI05-0212-1}    type Reference_Type (Element : not null access Element_Type) is private
      with Implicit_Dereference => Element;
16.3/3
{AI05-0212-1}    function Constant_Reference (Container : aliased in Map;
                                Position  : in Cursor)
      return Constant_Reference_Type;
16.4/3
{AI05-0212-1}    function Reference (Container : aliased in out Map;
                       Position  : in Cursor)
      return Reference_Type;
16.5/3
{AI05-0212-1}    function Constant_Reference (Container : aliased in Map;
                                Key       : in Key_Type)
      return Constant_Reference_Type;
16.6/3
{AI05-0212-1}    function Reference (Container : aliased in out Map;
                       Key       : in Key_Type)
      return Reference_Type;
16.7/3
{AI05-0001-1}    procedure Assign (Target : in out Map; Source : in Map);
16.8/3
{AI05-0001-1}    function Copy (Source : Map) return Map;
17/2
   procedure Move (Target : in out Map;
                   Source : in out Map);
18/2
   procedure Insert (Container : in out Map;
                     Key       : in     Key_Type;
                     New_Item  : in     Element_Type;
                     Position  :    out Cursor;
                     Inserted  :    out Boolean);
19/2
   procedure Insert (Container : in out Map;
                     Key       : in     Key_Type;
                     Position  :    out Cursor;
                     Inserted  :    out Boolean);
20/2
   procedure Insert (Container : in out Map;
                     Key       : in     Key_Type;
                     New_Item  : in     Element_Type);
21/2
   procedure Include (Container : in out Map;
                      Key       : in     Key_Type;
                      New_Item  : in     Element_Type);
22/2
   procedure Replace (Container : in out Map;
                      Key       : in     Key_Type;
                      New_Item  : in     Element_Type);
23/2
   procedure Exclude (Container : in out Map;
                      Key       : in     Key_Type);
24/2
   procedure Delete (Container : in out Map;
                     Key       : in     Key_Type);
25/2
   procedure Delete (Container : in out Map;
                     Position  : in out Cursor);
26/2
   procedure Delete_First (Container : in out Map);
27/2
   procedure Delete_Last (Container : in out Map);
28/2
   function First (Container : Map) return Cursor;
29/2
   function First_Element (Container : Map) return Element_Type;
30/2
   function First_Key (Container : Map) return Key_Type;
31/2
   function Last (Container : Map) return Cursor;
32/2
   function Last_Element (Container : Map) return Element_Type;
33/2
   function Last_Key (Container : Map) return Key_Type;
34/2
   function Next (Position : Cursor) return Cursor;
35/2
   procedure Next (Position : in out Cursor);
36/2
   function Previous (Position : Cursor) return Cursor;
37/2
   procedure Previous (Position : in out Cursor);
38/2
   function Find (Container : Map;
                  Key       : Key_Type) return Cursor;
39/2
   function Element (Container : Map;
                     Key       : Key_Type) return Element_Type;
40/2
   function Floor (Container : Map;
                   Key       : Key_Type) return Cursor;
41/2
   function Ceiling (Container : Map;
                     Key       : Key_Type) return Cursor;
42/2
   function Contains (Container : Map;
                      Key       : Key_Type) return Boolean;
43/3
This paragraph was deleted. {AI05-0212-1}    function Has_Element (Position : Cursor) return Boolean;
44/2
   function "<" (Left, Right : Cursor) return Boolean;
45/2
   function ">" (Left, Right : Cursor) return Boolean;
46/2
   function "<" (Left : Cursor; Right : Key_Type) return Boolean;
47/2
   function ">" (Left : Cursor; Right : Key_Type) return Boolean;
48/2
   function "<" (Left : Key_Type; Right : Cursor) return Boolean;
49/2
   function ">" (Left : Key_Type; Right : Cursor) return Boolean;
50/2
   procedure Iterate
     (Container : in Map;
      Process   : not null access procedure (Position : in Cursor));
51/2
   procedure Reverse_Iterate
     (Container : in Map;
      Process   : not null access procedure (Position : in Cursor));
51.1/3
{AI05-0212-1}    function Iterate (Container : in Map)
      return Map_Iterator_Interfaces.Reversible_Iterator'Class;
52/2
private
53/2
   ... -- not specified by the language
54/2
end Ada.Containers.Ordered_Maps;
55/2
 {AI95-00302-03} Two keys K1 and K2 are equivalent if both K1 < K2 and K2 < K1 return False, using the generic formal "<" operator for keys. Function Equivalent_Keys returns True if Left and Right are equivalent, and False otherwise.
56/3
 {AI95-00302-03} {AI05-0044-1} The actual function for the generic formal function "<" on Key_Type values is expected to return the same value each time it is called with a particular pair of key values. It should define a strict weak ordering relationship (see A.18), that is, be irreflexive, asymmetric, and transitive. If the actual for "<" behaves in some other manner, the behavior of this package is unspecified. Which subprograms of this package call "<" and how many times they call it, is unspecified.
56.a/2
Implementation Note: The implementation is not required to protect against "<" raising an exception, or returning random results, or any other “bad” behavior. It's not practical to do so, and a broken "<" function makes the container unusable.
56.b/2
The implementation can call "<" whenever it is needed; we don't want to specify how often that happens. The result must remain the same (this is a logically pure function), or the behavior is unspecified. 
57/2
 {AI95-00302-03} If the value of a key stored in a map is changed other than by an operation in this package such that at least one of "<" or "=" give different results, the behavior of this package is unspecified.
57.a/2
Implementation Note: The implementation is not required to protect against changes to key values other than via the operations declared in the Ordered_Maps package.
57.b/2
To see how this could happen, imagine an instance of Ordered_Maps package where the key type is an access-to-variable type and "<" returns a value derived from comparing the components of the designated objects. Then, any operation that has a key value (even if the key value is constant) could modify those components and change the result of "<":
57.c/2
Key (Map).Some_Component := New_Value;
57.d/2
This is really a design error on the part of the user of the map; it shouldn't be possible to modify keys stored in a map such that "<" changes. But we can't prevent this error anymore than we can prevent someone passing as "<" a routine that produces random answers. 
58/3
 {AI95-00302-03} {AI05-0262-1} The first node first node of a nonempty map is the one whose key is less than the key of all the other nodes in the map. The last node last node of a nonempty map is the one whose key is greater than the key of all the other elements in the map. The successor successor of a node is the node with the smallest key that is larger than the key of the given node. The predecessor predecessor of a node is the node with the largest key that is smaller than the key of the given node. All comparisons are done using the generic formal "<" operator for keys.
58.1/3
function Copy (Source : Map) return Map;
58.2/3
{AI05-0001-1} Returns a map whose keys and elements are initialized from the corresponding keys and elements of Source.
59/2
procedure Delete_First (Container : in out Map);
60/3
{AI95-00302-03} {AI05-0264-1} If Container is empty, Delete_First has no effect. Otherwise, the node designated by First (Container) is removed from Container. Delete_First tampers with the cursors of Container.
61/2
procedure Delete_Last (Container : in out Map);
62/3
{AI95-00302-03} {AI05-0264-1} If Container is empty, Delete_Last has no effect. Otherwise, the node designated by Last (Container) is removed from Container. Delete_Last tampers with the cursors of Container.
63/2
function First_Element (Container : Map) return Element_Type;
64/2
{AI95-00302-03} Equivalent to Element (First (Container)).
65/2
function First_Key (Container : Map) return Key_Type;
66/2
{AI95-00302-03} Equivalent to Key (First (Container)).
67/2
function Last (Container : Map) return Cursor;
68/2
{AI95-00302-03} Returns a cursor that designates the last node in Container. If Container is empty, returns No_Element.
69/2
function Last_Element (Container : Map) return Element_Type;
70/2
{AI95-00302-03} Equivalent to Element (Last (Container)).
71/2
function Last_Key (Container : Map) return Key_Type;
72/2
{AI95-00302-03} Equivalent to Key (Last (Container)).
73/2
function Previous (Position : Cursor) return Cursor;
74/3
{AI95-00302-03} {AI05-0262-1} If Position equals No_Element, then Previous returns No_Element. Otherwise, Previous returns a cursor designating the predecessor node of that precedes the one designated by Position. If Position designates the first element, then Previous returns No_Element.
75/2
procedure Previous (Position : in out Cursor);
76/2
{AI95-00302-03} Equivalent to Position := Previous (Position).
77/2
function Floor (Container : Map;
                Key       : Key_Type) return Cursor;
78/3
{AI95-00302-03} {AI05-0264-1} Floor searches for the last node whose key is not greater than Key, using the generic formal "<" operator for keys. If such a node is found, a cursor that designates it is returned. Otherwise, No_Element is returned.
79/2
function Ceiling (Container : Map;
                  Key       : Key_Type) return Cursor;
80/3
{AI95-00302-03} {AI05-0264-1} Ceiling searches for the first node whose key is not less than Key, using the generic formal "<" operator for keys. If such a node is found, a cursor that designates it is returned. Otherwise, No_Element is returned.
81/2
function "<" (Left, Right : Cursor) return Boolean;
82/2
{AI95-00302-03} Equivalent to Key (Left) < Key (Right).
83/2
function ">" (Left, Right : Cursor) return Boolean;
84/2
{AI95-00302-03} Equivalent to Key (Right) < Key (Left).
85/2
function "<" (Left : Cursor; Right : Key_Type) return Boolean;
86/2
{AI95-00302-03} Equivalent to Key (Left) < Right.
87/2
function ">" (Left : Cursor; Right : Key_Type) return Boolean;
88/2
{AI95-00302-03} Equivalent to Right < Key (Left).
89/2
function "<" (Left : Key_Type; Right : Cursor) return Boolean;
90/2
{AI95-00302-03} Equivalent to Left < Key (Right).
91/2
function ">" (Left : Key_Type; Right : Cursor) return Boolean;
92/2
{AI95-00302-03} Equivalent to Key (Right) < Left.
93/2
procedure Reverse_Iterate
  (Container : in Map;
   Process   : not null access procedure (Position : in Cursor));
94/3
{AI95-00302-03} {AI05-0212-1} Iterates over the nodes in Container as per procedure Iterate, with the difference that the nodes are traversed in predecessor order, starting with the last node.
94.1/3
function Iterate (Container : in Map)
   return Map_Iterator_Interfaces.Reversible_Iterator'Class;
94.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 according to the successor relation when used as a forward iterator, and starting with the last node and moving the cursor according to the predecessor relation 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.

Implementation Advice

95/2
 {AI95-00302-03} If N is the length of a map, then the worst-case time complexity of the Element, Insert, Include, Replace, Delete, Exclude and Find operations that take a key parameter should be O((log N)**2) or better. The worst-case time complexity of the subprograms that take a cursor parameter should be O(1). 
95.a/2
Implementation Advice: The worst-case time complexity of Element, Insert, Include, Replace, Delete, Exclude and Find operations that take a key parameter for Containers.Ordered_Maps should be O((log N)**2) or better. The worst-case time complexity of the subprograms of Containers.Ordered_Maps that take a cursor parameter should be O(1).
95.b/2
Implementation Note: A balanced (red-black) tree for keys has O(log N) worst-case performance. Note that a O(N) worst-case implementation (like a list) would be wrong. 
95.c/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) to find elements, that program could be unusable when the maps are large. We allow the extra log N factors 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. 

Extensions to Ada 95

95.d/2
{AI95-00302-03} The generic package Containers.Ordered_Maps is new. 

Incompatibilities With Ada 2005

95.e/3
{AI05-0001-1} Subprograms Assign and Copy are newly added to Containers.Ordered_Maps. If an instance of Containers.Ordered_Maps is referenced in a use_clause, and an entity E with the same defining_identifier as a new entity in Containers.Ordered_Maps 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

95.f/3
{AI05-0212-1} Added iterator and indexing support to make ordered map containers more convenient to use.

Wording Changes from Ada 2005

95.g/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.
95.h/3
{AI05-0084-1} Correction: Added a pragma Remote_Types so that containers can be used in distributed programs. 

Contents   Index   References   Search   Previous   Next 
Ada-Europe Ada 2005 and 2012 Editions sponsored in part by Ada-Europe