CODEWITHSUNDEEP
c++vectorpush-back
sancho.s ReinstateMonicaCellio
sancho.s ReinstateMonicaCellio

Reputation: 15561

Memory taken by a vector of vectors

What is the expected difference (if any) in memory taken by vvint1 and vvint2? Is vitest1 copied into a new memory position each time a push_back takes place? Is vitest2 copied into a new memory position each time a push_back takes place?

typedef vector<int> vint_t;
typedef vector<vint_t> vvint_t;
size_t nvec = 2;
size_t nvvec = 3;
vvint_t vvint1(nvvec), vvint2(nvvec);
vint_t vitest2(nvec, 1);
for ( j = 0; j < nvvec; j++ ) {
    vint_t vitest1(nvec, 2);
    vvint1.push_back(vitest1);
    vvint2.push_back(vitest2);
}

Upvotes: 0

Views: 152

Answers (2)

numzero
numzero

Reputation: 2057

vvint1 and vvint2 memory requirements are:

  1. (on stack, in the example) sizeof(vector<vector<int>>) for the objects themselves, which is the same (vector is 2–3 pointers usually, regardless of the inner type);
  2. (on heap) 2 * nvvec * sizeof(vector<int>) for the contents (nvvec initially and nvvec push_back-ed in the loop); again, that’s the same for vvint1 and vvint2;
  3. (on heap) contents of each vector stored in these vectors. Since vectors don’t share memory, and you store them by value, nvec * nnvec * sizeof(int). Again, the same.

So the overall requirements are the same: sizeof(vector<vector<int>>) + nvvec * sizeof(vector<int>) + nvec * nnvec * sizeof(int)

Plain vector<int> would take less space ofc as item 2 wouldn’t apply. But what is more important is that in vvint_t, inner vectors may be of different lengths, and resizing any inner vector doesn’t affect others. But that adds complexity, so unless you really need that, it’s simpler to use flat vector and calculate index; imaging libraries do it that way.

Regarding second part, both vitests are copied on each push_back. But since C++11, you can write vvint1.push_back(std::move(vitest1)); (or vvint1.emplace_back(std::move(vitest1));) to move instead. For vectors that means the newly-constructed vector takes ownership of vitest1 contents without copying it (so vitest1 becomes empty). That doesn’t change memory requirements but reduces allocations as the space allocated by vitest (at construction) would be reused instead of being freed (at destruction, at end of each iteration).

Upvotes: 0

Tommy
Tommy

Reputation: 100632

Both vvint1 and vvint2 are initially created with nvvec = 3 default-constructed members (i.e. empty vectors of int).

push_back always either copies or moves, but in this case you're not supplying rvalue references so you'll get copies. Look into std::move for more on that.

You're pushing the same number of things to both vectors. Therefore both vvint1 and vvint2 will end up being the same size.

Upvotes: 1

Related Questions