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.