Как Deque имеют амортизируются постоянное время Сложность

Question

here Я прочитал от принятого ответа, что станд :: Deque имеет следующие характеристики

1- Random access - constant O(1) 
2- Insertion or removal of elements at the end or beginning - amortized constant O(1) 
3- Insertion or removal of elements - linear O(n) 

Мой вопрос о пункте 2. Как может Deque иметь амортизируется постоянная вставка в конце или в начале?

Я понимаю, что a std::vector имеет амортизированную постоянную временную сложность для вставок в конце. Это связано с тем, что вектор является условным и представляет собой динамический массив. Поэтому, когда в конце памяти заканчивается push_back, он выделяет целый новый блок памяти, копирует существующие элементы из старого местоположения в новое место и затем удаляет элементы из старого местоположения. Эта операция, которую я понимаю, амортизируется постоянной. Как это относится к deque? Как вставки в верхней и нижней части дека амортизируются постоянными. У меня создалось впечатление, что он должен быть постоянным O (1). Я знаю, что дека состоит из кусков памяти.

Answer 1

Обычная реализация deque в основном представляет собой вектор указателей на узлы фиксированного размера.

Выделение узла фиксированного размера, очевидно, имеет постоянную сложность, поэтому его довольно легко обрабатывать - вы просто амортизируете затраты на выделение одного узла по количеству элементов в этом узле, чтобы получить постоянную сложность для каждого.

Вектор указательной части - это то, что (немного) более интересно. Когда мы выделяем достаточно узлы фиксированного размера, чтобы вектор указателей был заполнен, нам нужно увеличить размер вектора. Например, std::vector, нам нужно скопировать его содержимое на вновь выделенный вектор, поэтому его рост должен следовать геометрической (а не арифметической) прогрессии. Это означает, что у нас больше указателей на копирование, мы делаем копирование все реже и реже, поэтому общее время, затрачиваемое на копирование указателей, остается постоянным.

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

Answer 2

The (профанного) ответ лежит в containers.requirements.general, 23.2.1/2:

Все требования сложности в настоящем пункте изложены исключительно в по количеству операций на содержащиеся объекты.

Перераспределение массива указателей, следовательно, не покрывается гарантией сложности стандарта и может занимать сколь угодно долго. Как упоминалось ранее, он, вероятно, добавляет амортизированные постоянные накладные расходы для каждого вызова push_front()/push_back() (или эквивалентного модификатора) в любой «нормальной» реализации. Однако я бы не рекомендовал использовать deque в RT-критическом коде. Как правило, в сценарии RT вы не хотите иметь неограниченные очереди или стеки (которые в C++ по умолчанию используют deque в качестве базового контейнера) в любом случае, ни распределение памяти, которое может потерпеть неудачу, так что вы, скорее всего, будете использовать предварительно выделенное кольцо буфер (например, Boost's circular_buffer).