-2

I'm having some troubles with a large array of vectors in C++. Basicaly I wan't an array of 2 millions elements, and each elements is a vector<int> (It's for building an adjacency list).

So when I do vector<int> myList[10] it works great, but when i do vector<int> myList[2000000] it does not work and I don't know why.

I tried to do unsigned long int var = 2000000; vector<int> myList[var]; but still the same error. (I don't know what is the error, my program just crash)

If you have any idea,

Thanks

CharlesR
  • 53
  • 7
  • 1
    Are you trying to declare this array as a local variable? – Davis Herring Oct 21 '17 at 22:38
  • Maybe helpful - change `var` to a `const unsigned long int` - variable length arrays are a compiler extension, not part of C++. Adding the `const` makes it "correct" in the sense that the array length is compile-time determined, which removes a possible source of suspicious behaviour. – hnefatl Oct 21 '17 at 22:39
  • 1
    Use a vector of vectors. Trying to declare an array of that size on the stack is very likely to fail, as you've seen. You could also make it a global or static if you wish. *shrug* – Retired Ninja Oct 21 '17 at 22:41
  • Thanks. I will try with a vector of vector but i don't understand, 2 millions times 24B is not that large for the memory :/ – CharlesR Oct 21 '17 at 22:47
  • `sizeof(vector)` is probably somewhere around 24 bytes. 2 million of those is somewhere around 45 megabytes. The default stack size is generally much smaller than that, so if you try to make it a local variable you have a stack overflow. On the heap, that's not so much. – Retired Ninja Oct 21 '17 at 22:57

2 Answers2

5

There's a big difference between heap and stack memory. The heap is the nice big space where you can dynamically allocate gigabytes of memory - the stack is much more constrained in terms of allocation size (and is determined at compile time).

If defining a local variable, that means it lives on the stack (like your array). With 2 million elements, that's at least 2MB being allocated (or assuming ~24B of stack usage per vector, more like 48MB), which is quite a lot for the stack, and likely causes the crash. Dynamically allocating an array of vectors (or preferably just allocating a vector of vectors) ensures that the bulk of the memory is being allocated from the heap, which might prevent this crash.

You can also increase the size of the stack using compiler flags, but that's generally not preferable to just dynamic allocation.

hnefatl
  • 5,860
  • 2
  • 27
  • 49
  • Thanks hnefatl, yeap with a vector of vector it works but i still don't understand why an array is in the stack and a dynamic allocating is on the heap ? But thanks the problem is solved ! – CharlesR Oct 21 '17 at 23:05
  • @Charles C++ defaults to locally declared variables being on the stack. If you want dynamic memory, you can allocate it on the heap but the pointers to the memory are on the stack. It's just the way things are in C++. `vector`s internally allocate memory off the heap, whereas arrays by nature are allocated on the stack (which is why their size has to be given at compile time). – hnefatl Oct 21 '17 at 23:08
  • @hnefatl: It’s not that arrays go on the stack, it’s that local variables (only their static footprint!) do. – Davis Herring Oct 21 '17 at 23:09
  • @hnefatl: `new int[2]` makes an array on the heap. `vector foo(2);` puts `foo` on the stack, but the `int`s are still on the heap. Does that help? – Davis Herring Oct 21 '17 at 23:15
-2

This is helpfull

Dynamically allocate memory for my_List. or

Declare your array of vector of int's(my_List) as a global variable and size a `const. Thier storage locations are by design big enough to allocate such large mermory size.

For local variable, the stack segment might be to small to allocate 2e6*24B.

ytobi
  • 535
  • 1
  • 9
  • 19
  • Works, but bad advice. No need to go global for this. `static` would be better, but `vector` of `vector`s gets the job done without any fuss. – user4581301 Oct 21 '17 at 23:08
  • @user4581301 There are multiple ways of doing the same thing. considering all the options is not a bad idea. – ytobi Oct 21 '17 at 23:56
  • 1
    I can kill a wart on my foot by chopping off my leg. This does not make it an option worth considering. – user4581301 Oct 22 '17 at 00:05