Справочник Ada 2012
A.18.6 Обобщенный пакет Containers.Ordered_Maps
Статическая семантика
Обобщенный библиотечный пакет Containers.Ordered_Maps имеет следующее объявление:
with Ada.Iterator_Interfaces;
generic
type Key_Type is private;
type Element_Type is private;
with function "<" (Left, Right : Key_Type) return Boolean is <>;
with function "=" (Left, Right : Element_Type) return Boolean is <>;
package Ada.Containers.Ordered_Maps is
pragma Preelaborate(Ordered_Maps);
pragma Remote_Types(Ordered_Maps);
generic
type Key_Type is private;
type Element_Type is private;
with function "<" (Left, Right : Key_Type) return Boolean is <>;
with function "=" (Left, Right : Element_Type) return Boolean is <>;
package Ada.Containers.Ordered_Maps is
pragma Preelaborate(Ordered_Maps);
pragma Remote_Types(Ordered_Maps);
function Equivalent_Keys (Left, Right : Key_Type) return Boolean;
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 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) 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);
procedure Delete_First (Container : in out Map);
procedure Delete_Last (Container : in out Map);
function First (Container : Map) return Cursor;
function First_Element (Container : Map) return Element_Type;
function First_Key (Container : Map) return Key_Type;
function Last (Container : Map) return Cursor;
function Last_Element (Container : Map) return Element_Type;
function Last_Key (Container : Map) return Key_Type;
function Next (Position : Cursor) return Cursor;
procedure Next (Position : in out Cursor);
function Previous (Position : Cursor) return Cursor;
procedure Previous (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 Floor (Container : Map;
Key : Key_Type) return Cursor;
Key : Key_Type) return Cursor;
function Ceiling (Container : Map;
Key : Key_Type) return Cursor;
Key : Key_Type) return Cursor;
function Contains (Container : Map;
Key : Key_Type) return Boolean;
Key : Key_Type) return Boolean;
Этот абзац был удален.
function "<" (Left, Right : Cursor) return Boolean;
function ">" (Left, Right : Cursor) return Boolean;
function "<" (Left : Cursor; Right : Key_Type) return Boolean;
function ">" (Left : Cursor; Right : Key_Type) return Boolean;
function "<" (Left : Key_Type; Right : Cursor) return Boolean;
function ">" (Left : Key_Type; 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));
procedure Reverse_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.Reversible_Iterator'Class;
return Map_Iterator_Interfaces.Reversible_Iterator'Class;
function Iterate (Container : in Map; Start : in Cursor)
return Map_Iterator_Interfaces.Reversible_Iterator'Class;
return Map_Iterator_Interfaces.Reversible_Iterator'Class;
private
... -- не указано языком
end Ada.Containers.Ordered_Maps;
Два ключа K1 и K2 считаются эквивалентными, если для них K1 < K2 и K2 < K1 возвращают False, используя обобщенный формальный оператор "<" для ключей. Функция Equivalent_Keys возвращает True, если Left и Right эквивалентны, и False в противном случае.
Ожидается, что фактическая функция для обобщенного формального оператора "<" над значениями Key_Type будет каждый раз возвращать одно и то же значение при вызове с конкретной парой значений ключей. Она должна определять строго слабое упорядочение (см. A.18). Если фактическая реализация "<" ведет себя по-другому, поведение этого пакета не определено. Не определено, какие подпрограммы этого пакета вызывают "<" и сколько раз они это делают.
Если значение ключа, хранящегося в карте, изменяется каким-либо способом, отличным от операции в этом пакете, так что хотя бы один из операторов "<" или "=" даёт другой результат, поведение этого пакета не определено.
Первый узел непустой карты — это узел, ключ которого меньше ключей всех других узлов в карте. Последний узел непустой карты — это узел, ключ которого больше ключей всех остальных элементов в карте. Преемник узла — это узел с наименьшим ключом, который больше ключа данного узла. Предшественник узла — это узел с наибольшим ключом, который меньше ключа данного узла. Все сравнения выполняются с использованием обобщенного формального оператора "<" для ключей.
function Copy (Source : Map) return Map;
Возвращает карту, ключи и элементы которой инициализированы соответствующими ключами и элементами Source.
procedure Delete_First (Container : in out Map);
Если Container пуста, Delete_First не имеет эффекта. В противном случае, узел, обозначенный First (Container), удаляется из Container. Delete_First изменяет курсоры Container.
procedure Delete_Last (Container : in out Map);
Если Container пуста, Delete_Last не имеет эффекта. В противном случае, узел, обозначенный Last (Container), удаляется из Container. Delete_Last изменяет курсоры Container.
function First_Element (Container : Map) return Element_Type;
Эквивалентно Element (First (Container)).
function First_Key (Container : Map) return Key_Type;
Эквивалентно Key (First (Container)).
function Last (Container : Map) return Cursor;
Возвращает курсор, указывающий на последний узел в Container. Если Container пуст, возвращает No_Element.
function Last_Element (Container : Map) return Element_Type;
Эквивалентно Element (Last (Container)).
function Last_Key (Container : Map) return Key_Type;
Эквивалентно Key (Last (Container)).
function Previous (Position : Cursor) return Cursor;
Если Position равно No_Element, то Previous возвращает No_Element. В противном случае Previous возвращает курсор, указывающий на предшествующий узел того, который указан Position. Если Position указывает на первый элемент, то Previous возвращает No_Element.
procedure Previous (Position : in out Cursor);
Эквивалентно Position := Previous (Position).
function Floor (Container : Map;
Key : Key_Type) return Cursor;
Key : Key_Type) return Cursor;
Floor ищет последний узел, ключ которого не больше Key, используя общий формальный оператор "<" для ключей. Если такой узел найден, возвращается курсор, указывающий на него. В противном случае возвращается No_Element.
function Ceiling (Container : Map;
Key : Key_Type) return Cursor;
Key : Key_Type) return Cursor;
Ceiling ищет первый узел, ключ которого не меньше Key, используя общий формальный оператор "<" для ключей. Если такой узел найден, возвращается курсор, указывающий на него. В противном случае возвращается No_Element.
function "<" (Left, Right : Cursor) return Boolean;
Эквивалентно Key (Left) < Key (Right).
function ">" (Left, Right : Cursor) return Boolean;
Эквивалентно Key (Right) < Key (Left).
function "<" (Left : Cursor; Right : Key_Type) return Boolean;
Эквивалентно Key (Left) < Right.
function ">" (Left : Cursor; Right : Key_Type) return Boolean;
Эквивалентно Right < Key (Left).
function "<" (Left : Key_Type; Right : Cursor) return Boolean;
Эквивалентно Left < Key (Right).
function ">" (Left : Key_Type; Right : Cursor) return Boolean;
Эквивалентно Key (Right) < Left.
procedure Reverse_Iterate
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
Итерируется по узлам в Container согласно процедуре Iterate, с той разницей, что узлы просматриваются в порядке предшественников, начиная с последнего узла.
function Iterate (Container : in Map)
return Map_Iterator_Interfaces.Reversible_Iterator'Class;
return Map_Iterator_Interfaces.Reversible_Iterator'Class;
Iterate возвращает объект обратимого итератора (см. 5.5.1), который будет генерировать значение для параметра цикла (см. 5.5.2) для каждого узла в Container, начиная с первого узла и перемещая курсор по отношению к преемнику при использовании в качестве прямого итератора, и начиная с последнего узла и перемещая курсор по отношению к предшественнику при использовании в качестве обратного итератора. Изменение курсоров Container запрещено во время существования объекта итератора (в частности, в sequence_of_statements оператора цикла loop_statement, чья iterator_specification обозначает этот объект). Объект итератора требует завершения.
function Iterate (Container : in Map; Start : in Cursor)
return Map_Iterator_Interfaces.Reversible_Iterator'Class;
return Map_Iterator_Interfaces.Reversible_Iterator'Class;
Если Start не равно No_Element и не указывает на элемент в Container, то происходит распространение Program_Error. Если Start равно No_Element, то происходит распространение Constraint_Error. В противном случае Iterate возвращает объект обратимого итератора (см. 5.5.1), который будет генерировать значение для параметра цикла (см. 5.5.2) для каждого узла в Container, начиная с узла, указанного Start, и перемещая курсор по отношению к преемнику при использовании в качестве прямого итератора, или перемещая курсор по отношению к предшественнику при использовании в качестве обратного итератора. Изменение курсоров Container запрещено во время существования объекта итератора (в частности, в sequence_of_statements оператора цикла loop_statement, чья iterator_specification обозначает этот объект). Объект итератора требует завершения.
Рекомендации по реализации
Если N — длина карты, то временная сложность операций Element, Insert, Include, Replace, Delete, Exclude и Find, принимающих параметр ключа, должна быть O((log N)**2) или лучше. Временная сложность подпрограмм, принимающих параметр курсора, должна составлять O(1).
