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

Subject: Re: [boost] Interest in StaticVector - fixed capacity vector
From: Krzysztof Czainski (1czajnik_at_[hidden])
Date: 2011-10-18 19:45:19

>
> 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.
>

2011/10/18 Andrew Hundt <athundt_at_[hidden]>

> Nate seems to have provided the best analysis of the situation that I
> have seen in the thread.
>
> On Sat, Oct 15, 2011 at 5:16 PM, Nathan Ridge <zeratul976_at_[hidden]>
> wrote:
> > 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.
>

2011/10/18 Andrew Hundt <athundt_at_[hidden]>

>  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 feel convinced to the above conclusions. However, one example comes to my
mind:

I can imagine using StaticVector all around my embedded application. At some
point, still in debug mode, I find one particular StaticVector not efficient
enough, so I'd like to disable the asserts for that particular StaticVector
only. I'd like to be able to do that without replacing every push_back with
unchecked_push_back. Furthermore, I might be using some algorithms on this
StaticVector, such as std::copy() with std::back_inserter, so trivial
replacing won't be possible.

Therefore I would like to see policies, or some other way to customize
checking for a particular StaticVector.

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?
>

How does using uint_value_t<N>::least inhibit such uses? If one needs a
size_t returning function, one can just add a forwarding function.

Regards
Kris