Сложность stl deque :: insert ()

Question

Я узнал всю сложность deque::insert() из стандарта C ++ 2003 (глава 23.2.1.3) следующим образом:

В худшем случае для вставки одного элемента в деку требуется линейное время в минимуме расстояния от точки вставки до начала дека и расстояния от точки вставки до конца дек.

Я всегда понимаю реализацию stl deque как коллекцию фрагментов памяти. Следовательно, вставка будет влиять только на элементы в том же фрагменте памяти, что и позиция вставки. У меня вопрос: что означает стандарт под «линейным по минимуму расстояния от точки вставки до начала deque и расстояния от точки вставки до конца deque»?

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

Другое предположение может заключаться в том, что, поскольку insert() сделает недействительными все итераторы, deque необходимо обновить все итераторы. Поэтому он линейный.

Answer 1

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

Answer 2

Я думаю, что вам лучше подать диаграмму ... давайте поиграем с искусством ASCII!

Как правило, deque - это массив фрагментов памяти, но все вместе, передний и задний блоки памяти заполнены,Это необходимо, поскольку deque является RandomAccessContainer, и для получения O (1) доступа к любому контейнеру у вас не может быть неограниченного количества контейнеров, из которых можно прочитать размер:

bool size() const { return first.size + (buckets.size()- 2) * SIZE + last.size; }

T& operator[](size_t i) {
  if (i < first.size) { return first[SIZE - i]; }

  size_t const correctedIndex = i - first.size;
  return buckets[correctedIndex / SIZE][correctedIndex % SIZE];
}

Эти операции выполняются O(1) из-за умножения / деления!

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

 // Deque
 0:       ++
 1: ++++++++
 2: ++++++++
 3: ++++++++
 4: +++++

Теперь скажите, что мы хотим вставить индекс 13. Он падает где-то в сегменте с пометкой 2Есть несколько стратегий, о которых мы можем подумать:

• расширение корзины 2 (только)
• введение нового сегмента до или после 2 и перетасовывание только нескольких элементов

Но эти две стратегии нарушили бы инвариант, согласно которому все "внутренние" сегменты имеют одинаковое количество элементов.

Поэтому нам остается перетасовывать элементы вокруг, либо к началу, либо к концу (в зависимости от того, что дешевле), в нашем случае:

 // Deque
 0:      +++
 1: ++++++++
 2: +O++++++
 3: ++++++++
 4: +++++

Обратите внимание, как выросла корзина 0.

Эта случайная последовательность подразумевает, что в худшем случае вы будете двигатьсяполовина элементов: O (N / 2).

deque имеет вставку O (1) либо в начале, либо в конце, потому что это просто вопрос добавления элемента в нужном месте или(если ведро фуll) создание нового сегмента.

Существуют другие контейнеры, которые имеют лучшее поведение вставки / удаления при случайных индексах, основанные на B + Trees .В индексированном дереве B + вы можете вместо «ключа» (или параллельно) вести внутреннее подсчет элементов до определенной позиции.Существуют различные методы, чтобы сделать это эффективно.В конце вы получите контейнер с:

• O (1): пустой, размер
• O (log N): at, insert, erase

Вы можете проверить модуль blist в Python, который реализует элемент, подобный списку Python, поддерживаемый такой структурой.

Answer 3

Ваша гипотеза ... 99,9% верно.Все зависит от того, что является реальной реализацией.Стандарт определяет минимальные требования как для разработчиков (которые не могут претендовать на стандарт, если они не соответствуют спецификациям), так и для пользователей (которые не должны ожидать «лучших результатов» при написании кода, независимого от реализации).

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

Более эффективная реализация не использует один блок, но несколько блоков для перераспределения проблемы «смещения» и выделения памяти в постоянном размере из базовой системы (таким образом, ограничивая перераспределение и фрагментацию).Если вы нацеливаетесь на одну из них, вы можете ожидать лучших результатов, в противном случае вам лучше не предполагать никакой оптимизации структуры.

Answer 4

Линейный по количеству вставленных элементов (копирование конструкции). Плюс, в зависимости от конкретной реализации библиотеки, дополнительное линейное время в зависимости от количества элементов между положением и одним из концов deque. Reference ...