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

В этом пункте представлены спецификации пакета 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).

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

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