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
– Kerrek SB, Commented Jan 6, 2013 at 12:33
for the future, stackoverflow = problems with dynamic allocation/s, you probably want to read something about allocation mechanism in c++ — user1824407
– user1824407, Commented Jan 6, 2013 at 12:36
Who doesn't absolutely love mixing stdlib stream io (std::cin >> x) with cstdio (scanf("%d\n",&n);). — WhozCraig
– WhozCraig, Commented Jan 6, 2013 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
– Tom Knapen, Commented Jan 6, 2013 at 12:51

Alok Save · Accepted Answer · 2013-01-06 12:35:45Z

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 6, 2013 at 12:35

Alok Save

208k56 gold badges449 silver badges540 bronze badges

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

2 Comments

WhozCraig Over a year ago

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).

Matthieu M. Over a year ago

@WhozCraig: This! I believe the right answer would be switching from array to an associative container.

Hui Zheng · Accepted Answer · 2013-01-06 12:45:32Z

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 6, 2013 at 12:45

answered Jan 6, 2013 at 12:37

Hui Zheng

10.2k2 gold badges37 silver badges40 bronze badges

Comments

Roee Gavirel · Accepted Answer · 2013-01-06 12:42:06Z

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");
}

Collectives™ on Stack Overflow

stack overflow c++

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related