В результате этого вопроса от нескольких дней назад есть несколько вещей, которые мешали мне в отношении требований к сложности для std::deque::push_back/push_front против фактических std::deque реализаций в дикой природе.
Результатом предыдущего вопроса было то, что эти операции должны иметь O(1) сложность наихудшего случая. Я подтвердил, что это действительно так в c++11:
из 23.3.3.4 модификаторы deque, вставка, вставка / вставка перед / зад
Сложность: сложность является линейной по количеству вставленных элементов плюс
меньшее из расстояний до начала и конца deque. Вставка одного
элемент в начале или в конце deque всегда занимает постоянное время и
вызывает один вызов конструктора 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[]. Это действительно может быть сделано?