A.18 Контейнеры

Этот раздел содержит спецификации пакета Containers и нескольких дочерних пакетов, предоставляющих средства для хранения коллекций элементов.

Предоставляются различные контейнеры последовательностей и ассоциативные контейнеры. Каждый пакет контейнеров определяет тип курсора, а также тип контейнера. Курсор — это ссылка на элемент внутри контейнера. Многие операции над курсорами являются общими для всех контейнеров. Курсор, ссылающийся на элемент в контейнере, считается перекрывающимся только с самим элементом.

Некоторые операции определённых дочерних модулей Ada.Containers имеют параметры доступа к подпрограммам. Чтобы гарантировать корректность таких операций, они предотвращают определённые действия со стороны указанной подпрограммы. Действие над контейнером, которое может добавить или удалить элемент, считается вмешательством в курсоры, и это запрещено во время всех таких операций. Действие над контейнером, которое может заменить элемент элементом другого размера, считается вмешательством в элементы, и это запрещено во время некоторых таких операций. Подробности конкретных действий, которые считаются вмешательством в курсоры или элементы, определены для каждого дочернего модуля Ada.Containers.

Несколько из определённых языком дочерних модулей Ada.Containers включают вложенный пакет Stable, который предоставляет представление контейнера, запрещающее любые операции, которые могли бы вмешаться в элементы. Используя представление Stable для управления контейнером, можно уменьшить количество проверок вмешательства, выполняемых во время выполнения операций. Подробности вложенного пакета Stable определены отдельно для каждого дочернего модуля Ada.Containers, который включает такой вложенный пакет.

В этом разделе мы предоставляем рекомендации по реализации для желаемой средней или наихудшей временной сложности определённых операций над контейнером. Эти рекомендации выражены с помощью символа Ландау O(X). Предполагая, что f — это некоторая функция длины параметра N, а t(N) — это время выполнения операции (в среднем или в худшем случае, как указано) для длины N, сложность O(f(N)) означает, что существует конечное A такое, что для любого N, t(N)/f(N) < A.

Если рекомендации предполагают, что сложность должна быть меньше O(f(N)), то для любого произвольно малого положительного действительного числа D должно существовать положительное целое число M такое, что для всех N > M, t(N)/f(N) < D.

Когда формальная функция используется для обеспечения порядка в контейнере, обычно требуется определить строгое слабое упорядочение. Функция «<» определяет строгое слабое упорядочение, если она является антирефлексивной, асимметричной, транзитивной и, кроме того, если x < y для любых значений x и y, то для всех остальных значений z, (x < z) или (z < y). Элементы находятся в порядке сначала наименьший с использованием такого оператора, если для каждого элемента y с предшественником x в порядке (y < x) ложно.

Определенные подпрограммы, объявленные внутри экземпляров некоторых из обобщенных пакетов, представленных в этом разделе, называются выполняющими неопределённую вставку. Эти подпрограммы соответствуют (в смысле копирования, описанного в 12.3) подпрограммам, имеющим формальные параметры обобщенного формального неопределенного типа и идентифицированные как выполняющие неопределённую вставку в подпункте, определяющем обобщенный пакет.

Если подпрограмма выполняет неопределённую вставку, то в рамках вызова подпрограммы выполняются определенные проверки во время выполнения; если любая из этих проверок терпит неудачу, то соответствующее исключение передаётся вызывающей стороне, и контейнер не изменяется вызовом. Эти проверки выполняются для каждого параметра, соответствующего (в смысле копирования, описанного в 12.3) параметру в соответствующем обобщенном, тип которого является обобщенным формальным неопределенным типом. Проверки, выполняемые для данного параметра, — это те проверки, которые явно указаны в 4.8, которые выполнялись бы в рамках вычисления инициализируемого аллокатора, тип доступа которого объявлен непосредственно внутри экземпляра, где:

Для неопределенного контейнера (тип которого определён в экземпляре дочернего пакета Containers, где defining_identifier содержит "Indefinite"), каждый элемент контейнера создаётся при вставке в контейнер и завершается при удалении из контейнера (или при завершении объекта контейнера, если элемент не был удалён). Для ограниченного контейнера (тип которого определён в экземпляре дочернего пакета Containers, где defining_identifier начинается с "Bounded"), который не является неопределённым контейнером, все элементы ёмкости контейнера создаются и инициализируются по умолчанию при создании объекта контейнера; элементы завершаются при завершении объекта контейнера. Для других типов контейнеров время создания и завершения элементов не определено.

Для экземпляра I пакета контейнера с типом контейнера, конкретный тип T объекта, возвращаемого функцией, возвращающей объект интерфейса итератора, а также примитивные операции T, должны быть неблокирующими. Глобальный аспект, указанный для T и примитивных операций T, должен быть (во всех, синхронизировано выводимый) или спецификацией, позволяющей получить доступ к меньшему числу глобальных объектов.