Справочник Ada 2005

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; или

она вызывает процедуру Move с M в качестве параметра; или

она вызывает одну из операций, определённых как вмешивающиеся в курсоры M.

Подпрограмма считается вмешивающейся в элементы объекта карты M, если:

она вмешивается в курсоры M; или

она заменяет один или несколько элементов M, то есть вызывает процедуры Replace или Replace_Element с M в качестве параметра.

Empty_Map представляет пустой объект Map. Его длина равна 0. Если объект типа Map не инициализирован иначе, он инициализируется тем же значением, что и Empty_Map.

No_Element представляет курсор, не обозначающий ни одного узла. Если объект типа Cursor не инициализирован иначе, он инициализируется тем же значением, что и No_Element.

Предопределённый оператор «=» для типа Cursor возвращает True, если оба курсора — No_Element или обозначают один и тот же элемент в одном и том же контейнере.

Выполнение стандартной реализации атрибутов Input, Output, Read или Write типа Cursor вызывает Program_Error.

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 равно 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 равно No_Element, то генерируется Constraint_Error. В противном случае Query_Element вызывает Process.all с ключом и элементом из узла, обозначенного Position, в качестве аргументов. Program_Error генерируется, если Process.all вмешивается в элементы Container. Любое исключение, поднятое 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));

Если Position равно No_Element, то генерируется Constraint_Error; если Position не обозначает элемент в Container, то генерируется Program_Error. В противном случае Update_Element вызывает Process.all с ключом и элементом из узла, обозначенного Position, в качестве аргументов. Program_Error генерируется, если Process.all вмешивается в элементы Container. Любое исключение, поднятое Process.all, передаётся.

Если Element_Type не ограничен и определён, то фактический параметр Element процедуры Process.all должен быть не ограниченным.

procedure Move (Target : in out Map;
Source : in out Map);

Если Target обозначает тот же объект, что и Source, то Move не имеет эффекта. В противном случае Move сначала вызывает Clear (Target). Затем каждый узел из Source удаляется из Source и вставляется в Target. Длина Source равна 0 после успешного вызова Move.

procedure Insert (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);

Insert проверяет, присутствует ли узел с ключом, эквивалентным Key, в Container. Если совпадение найдено, Inserted устанавливается в False, а Position обозначает элемент с соответствующим ключом. В противном случае Insert выделяет новый узел, инициализирует его Key и New_Item и добавляет его в Container; Inserted устанавливается в True, а Position обозначает вставленный узел. Любое исключение, возникшее во время выделения, передаётся, и Container не изменяется.

procedure Insert (Container : in out Map;
Key : in Key_Type;
Position : out Cursor;
Inserted : out Boolean);

Insert вставляет Key в Container в соответствии с пятиразовым Insert, с той разницей, что вставляется элемент, инициализированный по умолчанию (см. 3.3.1).

procedure Insert (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);

Insert вставляет Key и New_Item в Container в соответствии с пятиразовым Insert, с той разницей, что если узел с ключом, эквивалентным Key, уже находится в карте, то генерируется Constraint_Error.

procedure Include (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);

Include вставляет Key и New_Item в Container в соответствии с пятиразовым Insert, с той разницей, что если узел с ключом, эквивалентным Key, уже находится в карте, то эта операция присваивает Key и New_Item соответствующему узлу. Любое исключение, возникшее во время присваивания, передаётся.

procedure Replace (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);

Проверка на наличие узла с ключом, эквивалентным Key, в Container. Если совпадение найдено, Replace присваивает Key и New_Item соответствующему узлу; в противном случае генерируется Constraint_Error.

процедура Exclude (Container : in out Map;
Key : in Key_Type);

Exclude проверяет наличие узла с ключом, эквивалентным Key, в Container. Если совпадение найдено, Exclude удаляет узел из карты.

процедура Delete (Container : in out Map;
Key : in Key_Type);

Delete проверяет наличие узла с ключом, эквивалентным Key, в Container. Если совпадение найдено, Delete удаляет узел из карты; в противном случае генерируется Constraint_Error.

процедура Delete (Container : in out Map;
Position : in out Cursor);

Если Position равно No_Element, то генерируется Constraint_Error. Если Position не указывает на элемент в Container, то генерируется Program_Error. В противном случае Delete удаляет узел, обозначенный Position, из карты. Position устанавливается в No_Element при возврате.

функция First (Container : Map) возвращает Cursor;

Если Length (Container) = 0, то First возвращает No_Element. В противном случае First возвращает курсор, указывающий на первый узел в Container.

функция Next (Position : Cursor) возвращает Cursor;

Возвращает курсор, указывающий на преемника узла, обозначенного Position. Если Position указывает на последний узел, возвращается No_Element. Если Position равно No_Element, возвращается No_Element.

процедура Next (Position : in out Cursor);

Эквивалентно Position := Next (Position).

функция Find (Container : Map;
Key : Key_Type) возвращает Cursor;

Если Length (Container) равно 0, то Find возвращает No_Element. В противном случае Find проверяет наличие узла с ключом, эквивалентным Key, в Container. Если совпадение найдено, возвращается курсор, указывающий на соответствующий узел; в противном случае возвращается No_Element.

функция Element (Container : Map;
Key : Key_Type) возвращает Element_Type;

Эквивалентно Element (Find (Container, Key)).

функция Contains (Container : Map;
Key : Key_Type) возвращает Boolean;

Эквивалентно Find (Container, Key) /= No_Element.

функция Has_Element (Position : Cursor) возвращает Boolean;

Возвращает True, если Position указывает на узел, и False в противном случае.

процедура Iterate
(Container : in Map;
Process : не null доступная процедура (Position : in Cursor));

Iterate вызывает Process.all с курсором, указывающим на каждый узел в Container, начиная с первого узла и перемещая курсор в соответствии с отношением преемника. Program_Error генерируется, если Process.all изменяет курсоры Container. Любой исключительный сигнал, сгенерированный Process.all, передается дальше.

Ошибка выполнения

Значение Cursor является некорректным, если после его создания произошло одно из следующих событий:

Карта, содержащая узел, на который оно указывает, завершена;

Карта, содержащая узел, на который оно указывает, использовалась в качестве Источника или Цели вызова Move; или

Узел, на который оно указывает, был удалён из карты.

Результат «=» или Has_Element неопределён, если эти функции вызываются с некорректным параметром курсора. Выполнение является ошибочным, если любая другая подпрограмма, объявленная в Containers.Hashed_Maps или Containers.Ordered_Maps, вызывается с некорректным параметром курсора.

Требования к реализации

Хранение, связанное с объектом Map, не должно теряться при присваивании или выходе из области видимости.

Выполнение assignment_statement для карты должно иметь эффект копирования элементов из исходной карты в целевую карту.

A.18.4 Карты

Статическая семантика

Ошибка выполнения

Требования к реализации

Рекомендации по реализации