Why segmentation fault when using built-in array instead of vector or new

Question

I'm initializing an array n-size with all zeros. Using the vector class or allocating with "new" works but with built-in array, i get segmentation fault in hackerrank c++.

long long arr[n];
for(int a = 0;a < n;a++) {
    arr[n] = 0;
}
//segmentation fault in some cases.

long long arr = new long long[n]; // doesn't fail

vector<long long> arr(n,0); // works also

Complete code:

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

using namespace std;
typedef long long ll;

int main()
{
    ll n,m;
    ll biggest = 0;
    ll current = 0;
    cin >> n >> m;
    ll arr[n];
    for(int a = 0;a < n;a++) {
    arr[a] = 0;
    }

    for(int i = 0;i < m;i++) {
    ll a,b,k;
    cin >> a >> b >> k;
    arr[a - 1] += k;
    if(b < n) arr[b] -= k;
    }
    for(int j = 0;j < n; j++) {
    current += arr[j];
    biggest = max(current,biggest);
    }
    cout << biggest << endl;
    return 0;
}

Why built-in fails?

Link to problem

Note that `ll arr[n];` is not a built-in thing. You can't defined an array like that unless `n` is a compile-time constant, it isn't allowed in C++. GCC provides an extension which allows it but it isn't portable. — François Andrieux, Sep 23 '22 at 16:39
I'm not sure how GCC implements it, but the storage for `arr` is on the stack, a large `n` might cause a stack overflow. — François Andrieux, Sep 23 '22 at 16:39
Most likely because you array is to big. `ll arr[n];` is not legal C++, use `-pedantic-errors` when compiling and the compiler will reject this code. Switch back to using a vector when you want an array with a run time size — NathanOliver, Sep 23 '22 at 16:40
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Jesper Juhl, Sep 23 '22 at 16:40
Surprised that nobody has noted yet, beyond the fact that `n` must be a compile time constant to be used in this fashion, that your array access inside the loop should be `arr[a]` instead of `arr[n]` - `a` is your loop variable, `n` is your size limit Edit: I see that it is correct in the larger code segment — rdowell, Sep 23 '22 at 16:44
`arr[a - 1] += k;` is potentially an out of bounds array access. — Avi Berger, Sep 23 '22 at 16:46
Side note: When you encrypt your code with garbage like `typedef long long ll;` and single letter variable names, you should expect bugs and expect to spend more time finding and fixing them. Don't be a chump. Spend extra time writing clean, easy-to-read code and spend less time debugging. — user4581301, Sep 23 '22 at 16:46
Crash happens when invalid data are provided or when there is no data (since there is no error handling). When proper input is provided crash doesn't accrue: https://godbolt.org/z/ssYxrKn7d So once again: please provide example of input. — Marek R, Sep 23 '22 at 16:47
@NeilButterworth of course not. We do not know what are inputs constraints, since there is no problem description or link to task. I clearly ask to provide example of data. I'm not claiming code is correct. — Marek R, Sep 23 '22 at 16:52
Also `Complete code` doesn't match code pointed as a problem. — Marek R, Sep 23 '22 at 16:54
`0 < n < 10^7` means you have "stack overflow" and `std::vector` is needed. — Marek R, Sep 23 '22 at 16:56
so array[not-const] is not good practice and i should use "new" ? — Ismail Ayvaz, Sep 23 '22 at 16:57
No `new`? Just use `std::vector`. Use of `new` in this context would be ok in the `90s not in 2022. — Marek R, Sep 23 '22 at 16:58
Please provide link to task on hackerrank so everything is clear. — Marek R, Sep 23 '22 at 16:59
should i use vectors even when array size doesn't change later? — Ismail Ayvaz, Sep 23 '22 at 17:00
@IsmailAyvaz Yes. If you need a big array, or if you need an array with a size that isn't determined until your run the program then you want a `std::vector`. — NathanOliver, Sep 23 '22 at 17:02
After reading task description simple use of array in any form will not meet time requirements. You need smarter form of data structure. — Marek R, Sep 23 '22 at 17:06

score 1 · Accepted Answer · answered Sep 23 '22 at 16:48

1

The question has been subtly answered in the question itself. Allocating memory from stack is okay, but only for small numbers. Hackerrank problems may have large input n. As a thumb rule, 10^6 ints can be kept on stack since that's about 4 MB considering 4 bytes per integer. For anything larger, please use dynamic memory from heap using new keyword which has much higher limits.

answered Sep 23 '22 at 16:48

Madhav Sarpal

256
1
7

1

it's not ok and it is not part of c++ – Neil Butterworth Sep 23 '22 at 16:51
1

Note that on msvc the stack is 1MB by default. Although it does not support VLAs at all so this method would not work. – drescherjm Sep 23 '22 at 17:00
Using `new` to get a dynamic array is for chumps. Use a `std::vector`. Generalizing, [Avoid using `new`](https://stackoverflow.com/questions/6500313/why-should-c-programmers-minimize-use-of-new). – user4581301 Sep 23 '22 at 17:23
@user4581301, It was a nice read on why we should avoid new keyword. But in my defense, the submissions to be made on portals like Hackerrank have to be done after analyzing memory requirements too. If the input can go up to 10^8, then 8 bytes per long long would make total requirement as 800 MB which is fine for dynamic array, but a vector might hold twice as much and 1600 MB would cross the typical limit of 1500 MB offered by a SPOJ cluster. Not to forget that a dynamic array is much easier to type in a limited time competition and you can toss the pointer across functions easily. – Madhav Sarpal Sep 24 '22 at 02:28
Heck, if you're writing something that has to run for a few seconds once ever, good engineering isn't that important. Just don't let the kids find it. – user4581301 Sep 24 '22 at 03:31

Why segmentation fault when using built-in array instead of vector or new

1 Answers1