c++ Vector, what happens whenever it expands/reallocate on stack?

Question

I'm new to C++ and I'm using the vector class on my project. I found it quite useful because I can have an array that automatically reallocates whenever it is necessary (ie, if I want to push_back an item and the vector has reached it's maximum capacity, it reallocates itself asking more memory space to the OS), so access to an element of the vector is very quick (it's not like a list, that to reach the "n-th" element I must go through the "n" first elements).

I found this question very useful, because their answers explained perfectly how the "memory allocator" works when I want to store my vector on the heap/stack:

[1] vector<Type> vect;
[2] vector<Type> *vect = new vector<Type>;
[3] vector<Type*> vect;

However, a doubt is bugging me for a while, and I can't find its answer: Whenever I construct a vector and begin pushing a lot of items in, it would reach a moment when the vector would be full, so to continue growing it would need to reallocate, copy itself to a new location and then continue pushing_back items (obviously, this reallocation it's hidden on the implementation of the class, so it is completely transparent to me)

Fine, if I have created the vector on the heap [2], I have no troubles imagining what may be happening: class vector calls malloc, acquires new space and then copy itself into the new memory and finally deletes the old memory calling free.

However, a veil hides what is happening when I construct a vector on the stack [1]: What does it happens when the vector must reallocate? AFAIK, whenever on C/C++ you enter a new function, the computer would look at the declaration of variables and then expand the stack to get the necessary space to put these variables, but you can't allocate more space on the stack when the function is already running. How does the class vector solve this problem?

Answer 1

You wrote

[...] copy itself to a new location [...]

which is not the way a vector works. The vector data is copied to a new location, not the vector itself.

My answer should give you an idea of how a vector is designed.

The common std::vector layout*

Note: The std::allocator is actually likely to be an empty class and std::vector will probably not contain an instance of this class. This may not be true for an arbitrary allocator.

In most implementations it consists of three pointers where

• begin points to the start of the data memory of the vector on the heap (always on the heap if not nullptr)
• end points one memory location past the last element of the vector data -> size() == end-begin
• capacity points on memory location past the last element of the vector memory -> capacity() == capacity-begin

A vector on the stack

We declare a variable of type std::vector<T,A> where T is any type and A is an allocator type for T (i.e. std::allocator<T>).

std::vector<T, A> vect1;

How does this look like in memory?

As we see: Nothing happens on the heap but the variable occupies the memory that is necessary for all of its members on the stack. There it is and it will stay there until vect1 goes out of scope, since vect1 is just an object like any other object of type double, int or whatever. It will sit there on its stack position and wait to get destroyed, regardless of how much memory it handles itself on the heap.

The pointers of vect1 do not point anywhere, since the vector is empty.

A vector on the heap

Now we need a pointer to a vector and use some dynamic heap allocation to create the vector.

std::vector<T, A> * vp = new std::vector<T, A>;

Let's again look at the memory.

We have our vp variable on the stack and our vector is on the heap now. Again the vector itself will not move on the heap since its size is constant. Only the pointers (begin, end, capacity) will move to follow the data position in memory if a reallocation takes place. Let's have a look at that.

Pushing elements to a vector

Now we can start pushing elements to a vector. Let's look at vect1.

T a;
vect1.push_back(a);

The variable vect1 is still where it has been but memory on the heap was allocated to contain one element of T.

What happens if we add one further element?

vect1.push_back(a);

• The space allocated on the heap for the data elements will not be enough (since it is only one memory positions, yet).
• A new memory block will be allocated for two elements
• The first element will be copied/moved to the new storage.
• The old memory will be deallocated.

We see: The new memory location is different.

To have additional insight let's look at the situation if we destroy the last element.

vect1.pop_back();

The memory allocated won't change but the last element will have its destructor called and the end pointer moves one position down.

As you can see: capacity() == capacity-begin == 2 while size() == end-begin == 1

Answer 2

The vector object may well be instiantiated on the stack but the data within the vector will be on the heap.

(The trivial class class foo {int* data;}; has this characteristic)

Answer 3

The way you construct your vector (stack or heap) doesn't matter for this.

See the documentation for std::vector

Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it.

When a vector "grows", the vector object doesn't grow, only the internal dynamic array changes.

As for its implementation, you can look at GCC's vector implementation.

To keep it simple, it declares vector as a class with one protected member, of type _Vector_impl.

As you can see, it is declared as a structure that contains three pointers :

• One that points at the beginning of the storage (and the beginning of the data)
• One that points at the end of the data
• One for the end of the storage

Answer 4

You are essentially asking about the implementation details of a vector. The C++ Standard does not define how a vector is to be implemented -- it only defines what a vector should do and what operations are required to be implemented. Nobody can tell you with 100% accuracy what happens when a vector is reallocated, because every compiler is theoretically different.

That being said, it is not difficult to understand how a vector is typically implemented. The vector itself is simply a data structure which has a pointer to the actual data stored "in" the vector. Something along these lines:

template <typename Val> class vector
{
public:
  void push_back (const Val& val);
private:
  Val* mData;
}

The above is obviously psudocode, but you get the idea. When a vector is allocated on the stack (or on the heap):

vector<int> v;
v.push_back (42);

The memory might end up looking like this:

+=======+        
| v     |
+=======+       +=======+
| mData | --->  |  42   |
+=======+       +=======+

When you push_back to a full vector, the data will be reallocated:

+=======+        
| v     |
+=======+       +=======+
| mData | --->  |  42   |
+=======+       +-------+
                |  43   |
                +-------+
                |  44   |
                +-------+
                |  45   |
                +=======+

...and the vector's pointer to the new data will now point there.

Answer 5

you also can reserve to reserve anticipated size,

vect.reserve(10000);

this will reserve 10000 object space of the type used

Answer 6

A vector is not an array of elements, or the memory used to store such.

A vector manages an array of elements, the memory for which it allocates, de-allocates, shrinks and grows as required.

Your choice of how you allocate the vector itself has no connection to the vector's own decisions about how and where to allocate the memory it manages for you.

I don't want to discourage your interest in how the vector works internally (it's both interesting and useful), but ... the whole point of writing classes and documenting them is that you only need to understand the interface, not the implementation.

Answer 7

If you make some growing vector, from empty, to some size, will be using doubling strategy, and most of the time reallocation, in this example using integer from 1 to 10000, and clang (std=2a -O3) will get this, this is just for fun, showing the importance of using reserve. vector::begin() point to beginning of actual array, and vector::capacity show actual capacity. In the other hand, iterator invalidated is showed.

std::vector<int> my_vec;
auto it=my_vec.begin();
for (int i=0;i<10000;++i) {
    auto cap=my_vec.capacity();
    my_vec.push_back(i);
    if(it!=my_vec.begin()) {
        std::cout<<"it!=my_vec.begin() :";
        it=my_vec.begin();
    }
    if(cap!=my_vec.capacity())std::cout<<my_vec.capacity()<<'\n';
}

This produce the following result:

it!=my_vec.begin() :1
it!=my_vec.begin() :2
it!=my_vec.begin() :4
it!=my_vec.begin() :8
it!=my_vec.begin() :16
it!=my_vec.begin() :32
it!=my_vec.begin() :64
it!=my_vec.begin() :128
it!=my_vec.begin() :256
it!=my_vec.begin() :512
it!=my_vec.begin() :1024
it!=my_vec.begin() :2048
it!=my_vec.begin() :4096
it!=my_vec.begin() :8192
it!=my_vec.begin() :16384