CODEWITHSUNDEEP
c++vectorstldynamic-memory-allocation
abhinav1602
abhinav1602

Reputation: 1290

Dynamic memory allocation in Vector

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

Upvotes: 2

Views: 3124

Answers (3)

Andre Kampling
Andre Kampling

Reputation: 5630

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.

Upvotes: 5

Daniel Jour
Daniel Jour

Reputation: 16156

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.

Upvotes: 1

Serge Ballesta
Serge Ballesta

Reputation: 149175

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.

Upvotes: 0

Related Questions