Почему в С++ нет метода pop_front
std::vector
?
Почему в С++ std::vector нет метода pop_front?
Ответы (8)
Потому что std::vector
не имеет особой функции вставки элементов спереди, в отличие от некоторых других контейнеров. Функциональность, предоставляемая каждым контейнером, имеет смысл для этого контейнера.
Вероятно, вам следует использовать std::deque
, который явно хорош при вставке спереди и сзади.
Ознакомьтесь с этой схемой.
Хотя это неэффективно для больших векторов, следующее эквивалентно pop_front()
для std::vector
vec.erase(vec.begin());
Как указано в других ответах, std::vector
не предназначен для удаления первого элемента и потребует перемещения/копирования всех оставшихся элементов. В зависимости от конкретного варианта использования может быть удобно рассмотреть другие контейнеры.
vector обычно реализуется примерно так:
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» должен будет скопировать все T из задней части вектора в переднюю часть вектора, а это сравнительно медленно. поэтому они решили оставить его вне стандарта.
то, что вы хотите, это что-то вроде этого:
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 не работает таким образом? я предполагаю, что это был вопрос вкуса тех, кто писал стандарт. их цель, вероятно, заключалась в том, чтобы предоставить максимально простой «динамически изменяемый массив», и я думаю, что им это удалось.
Потому что push_back
и pop_back
— это специальные операции для вектора, которые требуют только O(1)
вычислений. Любой другой толчок или толчок занимает O(n)
.
Это не "баг" и не "причуда", это просто свойство векторного контейнера. Если вам нужен быстрый pop_front, подумайте о переходе на другой контейнер.
std::deque<>
, если вам нужен быстрый pop_front()
.
- person ildjarn; 06.04.2011
push_back
, в худшем случае - Theta (n), когда он должен перераспределяться, потому что вы не зарезервировали пространство.
- person Steve Jessop; 06.04.2011
push_back
не всегда нужно перераспределять.
- person Lightness Races in Orbit; 25.11.2012
pop_front
.
- person Lightness Races in Orbit; 24.07.2018
Однако, если вам нужен 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< /а>
template<typename T> void pop_front(std::vector<T>& v) { v.pop_back(); }
, вы не удаляете ожидаемый элемент front
. Я предлагаю поменять местами элементы front
и back
и удалить последний.
- person marchelbling; 02.11.2014
pop_front
в O (1).
- person marchelbling; 02.11.2014
pop_front
за постоянное время.
- person marchelbling; 25.06.2019
Вероятно, потому что это было бы монументально медленно для больших векторов.
pop_front()
для вектора, содержащего 1000 объектов, потребуется 999 operator=()
вызовов.
erase(v.begin())
. Это потому, что векторы не имеют специальных свойств для нажатия в начале, в отличие от нажатия в конце (или выталкивания).
- person orlp; 06.04.2011
Vector выглядит как контейнер стека, у нас есть стек для хранения данных. Так что мы просто pop_back
не pop_front
. Если вы хотите pop_front
, std::list
может быть лучшим выбором для вас. Потому что это двунаправленная структура очереди.
#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);