vector a[n] allocated in stack or heap? Difference between the declarations vector>a(n) and vectora[n]?

Question

When I declare vector< vector< int>> a(n), memory is allocated in heap whereas when I declare it vector< int> a[n], it is allocated on stack. But why? Doesn't the second one mean the way- a[i] is a pointer to the i-th vector, as the vectors are dynamically allocated in heap and hence the whole allocation should be in heap. Isn't it?

Could you please explain me if I am wrong?

VLA are not part of C++, it is C that supported by some compilers in C++ mode. — Slava, Sep 07 '17 at 18:26
This is a VLA variant of: https://stackoverflow.com/questions/1847789/segmentation-fault-on-large-array-sizes — jxh, Sep 07 '17 at 18:30
Good spot jxh. I should have gone looking for that dupe, rather than trying to answer. — Martin Bonner supports Monica, Sep 07 '17 at 18:35
Subject for this topic should be "Welcome to Stack Overflow" with double meanings... — Slava, Sep 07 '17 at 18:37
If you know that a vector is a dynamic array, why not do the common sense thing and make a vector (dynamic array) of vector? — PaulMcKenzie, Sep 07 '17 at 18:37

score 4 · Accepted Answer · 2017-09-07T19:21:54.500

4

vector<int> adj[n];

This is not legal C++ code, you are not allowed to declare a dynamicaly sized array on the stack like this.

It's also probably the cause of your issue, as making such a huge allocation on the stack can cause some major issues.

You should use the following instead:

vector<vector<int>> adj(n);

edited Sep 07 '17 at 19:21

answered Sep 07 '17 at 18:24

This doesn't answer the question. While the statement is true, it is obviously an extension supported by his compiler, and is not really the cause of his problem. – Martin Bonner supports Monica Sep 07 '17 at 18:26
Yeah, it's legal for some compilers. Although I've never run across one, myself. – zzxyz Sep 07 '17 at 18:26
3

@zzyz some compilers letting you do it does not make it legal C++. Otherwise the same could be said of any undefined behavior, or strict aliasing violation. – Sep 07 '17 at 18:27
1

@MartinBonner Added the explanation as to why I believe it's the root of the issue OP is trying to solve. Thanks! – Sep 07 '17 at 18:29
@Frank Fair enough, and upvoted your answer based on your edit. – zzxyz Sep 07 '17 at 18:32
Actually it should be `vector> adj(n, {1} );` which would even eliminate next loop – Slava Sep 07 '17 at 18:40

score 0 · Answer 2 · answered Sep 07 '17 at 18:28

As mentioned,

vector<int> adj[n];

is not standard C++, however some compilers (GCC) allow it as extension.

However such array is then created on the stack, and what you likely see is stack overflow (pun intended) - the stack is usually much smaller than the heap memory.

vector a[n] allocated in stack or heap? Difference between the declarations vector>a(n) and vectora[n]?

2 Answers2

Linked