Почему нет метода pop_front в C++ std::vector?

Question

Почему нет pop_front метод в C++ std::vector?

Answer 1

Потому что std::vector не имеет особых особенностей в отношении вставки элементов спереди, в отличие от некоторых других контейнеров. Функциональность, предоставляемая каждым контейнером, имеет смысл для этого контейнера.

Вы, вероятно, должны использовать std::deque, который явно хорош при вставке спереди и сзади.

Проверьте эту схему.

Answer 2

Просто. Просто попробуй:

vec.erase(vec.begin());

Answer 3

Вектор обычно реализуется примерно так:

struct 
{
  T* begin; // points to the first T in the vector
  T* end; // points just after the last T in the vector
  int capacity; // how many Ts of memory were allocated
};

"begin" выполняет двойную функцию как "указатель на первый T в векторе" и "указатель на всю выделенную память". поэтому невозможно "вытолкнуть" элементы с фронта вектора, просто увеличивая "начало" - сделайте это, и у вас больше не будет указателя на память, которую нужно освободить. что бы утечка памяти. поэтому "pop_front" должен был бы скопировать все Ts из задней части вектора в начало вектора, и это сравнительно медленно. поэтому они решили оставить это вне стандарта.

что вы хотите, это что-то вроде этого:

struct 
{
  T* allocated; // points to all the memory we allocated
  T* begin; // points to the first T in the vector
  T* end; // points just after the last T in the vector
  int capacity; // how many Ts of memory were allocated
};

при этом вы можете "pop_front", перемещая "begin" вперед и назад, без риска забыть, какую память освободить позже. почему std::vector не работает таким образом? Я думаю, что это был вопрос вкуса среди тех, кто написал стандарт. Их цель, вероятно, заключалась в том, чтобы предоставить как можно более простой "динамически изменяемый массив", и я думаю, что им это удалось.

Answer 4

Так как push_back а также pop_back специальные операции для вектора, которые требуют только O(1) вычисление. Любые другие push или pop дубли O(n),

Это не "ошибка" или "причуда", это просто свойство векторного контейнера. Если вам нужен быстрый pop_front, подумайте о переходе на другой контейнер.

Answer 5

Однако, если вам нужен pop_front и НЕ волнует индекс элементов в векторе, вы можете сделать что-то вроде pop_front с чем-то вроде

template<typename T>
void pop_front(std::vector<T>& vec)
{
   vec.front() = vec.back();
   vec.pop_back();
}

Дэн Хиггинс тоже об этом говорит: https://youtu.be/oBbGC-sUYVA?t=2m52s

Answer 6

Вероятно, потому что это будет монументально медленно для больших векторов.

pop_front() на вектор, содержащий 1000 объектов, потребуется 999 operator=() звонки.

Answer 7

      #define push_front(v,val) v.insert(v.begin(), 1, val);
#define pop_front(v)  if(!v.empty())v.erase(v.begin());

Вы можете напрямую написать это и использовать это

      push_front(vec,val);
pop_front(vec);

Answer 8

Vector похож на контейнер стека, у нас есть стек для хранения данных. Так что мы просто pop_backне делать. Если ты хочешь pop_front, std::listможет быть лучшим выбором для вас. Потому что это двунаправленная структура очереди.