2

I usually code in other languages (R, Python and Java), but recently started using C++. I've been solving problems on hackerrank.com, and specifically I bumped into this one: https://www.hackerrank.com/challenges/variable-sized-arrays

Prior to this question, I had never gotten a Segmentation Fault error. I've tinkered with the code and discovered that the error only occurs when I attempt to print from the arr variable.

I wonder if someone could help me with this, and maybe provide a detailed explanation as to the precise error?

The code is as follows, but the issue is likely with int arr[100000][100000] = {-1}; and printf("%d\n", arr[iHat][jHat]); because I can printf both iHat and jHat themselves, but I am unable to use them to access integers in the arr array.

#include <iostream>

using namespace std;
    int main(){

        int n, q;

        /*
        *scan in:
        *n array entries
        *q quaries
        */

        int arr[100000][100000] = {-1}; //initialize an array, larger than 10^5

        scanf("%d %d\n", &n, &q); //n is size of array, q is # of quaries

        for (int i = 0; i < n; ++i){ //loop through lines of input to populate array
        int c, y = 0; //initialize to zero at the start of each line
            while((c = getchar()) != '\n'){ //readline
                if(c != ' '){ //pass spaces
                    arr[i][y] = c; //place integer into array
                    ++y;
                }
            }
        }

        for (int i = 0; i < q; ++i){
            int iHat, jHat = 0;
            scanf("%d %d\n", &iHat, &jHat); //scan for coordinates
            printf("%d\n", arr[iHat][jHat]); //Segmentation fault occurs here, why?
        }
        return 0;
    }

Update

This question focused on memory management, and in particular the use of pointers. A functioning solution, resulting in no segmentation faults, is as follows:

#include <iostream>

using namespace std;
int main(){
    int n, q;
    /*
    *scan in:
    *n array entries
    *q quaries
    * format: %d %d
    */

    scanf("%d %d\n", &n, &q);//n is size of array of arrays, q is # of quaries

    int **arr = new int *[n]; //int** arr is a pointer of pointers of size n   

    for (int i = 0; i < n; ++i){//loop through lines of input to populate array  
        int k; //Always initialize variables in the narrowest scope possible!
        scanf("%d", &k);//grab k, the number of ints in the line
        arr[i] = new int[k];//create a 2nd dimension at entry i of size k
        for (int j = 0; j < k; ++j){
            scanf("%d", &arr[i][j]);//populate array
        }
    }

    for (int i = 0; i < q; ++i){
        int iHat, jHat = 0;
        scanf("%d %d\n", &iHat, &jHat); //scan for query coordinates
        printf("%d\n", arr[iHat][jHat]); //print results of query
    }

return 0;
}
Improve this question
1
  • 2
    Probably because 100000*100000 is too big to be placed in the stack. Try to use the heap (free store) Commented Dec 19, 2016 at 20:21

4 Answers 4

Reset to default
2

C++ gives you control of where you want to allocate memory. In your case, what you have found is that you allocated an array-of-array-of-int on the stack which exceeds the stack size. At some point, you access one of these elements which lies outside the bounds of the stack and also the program, which causes an access violation called a segmentation fault.

Since you mentioned being new to C++, it would help to understand these 3 areas of memory and how you would use each for your case:

Stack memory - space for temporary variables to automatically use without having to explicitly request. You will see undefined behavior if you exceed the stack size.

int main() {
  int arr[100000][100000];
}

Heap memory - space for dynamically allocating space whenever explicitly requested using the operator "new". An "std::bad_alloc" exception will be thrown if the requested memory size exceeds what is available.

 int main() {

    int **arr = new int *[100000];

    for (std::size_t i = 0; i < 100000; ++i) {
       arr[i] = new int[100000];
     }
  }

Static memory - space allocated for static objects before main runs. You will get a compiler error if the array dimensions are too large.

  int arr[100000][100000];

  int main() {
    ...
  }
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Compilers mentioned for reference were clang 3.5 and GCC 4.9
This is very clear and very well written, thank you!
1

That's 40 GB!

Even if you have that much RAM in the machine, it is surely not allocated as stack space.

If you do have that much memory you can move the arr to the global area before main. That way it will not be on the stack.

If you don't have 40+ GB available, you might have to rethink the solution. :-) Perhaps do the calculations in smaller segments?

Improve this answer

2 Comments

Okay, so that makes an awful lot of sense-- no seg fault is occurring when I reduced the size of the array. Thanks!
Typically, a Windows process has a 2MB stack (and Linux is similar). Anything over a few 10's of kbytes should probably be allocated on the heap.
1

Here are a few thoughts

1) You are trying to allocate 100,000 x 100,000 bytes, which equal 10,000,000,000 bytes (~10GB) on the stack. The default stack size is about 8MB on 32-bit linux. Even if the stack size is larger it won't be 10GB.

2) The name of the exercise you were working on is "Variable Sized Array" The line you entered,int arr[100000][100000] is a fixed size array. You should be using keyword new to dynamically create the array.

3) The reason for the Segmentation Fault error is because your print statement is attempting to access memory outside of the Virtual Memory space allowed for a stack size.

[Suggestion]

1) trying doing some exercises where you allocate and clean up dynamic memory using new and delete. Also in C++ allocating and deleting arrays is done differently than just a single data structure.

Cheers

Improve this answer

1 Comment

About point 3, is it accurate to say "outside the... space allowed for a stack size"? I don't think accessing memory beyond the stack boundary causes a segfault unless while doing so, you also reach beyond the virtual memory of the process. On UNIX, the OS catches this and sends a signal (SIGSEGV) to the running process, usually handled by termination. Also, if you consider how stack-based buffer overrun attacks/exploits work, they typically involve going beyond the stack to reach other regions of memory within the application while avoiding any crashes.
0

Are you trying to do this? 

#include <iostream>

using namespace std;
int main(){

int n, q;
const int length = 100;

int arr[length][length] = { -1 }; 
cout << "Enter length of 2d array" << endl;
cin>>n>>q; 

cout << "Fill the array" << endl;
for (int i = 0; i < n; ++i) { 

    for(int y=0;y<q;y++){
        int f;
        cin >> f;
        arr[i][y]=f;            
        }
}


    int iHat;
    int jHat;
    cout << "Enter coordinates" << endl;
    cin>>iHat>>jHat; 

    cout<<arr[iHat][jHat]; 

    return 0;

}

P.S i decreased array size, becouse 100000 x 100000 this is lot of gigabytes and it says array is too large

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.