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-18 13:44:10

On Sat, Oct 15, 2011 at 5:16 PM, Nathan Ridge <zeratul976_at_[hidden]> wrote:
>
> After reading this thread again, it seems to me that the reason we
> can't reach an agreement is that different people are proposing
> two fundamentally different ways of using static_vector:
>
>   1) As a variant of [std|boost]::array where not all the elements are
>       constructed/used at the same time, and which keeps track of
>       how many elements are currently in use.
>
>   2) As a variant of std::vector which keeps its memory on the
>       stack, and which is used, literally, as a drop-in replacement
>       for std::vector, in the sense that the developer was using
>       std::vector, but then identified that in non-exceptional
>       situations the actual number of elements used is below a
>       certain threshold, and the program could use the
>       optimization of not allocating memory dynamically.
>
> It's clear to me that for use (1), exceeding the bound of the
> static_vector is a logic error and therefore should be undefined
> behaviour, whereas for (2), exceeding the bound of the static_vector
> is not a logic error and therefore throwing an exception is
> reasonable.
>
> My own previous arguments for not throwing were based on the
> assumption that the use case is (1), without giving (2) much thought.
>
> It's been suggested (including by me) that we use a policy or other
> technique for accommodating both use cases within the same class.
> However, upon some reflection, I'd like to propose something more
> drastic:
>
> Let's not have a class that serves two conceptually different
> purposes at all. It would confuse people, and lead to more buggy
> code, as developers conflate these two fundamentally different
> concepts in their head because they are both served by the same
> class.
>
> Of course, both use cases are worthwhile and deserve having
> a class for them in boost, and one's push_back should assert
> and the other's should throw. We can call one capacity_array
> and the other stack_vector, or whatever better names we come
> up with - but let's not give them the same name, when they are
> very different beasts.
>
> Now the implementor of these classes can implement them like this:
>
> typedef boost::detail::static_vector<T, AssertPolicy> capacity_array;
> typedef boost::detail::static_vector<T, ThrowPolicy> stack_vector;
>
> if they so choose - but the user doesn't need to know that, and should
> not have access to the underlying static_vector class, which does not
> correspond to any clear concept.
>
> Regards,
> Nate
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>

Nate seems to have provided the best analysis of the situation that I
have seen in the thread.

> But isn't use-case 2 much better served by a vector that degrades
> gracefully by falling back to using the heap?  I just can't see how
> throwing serves anyone's purpose well.

As Dave Abrahams suggests, I agree that the best behavior for case (2)
is falling back to the heap after exhausting the buffer, which
conveniently fits the functionality provided by AutoBuffer. Therefore,
I think StaticVector should focus on use case (1).

I'll probably attempt to make StaticVector fulfill use case (1) with
bounds checking performed using assert, in a way that makes it viable
for use internally within AutoBuffer as well if the writer of that
library desired to. The way I see things, if I implement StaticVector
using assert, someone can inherit from my class and add exceptions if
desired. I may be mistaken, but one could not do the same the other
way around without any sacrifice, since some implementations of
exceptions incur performance penalties.

As for check/unchecked bounds, I'll start with push_back being
checked, and provide unchecked_push_back + unchecked_insert. I know it
is less popular than a policy based implementation but I feel like
there will be reduced overhead for compiler implementations with less
effective optimizations, though this is based only on others' comments
earlier on in the thread. Since this is (for me at least) designed to
also be useful for embedded applications which may have stricter
requirements, I find this to be a sensible choice.

Please rip my choices apart for me, so I can correct them now before I
write more code :-)

I have one additional question regarding the size. It was requested
that I use boost::uint_value_t<N>::least, but I am concerned this
would inhibit uses where one inherits from StaticVector to add
functionality such as what is found in AutoBuffer. Should I stick to
std::size_t, boost::uint_value_t<N>::least, or allow the size type to
be set with a template parameter?

Cheers!
Andrew Hundt