Почему нет push/pop перед вектором?

Question

В C++, STL, у нас есть класс шаблонов <vector>. Мы знаем, что он поддерживает O(1) случайный доступ и модификацию хвоста. Мой вопрос: почему мы не определяем push_front или pop_front в <vector>?

Одно из объяснений состоит в том, что если мы хотим, чтобы элемент push/pop в начале вектора, мы должны перенести каждый элемент в массив на один шаг, и это будет стоить O(n).

Но я думаю, что это не всегда так. Учитывая, что если мы реализуем <vector> с круговым массивом, мы можем достичь O(1) push/pop с фронта и хвоста вектора, не теряя при этом возможности O(1) случайного доступа. Поэтому лично я не могу думать о какой-либо причине, а не только о незначительных накладных расходах, чтобы не реализовывать push_front/pop_front для <vector>. Есть предположения?

Answer 1

Одним из объяснений является то, что если мы хотим, чтобы подтолкнуть/поп-элемент в передней части вектора, мы должны изменить каждый элемент массива на один шаг, и это будет стоить O (п)

Вы абсолютно правы, push_front не имеет возможности быстро запускать, потому что в дополнение к возможному перераспределению все элементы должны быть скопированы по одной позиции. Это дает вам амортизированную производительность O (n) для n объектов, которые разработчики библиотеки не хотели поощрять.

Учитывая, что, если мы реализуем <vector> с круговым массивом

Реализацией вектора с круговым массивом делает его намного труднее осуществить ряд важных гарантий, которые должны быть истинными для вектора. Например, вектор должен гарантировать, что если итератор a указывает на элемент с более низким индексом, чем итератор b, затем a < b. Когда вектор является линейным, сравнение сводится к сравнению адресов элементов, к которым указывают итераторы a и b. При реализации циклического массива нужно учитывать адрес начала координат, который теперь может находиться в середине выделенного блока памяти.

Другой гарантировала, что будет нарушено это:

Когда v является vector<T>, T любого типа, кроме bool и n число между нулем и размером вектора, &v[n] == &v[0] + n идентичность должна быть правдой.

Это не может быть реализовано с помощью круглой матрицы.

Answer 2

У нас уже есть что-то, что вы описываете в STL. Он называется deque.

Как вы писали, на самом деле есть некоторые накладные расходы. Поэтому, если вам нужна эта функциональность, и у вас нет проблем с накладными расходами, используйте deque. Если вы этого не требуете, вам не нужны накладные расходы, поэтому лучше иметь что-то, что позволяет избежать этих накладных расходов, названных vector.

И в качестве дополнения: vector гарантирует, что все его элементы хранятся в смежных местах хранения, поэтому вы можете применить арифметику указателя. Это не касается кругового буфера.

Answer 3

Фактически, это является реалистичным требованием. Насколько мне известно, ничто в стандарте не гарантирует, что вектор не может иметь буфер до элементов (v.prefix_capacity()), равно как после (v.capacity() - v.size()). Это может гарантировать то же время выполнения для v.push_front() и v.push_back(), не требуя затрат для тех, кто его не использует. Кроме того, он может гарантировать O (1) v.pop_front(), хотя и недействительными итераторами. Представляете себе предложение?

В то же время, вы можете создать шаблон в терминах вектора, который (devector?):

• имеет поле pre_capacity_ инициализируется 0 и поглотитель pre_capacity()
• реализует pre_reserve(size_t i), который вызывает как:
  • reserve(capacity() - pre_capacity_ + i)
  • pre_capacity_ += i
• реализует operator[](size_t i) и делегаты v[i + pre_capacity()]
• реализует at(size_t i) и делегатов v.at(i + pre_capacity())
• реализует begin() и делегирует v.begin() + pre_capacity()
• делегаты всех остальных методов vector

Или вы можете просто отслеживайте количество элементов, которые вы нажали/выскочили с фронта :).