A.18.5 The Generic Package Containers.Hashed_Maps
Static Semantics
1/2
{
AI95-00302-03}
The generic library package Containers.Hashed_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 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 is <>;
package Ada.Containers.Hashed_Maps is
pragma Preelaborate(Hashed_Maps);
pragma Remote_Types(Hashed_Maps);3/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);4/2
type Cursor is private;
pragma Preelaborable_Initialization(Cursor);
5/2
Empty_Map : constant Map;
6/2
No_Element : constant Cursor;
6.1/3
{
AI05-0212-1}
function Has_Element (Position : Cursor) return Boolean;6.2/3
{
AI05-0212-1}
package Map_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);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));
17.1/3
{
AI05-0212-1}
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;17.2/3
{
AI05-0212-1}
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;17.3/3
{
AI05-0212-1}
function Constant_Reference (Container : aliased in Map;
Position : in Cursor)
return Constant_Reference_Type;17.4/3
{
AI05-0212-1}
function Reference (Container : aliased in out Map;
Position : in Cursor)
return Reference_Type;17.5/3
{
AI05-0212-1}
function Constant_Reference (Container : aliased in Map;
Key : in Key_Type)
return Constant_Reference_Type;17.6/3
{
AI05-0212-1}
function Reference (Container : aliased in out Map;
Key : in Key_Type)
return Reference_Type;17.7/3
{
AI05-0001-1}
procedure Assign (Target : in out Map; Source : in Map);17.8/3
{
AI05-0001-1}
function Copy (Source : Map; Capacity : Count_Type := 0) return Map;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/3
This paragraph
was deleted. {
AI05-0212-1}
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));
37.1/3
{
AI05-0212-1}
function Iterate (Container : in Map)
return Map_Iterator_Interfaces.Forward_Iterator'Class;38/2
private
39/2
... -- not specified by the language
40/2
end Ada.Containers.Hashed_Maps;
41/2
{
AI95-00302-03}
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.41.a/2
Implementation Note:
The expected implementation for a Map uses a hash table which is
grown when it is too small, with linked lists hanging off of each bucket.
Note that in that implementation a cursor needs a back pointer to the
Map object to implement iteration; that could either be in the nodes,
or in the cursor object. To provide an average O(1) access time,
capacity would typically equal the number of buckets in such an implementation,
so that the average bucket linked list length would be no more than 1.0.
41.b/2
There is no defined relationship
between elements in a hashed map. Typically, iteration will return elements
in the order that they are hashed in.
42/2
{
AI95-00302-03}
Two keys K1 and K2
are defined to be equivalent if Equivalent_Keys (K1, K2)
returns True.43/2
{
AI95-00302-03}
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.43.a/2
Implementation Note:
The implementation is not required to protect against Hash raising
an exception, or returning random numbers, or any other “bad”
behavior. It's not practical to do so, and a broken Hash function makes
the container unusable.
43.b/2
The implementation can
call Hash whenever it is needed; we don't want to specify how often that
happens. The result must remain the same (this is logically a pure function),
or the behavior is unspecified.
44/2
{
AI95-00302-03}
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.44.a/2
Implementation Note:
As with Hash, the implementation is not required to protect against
Equivalent_Keys raising an exception or returning random results. Similarly,
the implementation can call this operation whenever it is needed. The
result must remain the same (this is a logically pure function), or the
behavior is unspecified.
45/2
{
AI95-00302-03}
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.45.a/2
Implementation Note:
The implementation is not required to protect against changes to
key values other than via the operations declared in the Hashed_Maps
package.
45.b/2
To
see how this could happen, imagine an instance of Hashed_Maps where the
key type is an access-to-variable type and Hash returns a value derived
from the components of the designated object. Then, any operation that
has a key value could modify those components and change the hash value:
45.c/2
Key (Map).Some_Component := New_Value;
45.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. But we can't prevent this error anymore
than we can prevent someone passing as Hash a random number generator.
46/2
{
AI95-00302-03}
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.46.a/2
Implementation Note:
Typically the first node will be the first node in the first bucket,
the last node will be the last node in the last bucket, and the successor
will be obtained by following the collision list, and going to the next
bucket at the end of each bucket.
47/2
function Capacity (Container : Map) return Count_Type;
48/2
49/2
procedure Reserve_Capacity (Container : in out Map;
Capacity : in Count_Type);
50/2
{
AI95-00302-03}
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.
51.a/2
Implementation Note:
This routine is used to preallocate the internal hash table to the
specified capacity such that future Inserts do not require expansion
of the hash table. Therefore, the implementation should allocate the
needed memory to make that true at this point, even though the visible
semantics could be preserved by waiting until enough elements are inserted.
51.b/3
{
AI05-0005-1}
While Reserve_Capacity can be used to reduce the
capacity of a map, we do not specify whether an implementation actually
supports reduction of the capacity. Since the actual capacity can be
anything greater than or equal to Capacity Count,
an implementation never has to reduce the capacity.51.c/2
Reserve_Capacity tampers
with the cursors, as rehashing probably will change the order that elements
are stored in the map.
52/2
procedure Clear (Container : in out Map);
53/2
{
AI95-00302-03}
In addition to the semantics described in A.18.4,
Clear does not affect the capacity of Container.53.1/3
procedure Assign (Target : in out Map; Source : in Map);
53.2/3
{
AI05-0001-1}
{
AI05-0248-1}
In addition to the semantics described in A.18.4,
if the length of Source is greater than the capacity of Target, Reserve_Capacity
(Target, Length (Source)) is called before assigning any elements.53.3/3
function Copy (Source : Map; Capacity : Count_Type := 0) return Map;
53.4/3
{
AI05-0001-1}
Returns a map whose keys and elements are initialized
from the keys and elements of Source. If Capacity is 0, then the map
capacity is the length of Source; if Capacity is equal to or greater
than the length of Source, the map capacity is at least the specified
value. Otherwise, the operation propagates Capacity_Error.53.a/2
Implementation
Note: In:
53.b/2
procedure Move (Target : in out Map;
Source : in out Map);
53.c/2
The intended implementation
is that the internal hash table of Target is first deallocated; then
the internal hash table is removed from Source and moved to Target.
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
{
AI95-00302-03}
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.55.a/2
Implementation Note:
Insert should only compare keys that hash to the same bucket in the
hash table.
55.b/2
We specify when Reserve_Capacity
is called to bound the overhead of capacity expansion operations (which
are potentially expensive). Moreover, expansion can be predicted by comparing
Capacity(Map) to Length(Map). Since we don't specify by how much the
hash table is expanded, this only can be used to predict the next expansion,
not later ones.
55.c/2
Implementation
Note: In:
55.d/2
procedure Exclude (Container : in out Map;
Key : in Key_Type);
55.e/2
Exclude should only compare
keys that hash to the same bucket in the hash table.
55.f/2
Implementation
Note: In:
55.g/2
procedure Delete (Container : in out Map;
Key : in Key_Type);
55.h/2
Delete should only compare
keys that hash to the same bucket in the hash table. The node containing
the element may be deallocated now, or it may be saved and reused later.
55.i/2
Implementation
Note: In:
55.j/2
function First (Container : Map) return Cursor;
55.k/2
In a typical implementation,
this will be the first node in the lowest numbered hash bucket that contains
a node.
55.l/2
Implementation
Note: In:
55.m/2
function Next (Position : Cursor) return Cursor;
55.n/2
In a typical implementation,
this will return the next node in a bucket; if Position is the last node
in a bucket, this will return the first node in the next non-empty bucket.
55.o/2
A typical implementation
will need to a keep a pointer at the map container in the cursor in order
to implement this function.
55.p/2
Implementation
Note: In:
55.q/2
function Find (Container : Map;
Key : Key_Type) return Cursor;
55.r/2
Find should only compare
keys that hash to the same bucket in the hash table.
56/2
function Equivalent_Keys (Left, Right : Cursor)
return Boolean;
57/2
{
AI95-00302-03}
Equivalent to Equivalent_Keys (Key (Left), Key
(Right)).58/2
function Equivalent_Keys (Left : Cursor;
Right : Key_Type) return Boolean;
59/2
{
AI95-00302-03}
Equivalent to Equivalent_Keys (Key (Left), Right).60/2
function Equivalent_Keys (Left : Key_Type;
Right : Cursor) return Boolean;
61/2
{
AI95-00302-03}
Equivalent to Equivalent_Keys (Left, Key (Right)).61.1/3
function Iterate (Container : in Map)
return Map_Iterator_Interfaces.Forward_Iterator'Class;
61.2/3
{
AI05-0212-1}
{
AI05-0265-1}
Iterate returns an 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. 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
62/2
{
AI95-00302-03}
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). 62.a/2
Implementation Advice:
The average time complexity of Element,
Insert, Include, Replace, Delete, Exclude and Find operations that take
a key parameter for Containers.Hashed_Maps should be O(log N).
The average time complexity of the subprograms of Containers.Hashed_Maps
that take a cursor parameter should be O(1). The average time
complexity of Containers.Hashed_Maps.Reserve_Capacity should be O(N).
62.b/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 for which Find is O(N), that
program could be unusable when the maps are large. We allow O(log
N) access 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
62.c/2
{
AI95-00302-03}
The generic package Containers.Hashed_Maps
is new. Incompatibilities With Ada 2005
62.d/3
{
AI05-0001-1}
Subprograms Assign and Copy
are newly added to Containers.Hashed_Maps. If an instance of Containers.Hashed_Maps
is referenced in a use_clause,
and an entity E with the same defining_identifier
as a new entity in Containers.Hashed_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
62.e/3
{
AI05-0212-1}
Added iterator and indexing
support to make hashed map containers more convenient to use.
Wording Changes from Ada 2005
62.f/3
{
AI05-0084-1}
Correction: Added a pragma Remote_Types
so that containers can be used in distributed programs.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
