Re: [Boost-users] Is there a boost equivalent of eastl::fixed_vector?

Subject: Re: [Boost-users] Is there a boost equivalent of eastl::fixed_vector?
From: dariomt (dariomt_at_[hidden])
Date: 2008-09-25 03:54:57

> 
> well if you are using words like "fixed-size" and "allocate no dynamic
> memory" then boost::array<T,N> is your candidate, isn't it?
> 
> personally i miss the stored count of objects so i can push_back until
> some capacity.  so i modified the source slightly for these purposes.
> 

That's what I meant with SSO, in this case I would call it SCO (Small Container
Optimization):

The container has 'within the container itself' a buffer (in the stack) with
space for N objects, so as long as size() <= N no dynamic allocation is needed.
When size() > N, a policy can decide to throw an exception or to switch to
dynamic allocation 'as usual'.

Some STL implementations (e.g. the one shipped with MS VC++) use this SSO in
std::basic_string with a 'small' non-tunable N (e.g. 16), so 'small' strings
don't use dynamic memory.

The situation I am trying to improve is where 'many' 'small' vectors (or other
containers) are constructed/copied/assigned/destructed, and
allocation/deallocation seems to be a significant overhead. I cannot switch the
vectors to boost::array because I need variable size (but guaranteed to be
'small'). 

It seems ublas::vector has the possibility to specify a 'bounded vector' (stack
buffer) as the underlying storage, but I think it lacks fallback to dynamic
allocation and a std::vector compatible interface. I'll take a look to the
implementation to get some ideas.

I was looking for a general solution based on allocators, to be able to apply it
to other containers as well. ¿Any ideas for this approach?

> 
> * dariomt <at> gmail.com <dariomt <at> gmail.com> [2008-09-24 11:32:45 +0200]:
> 
> > In EASTL http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.htmlthere
> > is something like SSO (Small String Optimization) applied to
> > std::vector (and other STL containers)
> > 
> > [begin quote]
> > "Fixed containers are fixed-size containers with their memory stored right
> > within the container itself. Fixed containers allocate no dynamic memory and
> > their memory tends to be cache-friendly due to its contiguity and proximity
> > to the container's housekeeping data. The user declares the max container
> > size as a template parameter, and can also specify that if the container
> > overflows that an auxiliary dynamic allocator is used.
> > 
> > template <typename T, size_t nodeCount, bool enableOverflow = true,
> >           typename Allocator overflowAllocator = EASTLAllocator>
> > class fixed_vector
> > {
> >    ...
> > };
> > 
> > [end quote]
> > 
> > I have tried a similar approach using some sort of
> > fixed_buffer_with_overflow allocator, with no success. I'm not sure SSO is
> > even possible just using an allocator with the standard containers, because
> > I always end up with stateful allocators.
> > 
> > So my question is if there is something similar already in boost.
> > 
> > TIA
> 
> > _______________________________________________
> > Boost-users mailing list
> > Boost-users <at> lists.boost.org
> > http://lists.boost.org/mailman/listinfo.cgi/boost-users
>