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 16:22:22

> On Mon, Jan 21, 2013 at 10:29 AM, Nevin Liber <nevin_at_[hidden]>wrote:
>>
>> I see no fundamental difference between your solution and a hybrid vector
>> with a null allocator.
>>
> [...]
>
> I would expect sizeof( static_vector ) < sizeof( hybrid_vector ) (even with
> EBO used for storing the allocator in the latter case), as hybrid_vector
> needs to discriminate between using internal and using external storage.
> Additionally, this will sometimes necessitate more branching and/or
> indirection in hybrid_vector than in static_vector for the same operation.
> Well, really, that's all just a guess, I haven't actually gone and
> implemented each myself. And it's assuming that hybrid_vector< T, N,
> null_allocator<T> > isn't special-cased to behave like a
> static_vector<T,N>, because, at that point, now we're just arguing over
> names.

Thank you Jeffrey, as far as I can tell everything you have said is
quite accurate and reflects my experience from the internal
implementation of static_vector.

On Mon, Jan 21, 2013 at 4:07 PM, Adam Wulkiewicz
<adam.wulkiewicz_at_[hidden]> wrote:
>
> Yes. It would be slower and consume more memory. It wouldn't be suitable for
> people who needs an array replacement instead of vector optimization. A
> replacement allowing to store objects with no default ctors defined or to
> use vector's functionality with this array. So maybe if the name included
> "array" of "buffer" instead of "vector" the reception would be better.
>
> In fact one of static_vector purposes is to be used as a part of the other
> container, not only as internals of the hybrid_vector. I'm using similar
> container in my R-tree and if I was forced to use hybrid_vector I'd rather
> write my own container (which I did).

I also agree with Adam's assessment that static_vector is an array
replacement rather than a vector optimization, and an improved name
would be welcome. There are also a few additional differences I'll
explain below:

With a normal vector or hybrid_vector you could catch bad_alloc, free
up some memory, then try again. With a hybrid_vector + null allocator
that won't help much, and throwing bad_alloc seems wrong since nothing
was heap allocated. Would there be a special exception interface for
the null allocator version? In that case, why is it not separate?

With C++11 I believe it is possible to implement a hybrid_allocator
that stack allocates some memory, then will heap allocate any memory
needed over that limit. That would require no new hybrid_vector,
essentially provide all the same benefits, and we could reuse
boost::container::vector and many other containers again. None of this
infringes upon the usefulness of static_vector.

I see no problem with a progression of tools that provide different guarantees:

C array - must default construct, no C++ interface, fixed capacity
boost::array - must default construct, can't track size, fixed
capacity, always O(N) swap
static_vector - construct elements individually, track size, fixed
capacity, always O(N) swap
hybrid_vector - construct elements individually, track size, variable
capacity, sometimes O(N) swap, sometimes O(1) swap, indirection
overhead. (assuming hybrid_vector cannot be a special allocator
implementation)
vector - construct elements individually, track size, variable
capacity, always O(1) swap

Cheers!
Andrew Hundt