How is dynamic memory managed in std::vector?

Question

How does std::vector implement the management of the changing number of elements: Does it use realloc() function, or does it use a linked list?

Thanks.

Answer 1

The memory managed by std::vector is guaranteed to be continuous, such that you can treat &vec[0] as a pointer to the beginning of a dynamic array.

Given this, how it actually manages it's reallocations is implementation specific.

Answer 2

One of the hard-and-fast rules of vectors is that the data will be stored in one contiguous block of memory.

That way you know you can theoretically do this:

const Widget* pWidgetArrayBegin = &(vecWidget[0]);

You can then pass pWidgetArrayBegin into functions that want an array as a parameter.

The only exception to this is the std::vector<bool> specialisation. It actually isn't bools at all, but that's another story.

So the std::vector will reallocate the memory, and will not use a linked list.

This means you can shoot yourself in the foot by doing this:

Widget* pInteresting = &(vecWidget.back());
vecWidget.push_back(anotherWidget);

For all you know, the push_back call could have caused the vector to shift its contents to an entirely new block of memory, invalidating pInteresting.

Answer 3

std::vector stored data in contiguous memory blocks.

Suppose we declare a vector as

std::vector intvect;

So initially a memory of x elements will be created . Here x is implementation depended.

If user is inserting more than x elements than a new memory block will be created of 2x (twice the size)elements and initial vector is copied into this memory block.

Thats why it is always recommended to reserve memory for vector by calling reserve function.

intvect.reserve(100);

so as to avoid deletion and copying of vector data.

Answer 4

It uses the allocator that was given to it as the second template parameter. Like this then. Say it is in push_back, let t be the object to be pushed:

...
if(_size == _capacity) { // size is never greater than capacity
    // reallocate
    T * _begin1 = alloc.allocate(_capacity * 2, 0);
    size_type _capacity1 = _capacity * 2;

    // copy construct items (copy over from old location).
    for(size_type i=0; i<_size; i++)
        alloc.construct(_begin1 + i, *(_begin + i));
    alloc.construct(_begin1 + _size, t);

    // destruct old ones. dtors are not allowed to throw here. 
    // if they do, behavior is undefined (17.4.3.6/2)
    for(size_type i=0;i<_size; i++)
        alloc.destroy(_begin + i);
    alloc.deallocate(_begin, _capacity);

    // set new stuff, after everything worked out nicely
    _begin = _begin1;
    _capacity = _capacity1;
} else { // size less than capacity
    // tell the allocator to allocate an object at the right
    // memory place previously allocated
    alloc.construct(_begin + _size, t);
}
_size++; // now, we have one more item in us
...

Something like that. The allocator will care about allocating memory. It keeps the steps of allocating memory and constructing object into that memory apart, so it can preallocate memory, but not yet call constructors. During reallocate, the vector has to take care about exceptions being thrown by copy constructors, which complicates the matter somewhat. The above is just some pseudo code snippet - not real code and probably contains many bugs. If the size gets above the capacity, it asks the allocator to allocate a new greater block of memory, if not then it just constructs at the previously allocated space.

The exact semantics of this depend on the allocator. If it is the standard allocator, construct will do

new ((void*)(_start + n)) T(t); // known as "placement new"

And the allocate allocate will just get memory from ::operator new. destroy would call the destructor

(_start + n)->~T();

All that is abstracted behind the allocator and the vector just uses it. A stack or pooling allocator could work completely different. Some key points about vector that are important

• After a call to reserve(N), you can have up to N items inserted into your vector without risking a reallocation. Until then, that is as long as size() <= capacity(), references and iterators to elements of it remain valid.
• Vector's storage is contiguous. You can treat &v[0] as a buffer containing as many elements you have currently in your vector.