Would vector of vectors be contiguous?

Question

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?

Have a look at this http://stackoverflow.com/questions/10898007/stdvector-of-stdvectors-continuity — Kakalokia, Oct 21 '13 at 20:55
Why do you care if they are contiguous? This might be an XY Problem. — John Dibling, Oct 21 '13 at 20:55
@user1150989: each of the two subarrays is contiguous (i.e. if you do `(&firstRow[0])[1]` it's guaranteed that you get 1), but it's not guaranteed (and in general it's not true) that the memory allocated for the two rows will be contiguous. — Matteo Italia, Oct 21 '13 at 20:56

score 19 · Accepted Answer · answered Oct 21 '13 at 21:03

19

In short, no. This is what actually happens:

enter image description here

answered Oct 21 '13 at 21:03

Todd Li

3,209
21
19

score 5 · Answer 2 · answered Oct 21 '13 at 21:00

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.

score 3 · Answer 3 · answered Oct 21 '13 at 21:03

3

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

answered Oct 21 '13 at 21:03

user541686

205,094
128
528
886

score 1 · Answer 4 · answered Oct 21 '13 at 20:54

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.

Thank you. How would you suggest I go about achieving data locality without using malloc and managing it on my own? — user1150989, Oct 21 '13 at 20:57
@user1150989: the low-tech method is to just allocate a vector (width*height) long and do the math yourself with it (i.e. to access the element (x,y) you do `vector[y*width+x]`). — Matteo Italia, Oct 21 '13 at 21:21

score 0 · Answer 5 · answered Oct 21 '13 at 20:54

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?

score 0 · Answer 6 · answered Oct 21 '13 at 20:55

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.

Would vector of vectors be contiguous?

6 Answers6

Linked