[ODE] Stack overflow

Gary R. Van Sickle g.r.vansickle at worldnet.att.net
Thu Jan 30 23:38:02 2003


> On Thu, 30 Jan 2003, Gary R. Van Sickle wrote:
>
> > > Alternately, you could declare your own alloca() and write your own memory
> > > manager. [...]
> >
> > Couldn't std::stack<> come to the rescue here?
>
> I'm sure it would work, but would it be fast?
>

Sure.  A lot faster than overflowing the runtime stack ;-).

> Does std::stack allocate a giant chunk of memory and then sub-allocate
> from that in stack-like fashion or does each object in the std::stack get
> allocated from the heap?  The former would probably be pretty fast, but
> the latter would be no faster than malloc().

They use a deque<> as the underlying data structure by default.  A deque is a
dynamically-resizable data structure which is basically a linked list of
medium-sized chunks of memory.  Push/pop on deque-based stack<>s is amortized
O(1) with a small C, worst-case O(1)+O(malloc/free of a medium-sized chunk).

--
Gary R. Van Sickle
Brewer.  Patriot.