When vectors are allocated, do they use memory on the heap or the stack?

Question

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?

Elvera

Possible duplicate of Class members and explicit stack/heap allocation – Eatage

Answer 1

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).

Easement

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. – Elvera

The same works properly when I am using the third declaration and allocates Type explicitly on the heap. Any thoughts on this? – Elvera

@Phelodas: without seeing your code, this is impossible to assess. Please open a new question. – Easement

About vector<Type> 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? – Lovemaking

@flyrain: vectors clean up after themselves. Read up on RAII. – Easement

Thank you very much. It's helpful. Another question is if I have a function foo like vector<int> foo(){vector<int> v1(1); return v} , another function like int main(){cout<<foo().size()<<endl;} , v1(at least its header info on the stack) is supposed to be reclaimed when foo returns, but actually not. why was that? This is so different from C. – Lovemaking

@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. – Easement

will allocate the vector on the stack what exactly we mean by vector on stack and array on heap, I am confused – Luzon

Answer 2

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.

Credulous

Is this true for all STL containers or just std::vector? – Skittle

@Skittle all the containers that have an Allocator template parameter (i.e. not std::array) – Hairless

Answer 3

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);
  }

Tacet

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? – Isodiametric

@Isodiametric - 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. – Tacet

You could use heap based allocation for everything and have a "cleanup stack" that manages automatic storage (and possibly delete too). – Tacet

Answer 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.

Breath

Answer 5

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.

Fresnel

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<int*> vec; vec.push_back(ptr_to_a); (see jpalecek's answer) – Cytotaxonomy

"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". – Fresnel

This answer is completely wrong. Type* doesn't mean anything, it can be on heap or from stack. – Select

@Enerccio, given the code vector <Type*> 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. – Fresnel

@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 – Liquefacient