0

Does the initialization of a vector of vectors this way copy the vectors n times?

const int n, m; 
vector<vector<int>> v(n, vector<int>(m));

Is the initialization efficient, or can we make it better?

anatolyg
  • 26,506
  • 9
  • 60
  • 134
asmbaty
  • 436
  • 2
  • 11
  • How are you going to initialize the vector more efficiently? – Vlad from Moscow Oct 23 '19 at 16:36
  • @VladfromMoscow The temporary `vector(m)` causes one unnecessary heap allocation, we could get rid of it somehow. – HolyBlackCat Oct 23 '19 at 16:39
  • IMO, this is efficient enough for most purposes. If you find this to be a performance bottleneck, only then do you have worry about finding an alternative. In the mean time, move on to more important things -- clean code, correct code, maintainable code. – R Sahu Oct 23 '19 at 16:44

1 Answers1

4

Does the initialization of a vector of vectors this way copy the vectors n times?

Yes. It is going to make N copies of vector<int>(m) so you'll have N + 1 allocations.

Is the initialization efficient, or can we make it better?

It is pretty good, but by no means is it the best you can do. For raw performance what you want to do is use a single vector and pretend that it is 2d. That would look like

std::vector<int> v(rows * cols);
v[row_index * cols + col_index] = 5; // same as 2d v[row_index][col_index] = 5;

This does a single allocation and you are guaranteed that all of the elements are in the same block of memory. A 2d vector does not give you that guarantee.

To make life easier you can encapsulate that into a class so you can overload the [] operator to make it act like a 2d structure. This is done by overloading the operator[] for the class and having it return proxy type that holds a reference to the row of the vector and you overload the operator[] for the proxy type to return a reference to the col in that refereed to vector.

NathanOliver
  • 171,901
  • 28
  • 288
  • 402