Preventing stack overflows in C++ using arrays?

Question

If we implement a stack using arrays in C++, what is the best way to reduce the chance of an overflow condition? Also while keeping in mind the time-space trade off?

Answer 1

Just resize your array when you get close to the "overflow condition", i.e. when the next element wouldn't fit any longer. Or use a std::vector, which you can resize easily.

Not sure, but you are aware of the std::stack class, which implements a stack which resizes automatically in C++?

[EDIT] If you don't want to resize, but fail properly, throwing an exception is the best thing you can do. For example, you could define a StackOverflowException and throw it if there is no space left, so clients can react.

Answer 2

You can use std::stack to implement a stack. If you're looking for the homework answer, keep an array of data items (or pointers to them). This array could grow or shrink as the stack grows or shrinks. The grow/shrink factor* determines how much you care for speed or size optimization.

*By grow/shrink factor, I mean how many elements you add or remove when you grow or shrink. These are naturally power-of-two values or multiples as you can just add or multiply by an easy number (e.g. += 4096, *= 2). Using large values helps prevent stack resizing, which results in faster code, but consumes more memory. Smaller values have an opposite effect, and can even cause memory fragmentation on non-MMU systems (like some portable devices). For an implementation which uses buckets, this is basically your bucket size.

For the stack, you can use a linked list, a linked list with buckets, an alloc'd array (using malloc/realloc/free), std::vector, or other linear structures.

If you care about code size, use std::stack (duh) or std::vector as your starting point. However, since most C++ compilers compile these as bulky sets of functions, you'll probably roll out a light class using a malloc'd array.

Answer 3

While this answer does not precisely give tips for implementation, it answers how you can often protect yourself from certain bugs like buffer-overflows. GCC has a flag for this:

-fmudflap -fmudflapth -fmudflapir For front-ends that support it (C and C++), instrument all risky pointer/array dereferencing operations, some standard library string/heap functions, and some other associated constructs with range/validity tests. Modules so instrumented should be immune to buffer overflows, invalid heap use, and some other classes of C/C++ programming errors. The instrumen‐ tation relies on a separate runtime library (libmudflap), which will be linked into a program if -fmudflap is given at link time. Run-time behavior of the instrumented program is controlled by the MUDFLAP_OPTIONS environment variable. See "env MUDFLAP_OPTIONS=-help a.out" for its options.

Generally, this requires compiler support, since cannot overload the subscript operator [] for a native array like char[], or a pointer like char*.

Answer 4

just keep track of the size of the array. if you have an array of size 10 just store that size in an 'int'. then every time you access your array just check the index value is less then your size vale. this wont hurt your 'Big O' time