Allen wrote:
What are some different approaches to dealing with stack overflows in
C++? I'm especially interested in approaches concerned with speed for
infrequent overflows.
Even more specifically, I have a recursive BST function for a
potentially very large tree. What kinds of schemes have others come up with
for dealing with stack overruns of this type?
Have you tried to allocate a bigger stack ? Some OS's allow you to
create bigger stacks.
Another alternative is to not use a recursive call but to create an
object that allows you to "stack" state in a "frame" object.
e.g.
// recursive function
int Recursive( node * here )
{
int has_stuff = 0;
if ( here )
{
has_stuff = here->do_some_stuff();
has_stuff += Recursive( here->left );
has_stuff += Recursive( here->right );
}
return has_stuff;
}
//
// non-recursive way to do the same thing -
//
//
// This class stores the state that would have been stored
// on the stack.
//
class Stuffer
{
public:
int m_has_stuff;
node * m_node;
enum State
{
DoLeft,
DoRight,
Done
};
State m_state;
Stuffer( node * i_here )
: m_has_stuff( i_here->do_some_stuff() ),
m_here( i_here ),
m_state( DoLeft )
{}
void Next()
{
switch ( m_state )
case DoLeft : m_state = DoRight; break;
case DoRight : m_state = Done; break;
case Done : break;
}
}
};
//
// This method performs everything in a while loop - no
// recursive calls.
//
int NonRecursive(node * here)
{
std::list<Stuffer> stuff_stack;
stuff_stack->push_front( Stuffer( here ) );
while ( stuff_stack->begin() != stuff_stack->end() )
{
std::list<Stuffer>::iterator p_stuffer = stuff_stack->begin();
switch ( p_stuffer->m_state )
{
case DoLeft :
stuff_stack->push_front(Stuffer(here->left));
p_stuffer->Next();
break;
case DoRight :
stuff_stack->push_front(Stuffer(here->right));
p_stuffer->Next();
break;
case Done :
std::list<Stuffer>::iterator p_last = p_stuffer;
p_last ++;
if ( p_last == stuff_stack->end() )
{
return p_stuffer->m_has_stuff;
}
p_last->m_has_stuff += p_stuffer->m_has_stuff;
stuff_stack->erase( p_stuffer );
break;
}
}
// should never get here
return 0;
}
..... this is all off the top of my brain - I didn't compile or verify
that this works - I just thought it's a good example of how to decompose
a recursive function into a separate stack.