Требования к сложности для std:: deque:: push_back/front

В результате этого вопроса из нескольких дней назад есть несколько вещей, которые подталкивали меня к требованиям сложности для std::deque::push_back/push_front против фактического std::deque реализация в дикой природе.

Результат предыдущего вопроса состоял в том, что для этих операций требуется O(1) наихудшая сложность. Я подтвердил, что это действительно так в c++11:

из 23.3.3.4 модификаторы deque, ссылающиеся на вставку, push/emplace front/back

Сложность: сложность линейна по числу вставленных элементов плюс меньше расстояний до начала и конца дека. Вставка одного элемент либо в начале, либо в конце дека всегда принимает постоянное время и вызывает один вызов конструктора T.

Это сочетается с требованием сложности O(1) для индексирования через operator[] и т.д.

Проблема заключается в том, что реализации не полностью удовлетворяют этим требованиям.

В терминах msvc и gcc реализация std::deque представляет собой заблокированную структуру данных, состоящую из блоков динамических массивов указателей на (фиксированный размер), где каждый блок хранит несколько элементов данных.

В худшем случае push_back/front etc может потребоваться выделение дополнительного блока (это ограничение - фиксированное распределение по размеру равно O(1)), но также может быть изменено размер динамического массива указателей блоков - это не так, так как это O(m), где m - количество блоков, которое в конце дня O(n).

Очевидно, это по-прежнему амортизируется сложностью O(1) и, поскольку обычно m << n на практике это будет довольно быстро. Но, похоже, проблема с соответствием?

В качестве еще одного момента я не вижу, как вы можете создать структуру данных, которая строго удовлетворяет как сложности O(1) для push_back/front etc, так и operator[]. У вас может быть связанный список указателей блоков, но это не дает вам желаемого поведения operator[]. Можно ли это сделать?

Ответы

Ответ 1

В С++ 11 FDIS мы можем прочитать:

23.2.3 Контейнеры последовательности [sequence.reqmts]

16/ В таблице 101 перечислены операции, которые предоставляются для некоторых типов контейнеров последовательностей, но не для других. Реализация должна обеспечивать эти операции для всех типов контейнеров, указанных в столбце "контейнер", и выполнять их таким образом, чтобы принимать амортизированное постоянное время.

Здесь таблица 101 называется необязательными операциями контейнера последовательности и списками deque для операций push_back и push_front.

Следовательно, это похоже на небольшое упущение в указанном вами параграфе. Возможно, стоит отчет о дефектах?

Обратите внимание, что одиночный вызов конструктора все еще сохраняется.

Ответ 2

Я подозреваю, что перераспределение указателей блоков выполняется с геометрически увеличивающимся размером - это общий трюк для std::vector. Я думаю, что это технически O (log m), но поскольку вы указываете m < n, так как практический вопрос не влияет на реальные результаты.