Справочник по Ada 2012
A.18.4 Карты
Определяемые языком обобщенные пакеты Containers.Hashed_Maps и Containers.Ordered_Maps предоставляют частные типы Map и Cursor, а также набор операций для каждого типа. Контейнер карты позволяет использовать произвольный тип в качестве ключа для поиска элемента, связанного с этим ключом. Хешированная карта использует хеш-функцию для организации ключей, а упорядоченная карта упорядочивает ключи в соответствии с заданным отношением.
В этом подпункте описаны объявления, общие для обоих типов карт. См. A.18.5 для описания семантики, специфичной для Containers.Hashed_Maps, и A.18.6 для описания семантики, специфичной для Containers.Ordered_Maps.
Статическая семантика
Ожидается, что фактическая функция обобщенной формальной функции "=" для значений Element_Type определит рефлексивное и симметричное отношение и вернет одно и то же значение результата каждый раз, когда она вызывается с конкретной парой значений. Если она ведет себя иным образом, функция "=" для значений карты возвращает неопределенное значение. Точные аргументы и количество вызовов этой обобщенной формальной функции функцией "=" для значений карты не определены.
Тип Map используется для представления карт. Тип Map требует финализации (см. 7.6).
Карта содержит пары ключей и элементов, называемые узлами. Курсоры карты обозначают узлы, но также могут рассматриваться как обозначающие элемент (элемент, содержащийся в узле) для согласованности с другими контейнерами. Существует отношение эквивалентности на ключах, определение которого отличается для хешированных карт и упорядоченных карт. Карта никогда не содержит два или более узлов с эквивалентными ключами. Длина карты — это количество узлов, которые она содержит.
Каждая непустая карта имеет два конкретных узла, называемые первым узлом и последним узлом (которые могут быть одинаковыми). Каждый узел, кроме последнего, имеет последующий узел. Если нет других промежуточных операций, начиная с первого узла и многократно переходя к последующему узлу, каждый узел в карте будет посещен ровно один раз до тех пор, пока не будет достигнут последний узел. Точное определение этих терминов отличается для хешированных карт и упорядоченных карт.
Некоторые операции этих обобщенных пакетов имеют параметры доступа к подпрограммам. Для обеспечения корректности таких операций они предохраняют от определенных действий указанной подпрограммой. В частности, некоторые операции проверяют «вмешательство с курсорами» контейнера, потому что они зависят от того, что множество элементов контейнера остается постоянным, а другие проверяют «вмешательство с элементами» контейнера, потому что они зависят от того, что элементы контейнера не заменяются.
Подпрограмма считается вмешивающейся с курсорами объекта карты M, если:
- она вставляет или удаляет элементы M, то есть вызывает процедуры Insert, Include, Clear, Delete или Exclude с M в качестве параметра; или
- она завершает M; или
- она вызывает процедуру Assign с M в качестве параметра Target; или
- она вызывает процедуру Move с M в качестве параметра; или
- она вызывает одну из операций, определенных как вмешивающиеся с курсорами M.
Подпрограмма считается вмешивающейся с элементами объекта карты M, если:
- она вмешивается с курсорами M; или
- она заменяет один или несколько элементов M, то есть вызывает процедуры Replace или Replace_Element с M в качестве параметра.
Когда вмешательство с курсорами запрещено для конкретного объекта карты M, Program_Error распространяется вызовом любой определенной языком подпрограммы, которая определена как вмешивающаяся с курсорами M, оставляя M неизмененным. Аналогично, когда вмешательство с элементами запрещено для конкретного объекта карты M, Program_Error распространяется вызовом любой определенной языком подпрограммы, которая определена как вмешивающаяся с элементами M (или вмешивающаяся с курсорами M), оставляя M неизмененным. Эти проверки выполняются до любого другого определенного поведения тела подпрограммы, определенной языком.
Empty_Map представляет собой пустой объект Map. Его длина равна 0. Если объект типа Map не инициализирован иначе, он инициализируется тем же значением, что и Empty_Map.
No_Element представляет собой курсор, который не обозначает ни одного узла. Если объект типа Cursor не инициализирован иначе, он инициализируется тем же значением, что и No_Element.
Предопределенный оператор "=" для типа Cursor возвращает True, если оба курсора являются No_Element или обозначают один и тот же элемент в одном и том же контейнере.
Выполнение стандартной реализации атрибутов Input, Output, Read или Write типа Cursor вызывает Program_Error.
Map'Write для объекта Map M записывает Length(M) элементов карты в поток. Также может быть записана дополнительная информация о карте.
Map'Read считывает представление карты из потока и присваивает Item карту с той же длиной и элементами, что и записанная Map'Write.
function Has_Element (Position : Cursor) return Boolean;
Возвращает True, если Position обозначает элемент, и False в противном случае.
function "=" (Left, Right : Map) return Boolean;
Если Left и Right обозначают один и тот же объект карты, функция возвращает True. Если Left и Right имеют разную длину, функция возвращает False. В противном случае для каждого ключа K в Left функция возвращает False, если:
ключ, эквивалентный K, отсутствует в Right; или
элемент, связанный с K в Left, не равен элементу, связанному с K в Right (используя обобщенный формальный оператор равенства для элементов).
Если функция не вернула результат после проверки всех ключей, она возвращает True. Любое исключение, возникшее во время оценки эквивалентности ключей или равенства элементов, распространяется.
function Length (Container : Map) return Count_Type;
Возвращает количество узлов в Container.
function Is_Empty (Container : Map) return Boolean;
Эквивалентно Length (Container) = 0.
procedure Clear (Container : in out Map);
Удаляет все узлы из Container.
function Key (Position : Cursor) return Key_Type;
Если Position равно No_Element, то генерируется Constraint_Error. В противном случае Key возвращает компонент ключа узла, обозначенного Position.
function Element (Position : Cursor) return Element_Type;
Если Position равно No_Element, то генерируется Constraint_Error. В противном случае Element возвращает компонент элемента узла, обозначенного Position.
procedure Replace_Element (Container : in out Map;
Position : in Cursor;
New_Item : in Element_Type);
Position : in Cursor;
New_Item : in Element_Type);
Если Position равно No_Element, то генерируется Constraint_Error; если Position не обозначает элемент в Container, то генерируется Program_Error. В противном случае Replace_Element присваивает New_Item элементу узла, обозначенного Position.
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));
Если Position равно No_Element, то генерируется Constraint_Error. В противном случае Query_Element вызывает Process.all с ключом и элементом из узла, обозначенного Position, в качестве аргументов. Вмешательство с элементами карты, содержащей элемент, обозначенный Position, запрещено во время выполнения вызова Process.all. Любое исключение, сгенерированное Process.all, распространяется.
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));
Если Position равно No_Element, то генерируется Constraint_Error; если Position не обозначает элемент в Container, то генерируется Program_Error. В противном случае Update_Element вызывает Process.all с ключом и элементом из узла, обозначенного Position, в качестве аргументов. Вмешательство с элементами Container запрещено во время выполнения вызова Process.all. Любое исключение, сгенерированное Process.all, распространяется.
Если Element_Type не ограничен и определен, то фактический параметр Element процесса Process.all должен быть не ограничен.
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;
Типы Constant_Reference_Type и Reference_Type требуют финализации.
Неявная инициализация объекта типа Constant_Reference_Type или Reference_Type вызывает Program_Error.
function Constant_Reference (Container : aliased in Map;
Position : in Cursor)
return Constant_Reference_Type;
Position : in Cursor)
return Constant_Reference_Type;
Эта функция (в сочетании с аспектами Constant_Indexing и Implicit_Dereference) предоставляет удобный способ получить доступ для чтения к отдельному элементу карты, заданного курсором.
Если Position равно No_Element, то Constraint_Error распространяется; если Position не указывает на элемент в Container, то распространяется Program_Error. В противном случае Constant_Reference возвращает объект, дискриминант которого является значением доступа, указывающим на элемент, на который указывает Position. Изменение элементов Container запрещено, пока существует возвращённый объектом Constant_Reference и он не завершён.
функция Reference (Container : aliased in out Map;
Position : in Cursor)
return Reference_Type;
Position : in Cursor)
return Reference_Type;
Эта функция (в сочетании с аспектами Variable_Indexing и Implicit_Dereference) предоставляет удобный способ получения чтения и записи доступа к отдельному элементу карты, используя указатель.
Если Position равно No_Element, то Constraint_Error распространяется; если Position не указывает на элемент в Container, то распространяется Program_Error. В противном случае Reference возвращает объект, дискриминант которого является значением доступа, указывающим на элемент, на который указывает Position. Изменение элементов Container запрещено, пока существует возвращённый объектом Reference и он не завершён.
функция Constant_Reference (Container : aliased in Map;
Key : in Key_Type)
return Constant_Reference_Type;
Key : in Key_Type)
return Constant_Reference_Type;
Эта функция (в сочетании с аспектами Constant_Indexing и Implicit_Dereference) предоставляет удобный способ получения чтения доступа к отдельному элементу карты, используя значение ключа.
Эквивалентно Constant_Reference (Container, Find (Container, Key)).
функция Reference (Container : aliased in out Map;
Key : in Key_Type)
return Reference_Type;
Key : in Key_Type)
return Reference_Type;
Эта функция (в сочетании с аспектами Variable_Indexing и Implicit_Dereference) предоставляет удобный способ получения чтения и записи доступа к отдельному элементу карты, используя значение ключа.
Эквивалентно Reference (Container, Find (Container, Key)).
процедура Assign (Target : in out Map; Source : in Map);
Если Target обозначает тот же объект, что и Source, операция не оказывает никакого влияния. В противном случае пары ключ/элемент Source копируются в Target, как при операторе присваивания, присваивая Source в Target.
процедура Move (Target : in out Map;
Source : in out Map);
Source : in out Map);
Если Target обозначает тот же объект, что и Source, то операция не оказывает никакого влияния. В противном случае операция эквивалентна Assign (Target, Source) за которым следует Clear (Source).
процедура 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);
Insert проверяет, присутствует ли в Container узел с ключом, эквивалентным Key. Если совпадение найдено, Inserted устанавливается в False, а Position указывает на элемент с совпадающим ключом. В противном случае Insert выделяет новый узел, инициализирует его Key и New_Item и добавляет его в Container; Inserted устанавливается в True, а Position указывает на новый вставленный узел. Любое исключение, возникшее во время выделения, распространяется, и Container не изменяется.
процедура 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);
Insert вставляет Key в Container в соответствии с пятипараметрическим Insert, с разницей, что вставляется элемент, инициализированный по умолчанию (см. 3.3.1).
процедура Insert (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
Key : in Key_Type;
New_Item : in Element_Type);
Insert вставляет Key и New_Item в Container в соответствии с пятипараметрическим Insert, с разницей, что если узел с ключом, эквивалентным Key, уже присутствует в карте, то Constraint_Error распространяется.
процедура Include (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
Key : in Key_Type;
New_Item : in Element_Type);
Include вставляет Key и New_Item в Container в соответствии с пятипараметрическим Insert, с разницей, что если узел с ключом, эквивалентным Key, уже присутствует в карте, то эта операция присваивает Key и New_Item соответствующему узлу. Любое исключение, возникшее во время присваивания, распространяется.
процедура Replace (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
Key : in Key_Type;
New_Item : in Element_Type);
Replace проверяет, присутствует ли в Container узел с ключом, эквивалентным Key. Если совпадение найдено, Replace присваивает Key и New_Item соответствующему узлу; в противном случае распространяется Constraint_Error.
процедура Exclude (Container : in out Map;
Key : in Key_Type);
Key : in Key_Type);
Exclude проверяет, присутствует ли в Container узел с ключом, эквивалентным Key. Если совпадение найдено, Exclude удаляет узел из карты.
процедура Delete (Container : in out Map;
Key : in Key_Type);
Key : in Key_Type);
Delete проверяет, присутствует ли в Container узел с ключом, эквивалентным Key. Если совпадение найдено, Delete удаляет узел из карты; в противном случае распространяется Constraint_Error.
процедура Delete (Container : in out Map;
Position : in out Cursor);
Position : in out Cursor);
Если Position равно No_Element, то Constraint_Error распространяется. Если Position не указывает на элемент в Container, то распространяется Program_Error. В противном случае Delete удаляет узел, обозначенный Position, из карты. Позиция устанавливается в No_Element при возврате.
функция First (Container : Map) return Cursor;
Если Length (Container) = 0, то First возвращает No_Element. В противном случае First возвращает указатель, который указывает на первый узел в Container.
функция Next (Position : Cursor) return Cursor;
Возвращает указатель, который указывает на преемника узла, обозначенного Position. Если Position указывает на последний узел, возвращается No_Element. Если Position равно No_Element, то возвращается No_Element.
процедура Next (Position : in out Cursor);
Эквивалентно Position := Next (Position).
функция Find (Container : Map;
Key : Key_Type) return Cursor;
Key : Key_Type) return Cursor;
Если Length (Container) равно 0, то Find возвращает No_Element. В противном случае Find проверяет, присутствует ли в Container узел с ключом, эквивалентным Key. Если совпадение найдено, возвращается указатель, указывающий на соответствующий узел; в противном случае возвращается No_Element.
функция Element (Container : Map;
Key : Key_Type) return Element_Type;
Key : Key_Type) return Element_Type;
Эквивалентно Element (Find (Container, Key)).
функция Contains (Container : Map;
Key : Key_Type) return Boolean;
Key : Key_Type) return Boolean;
Эквивалентно Find (Container, Key) /= No_Element.
Абзацы 72 и 73 были перемещены выше.
процедура Iterate
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
Iterate вызывает Process.all с указателем, который указывает на каждый узел в Container, начиная с первого узла и перемещая указатель в соответствии с отношением преемственности. Изменение указателей Container запрещено во время выполнения вызова Process.all. Любое исключение, поднятое Process.all, распространяется.
Ограниченные (временно́й) ошибки
Ограниченная ошибка для фактической функции, связанной с формальным подпрограммой, когда она вызывается как часть операции пакета карты, заключается в изменении элементов любого параметра карты операции. Или Program_Error поднимается, или операция работает так, как определено на значении карты, как до, так и после некоторых или всех модификаций карты.
Ошибка вызывать любую подпрограмму, объявленную в видимой части пакета карты, когда связанный контейнер был завершён. Если операция принимает Container в качестве параметра in out, то она поднимает Constraint_Error или Program_Error. В противном случае операция либо происходит так, как она бы для пустого контейнера, либо она поднимает Constraint_Error или Program_Error.
Ошибка выполнения
Значение Cursor является недействительным, если после его создания произошло любое из следующего:
- Карта, содержащая узел, на который оно указывает, завершена;
- Карта, содержащая узел, на который оно указывает, использовалась как Target вызова Assign, или как целевой объект оператора присваивания;
- Карта, содержащая узел, на который оно указывает, использовалась как Source или Target вызова Move; или
- Узел, на который оно указывает, был удалён из карты, которая ранее содержала узел.
Результат «=» или Has_Element не определён, если эти функции вызываются с недействительным параметром курсора. Выполнение является ошибочным, если любая другая подпрограмма, объявленная в Containers.Hashed_Maps или Containers.Ordered_Maps, вызывается с недействительным параметром курсора.
Выполнение является ошибочным, если карта, связанная с результатом вызова Reference или Constant_Reference, завершается до завершения объекта результата, возвращённого вызовом Reference или Constant_Reference.
Требования к реализации
Никакой памяти, связанной с объектом Map, не должна теряться при присваивании или выходе из области видимости.
Выполнение оператора присваивания для карты должно иметь эффект копирования элементов из источника в целевой объект карты и изменения длины целевого объекта на длину источника.
END_OF_DOCUMENT_MARKER Рекомендации по реализации
Перемещение не должно копировать элементы и должно минимизировать копирование внутренних структур данных.
Если исключение распространяется из операции над картой, никакие данные не должны быть потеряны, и никакие элементы не должны быть удалены из карты, если это не указано в операции.
