Code running successfully using vector but showing error using array

Question

I was practicing an array manipulation question. While solving I declared an array (array A in code). For some test cases, I got a segmentation fault. I replaced the array with vector and got AC. I don't know the reason for this. Plz, explain.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,m,a,b,k;
    cin>>n>>m;
    vector<long int> A(n+2);
    //long int A[n+2]={0};

    for(int i=0;i<m;i++)
    {
        cin>>a>>b>>k;
        A[a]+=k;
        A[b+1]-=k;
    }
    long res=0;
    for(int i=1;i<n+2;i++)
    {
        A[i]+=A[i-1];
        if(res<A[i])
        res=A[i];
    }
    cout<<res;
    return 0;
}

Can you please make sure that the code you provide compiles? This example doesn't. It's also more helpful if you hardcode values that you use for n,m,a,b, and k. There are MANY ways to break the code as-is in a few different places, and it's impossible to tell how or where it's breaking in your case. — Thomas, Jul 02 '20 at 20:13

score 0 · Answer 1 · answered Jul 03 '20 at 02:03

Since it looks like you haven't being programming in C++ for very long I will try to break it down for you to make it simpler to understand: First of all c++ does not intialize any values for you this is not Java, so please do not do:

int n,m,a,b,k;

And then use:

A[a]+=k;
A[b+1]-=k;

At this point we have no idea what a and b are it might be -300 for all we know, you never intialized it. Hence, occasically you get lucky and the number that is initalized by the compiler does not cause a segmentation fault, and other times you are not so lucky and the value intialized by the compiler does cause a segmentation fault.

score 0 · Answer 2 · answered Jul 04 '20 at 01:18

long int A[n+2]={0}; is not legal in Standard C++. There are a bunch of reasons for this and I think you stumbled over one of them.

Compilers that allow Variable Length Arrays follow the example of C99 and the array is allocated on the stack. Stack is a limited resource, usually between 1 and 10 MB for a desktop computer. If the user inputs an n of sufficient size, the array will take up too much of the stack or breach the bounds of the stack resulting in Undefined Behaviour. of then this behaviour manifests in a segmentation fault from accessing memory that is so far off the end of the stack that it's not controlled by the program. There are typically no warnings when you overflow the stack. Often a program crash or corrupted data is the the way you find out, and it's too late to salvage the program by then.

On the other hand, a vector allocates it's internal buffer from the freestore, and on a modern PC with virtual memory and 64 bit addressing the freestore is fantastically huge and throws an exception if you attempt to exceed what it can allocate.

Another important difference is

long int A[n+2]={0};

likely did not zero initialize the array. This is the case with g++. The first byte will be set to zero and the remainder are uninitialized. Such is the curse of using non-Standard extensions. You cannot count on the behaviour guaranteed by the Standard.

std::vector will zero initialize the whole array or set the array to whatever value you tell it to use.

Code running successfully using vector but showing error using array

2 Answers2