Re: [boost] Interest in StaticVector - fixed capacity vector

Subject: Re: [boost] Interest in StaticVector - fixed capacity vector
From: Andrew Hundt (athundt_at_[hidden])
Date: 2011-10-13 19:08:49

2011/10/13 Ion Gaztañaga <igaztanaga_at_[hidden]>:
> It's interesting but we need some consensus on several issues

IMO, here are the most interesting and consensus worthy choices so far

> If swap is O(N), should it be provided?

Yes, I am fairly certain std::array provides a linear swap, and
boost.array definitely provides it, so StaticVector should too.

> unchecked functions?

They should definitely be provided.

> what to do when there is no room for more elements?

After comments by Nate Ridge, Dave Abrahams, and others, I have become
convinced that push_back should be unchecked and exceeding the bounds
should be undefined, with an option to turn on checking.

I haven't been convinced how the option should be defined, though I've
seen several options:
1) locally defined option
2) defined generally for boost
3) combination of 1 and 2, since they are not mutually exclusive
4) policy based.

> and the implementation should support movable
> types and other goodies from boost.Container.
> One of the extensions I was thinking for Boost.Container was a fixed
> capacity vector, and the solution I planned was reusing
> boost::container::vector code, maybe with some extensions supporting a
> pseudo-allocator. boost::container:: vector could treat this
> pseudo-allocator specially and avoid storing a m_capacity or m_pointer
> member to save some words. Then allocate() could implement the policy
> (assert, throw, or just ignore).
>

Interesting. So this stack allocated pseudo-allocator would look and
act (partially) like an allocator, but not fit the definition of one
due to the C++03 and C++11 rules against them.

Is this suggesting that boost::container::vector be directly modified
to support both fixed capacity as well, or just mixing some of the
shared code in?

> There are more issues. Do we want to support some kind of StaticVector
> compatible with shared memory? then we need to specify pointer and
> const_pointer as those define the pointer type stored in iterators...
>
> Anyway, I think that we could implement an approach similar to Howard's
> stack_alloc quite easily, and get most benefits with a bit of size overhead.

so considering the other posts that internal storage allocators are
forbidden, how would this work?

Well that may mark the end of my StaticVector work, but that is how
these things go. At the very least there has been productive
discussion. Although, perhaps the size overhead advantage of
StaticVector would allow room for it considering to the difference it
could make for embedded systems.