Re: [boost] stack-based std::containers

From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 2007-03-02 01:07:26

On Mar 1, 2007, at 2:11 AM, Thorsten Ottosen wrote:

> Michael Marcin wrote:
>> I have functions like say a quartic equation solver that can return a
>> variable number of solutions.  It would be clean IMO to return or  
>> pass
>> by reference a std::vector or like container that store the  
>> solutions.
>> However heap allocation is fairly expensive here so the usual  
>> solution
>> is to have a local array with max solutions elements and pass that by
>> reference into the solver and return the number of solutions.   
>> This is
>> ugly to use and read.  Is there a library for stack-based std-like
>> containers?  Alternatively is it possible to make an compatible
>> stack-based allocator for std::vector using alloca?
>
> You can definitely make a stack-based version of allocators. The
> allocator would store a  pointer to the local array.
> It's still fairly ugly though.

Ugly but really efficient.   The question is how to tune it (choose  
the capacity).  If you know there aren't going to be more than N  
instances at any given time, then it's a real good solution.  For  
instance e.g. if you have no more than one temporary at any given  
time, per thread, and you have an upper limit on the number of  
threads.  You would need to make double sure your code can handle  
std::bad_alloc, though, just in case.

However, as you say, the usual way to handle this kind of stack  
allocation is to pass in the buffer to use to return the solution.  I  
don't know why you say this is ugly:  this is the design used by the  
STL.  Just pass in an OutputIterator "result" (your buffer's begin)  
and return an OutputIterator (the end of the buffer holding the  
solution).  Make that a template parameter and you can handle any  
situation, including dynamic allocation by passing an  
std::insert_iterator<...>  or even an iterator adapter that will  
throw an exception if you overflow your buffer (is there such an  
iterator adaptor in boost???)

Am I missing something?
--
Herve