Would vector of vectors be contiguous? [duplicate]

问题:

This question already has an answer here:

• std::vector of std::vectors contiguity 4 answers

I need to allocate a vector of rows where row contains a vector of rows. I know that a vector would be contiguous. I wanted to know whether a vector of vectors would also be contiguous. Example code is given below

vector<long> firstRow;

firstRow.push_back(0);

firstRow.push_back(1);

vector<long> secondRow;

secondRow.push_back(0);

secondRow.push_back(1); 

vector< vector < long> > data;

data.push_back(firstRow);

data.push_back(secondRow);

Would the sequence in memory be 0 1 0 1?

回答1:

In short, no. This is what actually happens:

回答2:

As others have said, no: nested vectors are not contiguous (nested arrays are the same, by the way; a statically sized array is an exception).

The way to implement a contiguous array of arrays (and generally any dense matrix) in C++ (and many other languages) is to have a flat array and calculate the indices manually:

typedef std::vector<long> matrix_t;

matrix_t M(width * height);
// Assign to index i, j:
M[i + j * width] = value;

… of course this should be encapsulated appropriately into a class.

回答3:

Nope, use boost::multi_array<long, 2> instead.

回答4:

No. The vectors do not somehow communicate with one another in order to achieve one, large, contiguous storage space as they are added to parent vectors.

In this case, the storage used for the instances of firstRow and secondRow is contiguous, per the spec. However, vectors use heap storage for their elements, and it is very (very) unlikely that the two sub vectors will have, by coincidence, shared a single block for their respective allocations.

Don't confuse your elements (the vectors) with your elements individual allocations. It's those allocations which matter, and in this case you will be hopping around memory traversing them. A vector of vectors is not a good idea from a data locality perspective.

Want one large chunk of memory? Use an array.

回答5:

Considering that vectors tend to automatically re-size themselves, I'd assume that it can't be contiguous.

Sure, the references to the vectors could be contiguous, but the data itself can't all be.

If a vector of vectors were continuous, how would individual vectors re-size themselves?

回答6:

vector< vector < long> > data would hold a pointer to a contiguous array of vector<long> objects. Each of which, in turn, would hold a pointer to a contiguous array of long. But if you expect all longs together, as would be the case with long[10][20], then no, that's not how it works.