Справочное руководство по Ada 2012
A.18.8 Обобщённый пакет Containers.Hashed_Sets
Статическая семантика
Обобщённый пакет библиотек Containers.Hashed_Sets имеет следующее объявление:
with Ada.Iterator_Interfaces;
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);
pragma Remote_Types(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);
pragma Remote_Types(Hashed_Sets);
type Set is tagged private
with Constant_Indexing => Constant_Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
pragma Preelaborable_Initialization(Set);
with Constant_Indexing => Constant_Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
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 Has_Element (Position : Cursor) return Boolean;
package Set_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
Ada.Iterator_Interfaces (Cursor, Has_Element);
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));
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;
function Constant_Reference (Container : aliased in Set;
Position : in Cursor)
return Constant_Reference_Type;
Position : in Cursor)
return Constant_Reference_Type;
procedure Assign (Target : in out Set; Source : in Set);
function Copy (Source : Set; Capacity : Count_Type := 0) return Set;
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 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));
function Iterate (Container : in Set)
return Set_Iterator_Interfaces.Forward_Iterator'Class;
return Set_Iterator_Interfaces.Forward_Iterator'Class;
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));
type Reference_Type
(Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
(Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
function Reference_Preserving_Key (Container : aliased in out Set;
Position : in Cursor)
return Reference_Type;
Position : in Cursor)
return Reference_Type;
function Constant_Reference (Container : aliased in Set;
Key : in Key_Type)
return Constant_Reference_Type;
Key : in Key_Type)
return Constant_Reference_Type;
function Reference_Preserving_Key (Container : aliased in out Set;
Key : in Key_Type)
return Reference_Type;
Key : in Key_Type)
return Reference_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 каждый раз возвращает одно и то же значение при вызове с определённой парой значений Element. Она должна определять отношение эквивалентности, то есть быть рефлексивной, симметричной и транзитивной. Если фактическая функция Equivalent_Elements ведёт себя по-другому, поведение этого пакета не определено. Какие подпрограммы этого пакета вызывают Equivalent_Elements и сколько раз они это делают, не определено.
Если фактическая функция для обобщённого формального параметра "=" возвращает True для любой пары неэквивалентных элементов, то поведение контейнерной функции "=" не определено.
Если значение элемента, хранящегося в наборе, изменяется способом, отличным от операции в этом пакете, так что по крайней мере одно из Hash или Equivalent_Elements даёт разные результаты, поведение этого пакета не определено.
Какие элементы являются первым и последним элементом множества, а какой элемент является преемником заданного элемента, не определено, за исключением общей семантики, описанной в A.18.7.
функция Capacity (Container : Set) возвращает Count_Type;
Возвращает емкость Container.
процедура 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.
процедура Clear (Container : in out Set);
В дополнение к семантике, описанной в A.18.7, Clear не влияет на емкость Container.
процедура Assign (Target : in out Set; Source : in Set);
В дополнение к семантике, описанной в A.18.7, если длина Source больше, чем емкость Target, вызывается Reserve_Capacity (Target, Length (Source)) перед назначением любых элементов.
функция Copy (Source : Set; Capacity : Count_Type := 0) возвращает Set;
Возвращает множество, элементы которого инициализируются из элементов Source. Если Capacity равно 0, то емкость множества равна длине Source; если Capacity равно или больше длины Source, емкость множества по крайней мере равна указанному значению. В противном случае операция распространяет Capacity_Error.
процедура 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 до некоторого большего значения.
функция First (Container : Set) возвращает Cursor;
Если Length (Container) = 0, то First возвращает No_Element. В противном случае First возвращает курсор, который обозначает первый хешированный элемент в Container.
функция Equivalent_Elements (Left, Right : Cursor)
возвращает Boolean;
возвращает Boolean;
Эквивалентно Equivalent_Elements (Element (Left), Element (Right)).
функция Equivalent_Elements (Left : Cursor;
Right : Element_Type) возвращает Boolean;
Right : Element_Type) возвращает Boolean;
Эквивалентно Equivalent_Elements (Element (Left), Right).
функция Equivalent_Elements (Left : Element_Type;
Right : Cursor) возвращает Boolean;
Right : Cursor) возвращает Boolean;
Эквивалентно Equivalent_Elements (Left, Element (Right)).
функция Iterate (Container : in Set)
возвращает Set_Iterator_Interfaces.Forward_Iterator'Class;
возвращает Set_Iterator_Interfaces.Forward_Iterator'Class;
Iterate возвращает объект итератора (см. 5.5.1), который будет генерировать значение для параметра цикла (см. 5.5.2), обозначающее каждый элемент в Container, начиная с первого элемента и перемещая курсор в соответствии с отношением преемственности. Изменение курсоров Container запрещено, пока существует объект итератора (в частности, в sequence_of_statements оператора loop_statement, у которого iterator_specification обозначает этот объект). Объект итератора требует завершения работы.
Для любого элемента E, фактическая функция для обобщенной формальной функции Generic_Keys.Hash должна быть такой, что Hash (E) = Generic_Keys.Hash (Key (E)). Если фактические значения для Key или Generic_Keys.Hash ведут себя иначе, поведение Generic_Keys не определено. Какие подпрограммы Generic_Keys вызывают Generic_Keys.Hash и сколько раз они это делают, не определено.
Для любых двух элементов E1 и E2, ожидается, что булевы значения Equivalent_Elements (E1, E2) и Equivalent_Keys (Key (E1), Key (E2)) будут равны. Если фактические значения для Key или Equivalent_Keys ведут себя иначе, поведение Generic_Keys не определено. Какие подпрограммы Generic_Keys вызывают Equivalent_Keys и сколько раз они это делают, не определено.
Рекомендации по реализации
Если N - длина множества, средняя временная сложность подпрограмм Insert, Include, Replace, Delete, Exclude и Find, принимающих параметр элемента, должна составлять O(log N). Средняя временная сложность подпрограмм, принимающих параметр курсора, должна составлять O(1). Средняя временная сложность Reserve_Capacity должна составлять O(N).
