Справочник Ada 2005
A.18.8 Пакет Containers.Hashed_Sets
Статическая семантика
В общем библиотечном пакете Containers.Hashed_Sets содержится следующее объявление:
generic
type Element_Type is private;
with function Hash (Element : Element_Type) return Hash_Type;
with function Equivalent_Elements (Left, Right : Element_Type)
return Boolean;
with function "=" (Left, Right : Element_Type) return Boolean is <>;
package Ada.Containers.Hashed_Sets is
pragma Preelaborate(Hashed_Sets);
type Element_Type is private;
with function Hash (Element : Element_Type) return Hash_Type;
with function Equivalent_Elements (Left, Right : Element_Type)
return Boolean;
with function "=" (Left, Right : Element_Type) return Boolean is <>;
package Ada.Containers.Hashed_Sets is
pragma Preelaborate(Hashed_Sets);
type Set is tagged private;
pragma Preelaborable_Initialization(Set);
pragma Preelaborable_Initialization(Set);
type Cursor is private;
pragma Preelaborable_Initialization(Cursor);
pragma Preelaborable_Initialization(Cursor);
Empty_Set : constant Set;
No_Element : constant Cursor;
function "=" (Left, Right : Set) return Boolean;
function Equivalent_Sets (Left, Right : Set) return Boolean;
function To_Set (New_Item : Element_Type) return Set;
function Capacity (Container : Set) return Count_Type;
procedure Reserve_Capacity (Container : in out Set;
Capacity : in Count_Type);
Capacity : in Count_Type);
function Length (Container : Set) return Count_Type;
function Is_Empty (Container : Set) return Boolean;
procedure Clear (Container : in out Set);
function Element (Position : Cursor) return Element_Type;
procedure Replace_Element (Container : in out Set;
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 (Element : in Element_Type));
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
procedure Move (Target : in out Set;
Source : in out Set);
Source : in out Set);
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
procedure Insert (Container : in out Set;
New_Item : in Element_Type);
New_Item : in Element_Type);
procedure Include (Container : in out Set;
New_Item : in Element_Type);
New_Item : in Element_Type);
procedure Replace (Container : in out Set;
New_Item : in Element_Type);
New_Item : in Element_Type);
procedure Exclude (Container : in out Set;
Item : in Element_Type);
Item : in Element_Type);
procedure Delete (Container : in out Set;
Item : in Element_Type);
Item : in Element_Type);
procedure Delete (Container : in out Set;
Position : in out Cursor);
Position : in out Cursor);
procedure Union (Target : in out Set;
Source : in Set);
Source : in Set);
function Union (Left, Right : Set) return Set;
function "or" (Left, Right : Set) return Set renames Union;
procedure Intersection (Target : in out Set;
Source : in Set);
Source : in Set);
function Intersection (Left, Right : Set) return Set;
function "and" (Left, Right : Set) return Set renames Intersection;
procedure Difference (Target : in out Set;
Source : in Set);
Source : in Set);
function Difference (Left, Right : Set) return Set;
function "-" (Left, Right : Set) return Set renames Difference;
procedure Symmetric_Difference (Target : in out Set;
Source : in Set);
Source : in Set);
function Symmetric_Difference (Left, Right : Set) return Set;
function "xor" (Left, Right : Set) return Set
renames Symmetric_Difference;
renames Symmetric_Difference;
function Overlap (Left, Right : Set) return Boolean;
function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;
Of_Set : Set) return Boolean;
function First (Container : Set) return Cursor;
function Next (Position : Cursor) return Cursor;
procedure Next (Position : in out Cursor);
function Find (Container : Set;
Item : Element_Type) return Cursor;
Item : Element_Type) return Cursor;
function Contains (Container : Set;
Item : Element_Type) return Boolean;
Item : Element_Type) return Boolean;
function Has_Element (Position : Cursor) return Boolean;
function Equivalent_Elements (Left, Right : Cursor)
return Boolean;
return Boolean;
function Equivalent_Elements (Left : Cursor;
Right : Element_Type)
return Boolean;
Right : Element_Type)
return Boolean;
function Equivalent_Elements (Left : Element_Type;
Right : Cursor)
return Boolean;
Right : Cursor)
return Boolean;
procedure Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor));
(Container : in Set;
Process : not null access procedure (Position : in Cursor));
generic
type Key_Type (<>) is private;
with function Key (Element : Element_Type) return Key_Type;
with function Hash (Key : Key_Type) return Hash_Type;
with function Equivalent_Keys (Left, Right : Key_Type)
return Boolean;
package Generic_Keys is
type Key_Type (<>) is private;
with function Key (Element : Element_Type) return Key_Type;
with function Hash (Key : Key_Type) return Hash_Type;
with function Equivalent_Keys (Left, Right : Key_Type)
return Boolean;
package Generic_Keys is
function Key (Position : Cursor) return Key_Type;
function Element (Container : Set;
Key : Key_Type)
return Element_Type;
Key : Key_Type)
return Element_Type;
procedure Replace (Container : in out Set;
Key : in Key_Type;
New_Item : in Element_Type);
Key : in Key_Type;
New_Item : in Element_Type);
procedure Exclude (Container : in out Set;
Key : in Key_Type);
Key : in Key_Type);
procedure Delete (Container : in out Set;
Key : in Key_Type);
Key : in Key_Type);
function Find (Container : Set;
Key : Key_Type)
return Cursor;
Key : Key_Type)
return Cursor;
function Contains (Container : Set;
Key : Key_Type)
return Boolean;
Key : Key_Type)
return Boolean;
procedure Update_Element_Preserving_Key
(Container : in out Set;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type));
(Container : in out Set;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type));
end Generic_Keys;
private
... -- не определено языком
end Ada.Containers.Hashed_Sets;
Объект типа Set содержит расширяемую хеш-таблицу, используемую для прямого доступа к элементам. Емкость объекта типа Set — это максимальное количество элементов, которое может быть вставлено в хеш-таблицу до ее автоматического расширения.
Два элемента E1 и E2 определяются как эквивалентные, если Equivalent_Elements (E1, E2) возвращает True.
Ожидается, что фактическая функция для обобщенного формального параметра Hash каждый раз будет возвращать одно и то же значение при вызове с конкретным значением элемента. Для любых двух эквивалентных элементов фактическая функция Hash должна возвращать одно и то же значение. Если фактическая функция Hash ведет себя иначе, поведение этого пакета не определено. Какие подпрограммы этого пакета вызывают Hash и сколько раз они это делают — не определено.
Ожидается, что фактическая функция для обобщенного формального параметра Equivalent_Elements каждый раз будет возвращать одно и то же значение при вызове с конкретной парой значений элемента. Она должна определять отношение эквивалентности, то есть быть рефлексивной, симметричной и транзитивной. Если фактическая функция Equivalent_Elements ведет себя иначе, поведение этого пакета не определено. Какие подпрограммы этого пакета вызывают Equivalent_Elements и сколько раз они это делают — не определено.
Если значение элемента, хранящегося в множестве, изменяется иным образом, чем операция в этом пакете, так что по крайней мере одно из Hash или Equivalent_Elements дает разные результаты, поведение этого пакета не определено.
Какие элементы являются первым и последним элементом множества и какой элемент является преемником данного элемента — не определено, кроме общей семантики, описанной в A.18.7.
function Capacity (Container : Set) return Count_Type;
Возвращает емкость Container.
procedure Reserve_Capacity (Container : in out Set;
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 Set);
В дополнение к семантике, описанной в A.18.7, Clear не влияет на емкость Container.
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
В дополнение к семантике, описанной в A.18.7, если Length (Container) равно Capacity (Container), то Insert сначала вызывает Reserve_Capacity для увеличения емкости Container до некоторого большего значения.
function First (Container : Set) return Cursor;
Если длина (Контейнер) = 0, то First возвращает No_Element. В противном случае First возвращает курсор, обозначающий первый хэшированный элемент в Контейнере.
функция Equivalent_Elements (Left, Right : Курсор)
возвращает Булево;
возвращает Булево;
Эквивалентно Equivalent_Elements (Элемент (Left), Элемент (Right)).
функция Equivalent_Elements (Left : Курсор;
Right : Тип_Элемента) возвращает Булево;
Right : Тип_Элемента) возвращает Булево;
Эквивалентно Equivalent_Elements (Элемент (Left), Right).
функция Equivalent_Elements (Left : Тип_Элемента;
Right : Курсор) возвращает Булево;
Right : Курсор) возвращает Булево;
Эквивалентно Equivalent_Elements (Left, Элемент (Right)).
Для любого элемента E, фактическая функция для обобщенной формальной функции Generic_Keys.Hash должна быть такой, что Hash (E) = Generic_Keys.Hash (Ключ (E)). Если фактические значения для Ключа или Generic_Keys.Hash ведут себя по-другому, поведение Generic_Keys не определено. Какие подпрограммы Generic_Keys вызывают Generic_Keys.Hash и сколько раз они это делают, не определено.
Для любых двух элементов E1 и E2, ожидается, что булевы значения Equivalent_Elements (E1, E2) и Equivalent_Keys (Ключ (E1), Ключ (E2)) будут равны. Если фактические значения для Ключа или Equivalent_Keys ведут себя по-другому, поведение Generic_Keys не определено. Какие подпрограммы Generic_Keys вызывают Equivalent_Keys и сколько раз они это делают, не определено.
Рекомендации по реализации
Если N — длина множества, средняя временная сложность подпрограмм Insert, Include, Replace, Delete, Exclude и Find, которые принимают параметр элемента, должна быть O(log N). Средняя временная сложность подпрограмм, которые принимают параметр курсора, должна быть O(1). Средняя временная сложность Reserve_Capacity должна быть O(N).
