Why not implement C ++ std :: vector :: pop_front () by moving the pointer to vector [0]?

Question

Why is it impossible to implement pop_front() for C ++ vectors by simply moving the pointer contained in the name of the vector one place? Thus, in the vector containing the array foo , foo is a pointer to foo[0] , so pop_front() will make the pointer foo = foo[1] , and the bracket operator will just do the normal math of the pointer. This has something to do with how C ++ keeps track of the memory you are using, why, when does it allocate space for an array?

This is similar to other questions that I saw about why std::vector does not have the pop_front() function, I agree, but I do not ask anyone about why you cannot move the pointer.

Answer 1

vector cannot free its memory if it does.

Typically, you want the overhead of a vector object to be small. This means that you save only three elements: a pointer to the first element, capacity and length.

To implement what you are proposing, for each vector ever ( all ) an additional member variable is required: the offset from the start pointer where the null element is located. Otherwise, the memory cannot be freed, since the original descriptor to it would be lost.

This is a compromise, but overall, the memory consumption of an object, which can have millions of instances, is more valuable than the corner case when you do the absolute worst, which you can do in terms of vector performance.

Answer 2

Because the developers want to optimize the size of the vector. Usually they use 3 pointers, one for the start, one for the tank (highlighted end) and one for the end.

Doing what you need adds 4 more bytes to each vector (and there are many of them in a C ++ program) is very small: the vector contract should be fast when discarding new elements, deleting and inserting "non-hazardous" operations and their performance is less than class size.

Answer 3

I started typing a detailed answer explaining how memory is allocated and freed, but after entering all of this, I realized that memory problems alone do not justify why pop_front does not exist, as other answers are suggested here.

Having pop_front in a vector where the extra cost is another pointer is justified in most cases. The problem, in my opinion, is push_front . If the container has pop_front , then it must also have push_front , otherwise the container will not be negotiated. push_front definitely expensive for a vector container (unless you compare your push es with your pop , which is not a good design). Without push_front vector does waste memory if many pop_front operations are pop_front without the push_front function.

Now the need for pop_front and push_front exists for a container that looks like a vector (permanent temporary random access), so deque exists.

Answer 4

You could, but that would complicate the implementation a bit and add an overhead pointer to the font size (so that it can track the actual location address). It's worth it? Sometimes. First, consider other structures that might better handle your use (perhaps deque?).

Answer 5

You can do this, but vector is for a simple container with a constant search for the time index and push / pop from the end. Doing what you propose will complicate the implementation, as it will have to keep track of the highlighted start and the “current” start. Not to mention the fact that you still cannot guarantee a constant time setting in the front, but sometimes you can get it.

If you need a container with constant insertion and deletion in time and back, for what exactly deque , there is no need to change vector to process it.

Answer 6

You can use std::deque instead of std::vector . This is a bidirectional queue with also vector access elements. It implements both front and rear push / pop.

http://www.cplusplus.com/reference/stl/deque/

Answer 7

Another drawback of your proposal is that you will waste memory space, because after the shift you will not be able to use the ones to the left of the array. The more you execute pop_front() , the more you will spend until the vector is destroyed.