Re: [boost] [container] static_vector: fixed capacity vector update

Subject: Re: [boost] [container] static_vector: fixed capacity vector update
From: Andrew Hundt (athundt_at_[hidden])
Date: 2013-01-21 12:19:33

On Mon, Jan 21, 2013 at 10:45 AM, Olaf van der Spek <ml_at_[hidden]> wrote:
> What happened to hybrid array/vector?

I discussed this a bit in Q1 of the Q&A in my first post in this
thread. static_vector is a combination of fixed capacity vector and
adjustable size array. I believe hybrid_vector would be an
implementation of a vector with small size optimization, possibly with
configuration of what “small size” means. hybrid_vector is being left
as future work for a separate implementation for reasons I discuss
below.

On Mon, Jan 21, 2013 at 10:45 AM, Olaf van der Spek <ml_at_[hidden]> wrote
> A hybrid seems a proper superset of static_vector.

Strictly speaking it's not a proper superset since there are some
fundamental interface differences between a container with a hard size
limit of N vs one with a more flexible size limit. There are some more
details on this topic in Q4 of the Q&A in my first post in this
thread. I've quoted the relevant section here:

> It also seems to be backed by the fundamental interface differences between
> the various classes (static_vector, std::vector, AutoBuffer/hybrid_vector)
> as outlined by Dave Abrahams:
>
> On Wed, Oct 19, 2011 at 1:26 PM, Dave Abrahams <dave_at_[hidden]> wrote:
>> I see a container that can never store more than N items, for some
>> reasonably small N, as fundamentally, semantically different from one
>> that is highly likely to be able to store any M items you have to deal
>> with, and for which you can't determine a hard limit N ahead of time
>> (no, max_size() doesn't count—that's typically just
>> numeric_limits<size_t>::max()).  I grant you that we don't have a very
>> strict way of expressing this difference in a specification, but I think
>> that's just missing.  I wouldn't, except in very special circumstances,
>> consider one of those containers to be a suitable replacement for the
>> other, despite the similarity of the specification text.  Would you?

The limitations of static_vector also provides some of its strengths.
For instance, an individual call to push back() will never be an O(N)
operation due to reallocation which is important when latency is
critical. Also, for real time systems allocation is not desirable and
hybrid_vector would require much more care to avoid allocations than
static_vector will.

There are also some properties of hybrid_vector that place it outside
the scope of static_vector. For instance, hybrid_vector's swap() could
sometimes be O(1) for large N, and O(N) for small N, while
static_vector always occupies the small N case. Of course you could
read this as O(1) for small N since N is a fixed compile time value,
but hopefully you can appreciate the measurable effect it will have on
real performance when calling swap().

Ultimately, I think static_vector and hybrid_vector make the most
sense as two separate classes.

static_vector may be useful to implement hybrid_vector, so all is not
lost. To avoid hijacking this thread a new thread may be good for
discussion of hybrid_vector implementation details if many are
interested in that topic.

Cheers!
Andrew Hundt