2D vector vs 1D vector

Question

In C++11, how does a 2D vector against 1D vector in terms of time?
In the 2D vector given, all the inner vectors are of the same size.

Ex:

std::vector<std::vector<int>> X{10, std::vector<int>(4)};

vs

std::vector<int> Y(40);

Which avatar of the vector would perform better when the elements are randomly accessed?

Answer 1

A single std::vector is inherently simpler, it's just a contiguous block of memory stored somewhere.

A std::vector of std::vector has more overhead but it's also more powerful (since each inner vector can be of different size, for example).

Random access performance should be benchmarked thoroughly for your specific pattern of usage but the main difference is that:

• with single vector you just compute size_t index = x + y*WIDTH and access the element
• with nested vector you have two levels of indirection, first you must obtain the memory containing the inner vector, then you must obtain the memory of the data of the inner vector.