Rohit Walavalkar Rohit Walavalkar - 8 days ago 5
C++ Question

size of 2 dimensional vector

I have been trying to figure out the size of 2 dimensional vector and not able to figure out entirely.

The test program that I have written is as below.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
vector<int> one(1);
vector < vector<int> > two(1, vector <int>(1));

return 0;
}


Memory allocation when I check with the help of valgrind is confusing me. After executing the first statement in the main block, I get the below output.

==19882== still reachable: 4 (+4) bytes in 1 (+1) blocks


So far so good. But after running the next statement I get the below log.

==19882== still reachable: 32 (+28) bytes in 3 (+2) blocks


Now this is confusing, I don't know how to justify the 28 bytes allocated.
If I change the second line as below

vector < vector<int> > two(1, vector <int>(0));


I get the below log

==19882== still reachable: 32 (+24) bytes in 3 (+1) blocks


Kindly help in understanding how the memory is allocated.

Answer

tl;dr

The first case just shows the allocation for the (int) storage managed by the vector. The second shows both the inner vector's int storage, and the storage for the inner vector object itself.


So it's telling you this

vector<int> one(1);

allocates one block of 4 bytes.

It doesn't tell you about the automatic storage for the vector object itself, only the dynamic storage for the single integer: assuming sizeof(int)==4, this seems pretty reasonable.

Next it tells you this:

vector < vector<int> > two(1, vector <int>(1));

allocates two more blocks of 28 bytes in total.

Now, one of those blocks will contain the dynamic storage for the vector<int> - remember the previous instance was an automatic local - and the other block will contain the dynamic storage for the nested vector's single integer.

We can assume the second (single integer) allocation is a single block of 4 bytes, as it was last time. So, the dynamically-allocated vector<int> itself is taking 24 bytes in another single block.

Is 24 bytes a reasonable size for a std::vector instance? That could easily be

template <typename T> class vector {
    T* begin;
    size_t used;
    size_t allocated;
};

on a platform with 64-bit pointers and size_t. This assumes a stateless allocator, which is probably right.