What are the Issues with a vector-of-vectors?

Question

I've read that a vector-of-vectors is bad given a fixed 2^nd dimension, but I cannot find a clear explanation of the problems on http://www.stackoverflow.com.

Could someone give an explanation of why using 2D indexing on a single vector is preferable to using a vector-of-vectors for a fixed 2^nd dimension?

Also, I'm assuming that a vector-of-vectors is the preferable data structure for a 2D array with a variable 2^nd dimension? If there is any proof to the contrary I'd love to see that.

Answer 1

For a std::vector the underlying array is dynamically allocated from the heap. If you have e.g. std::vector<std::vector<double>>, then your outer vector would look like

{v1, v2, v3, v4, ... vn}

This looks like each of the inner vectors will be in contiguous memory, and they will, but their underlying arrays will not be contiguous. See the diagram of the memory layout in this post. In other words the you cannot say that

&(v1.back()) + 1 == &(v2.front()) // not necessarily true!

Instead if you used a single vector with striding then you would gain data locality, and it would inherently be more cache friendly as all your data is contiguous.

For the sake of completeness, I would use neither of these methods if your matrix was sparse, as there are more elegant and efficient storage schemes than straight 1D or 2D arrays. Though since you mentioned you have a "fixed 2nd dimension" I will assume that is not the case here.

Answer 2

I shall answer with a simple analogy.

What is "better" in general out of the two things?

1. A telephone book where each entry is a code referring to a different book that you have to find and read to discover someone's telephone number
2. A telephone book that lists people's telephone numbers

Keeping all your data in a single big blob is more simple, more sensible, and easier on your computer's cache. A vector with N vectors inside it is much more operationally complex (remember, each of those requires a dynamic allocation and size management operations!); one vector is, well, one vector. You haven't multiplied the workload by N.

The only downside really is that to simulate 2D array access with a 1D underlying data store, you need to write a facade. Fortunately, this is very easy.

Now for the subjective part: on balance I'd say that it's worthwhile unless you're really in a rush and your code quality doesn't particularly matter.