Where does a std::vector allocate its memory?

Question

Consider the following code snippet:

#include <vector>
using namespace std;

void sub(vector<int>& vec) {
    vec.push_back(5);
}

int main() {
    vector<int> vec(4,0);
    sub(vec);
    return 0;
}

Assuming "vec" has no space left to store the 5 in the "sub" function, where does it allocate new memory?

In the stack frame of the sub function? In that case the 5 would be deleted at the end of the sub function. But the stack frame of the main function can't grow, as the stack frame of the sub function lies on top of the stack at that moment.
Does a std::vector allocate memory for its elements on the heap? But how does it free that heap memory? If it's a local vector on the stack, the stack frame of a function including the vector is deleted in the end without signaling the vector that it will be deleted?

Solution 1

Does a std::vector allocate memory for its elements on the heap?

Yes. Or more accurately it allocates based on the allocator you pass in at construction. You didn't specify one, so you get the default allocator. By default, this will be the heap.

But how does it free that heap memory?

Through its destructor when it goes out of scope. (Note that a pointer to a vector going out of scope won't trigger the destructor). But if you had passed by value to sub you'd construct (and later destruct) a new copy. 5 would then get pushed back onto that copy, the copy would be cleaned up, and the vector in main would be untouched.

Solution 2

All containers in the STL are parameterized with template arguments, usually the last argument is called A or Allocator and defaults to std::allocator<...> where ... represents the type of the value stored within the container.

The Allocator is a class that is used to provide memory and build/destroy the elements in this memory area. It can allocate memory from a pool or directly from the heap, whichever you build the allocator from. By default the std::allocator<T> is a simple wrapper around ::operator new and will thus allocate memory on the heap as you inferred.

The memory is allocated on demand, and is deallocated at the very least when the vector's destructor is called. C++11 introduces shrink_to_fit to release memory sooner too. Finally, when the vector outgrow its current capacity, a new (larger) allocation is made, the objects are moved to it, and the old allocation is released.

As will all local variables, the destructor is called when executed reaches the end of the scope it has been declared into. So, before the function is exited, the vector destructor is called, and only afterward does the stack shrinks and control returns to the caller.

Solution 3

Also note that your vector (vec) is object itself. It resides on the stack and when this object goes out of scope (which is end of main in your case), it is destructed. Memory for elements is allocated during initialization of this object and released with its destruction, which is a lovely example of RAII idiom, since the resource management of elements is tied to the lifespan of vector object.

Comments

[Tom Knapen]

There is absolutely no link between a vector on the heap, and it allocating it's memory on the heap.

[juanchopanza]

The vector isn't on "the heap", whatever that may be. It is in main's stack.

[Tom Knapen]

It doesn't matter wether you allocate a vector on the stack or on the heap, the default implementation will always allocate it's memory on the heap.

[Stefan]

at least that was what I wanted to say. considering I did not say it accurately enough. my fault!

[athos]

I didn't see the cplusplus.com/reference/std/memory/allocator/allocate page mentioned anything about default allocation on heap?