C++ vector and array

Question

I was trying to solve a HackerRank question named "Array Manipulation"The link of the problem. I wrote this code below. It works fine. However, when I use an array instead of vector I got segmentation fault at case 7-13. Why did it happen?

long arrayManipulation(int n, vector<vector<int>> queries) {
    vector<long> arr(n);
    long sum=0, max=LONG_MIN;
    for(int i=0;i<n;i++){
        arr[i] = 0;
    }
    for(int i=0;i<queries.size();i++){
        arr[queries[i][0]-1] += queries[i][2];
        if(queries[i][1]<n) arr[queries[i][1]] -= queries[i][2];
    }
    for(int i=0;i<n;i++){
        sum += arr[i];
        if(sum>max) max=sum;
    }
    return max; }

long arrayManipulation(int n, vector<vector<int>> queries) {
    long arr[n];
    long sum=0, max=LONG_MIN;
    for(int i=0;i<n;i++){
        arr[i]=0;
    }
    for(int i=0;i<queries.size();i++){
        arr[queries[i][0]-1]+=queries[i][2];
        if(queries[i][1]<n) arr[queries[i][1]]-=queries[i][2];
    }
    for(int i=0;i<n;i++){
        sum+=arr[i];
        if(sum>max) max=sum;
    }
    return max;
}

You probably go out of bounds, which leads to undefined behavior, which unfortunately sometimes might seem to work. How is this function called? What is the contents of queries? — Some programmer dude
– Some programmer dude, Commented Feb 5, 2020 at 11:39
"queries[i][0]-1" looks suspicious to result in "-1" at some point and thus access a position of "arr" that cannot exist. Best would be if you run the vector variant in an IDE with debugger activated so you get an error when the vector is accessed out of bounds. — AlexGeorg
– AlexGeorg, Commented Feb 5, 2020 at 11:42
Apart from the possibility of going out of array bounds ... long arr[n] where n is a variable (or function argument) is a VLA (variable length array) which is not valid C++. Some compilers support VLAs as a non-standard extension. Those that do support VLAs typically use process stack space, which is subject to a fairly small quota under most unix environments so the possible size of such an array is therefore significantly smaller than is possible with a std::vector, which uses dynamic memory allocation. A fairly common symptom of exceeding available stack space is a segmentation fault — Peter
– Peter, Commented Feb 5, 2020 at 11:55
long arr[n]; -- I wish that these coding sites such as HackerRank would turn on the correct compiler options to make this illegal, or at least give that option to do so. This is not legal C++. As to using std::vector, use the at() function instead of [ ] to access the elements in the vector. If you now get a std::out_of_range exception thrown, then indeed you are going out-of-bounds. — PaulMcKenzie
– PaulMcKenzie, Commented Feb 5, 2020 at 12:25

cosmos · Accepted Answer · 2020-02-05 11:57:13Z

2

Variable length arrays have a limit of available stack limit, if it surpasses the limit SegV (by stack overflow) can occur.

The same can happen for fixed length array if size is large enough.

Try with this to see the issue:

long arr[10000000];  // should fail for same reason in HackerRank

answered Feb 5, 2020 at 11:57

cosmos

2,3131 gold badge18 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Borgleader Over a year ago

Also important to note that VLAs are not standard C++ (they're a compiler extension)

Collectives™ on Stack Overflow

C++ vector and array

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related