Boost logo

Boost :

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

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk