225

Are all of the following statements true?

vector<Type> vect; //allocates vect on stack and each of the Type (using std::allocator) also will be on the stack

vector<Type> *vect = new vector<Type>; //allocates vect on heap and each of the Type will be allocated on stack

vector<Type*> vect; //vect will be on stack and Type* will be on heap.

How is the memory allocated internally for Type in a vector or any other STL container?

trincot
  • 317,000
  • 35
  • 244
  • 286
Phelodas
  • 3,853
  • 5
  • 25
  • 30
  • 1
    Possible duplicate of [Class members and explicit stack/heap allocation](https://stackoverflow.com/questions/10836591/class-members-and-explicit-stack-heap-allocation) – underscore_d Nov 12 '17 at 14:51

5 Answers5

321
vector<Type> vect;

will allocate the vector, i.e. the header info, on the stack, but the elements on the free store ("heap").

vector<Type> *vect = new vector<Type>;

allocates everything on the free store (except vect pointer, which is on the stack).

vector<Type*> vect;

will allocate the vector on the stack and a bunch of pointers on the free store, but where these point is determined by how you use them (you could point element 0 to the free store and element 1 to the stack, say).

Rustem Kakimov
  • 2,421
  • 20
  • 25
Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • 3
    But I am having a scenario, where I am getting a segmentation fault when Type is growing big on the second declaration. I was assuming that it was because Type was being allocated on the stack. – Phelodas Nov 07 '11 at 12:35
  • The same works properly when I am using the third declaration and allocates Type explicitly on the heap. Any thoughts on this? – Phelodas Nov 07 '11 at 12:37
  • 5
    @Phelodas: without seeing your code, this is impossible to assess. Please open a new question. – Fred Foo Nov 07 '11 at 12:48
  • 2
    About `vector vect;` since the elements is on the heap and header info is on the stack, when the header info is removed from memory, like function return, what will happen to the elements memories? Are them reclaimed with the header info or not? If they are not, will this cause memory leak? – flyrain Sep 22 '13 at 17:39
  • 4
    @flyrain: vectors clean up after themselves. Read up on [RAII](https://en.wikipedia.org/wiki/RAII). – Fred Foo Sep 25 '13 at 12:08
  • Thank you very much. It's helpful. Another question is if I have a function foo like `vector foo(){vector v1(1); return v}` , another function like `int main(){cout< – flyrain Sep 27 '13 at 22:13
  • 1
    @flyrain: that should work. Please post a new question with more details. If you post the link here, I might have a look at it. – Fred Foo Sep 28 '13 at 15:41
  • `will allocate the vector on the stack` what exactly we mean by vector on stack and array on heap, I am confused – Himanshu Poddar May 20 '21 at 11:56
43
vector<Type> vect; //allocates vect on stack and each of the Type (using std::allocator) also will be on the stack

No, vect will be on the stack, but the array it uses internally to store the items will be on the heap. The items will reside in that array.

vector<Type> *vect = new vector<Type>; //allocates vect on heap and each of the Type will be allocated on stack

No. Same as above, except the vector class will be on the heap as well.

vector<Type*> vect; //vect will be on stack and Type* will be on heap.

vect will be on the stack, its items (pointers to Type) will be on the heap, and you can't tell where will be the Types the pointers point to. Could be on stack, could be on the heap, could be in the global data, could be nowhere (ie. NULL pointers).

BTW the implementation could in fact store some vectors (typically of small size) on the stack entirely. Not that I know of any such implementation, but it can.

Community
  • 1
  • 1
jpalecek
  • 47,058
  • 7
  • 102
  • 144
25

Assuming an implementation which actually has a stack and a heap (standard C++ makes no requirement to have such things) the only true statement is the last one. 

vector<Type> vect;
//allocates vect on stack and each of the Type (using std::allocator) also will be on the stack

This is true, except for the last part (Type won't be on the stack). Imagine:

  void foo(vector<Type>& vec) {
     // Can't be on stack - how would the stack "expand"
     // to make the extra space required between main and foo?
     vec.push_back(Type());
  }

  int main() {
    vector<Type> bar;
    foo(bar);
  }

Likewise:

 vector<Type> *vect = new vector<Type>; //allocates vect on heap and each of the Type will be allocated on stack

True except the last part, with a similar counter example:

  void foo(vector<Type> *vec) {
     // Can't be on stack - how would the stack "expand"
     // to make the extra space required between main and foo?
     vec->push_back(Type());
  }

  int main() {
    vector<Type> *bar = new vector<Type>;
    foo(bar);
  }

For:

vector<Type*> vect; //vect will be on stack and Type* will be on heap.

this is true, but note here that the Type* pointers will be on the heap, but the Type instances they point to need not be:

  int main() {
    vector<Type*> bar;
    Type foo;
    bar.push_back(&foo);
  }
Flexo
  • 87,323
  • 22
  • 191
  • 272
  • in what sort of context would you not have a stack? I understand you're saying the standard doesn't require it, but practically speaking, when would you be without a stack? – Nerdtron Nov 07 '11 at 14:59
  • 3
    @Nerdtron - IIRC on some small microcontrollers you have a call stack that can store nothing other than the PC (program counter) at the point of the last call, ready for a RET. Your compiler might therefore choose to place "automatic storage" (for non-recursive functions) in a fixed location with little/no relation to the flow of execution. It could quite sensibly flatten the whole program out. Even for the recursive case you could have a "stack per function" policy or a separate stack for automatic variables and return addresses, which makes the phrase "the stack" somewhat meaningless. – Flexo Nov 07 '11 at 15:36
  • You could use heap based allocation for *everything* and have a "cleanup stack" that manages automatic storage (and possibly `delete` too). – Flexo Nov 07 '11 at 15:38
4

vector has an internal allocator which is in charge of allocating/deallocating memories from heap for the vector element. So no matter how you create a vector, its element is always allocated on the heap. As for the vector's metadata, it depends on the way you create it.

Bingo
  • 95
  • 7
3

Only this statement is true:

vector <Type*> vect; //vect will be on stack and Type* will be on heap.

Type* pointers are stored on heap, because amount of the pointers can change dynamically.

vect in this case is allocated on stack, because you defined it as a local stack variable.

Alexei Khlebnikov
  • 2,126
  • 1
  • 21
  • 21
  • 4
    Type* doesn't indicate heap allocation, simply a pointer to a Type object. That said, the vector does store the pointer on the heap. int a = 5; int *ptr_to_a = &a; vector vec; vec.push_back(ptr_to_a); (see jpalecek's answer) – optimus_prime Jul 29 '19 at 16:07
  • 1
    "Type* doesn't indicate heap allocation" - agree, I did not claim the opposite. "the vector does store the pointer on the heap" - also agree, that's exactly what I meant by "Type* pointers are allocated on heap". – Alexei Khlebnikov Nov 25 '20 at 13:37
  • This answer is completely wrong. `Type*` doesn't mean anything, it can be on heap or from stack. – Enerccio Aug 31 '22 at 09:25
  • @Enerccio, given the code `vector vect;`, the `Type*` pointers are stored on heap. The pointers are stored on heap not because they are pointers, but because they are stored in a vector. – Alexei Khlebnikov Sep 01 '22 at 21:15
  • @AlexeiKhlebnikov The standards dont mention that the data has to be heap allocated, it *could* be allocated with alloca, the vast majority will heap-allocate the memory however – Tom McLean Jan 10 '23 at 09:09