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


A.18.5 The Package Containers.Hashed_Maps

Static Semantics

1/2
The generic library package Containers.Hashed_Maps has the following declaration:

2/2

     generic
        type Key_Type is private;
        type Element_Type is private;
        with function Hash (Key Key_Type) return Hash_Type;
        with function Equivalent_Keys (Left, Right Key_Type)
           return Boolean;
        with function "=" (Left, Right Element_Type)
           return Boolean is <>;
     package Ada.Containers.Hashed_Maps is   pragma Preelaborate(Hashed_Maps);

3/2

        type Map is tagged private;
        pragma Preelaborable_Initialization(Map);

4/2

        type Cursor is private;
        pragma Preelaborable_Initialization(Cursor);

5/2

        Empty_Map constant Map;

6/2

        No_Element constant Cursor;

7/2

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

8/2

        function Capacity (Container Map) return Count_Type;

9/2

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

10/2

        function Length (Container Map) return Count_Type;

11/2

        function Is_Empty (Container Map) return Boolean;

12/2

        procedure Clear (Container in out Map);

13/2

        function Key (Position Cursor) return Key_Type;

14/2

        function Element (Position Cursor) return Element_Type;

15/2

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

16/2

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

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

18/2

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

19/2

        procedure Insert (Container in out Map;
                          Key       in     Key_Type;
                          New_Item  in     Element_Type;
                          Position     out Cursor;
                          Inserted     out Boolean);

20/2

        procedure Insert (Container in out Map;
                          Key       in     Key_Type;
                          Position     out Cursor;
                          Inserted     out Boolean);

21/2

        procedure Insert (Container in out Map;
                          Key       in     Key_Type;
                          New_Item  in     Element_Type);

22/2

        procedure Include (Container in out Map;
                           Key       in     Key_Type;
                           New_Item  in     Element_Type);

23/2

        procedure Replace (Container in out Map;
                           Key       in     Key_Type;
                           New_Item  in     Element_Type);

24/2

        procedure Exclude (Container in out Map;
                           Key       in     Key_Type);

25/2

        procedure Delete (Container in out Map;
                          Key       in     Key_Type);

26/2

        procedure Delete (Container in out Map;
                          Position  in out Cursor);

27/2

        function First (Container Map)
           return Cursor;

28/2

        function Next (Position  Cursor) return Cursor;

29/2

        procedure Next (Position  in out Cursor);

30/2

        function Find (Container Map;
                       Key       Key_Type)
           return Cursor;

31/2

        function Element (Container Map;
                          Key       Key_Type)
           return Element_Type;

32/2

        function Contains (Container Map;
                           Key       Key_Type) return Boolean;

33/2

        function Has_Element (Position Cursor) return Boolean;

34/2

        function Equivalent_Keys (Left, Right Cursor)
           return Boolean;

35/2

        function Equivalent_Keys (Left  Cursor;
                                  Right Key_Type)
           return Boolean;

36/2

        function Equivalent_Keys (Left  Key_Type;
                                  Right Cursor)
           return Boolean;

37/2

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

38/2

     private

39/2

        ... −− not specified by the language

40/2

     end Ada.Containers.Hashed_Maps;

41/2
An object of type Map contains an expandable hash table, which is used to provide direct access to nodes. The capacity of an object of type Map is the maximum number of nodes that can be inserted into the hash table prior to it being automatically expanded.42/2
Two keys K1 and K2 are defined to be equivalent if Equivalent_Keys (K1, K2) returns True.

43/2
The actual function for the generic formal function Hash is expected to return the same value each time it is called with a particular key value. For any two equivalent key values, the actual for Hash is expected to return the same value. If the actual for Hash behaves in some other manner, the behavior of this package is unspecified. Which subprograms of this package call Hash, and how many times they call it, is unspecified.44/2
The actual function for the generic formal function Equivalent_Keys 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 an equivalence relationship, that is, be reflexive, symmetric, and transitive. If the actual for Equivalent_Keys behaves in some other manner, the behavior of this package is unspecified. Which subprograms of this package call Equivalent_Keys, and how many times they call it, is unspecified.45/2
If the value of a key stored in a node of a map is changed other than by an operation in this package such that at least one of Hash or Equivalent_Keys give different results, the behavior of this package is unspecified.46/2
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.18.4.47/2

     function Capacity (Container Map) return Count_Type;

48/2

Returns the capacity of Container.

49/2

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

50/2

Reserve_Capacity allocates a new hash table such that the length of the resulting map 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 rehashes the nodes in Container onto the new hash table. It replaces the old hash table with the new hash table, and then deallocates the old hash table. Any exception raised during allocation is propagated and Container is not modified.

51/2

Reserve_Capacity tampers with the cursors of Container.

52/2

     procedure Clear (Container in out Map);

53/2

In addition to the semantics described in A.18.4, Clear does not affect the capacity of Container.

54/2

     procedure Insert (Container in out Map;
                       Key       in     Key_Type;
                       New_Item  in     Element_Type;
                       Position     out Cursor;
                       Inserted     out Boolean);

55/2

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.

56/2

     function Equivalent_Keys (Left, Right Cursor)
           return Boolean;

57/2

Equivalent to Equivalent_Keys (Key (Left), Key (Right)).

58/2

     function Equivalent_Keys (Left  Cursor;
                               Right Key_Type) return Boolean;

59/2

Equivalent to Equivalent_Keys (Key (Left), Right).

60/2

     function Equivalent_Keys (Left  Key_Type;
                               Right Cursor) return Boolean;

61/2

Equivalent to Equivalent_Keys (Left, Key (Right)).
Implementation Advice

62/2
If N is the length of a map, the average time complexity of the subprograms Element, Insert, Include, Replace, Delete, Exclude and Find that take a key parameter should be O(log N). The average time complexity of the subprograms that take a cursor parameter should be O(1). The average time complexity of Reserve_Capacity should be O(N).