Справочник Ada 2012
A.18.5 Общий пакет Containers.Hashed_Maps
Статическая семантика
Общий библиотечный пакет Containers.Hashed_Maps имеет следующее объявление:
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 <>;
package Ada.Containers.Hashed_Maps is
pragma Preelaborate(Hashed_Maps);
pragma Remote_Types(Hashed_Maps);
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);
pragma Remote_Types(Hashed_Maps);
type Map is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
pragma Preelaborable_Initialization(Map);
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
pragma Preelaborable_Initialization(Map);
type Cursor is private;
pragma Preelaborable_Initialization(Cursor);
pragma Preelaborable_Initialization(Cursor);
Empty_Map : constant Map;
No_Element : constant Cursor;
function Has_Element (Position : Cursor) return Boolean;
package Map_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
Ada.Iterator_Interfaces (Cursor, Has_Element);
function "=" (Left, Right : Map) return Boolean;
function Capacity (Container : Map) return Count_Type;
procedure Reserve_Capacity (Container : in out Map;
Capacity : in Count_Type);
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);
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));
(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));
(Container : in out Map;
Position : in Cursor;
Process : not null access procedure
(Key : in Key_Type;
Element : in out Element_Type));
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
with Implicit_Dereference => Element;
function Constant_Reference (Container : aliased in Map;
Position : in Cursor)
return Constant_Reference_Type;
Position : in Cursor)
return Constant_Reference_Type;
function Reference (Container : aliased in out Map;
Position : in Cursor)
return Reference_Type;
Position : in Cursor)
return Reference_Type;
function Constant_Reference (Container : aliased in Map;
Key : in Key_Type)
return Constant_Reference_Type;
Key : in Key_Type)
return Constant_Reference_Type;
function Reference (Container : aliased in out Map;
Key : in Key_Type)
return Reference_Type;
Key : in Key_Type)
return Reference_Type;
procedure Assign (Target : in out Map; Source : in Map);
function Copy (Source : Map; Capacity : Count_Type := 0) return Map;
procedure Move (Target : in out Map;
Source : 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);
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);
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);
Key : in Key_Type;
New_Item : in Element_Type);
procedure Include (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
Key : in Key_Type;
New_Item : in Element_Type);
procedure Replace (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
Key : in Key_Type;
New_Item : in Element_Type);
procedure Exclude (Container : in out Map;
Key : in Key_Type);
Key : in Key_Type);
procedure Delete (Container : in out Map;
Key : in Key_Type);
Key : in Key_Type);
procedure Delete (Container : in out Map;
Position : in out Cursor);
Position : in out Cursor);
function First (Container : Map)
return Cursor;
return Cursor;
function Next (Position : Cursor) return Cursor;
procedure Next (Position : in out Cursor);
function Find (Container : Map;
Key : Key_Type)
return Cursor;
Key : Key_Type)
return Cursor;
function Element (Container : Map;
Key : Key_Type)
return Element_Type;
Key : Key_Type)
return Element_Type;
function Contains (Container : Map;
Key : Key_Type) return Boolean;
Key : Key_Type) return Boolean;
Этот абзац был удалён.
function Equivalent_Keys (Left, Right : Cursor)
return Boolean;
return Boolean;
function Equivalent_Keys (Left : Cursor;
Right : Key_Type)
return Boolean;
Right : Key_Type)
return Boolean;
function Equivalent_Keys (Left : Key_Type;
Right : Cursor)
return Boolean;
Right : Cursor)
return Boolean;
procedure Iterate
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
function Iterate (Container : in Map)
return Map_Iterator_Interfaces.Forward_Iterator'Class;
return Map_Iterator_Interfaces.Forward_Iterator'Class;
private
... -- не определено языком
end Ada.Containers.Hashed_Maps;
Объект типа Map содержит расширяемую хеш-таблицу, которая используется для предоставления прямого доступа к узлам. Ёмкость объекта типа Map — это максимальное количество узлов, которое может быть вставлено в хеш-таблицу до её автоматического расширения.
Два ключа K1 и K2 определяются как эквивалентные, если Equivalent_Keys (K1, K2) возвращает True.
Ожидается, что фактическая функция для общего формального параметра Hash всегда будет возвращать одно и то же значение при вызове с конкретным значением ключа. Для любых двух эквивалентных значений ключа фактическая функция Hash должна возвращать одно и то же значение. Если фактическая функция Hash ведет себя иным образом, поведение этого пакета не определено. Какие подпрограммы этого пакета вызывают Hash и сколько раз они это делают, не определено.
Ожидается, что фактическая функция для общего формального параметра Equivalent_Keys для значений Key_Type всегда будет возвращать одно и то же значение при вызове с конкретной парой значений ключей. Она должна определять отношение эквивалентности, то есть быть рефлексивной, симметричной и транзитивной. Если фактическая функция Equivalent_Keys ведет себя иным образом, поведение этого пакета не определено. Какие подпрограммы этого пакета вызывают Equivalent_Keys и сколько раз они это делают, не определено.
Если значение ключа, хранящегося в узле карты, изменяется не через операцию в этом пакете таким образом, что по крайней мере одно из Hash или Equivalent_Keys даёт разные результаты, поведение этого пакета не определено.
Какие узлы являются первым и последним узлом карты, и какой узел является преемником данного узла, не определено, за исключением общей семантики, описанной в A.18.4.
function Capacity (Container : Map) return Count_Type;
Возвращает ёмкость Container.
procedure Reserve_Capacity (Container : in out Map;
Capacity : in Count_Type);
Capacity : in Count_Type);
Reserve_Capacity выделяет новую хеш-таблицу таким образом, что длина полученной карты может стать по крайней мере равной Capacity без необходимости дополнительного вызова Reserve_Capacity, и достаточно большая, чтобы содержать текущую длину Container. Затем Reserve_Capacity перехеширует узлы в Container на новую хеш-таблицу. Она заменяет старую хеш-таблицу новой, а затем освобождает старую хеш-таблицу. Любое исключение, поднятое во время выделения, передаётся, и Container не изменяется.
Reserve_Capacity изменяет курсоры Container.
procedure Clear (Container : in out Map);
В дополнение к семантике, описанной в A.18.4, Clear не влияет на ёмкость Container.
procedure Assign (Target : in out Map; Source : in Map);
В дополнение к семантике, описанной в A.18.4, если длина Source больше ёмкости Target, вызывается Reserve_Capacity (Target, Length (Source)) перед назначением любых элементов.
function Copy (Source : Map; Capacity : Count_Type := 0) return Map;
Возвращает карту, ключи и элементы которой инициализируются из ключей и элементов Source. Если Capacity равно 0, то ёмкость карты — это длина Source; если Capacity равно или больше длины Source, ёмкость карты по крайней мере соответствует указанному значению. В противном случае операция передаёт Capacity_Error.
procedure Insert (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
END_OF_DOCUMENT_MARKER Key : in Key_Type;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
В дополнение к семантике, описанной в A.18.4, если Длина (Контейнер) равна Емкости (Контейнер), то Insert сначала вызывает Reserve_Capacity для увеличения емкости Контейнера до некоторого большего значения.
function Equivalent_Keys (Left, Right : Cursor)
return Boolean;
return Boolean;
Эквивалентно Equivalent_Keys (Key (Left), Key (Right)).
function Equivalent_Keys (Left : Cursor;
Right : Key_Type) return Boolean;
Right : Key_Type) return Boolean;
Эквивалентно Equivalent_Keys (Key (Left), Right).
function Equivalent_Keys (Left : Key_Type;
Right : Cursor) return Boolean;
Right : Cursor) return Boolean;
Эквивалентно Equivalent_Keys (Left, Key (Right)).
function Iterate (Container : in Map)
return Map_Iterator_Interfaces.Forward_Iterator'Class;
return Map_Iterator_Interfaces.Forward_Iterator'Class;
Iterate возвращает объект итератора (см. 5.5.1), который будет генерировать значение для параметра цикла (см. 5.5.2), обозначающее каждый узел в Container, начиная с первого узла и перемещая курсор в соответствии с отношением преемника. Вмешательство в курсоры Container запрещено во время существования объекта итератора (в частности, в последовательности_операторов оператора цикла, чья спецификация_итератора обозначает этот объект). Объект итератора требует завершения.
Рекомендации по реализации
Если N — длина карты, средняя временная сложность подпрограмм Element, Insert, Include, Replace, Delete, Exclude и Find, принимающих параметр ключа, должна быть O(log N). Средняя временная сложность подпрограмм, принимающих параметр курсора, должна быть O(1). Средняя временная сложность Reserve_Capacity должна быть O(N).
