4

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?

matias
  • 43
  • 3
  • Fred has asked [a new question](http://stackoverflow.com/questions/7269369/can-wrapping-a-type-in-a-struct-cause-additional-padding) that may be pertinent to your contiguity questions, and also [see this question](http://stackoverflow.com/questions/7269099/may-i-treat-a-2d-array-as-a-contiguous-1d-array). – Kerrek SB Sep 01 '11 at 11:05

3 Answers3

6

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!

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
  • 2
    -1 "There is no stack" is incorrect (an urban myth about what systems C++ must support). Please don't propagate silly urban myths. It makes it difficult for beginners to grok standardese such as "stack unwinding" -- it's a bit difficult to unwind if it isn't there. – Cheers and hth. - Alf Sep 01 '11 at 02:39
  • @Alf: I think the standard is badly worded there. It is not really "stack unwinding" but "scope unwinding" we just use the term as it makes it easy to grok for beginners. Just as there is technically no requirement for a stack it just the easiest way (and only real practical way to implement it (though it can be done in other ways (History and Russian compilers from the 60's have shown that (they generated self modifying code)). The concept of a stack does not help beginners to understand C++ (personally I think it makes it harder) especially for the answer to this question. – Martin York Sep 01 '11 at 04:26
  • 1
    It is much easier to explain the problem in terms of automatic and dynamic storage duration objects and scope. This is also the correct way to explain in terms of the standard. so I have to agree: like "there is no Spoon" it is just an easy way to perceive certain concepts just not variables and their lifespan. (Yes I did mean Spoon because there will always be a stack its just not relavant). – Martin York Sep 01 '11 at 04:29
  • @Tux-D: please don't propagate myths like "there is technically no requirement for a stack". That is incorrect, false, stupid, idiotic, wrong, etc. The C++ standard does guarantee a stack. It is not a question of agreement. – Cheers and hth. - Alf Sep 01 '11 at 04:32
  • @Alf: I am always willing to be proved wrong. That is the best way for me to learn. Personally I don;t think it does (because we don't need it). As I said people have built (horrible) systems that don't use a conventional stack. – Martin York Sep 01 '11 at 04:37
  • @Tux-D: you refer to 1960's compilers. There was no C++ in the 1960's. Stop trolling. – Cheers and hth. - Alf Sep 01 '11 at 04:41
  • 1
    @Alf: I was not trying to troll, I just disagree with you. And I am currently searching the standard to try and prove myself wrong. – Martin York Sep 01 '11 at 04:46
  • 1
    @Alf: I know I was being petty, and usually it'd be perfectly fine to think in terms of stacks. But for this question I really think that it is the wrong way to think about the problem -- the initial question "is an array on the stack" is already going about it the wrong way, especially paired with "where do containers of arrays go". Thinking about it in terms of automatic vs dynamic storage and allocators is just cleaner, and it frees the mind from unneeded clutter and details that aren't pertinent to the concepts. – Kerrek SB Sep 01 '11 at 10:01
2

As a side note, it might be helpful to use gdb. It lets you manually examine your memory, including the locations of your variables. You can check yourself precisely what memory you are using.

Kat
  • 1,604
  • 17
  • 24
1

Your code example:

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?" No. Whether something is allocated on the stack depends on the declaration context. You have omitted the context, hence nothing can be said. If an object is local and non-static, then you get stack allocation for the object itself, but not necessarily for parts that it refers to internally. By the way, since another answer here claimed "there is no stack", just disregard that urban legend about what kinds of systems C++ must support. It came originally from a misunderstanding of how a rather unsuccessful hardware level optimized computer worked, that some people erroneously thought that it didn't have a simple hardware-supported array-like stack implementation. It is quite a stretch from "not simple" to "not there", and even the "not simple" was utterly wrong, not just factually but logically (ultimately a self-contradiction). I.e. it was a not-too-smart beginner's mistake, even though the myth has been propagated by at least one person with some experience. Anyway, C++ guarantees an abstract stack, and on all extant computers that guaranteed abstract stack is implemented in terms of a hardware-assisted array-like simple stack

"What about the memory for vector para? Is that on the stack" Again, that depends on the declaration context, which you don't show. And again, even if the object itself is allocated on the stack, parts that it refer to internally will not (in general) be allocated on the stack.

"i.e. should I worry if my para gets too large?" No, there's no need to worry. A std::vector allocates its buffer dynamically. It's not limited by available stack space.

"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?" No and no.

"Is the memory for Paragraph contiguous?" No. But the vector's buffer is contiguous. That's because std::array is guaranteed contiguous, and a std::vector's buffer is guaranteed contiguous.

"Is the memory for book contiguous?" No.

Cheers and hth. - Alf
  • 142,714
  • 15
  • 209
  • 331
  • @anonymous downvoter: please state the reason for your downvote, so that others may benefit from your insight(s), heh.'' – Cheers and hth. - Alf Sep 01 '11 at 06:10
  • OK, nitpick now, but I think it's important to understand the philosophy of C++: "a vector allocates its buffer dynamically" is correct of course, but doesn't directly have anything to do with limited stack space -- what's true is that `malloc()` doesn't depend on the stack size. But I could write an allocator for my vector that does allocated from a memory buffer that I put on the stack before declaring the vector. It's contrived, but it goes to show how flexible the language is, and how any given presupposition may fail to account for all situations. – Kerrek SB Sep 01 '11 at 11:30
  • @All: I am not sure what your answer on contiguity of Paragraph ' memory means in practical terms. The memory is NOT contiguous but the buffers are contiguous? – matias Sep 01 '11 at 12:58
  • @matias: a `std::vector` is a small object of fixed size, that contains (among possible other things) a pointer to a buffer, which resides elsewhere in memory. Draw that. Then consider a vector of vectors. The contained vector objects reside in the outer vector's buffer. Each of them contains a pointer to its own buffer. Draw that. – Cheers and hth. - Alf Sep 01 '11 at 13:53