Dynamic memory allocation in Vector

Question

I have a doubt regarding memory allocation in vector(STL - C++). As far as I know, its capacity gets doubled dynamically every time the size of vector gets equal to its capacity. If this is the case, how come the allocation be continuous? How does it still allow to use the [] access operator for O(1) access just like arrays? Can anyone explain this behavior? (List also has dynamic memory allocation but we cannot access its elements using [] access operator, how is it still possible with vector? )

#include<iostream>
#include<vector>
using namespace std;

int main() {
    // your code goes here
    vector<int> v;

    for(int i=0;i<10;i++){
        v.push_back(i);
        cout<<v.size()<<" "<<v.capacity()<<" "<<"\n";
    }

    return 0;
}

Output:

1 1
2 2
3 4
4 4
5 8
6 8
7 8
8 8
9 16
10 16

The vector moves the elements it contains into the new buffer. — StoryTeller - Unslander Monica, Jun 13 '17 at 07:16
The capacity doesn't *have* to get doubled. How the vector increases its capacity is up to the implementation. — Some programmer dude, Jun 13 '17 at 07:16
@Someprogrammerdude but it has to be a amortized constant push_back. — , Jun 13 '17 at 07:23
@manni66 - You can get that with a 50% increase. It's left to the implementation for a reason. — StoryTeller - Unslander Monica, Jun 13 '17 at 07:25
This will give you an help understanding why it works: https://mortoray.com/2014/08/22/the-amortized-cost-of-vector-insert-is-3/ — Davide Spataro, Jun 13 '17 at 07:28
When the vector reaches the max capacity, it will allocate new memory large enough to accommodate twice the number of elements already existing in the Vector. After that, it moves/copies the old elements in the new memory area and frees the old. — AdrianRK, Jun 13 '17 at 07:32

Andre Kampling · Answer 1 · 2017-06-15T16:22:31.497

As far as I know, its capacity gets doubled dynamically every time the size of vector gets equal to its capacity.

It does not need to double like in your case, it's implementation defined. So it may differ if you use another compiler.

If this is the case, how come the allocation be continuous?

If there is no more continuous memory which the vector could allocate, the vector has to move it's data to a new continuous memory block which meets it's size requirements. The old block will be marked as free, so that other can use it.

How does it still allow to use the [] access operator for O(1) access just like arrays?

Because of the facts said before the access will be possible with the [] operator or a pointer + offset. The access to the data will be O(1).

List also has dynamic memory allocation but we cannot access its elements using [] access operator, how is it still possible with vector?

A list (std::list for example) is totally different from a std::vector. In the case of a C++ std::list it saves nodes with data, a pointer to the next node and a pointer the previous node (double-linked list). So you have to walk through the list to get one specific node you want. Vectors work like said above.

The `std::list` in C++ is implemented as double-linked list as said [here](http://www.cplusplus.com/reference/list/list/): `List containers are implemented as doubly-linked lists; Doubly linked lists can store each of the elements they contain in different and unrelated storage locations.` — Andre Kampling, Jun 13 '17 at 07:49
You are write, I was thinking of std::dequeue. I've deleted my (wrong) previous comment and will delete this one in a while... — Serge Ballesta, Jun 13 '17 at 07:54
Hi @Abhinav1602 if this or any answer has solved your question please consider [accepting it](https://meta.stackexchange.com/q/5234/179419) by clicking the check-mark. This indicates to the wider community that you've found a solution and gives some reputation to both the answerer and yourself. There is no obligation to do this. — Andre Kampling, Jul 09 '17 at 09:45

Daniel Jour · Answer 2 · 2017-06-13T07:47:49.837

The vector has to store the objects in one continuous memory area. Thus when it needs to increase its capacity, it has to allocate a new (larger) memory area (or expand the one it already has, if that's possible), and either copy or move the objects from the "old, small" area to the newly allocated one.

This can be made apparent by using a class with a copy/move constructor with some side effect (ideone link):

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

#define V(p) static_cast<void const*>(p)

struct Thing {
    Thing() {}
    Thing(Thing const & t) {
        cout << "Copy " << V(&t) << " to " << V(this) << endl;
    }
    Thing(Thing && t) /* noexcept */ {
        cout << "Move " << V(&t) << " to " << V(this) << endl;
    }
};

int main() {
    vector<Thing> things;
    for (int i = 0; i < 10; ++i) {
        cout << "Have " << things.size() << " (capacity " << things.capacity()
            << "), adding another:\n";
        things.emplace_back();
    }
}

This will lead to output similar to

[..]
Have 2 (capacity 2), adding another:
Move 0x2b652d9ccc50 to 0x2b652d9ccc30
Move 0x2b652d9ccc51 to 0x2b652d9ccc31
Have 3 (capacity 4), adding another:
Have 4 (capacity 4), adding another:
Move 0x2b652d9ccc30 to 0x2b652d9ccc50
Move 0x2b652d9ccc31 to 0x2b652d9ccc51
Move 0x2b652d9ccc32 to 0x2b652d9ccc52
Move 0x2b652d9ccc33 to 0x2b652d9ccc53
[..]

This shows that, when adding a third object to the vector, the two objects it already contains are moved from one continuous area (look at the by 1 (sizeof(Thing)) increasing addresses to another continuous area. Finally, when adding the fifth object, you can see that the third object was indeed placed directly after the second.

When does it move and when copy? The move constructor is considered when it is marked as noexcept (or the compiler can deduce that). Otherwise, if it would be allowed to throw, the vector could end up in a state where some part of its objects are in the new memory area, but the rest is still in the old one.

score 0 · Answer 3 · answered Jun 13 '17 at 07:43

The question should be considered at 2 different levels.

From a standard point of view, it is required to provided a continuous storage to allow the programmer to use the address of its first element as the address of the first element of an array. And it is required to let its capacity grow when you add new elements by reallocation still keeping previous elements - but their address may change.

From an implementation point of view, it can try to extend the allocated memory in place and, if it cannot, allocate a brand new piece of memory and move or copy construct existing elements in the new allocated memory zone. The size increase is not specified by the standard and is left to the implementation. But you are right, doubling allocated size on each time is the common usage.

Dynamic memory allocation in Vector

3 Answers3