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

Subject: Re: [boost] Interest in StaticVector - fixed capacity vector
From: Stewart, Robert (Robert.Stewart_at_[hidden])
Date: 2011-10-12 06:38:59

Nevin Liber wrote:
> On 11 October 2011 20:01, Nathan Ridge
> <zeratul976_at_[hidden]> wrote:
>
> >> If you are checking all the preconditions yourself, why do
> >> you care if it throws or not?
> >> [ That sounds glib - but it's a serious question. ]
> >>
> >> Why do you care if it ASSERTs, calls abort (), throws, or
> >> gets your cat pregnant?
> >
> > You care because if it throws, it is incurring the runtime
> > cost of checking whether the precondition has been met.
>
> So does the assert.  The "complication" is there (performance
> is a different issue) unless you make it undefined behavior AND
> ignore it.

He did call out the runtime cost, so he was addressing performance which you set aside.

> > The design choice between throwing and undefined behaviour
> > (in release builds, where asserts become no-ops) boils down
> > to the choice of who should check the precondition: the
> > callee, or the caller. Tradition has favoured the caller
> > checking the precondition whenever possible, because the
> > caller has more information and can sometimes check more
> > efficiently (e.g. by eliding the check altogether in cases
> > where it already knows the precondition is met).
>
> And sometimes is less efficient.  For instance, if you are
> populating from StaticVector from list iterators (or any
> non-random access iterators), it's an O(n) check ahead of time
> or a complicated wrapper around a one-at-a-time insert.

That can be handled by dispatching on iterator category.  When the iterators are random access, computing the input range size is O(1), so the insert can be as efficient as possible.  Otherwise, a checking copy operation can be used.

Generally, making it undefined behavior when exceeding capacity is the more efficient approach.  One can always wrap such a class to create one that checks.  The reverse is not true.

> > Note that vector::push_back() throwing on out-of-memory
> > is *not* a counterexample to this - unlike exceeding the
> > capacity of a StaticVector, running out of memory is not a
> > condition that can be checked beforehand by the caller.
>
> Sure it is.  You can duplicate the functionality of exponential
> growth by calling size(), capacity() and reserve() before doing
> push_back().

This really comes down to whether static_vector is considered something more akin to std::array or std::vector.

> I'd really like to see the interface be as close to C++11
> std::vector as possible (other than vector<bool>).

Interface is one thing.  That doesn't address the idea of throwing exceptions when exceeding capacity.  Many wanting to use static_vector in embedded environments don't want exceptions.  The rest of us find them useful.  Still, BOOST_THROW_EXCEPTION provides a means to configure that, but it affects all Boost code; localizing the effect may be desirable.  Matt called for a differently named container as a means to provide the no-exception behavior.  I think a policy class, defaulted to the throwing behavior, is the better approach, despite Jeff's thinking it an unnecessary complication.

_____
Rob Stewart                           robert.stewart_at_[hidden]
Software Engineer                     using std::disclaimer;
Dev Tools & Components
Susquehanna International Group, LLP  http://www.sig.com

________________________________

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.