C++ Vector, What Happens Whenever It Expands/Reallocate on Stack

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

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

How does std::vector reallocates every time an item is inserted using a loop?

std::vector does not reallocate every time an element is added. It reallocates when it runs out of capacity. And when it reallocates, it doesn't allocate space for just 1 more element. It typically allocates by some factor of the the current capacity. I believe VS uses a factor of 1.5, and some others use 2. It has to do this in order to ensure that push_back has amortized O(1) complexity, which is a requirement of the standard.

If you know for certain exactly how many elements you are going to add to the vector over its lifetime, it is still a good idea to reserve though, imo. Some might consider that premature optimization. But it is such a simple thing to do, I consider not doing it to be premature pessimization.

vector reallocation C++

Bear in mind that if you measure memory usage based on "top" or "Task Manager", the memory "freed" is not necessarily actually "made to go away". Most modern heap managers don't free the memory all the way down to the OS level, since the expectation is that memory allocated once will be needed again. Only once the amount freed reaches a certain limit (of a contiguous range, so if there are small "islands" of still used memory in the sea of freed memory, it can't be freed as one block and will most likely stay with your application "forever").

There is nothing much you can do about this, just live with it. If you know beforehand how much memory you need, use reserve() to reserve it. If you don't, let it grow by itself. The memory is freed, it's just not given back to the actual OS as "free memory", it sits in the heap of your application. If there is low memory in the overall system, the memory that isn't used will be swapped out and other, more useful things will be loaded into memory in its place, so it's not "occupied and can never be used for anything else". (Of course, if you have little islands of used memory that gets accessed every now and again, then it's likely that the memory can't be reused).

When vectors are allocated, do they use memory on the heap or the stack?

vector<Type> vect;

will allocate the vector, i.e. the header info, on the stack, but the elements on the free store ("heap").

vector<Type> *vect = new vector<Type>;

allocates everything on the free store.

vector<Type*> vect;

will allocate the vector on the stack and a bunch of pointers on the free store, but where these point is determined by how you use them (you could point element 0 to the free store and element 1 to the stack, say).

When does a std::vector reallocate its memory array?

From C++ standard 23.2.4.2:

size_type capacity() const;

Returns: The total number of elements that the vector can hold without requiring reallocation.

Also from Standard

Notes: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the
sequence. It is guaranteed that no reallocation takes place during insertions that happen after a call to
reserve() until the time when an insertion would make the size of the vector greater than the size
specified in the most recent call to reserve().

So yes, you can be sure.

Edit: As @Bo Persson mentioned there is a catch. Standard doesn't say anything if we never call reserve() . However in practice it works well, because no implementation will care to remember if you called reserve, or not. I believe that this is bug. And as @Martin mentioned in his answer in C++0x draft it is corrected.

How do I make a vector reallocate with out calling a destructor?

There is a bigger problem here. Since you have a destructor, you will also need to properly implement an assignment operator and copy constructor. Then your code will work fine as is. Google c++ and The Rule of Three. As mentioned, smart pointers could eliminate the need for the big three since they will handle copying and deleting for you behind the scenes.

Does std::vector::resize() ever reallocate when new size is smaller than current size?

No, resizeing to a smaller size will never reallocate.

In case the container shrinks, all iterators, pointers and references to elements that have not been removed remain valid after the resize and refer to the same elements they were referring to before the call.

(From here)

Given that, we can be sure that a reallocation cannot have happened.

---

Related Topics