В результате этого вопроса из нескольких дней назад есть несколько вещей, которые подталкивали меня к требованиям сложности для 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[]. Можно ли это сделать?
