A.18.5 The Package Containers.Hashed_Maps
Static Semantics
The generic library
package Containers.Hashed_Maps has the following declaration:
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);
type Map
is tagged private;
pragma Preelaborable_Initialization(Map);
type Cursor
is private;
pragma Preelaborable_Initialization(Cursor);
Empty_Map :
constant Map;
No_Element :
constant Cursor;
function "=" (Left, Right : Map) return Boolean;
function Capacity (Container : Map)
return Count_Type;
procedure Reserve_Capacity (Container :
in out Map;
Capacity :
in Count_Type);
function Length (Container : Map)
return Count_Type;
function Is_Empty (Container : Map)
return Boolean;
procedure Clear (Container :
in out Map);
function Key (Position : Cursor)
return Key_Type;
function Element (Position : Cursor)
return Element_Type;
procedure Replace_Element (Container :
in out Map;
Position :
in Cursor;
New_Item :
in Element_Type);
procedure Query_Element
(Position :
in Cursor;
Process :
not null access procedure (Key :
in Key_Type;
Element :
in Element_Type));
procedure Update_Element
(Container :
in out Map;
Position :
in Cursor;
Process :
not null access procedure
(Key :
in Key_Type;
Element :
in out Element_Type));
procedure Move (Target :
in out Map;
Source :
in out Map);
procedure Insert (Container :
in out Map;
Key :
in Key_Type;
New_Item :
in Element_Type;
Position :
out Cursor;
Inserted :
out Boolean);
procedure Insert (Container :
in out Map;
Key :
in Key_Type;
Position :
out Cursor;
Inserted :
out Boolean);
procedure Insert (Container :
in out Map;
Key :
in Key_Type;
New_Item :
in Element_Type);
procedure Include (Container :
in out Map;
Key :
in Key_Type;
New_Item :
in Element_Type);
procedure Replace (Container :
in out Map;
Key :
in Key_Type;
New_Item :
in Element_Type);
procedure Exclude (Container :
in out Map;
Key :
in Key_Type);
procedure Delete (Container :
in out Map;
Key :
in Key_Type);
procedure Delete (Container :
in out Map;
Position :
in out Cursor);
function First (Container : Map)
return Cursor;
function Next (Position : Cursor)
return Cursor;
procedure Next (Position :
in out Cursor);
function Find (Container : Map;
Key : Key_Type)
return Cursor;
function Element (Container : Map;
Key : Key_Type)
return Element_Type;
function Contains (Container : Map;
Key : Key_Type)
return Boolean;
function Has_Element (Position : Cursor)
return Boolean;
function Equivalent_Keys (Left, Right : Cursor)
return Boolean;
function Equivalent_Keys (Left : Cursor;
Right : Key_Type)
return Boolean;
function Equivalent_Keys (Left : Key_Type;
Right : Cursor)
return Boolean;
procedure Iterate
(Container :
in Map;
Process :
not null access procedure (Position :
in Cursor));
private
... -- not specified by the language
end Ada.Containers.Hashed_Maps;
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.
Two keys
K1 and
K2
are defined to be
equivalent if Equivalent_Keys (
K1,
K2)
returns True.
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.
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.
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.
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.
function Capacity (Container : Map) return Count_Type;
Returns the capacity
of Container.
procedure Reserve_Capacity (Container : in out Map;
Capacity : in Count_Type);
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.
Reserve_Capacity
tampers with the cursors of Container.
procedure Clear (Container : in out Map);
In addition to the
semantics described in
A.18.4, Clear does
not affect the capacity of Container.
procedure Insert (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
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.
function Equivalent_Keys (Left, Right : Cursor)
return Boolean;
Equivalent to Equivalent_Keys
(Key (Left), Key (Right)).
function Equivalent_Keys (Left : Cursor;
Right : Key_Type) return Boolean;
Equivalent to Equivalent_Keys
(Key (Left), Right).
function Equivalent_Keys (Left : Key_Type;
Right : Cursor) return Boolean;
Equivalent to Equivalent_Keys
(Left, Key (Right)).
Implementation Advice
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).
Sponsored by Ada-Europe