stack overflow c++

Question

So i', trying to solve a task. a already have code, but system outs, "stack overflow" i'm new in c++ and my english isn't good so i'm sorry for misunderstanding =)

   #include <iostream> 

using namespace std;

int main (){
    int n;
    int x;
    int k = 0; // счетчик для рабочего массива
    int a [200000];
 scanf("%d\n",&n);   

 for (int i = 0; i< n; ++i){
     std::cin >> x;
     if (x > 0){
             k++;
             a[k] = x;
           }else if(x == 0){
                 for (int q = 1; q <= k; ++q){ // копирование 
                          a[k+q] = a[q];
                     }
                 k *= 2;
                 }else{
                          printf("%d %d\n",a[k],k);
                          k--;
                        }
     }
     system("pause");


}

looks like algorithm works correctly, but only problem is stack. thanks a lot!

Try making the array `a` global, i.e. moving it outside of `main`. — Kerrek SB, Jan 06 '13 at 12:33
for the future, stackoverflow = problems with dynamic allocation/s, you probably want to read something about allocation mechanism in c++ — user1824407, Jan 06 '13 at 12:36
Who doesn't absolutely *love* mixing stdlib stream io (`std::cin >> x`) with cstdio (`scanf("%d\n",&n);`). — WhozCraig, Jan 06 '13 at 12:40
@user1824407 stackoverflows and dynamic memory allocations have (almost) nothing to do with eachother. Especially not in this case, since the OP doesn't do any dynamic allocations. — Tom Knapen, Jan 06 '13 at 12:51

score 6 · Answer 1 · answered Jan 06 '13 at 12:35

6

Root Cause:

As you guessed correctly, the stack is limited and seems your allocation is large enough to be catered through it. This is not an language syntax error so it does not warrant a compilation error but it results in a run time exception thus causing a crash.

Solution 1:

You can make the array global, the allocation of an global array is not on stack so it should work fine for you:

int a [200000];

int main()
{
   .....
}

Solution 2:

You could use a std::vector

Solution 3:

You can use dynamic allocation through new.

answered Jan 06 '13 at 12:35

Alok Save

202,538
53
430
533

1

Solution 4: You could reduce your array size considerably **and** filter-check the user-input, which btw, can currently *still* overrun your 200000 element array by entering 200001, a perfectly valid `int`. (oh, and +1, nice answer). – WhozCraig Jan 06 '13 at 12:43
1

@WhozCraig: This! I believe the right answer would be switching from array to an associative container. – Matthieu M. Jan 06 '13 at 13:44

Hui Zheng · Answer 2 · 2013-01-06T12:45:32.920

2

Statement int a [200000]; attempts to allocate more memory on the stack than will fit, which caused stack overflow. Some people recommend that arrays larger than a few kilobytes should be allocated dynamically instead of as a local variable. Please refer to wikipedia: http://en.wikipedia.org/wiki/Stack_overflow#Very_large_stack_variables

edited Jan 06 '13 at 12:45

answered Jan 06 '13 at 12:37

Hui Zheng

10,084
2
35
40

score 0 · Answer 3 · answered Jan 06 '13 at 12:42

3 changes I can see.
1 - allocating on the stack more than the stack can handle.
2 - k should always pointing to the next free space so you need to update than increase it.
3 - the index are starting from "0" both for the "q" for.

Fixed code:

#include <iostream> 

using namespace std;

int a [200000];

int main (){
    int n;
    int x;
    int k = 0; // счетчик для рабочего массива
 scanf("%d\n",&n);   

 for (int i = 0; i< n; ++i){
     std::cin >> x;
     if (x > 0)
     {
             a[k] = x;
             k++; //<< change 1
     }
     else if (x == 0)
     {
         for (int q = 0; q <= k; ++q) //<<change 2
         { // копирование 
             a[k+q] = a[q];
         }
         k *= 2;
     }
     else 
     {
         printf("%d %d\n",a[k],k);
         k--;
                        }
 }
 system("pause");
}

stack overflow c++

3 Answers3

Linked

Related