Is this nested array using stack or heap memory?

Question

Say I have this declaration and use of array nested in a vector

const int MAX_LEN = 1024;
typedef std::tr1::array<char, MAX_LEN> Sentence;
typedef std::vector<Sentence> Paragraph;

Paragraph para(256);
std::vector<Paragraph> book(2000);

I assume that the memory for Sentence is on the stack.
Is that right? What about the memory for vector para? Is that on the stack i.e. should I worry if my para gets too large?
And finaly what about the memory for book? That has to be on the heap I guess but the nested arrays are on the stack, aren't they?
Additional questions
Is the memory for Paragraph contiguous?
Is the memory for book contiguous?

Answer 1

There is no stack. Don't think about a stack. What matters is whether a given container class performs any dynamic allocation or not.

std::array<T,N> doesn't use any dynamic allocation, it is a very thing wrapper around an automatically allocated T[N].

Anything you put in a vector will however be allocated by the vector's own allocator, which in the default case (usually) performs dynamic allocation with ::operator new().

So in short, vector<array<char,N>> is very simiar to vector<int>: The allocator simply allocates memory for as many units of array<char,N> (or int) as it needs to hold and constructs the elements in that memory. Rinse and repeat for nested vectors.

---

For your "additional questions": vector<vector<T>> is definitely not contiguous for T at all. It is merely contiguous for vector<T>, but that only contains the small book-keeping part of the inner vector. The actual content of the inner vector is allocated by the inner vector's allocator, and separately for each inner vector. In general, vector<S> is contiguous for the type S, and nothing else.

I'm not actually sure about vector<array<U,N>> -- it might be contiguous for U, because the array has no reason to contain any data besides the contained U[N], but I'm not sure if that's mandatory.

You might want to ask that as a separate question, it's a good question!