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

[Andrew Hundt]

*static_vector is a hybrid of boost::container::vector and boost::array
with fixed capacity.

Adam Wulkiewicz and I have updated static_vector with improvements from the
list discussion and reorganized it for possible inclusion into
boost.container.

Overview:
static_vector is a sequence container with contiguous storage that can
change in size like boost::container::vector. It also includes static
allocation, low overhead, and fixed capacity similar to boost::array.

Synopsis:
template*
*<*
* typename Value, *
* std::size_t Capacity, *
* typename Strategy =
strategy::def<https://svn.boost.org/svn/boost/sandbox/static_vector/doc/html/static_vector/reference.html#structboost_1_1container_1_1strategy_1_1def>
<Value> *
*>*
*class static_vector;

Example:
// static_vector of ints, fixed capacity: 3
boost::container::static_vector<int,3> three; // size: 0

three.push_back(1); // size: 1
three.push_back(2); // size: 2
three.push_back(3); // size: 3

//three.reserve(4); // no effect, fixed capacity: 3
//three.push_back(3); // size: 4, undefined behavior

three.pop_back(); // size: 2
three.shrink_to_fit(); // no effect, fixed capacity: 3

Documentation:
https://svn.boost.org/svn/boost/sandbox/static_vector/doc/html/index.html

Source:
https://svn.boost.org/svn/boost/sandbox/static_vector/

Discussions from boost.devel archive:
http://goo.gl/PKEpB [google groups]

Changes:
- C++11 support
- moved to boost::container namespace
- strategy based error handling (“strategy” is aka “policy”)
- bounds checks are asserts by default but can be switched to exceptions
- memory is uninitialized until objects are inserted
- internal size is currently the same as Strategy::size_type
- expanded documentation and unit tests
- optimizations based on type traits
- boost::interprocess support

------------------------------------------------
------------------------------------------------
Major questions from prior list discussions and the related design
decisions:

------------------------
Q1:
static_vector design
*a) combination of fixed capacity vector and adjustable size array
b) vector with small size optimization, possibly with configuration of what
“small size” means.

A1:
(a) is implemented by static_vector, leaving the (b) as future work for a
separate class.

------------------------
Q2:
Is it best to implement push_back() and similar functions with or without
bounds check?

Main use cases:
*a) no bounds check on each insertion because it is an undesirable use of
resources
b) vector emulation where static_vector is a drop in replacement and
optimization so bounds checking is essential to minimize the amount of code
that must be changed.

A2:
(a) no bounds check is the default for static_vector. A vector emulation
strategy can be implemented for (b).

------------------------
Q3:
Should a failed bounds check trigger an assertion or an exception?

Main use cases:
a) bounds check is too much overhead, but assert() allows for testing in
debug mode
b) vector emulation, so bad_alloc should be thrown when the capacity is
exceeded
c) exceptions are desired when bounds checking, but bad_alloc would cause
the wrong behavior because freeing up memory will not allow the possibility
of a larger capacity as it would in a vector.

A3:
(a) failed bounds checks trigger an assertion, and the user can implement
the necessary strategy and traits to achieve (b) or (c).

------------------------------------------------
------------------------------------------------
New/Unanswered Questions:
------------------------
Q4:
Should the current static_vector actually be in the detail namespace, with
policy specializations providing the actual interface to several classes
with different desired functionality?

This could be similar to what was suggested by Nate Ridge:

On Sat, Oct 15, 2011 at 5:16 PM, Nathan Ridge <zerat...@hotmail.com>
wrote:
> 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;

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 <da...@boostpro.com> 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?

This would mean that the official interfaces can be specific to various
common use cases and a bit simpler. An additional benefit here is that
simpler interfaces are more welcoming to a wider range of developers.

On the other hand, the current design makes the official interface
configurable so they could customize it without being as concerned about
changes in the detail implementation. If everyone will want something
different for their specific use case, leaving the design as is may make
the most sense. Furthermore, a reasonable default provides a simpler
interface while permitting advanced configuration for those who need it.

------------------------
Q5:
Should the static_vector Strategy concept
(a) remain as is
(b) add the Capacity as an additional template parameter
(c) permit Standard Library Allocators as a strategy


Currently, the default traits assume that the Strategy defines types
normally defined by Allocator and provides a capacity check failure
callback. Also, a different strategy and traits specialization can be used
to configure the class as desired, such as modifying the size_type based on
the Capacity. Consequently, leaving the Strategy as is (a) remains fairly
reasonable.

Adding an additional Capacity template parameter (b) to the Strategy
concept would take the Strategy further from the Allocator concept, but
ensure configuration of size_type based on the capacity is easy and
consistent.

We believe (c) does not make sense despite allowing static_vector to be
more compatible with vector due to the fundamental interface differences
discussed in Q4. Option (c) makes more sense for a class like
AutoBuffer/hybrid_vector than it does for static_vector.

Thus, the question ultimately becomes one concerning the tradeoff between
options (a) and (b).

------------------------
Q6:
Should static_vector_traits be part of the public interface or remain in
the detail namespace?

This would make some of the functionality in Q5a part of the official
interface, but restrict future changes. In Boost.Container traits are
defined in the detail namespace so we were hoping to find out the reasoning
for this choice.

The direction of the design discussion for Q4 could also make this a moot
point.

------------------------
Q7:
Does static_vector provide significant benefits over
boost::container::vector with a stack Allocator template parameter?

This has been discussed previously and we believe the answer is yes for the
reasons outlined in Q4 and the documentation, but we wanted to bring it up
again in case someone wanted to play devil’s advocate.

------------------------


That covers all the basics of the updated static_vector implementation and
some of the biggest outstanding design questions. We appreciate any and all
questions, design ideas, or issues you can come up with, so fire away. :-)

Regards,
Andrew Hundt*
Adam Wulkiewicz

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Jeffrey Lee Hellrung, Jr.]

On Thu, Jan 17, 2013 at 7:19 AM, Andrew Hundt <ath...@gmail.com> wrote:

> *static_vector is a hybrid of boost::container::vector and boost::array
> with fixed capacity.
>
> Adam Wulkiewicz and I have updated static_vector with improvements from the
> list discussion and reorganized it for possible inclusion into
> boost.container.
>

This is encouraging!

Great, seems almost simple enough. I say "almost" because, IMHO, we
shouldn't try *too* hard to make static_vector a drop-in replacement for
vector. Make the interface common where it makes sense, but reserve and
shrink_to_fit shouldn't be part of the interface. It would just confuse me
if I saw a reserve or shrink_to_fit method call on a static_vector in real
code.

Changes:
> - C++11 support
>

Please elaborate.

> - moved to boost::container namespace
> - strategy based error handling (“strategy” is aka “policy”)
>

The documentation is not the prettiest right now, which is fine, but one
key omission is a Strategy concept specification (at least, I didn't see
one).

Also, I'm not 100% sold on the Strategy template parameter. I think there's
something to be said for simplicity, and the simplest implementation would
have just 2 template parameters and assert on any bounds violations; if you
want to throw, use, say, a free function push_back_and_throw_on_error. At
least, that's what I'd say is an alternative design.

- bounds checks are asserts by default but can be switched to exceptions
>

Is this true for static_vector::at as well, or does that throw regardless
as with std::vector?

> - memory is uninitialized until objects are inserted
>

Hmmm...this is a change?! I would think this is a correctness requirement :/

> - internal size is currently the same as Strategy::size_type
> - expanded documentation and unit tests
> - optimizations based on type traits
>

Please elaborate.


> - boost::interprocess support
>

Please elaborate.

[...snip Q&A's, design discussion...]

- Jeff

[Andrew Hundt]

On Fri, Jan 18, 2013 at 4:17 PM, Jeffrey Lee Hellrung, Jr.
<jeffrey....@gmail.com> wrote:
>
> This is encouraging!

Thanks!

> Great, seems almost simple enough. I say "almost" because, IMHO, we
> shouldn't try *too* hard to make static_vector a drop-in replacement for
> vector. Make the interface common where it makes sense, but reserve and
> shrink_to_fit shouldn't be part of the interface. It would just confuse me
> if I saw a reserve or shrink_to_fit method call on a static_vector in real
> code.

This may make sense to do. It could alternately be #ifdef'd out in some
BOOST_CONTAINER_VECTOR_COMPATIBILITY mode that enables shrink_to_fit()
for those that are clients of template code they cant change, but could
specify the container type. Perhaps that isn't worthwhile either and
users should just remove their shrink_to_fit calls if they want to use
static_vector.

> > Changes:
> > - C++11 support
>
> Please elaborate.

It supports all the C++11 member functions, such as move semantics and
emplace() that boost::container::vector supports. Allocators are the
obvious exception in addition to some runtime performance degradation
in cases such as swap() because a simple pointer swap is not possible.

In case you were concerned, everything is also set up for C++03.

> The documentation is not the prettiest right now, which is fine

I agree that the documentation wording, formatting, and examples still
need improvement.

> one key omission is a Strategy concept specification (at least, I didn't
see
> one).

The Strategy concept is defined in the code using Boost.concept_check.
Adding it to the documentation depends on how the discussion
immediately below and in Q4 of my Q&A goes since it wouldn't make
sense to document the strategy if it is not part of the public API.

> Also, I'm not 100% sold on the Strategy template parameter. I think
there's
> something to be said for simplicity, and the simplest implementation would
> have just 2 template parameters and assert on any bounds violations; if
you
> want to throw, use, say, a free function push_back_and_throw_on_error. At
> least, that's what I'd say is an alternative design.

I concur, while I'm fairly happy with the current code I too am not
100% sold on the Strategy. I wrote more detail in Q4 of the Q&A
section of my original post. The proposed alternative is putting the
current version into the detail namespace and defining one or more
publicly available interfaces using partial specializations in which
the strategy is fully defined.

> > - bounds checks are asserts by default but can be switched to
exceptions
>
> Is this true for static_vector::at as well, or does that throw regardless
> as with std::vector?

static_vector::at() throws in the same manner as
boost::container::vector::at() by default. It is also possible to
disable exceptions so in that case there is an assert() when indexed
out of bounds. Perhaps the case where exceptions are disabled should
use BOOST_VERIFY so it triggers in release mode too for at()?

> > - memory is uninitialized until objects are inserted
>
> Hmmm...this is a change?! I would think this is a correctness requirement
:/

The original version was boost::array with size so the behavior was
much more understandable. I agree that the new behavior is much better
and that's why it has been changed. :-)

> > - internal size is currently the same as Strategy::size_type
> > - expanded documentation and unit tests
> > - optimizations based on type traits
>
> Please elaborate.

This is related to Q5 of the Q&A in my original post. People on the
list expressed the desire to make the value tracking the vector size
configurable, so if the capacity was 20 you could use uint8_t, or if
it was 20000 you could use uint16_t instead of the default, which is
std::size_t. This configuration can be accomplished by modifying the
strategy.

The type traits optimizations are the same ones provided by
boost::container::vector, such as using memcpy/memmove for POD types
where appropriate, and selecting algorithms based on traits indicating
if an iterator is a RandomAccessIterator, ForwardIterator, etc.

> > - boost::interprocess support
>
> Please elaborate.

Since the pointer type is configurable you can initialize
static_vector in shared memory with the specialized pointers
interprocess provides. There is also some example code that uses a
static_vector with boost::interprocess here: http://goo.gl/oUyj7

Cheers!

Cheers!
Andrew Hundt

[Dave Abrahams]

on Sun Jan 20 2013, Andrew Hundt <athundt-AT-gmail.com> wrote:

> The Strategy concept is defined in the code using Boost.concept_check.

Just to be clear, a concept has semantics as well as syntactic
requirements, and you have to spell the semantics out in documentation.
You can't do it all using Boost.concept_check (or any meaningful
language feature, either).

--
Dave Abrahams
BoostPro Computing Software Development Training
http://www.boostpro.com Clang/LLVM/EDG Compilers C++ Boost

[Andrew Hundt]

On Sun, Jan 20, 2013 at 5:53 PM, Dave Abrahams <da...@boostpro.com> wrote:

>
> on Sun Jan 20 2013, Andrew Hundt <athundt-AT-gmail.com> wrote:
>
> > The Strategy concept is defined in the code using Boost.concept_check.
>
> Just to be clear, a concept has semantics as well as syntactic
> requirements, and you have to spell the semantics out in documentation.
> You can't do it all using Boost.concept_check (or any meaningful
> language feature, either).

Thanks, you are correct. Allow me to clarify my statement. One of the open
questions is "should the strategy be a user facing feature" so there is not
documentation for the Strategy yet, but I plan to create it if the question
is answered affirmatively. I mentioned the concept check as an existing
first step in that direction.

Cheers!
Andrew Hundt

[Olaf van der Spek]

On Mon, Jan 21, 2013 at 4:39 PM, Andrew Hundt <ath...@gmail.com> wrote:
> Thanks, you are correct. Allow me to clarify my statement. One of the open
> questions is "should the strategy be a user facing feature" so there is not
> documentation for the Strategy yet, but I plan to create it if the question
> is answered affirmatively. I mentioned the concept check as an existing
> first step in that direction.

What happened to hybrid array/vector?
A hybrid seems a proper superset of static_vector.

--
Olaf

[Andrew Hundt]

On Mon, Jan 21, 2013 at 10:45 AM, Olaf van der Spek <m...@vdspek.org> 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 <m...@vdspek.org> 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 <da...@boostpro.com> 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

[Nevin Liber]

On 21 January 2013 11:19, Andrew Hundt <ath...@gmail.com> wrote:

> On Mon, Jan 21, 2013 at 10:45 AM, Olaf van der Spek <m...@vdspek.org> wrote:
> > What happened to hybrid array/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.

I see no fundamental difference between your solution and a hybrid vector
with a null allocator.

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.

Neither is there one in a hybrid vector with a null allocator.

> Also, for real time systems allocation is not desirable and
> hybrid_vector would require much more care to avoid allocations than
> static_vector will.
>

I need correctness first. If I can live with a fixed upper bound, I can
use a null allocator.

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

And you see this as an *advantage* for your solution? For swap, the hybrid
vector is never any worse and sometimes better than your solution.

Ultimately, I think static_vector and hybrid_vector make the most

> sense as two separate classes.
>

Which is what it boils down to. The rest is just rationalization.

I see your solution as a subset of hybrid vector, and if hybrid vector
exists, I don't see any reason to use yours over it.
--
Nevin ":-)" Liber <mailto:ne...@eviloverlord.com> (847) 691-1404

[Jeffrey Lee Hellrung, Jr.]

On Mon, Jan 21, 2013 at 10:29 AM, Nevin Liber <ne...@eviloverlord.com>wrote:

> On 21 January 2013 11:19, Andrew Hundt <ath...@gmail.com> wrote:
>
> > On Mon, Jan 21, 2013 at 10:45 AM, Olaf van der Spek <m...@vdspek.org>
> wrote:
> > > What happened to hybrid array/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.
>
>
> 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.

- Jeff

[Adam Wulkiewicz]

Jeffrey Lee Hellrung, Jr. wrote:
> 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.

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

Regards,
Adam

[Andrew Hundt]

> On Mon, Jan 21, 2013 at 10:29 AM, Nevin Liber <ne...@eviloverlord.com>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.wu...@gmail.com> 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

[Jeffrey Lee Hellrung, Jr.]

On Sun, Jan 20, 2013 at 12:59 PM, Andrew Hundt <ath...@gmail.com> wrote:

> On Fri, Jan 18, 2013 at 4:17 PM, Jeffrey Lee Hellrung, Jr.
> <jeffrey....@gmail.com> wrote:
> >
> > This is encouraging!
>
> Thanks!
>
> > Great, seems almost simple enough. I say "almost" because, IMHO, we
> > shouldn't try *too* hard to make static_vector a drop-in replacement for
> > vector. Make the interface common where it makes sense, but reserve and
> > shrink_to_fit shouldn't be part of the interface. It would just confuse
> me
> > if I saw a reserve or shrink_to_fit method call on a static_vector in
> real
> > code.
>
> This may make sense to do. It could alternately be #ifdef'd out in some
> BOOST_CONTAINER_VECTOR_COMPATIBILITY mode that enables shrink_to_fit()
> for those that are clients of template code they cant change, but could
> specify the container type. Perhaps that isn't worthwhile either and
> users should just remove their shrink_to_fit calls if they want to use
> static_vector.
>

I would argue for the latter. As I think Dave expressed, I don't see this
as a general drop-in replacement for std::vector (and I realize it was
never necessarily marketed as such), rather its a drop-in replacement for
certain use cases that presently might use std::vector but probably
shouldn't.

> > Changes:
> > > - C++11 support
> >
> > Please elaborate.
>
> It supports all the C++11 member functions, such as move semantics and
> emplace() that boost::container::vector supports. Allocators are the
> obvious exception in addition to some runtime performance degradation
> in cases such as swap() because a simple pointer swap is not possible.
>
> In case you were concerned, everything is also set up for C++03.
>

Good. I'd encourage making it Boost.Move-compatible as well.

> The documentation is not the prettiest right now, which is fine
>
> I agree that the documentation wording, formatting, and examples still
> need improvement.
>
> > one key omission is a Strategy concept specification (at least, I didn't
> see
> > one).
>
> The Strategy concept is defined in the code using Boost.concept_check.
> Adding it to the documentation depends on how the discussion
> immediately below and in Q4 of my Q&A goes since it wouldn't make
> sense to document the strategy if it is not part of the public API.
>
> > Also, I'm not 100% sold on the Strategy template parameter. I think
> there's
> > something to be said for simplicity, and the simplest implementation
> would
> > have just 2 template parameters and assert on any bounds violations; if
> you
> > want to throw, use, say, a free function push_back_and_throw_on_error. At
> > least, that's what I'd say is an alternative design.
>
> I concur, while I'm fairly happy with the current code I too am not
> 100% sold on the Strategy. I wrote more detail in Q4 of the Q&A
> section of my original post. The proposed alternative is putting the
> current version into the detail namespace and defining one or more
> publicly available interfaces using partial specializations in which
> the strategy is fully defined.
>

Or just offer one variant, period, which asserts on bounds errors. I'd lean
toward that but I guess I might have a different philosophy on throwing
than others (I'd say, by default, only provide a throwing interface when
preconditions can't be reasonable checked by the calling code).

> > - bounds checks are asserts by default but can be switched to
> exceptions
> >
> > Is this true for static_vector::at as well, or does that throw regardless
> > as with std::vector?
>
> static_vector::at() throws in the same manner as
> boost::container::vector::at() by default. It is also possible to
> disable exceptions so in that case there is an assert() when indexed
> out of bounds. Perhaps the case where exceptions are disabled should
> use BOOST_VERIFY so it triggers in release mode too for at()?
>

Eh, I don't really care; does anyone actually use std::vector::at in
practice? Serious question (I haven't seen it yet, but I haven't been doing
software development professionally for very long, either).

> > - memory is uninitialized until objects are inserted
> >
> > Hmmm...this is a change?! I would think this is a correctness requirement
> :/
>
> The original version was boost::array with size so the behavior was
> much more understandable. I agree that the new behavior is much better
> and that's why it has been changed. :-)
>

Make sense.

[...]

> > > - optimizations based on type traits
> >
> > Please elaborate.
>

[...]

> The type traits optimizations are the same ones provided by
> boost::container::vector, such as using memcpy/memmove for POD types
> where appropriate, and selecting algorithms based on traits indicating
> if an iterator is a RandomAccessIterator, ForwardIterator, etc.
>

Okay.

> > > - boost::interprocess support
> >
> > Please elaborate.
>
> Since the pointer type is configurable you can initialize
> static_vector in shared memory with the specialized pointers
> interprocess provides. There is also some example code that uses a
> static_vector with boost::interprocess here: http://goo.gl/oUyj7
>

Interesting. I suppose the pointer type is indirectly specified by the
Strategy?

- Jeff

[Olaf van der Spek]

On Mon, Jan 21, 2013 at 9:50 PM, Jeffrey Lee Hellrung, Jr.
<jeffrey....@gmail.com> wrote:
> 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.

Given that hybrid functionality is desired too I think it makes sense
to provide it.
Then, if static vector really can't be provided efficiently as a case
of hybrid_vector could you implement static vector.

> I would expect sizeof( static_vector ) < sizeof( hybrid_vector )

> as hybrid_vector
> needs to discriminate between using internal and using external storage.

That's just a single bit.

Olaf

[Adam Wulkiewicz]

Olaf van der Spek wrote:
>> I would expect sizeof( static_vector ) < sizeof( hybrid_vector )
>

>> as hybrid_vector
>> needs to discriminate between using internal and using external storage.
>
> That's just a single bit.

No, because static part will be created on stack and if external storage
was created by non-std allocator then hybrid_vector would have a full
set of additional members.

Regards,
Adam

[Olaf van der Spek]

On Tue, Jan 22, 2013 at 2:33 PM, Adam Wulkiewicz
<adam.wu...@gmail.com> wrote:
>> That's just a single bit.
>
>
> No, because static part will be created on stack and if external storage was
> created by non-std allocator then hybrid_vector would have a full set of
> additional members.

You need either those members or the static storage, not both at the
same time, so they could share the same space.

--
Olaf

[Adam Wulkiewicz]

2013/1/22 Olaf van der Spek <m...@vdspek.org>:

> On Tue, Jan 22, 2013 at 2:33 PM, Adam Wulkiewicz
> <adam.wu...@gmail.com> wrote:
>>> That's just a single bit.
>>
>>
>> No, because static part will be created on stack and if external storage was
>> created by non-std allocator then hybrid_vector would have a full set of
>> additional members.
>
> You need either those members or the static storage, not both at the
> same time, so they could share the same space.

Yes, then additional creation and move of those members would be needed while
moving to the new memory but this is probably not significant.

On the other hand we could store the whole static_vector or vector in
the storage
inside the hybrid_vector. We couldn't use size/capacity to store this
flag bit but I'm
not so sure if I'd do it anyway because it would decrease the max size
of the container.
And again creation and move of a vector would be required like in the
previous case,
this time with allocator which is stored inside.

Regards,
Adam

[Adam Wulkiewicz]

2013/1/22 Olaf van der Spek <m...@vdspek.org>:

>
> Given that hybrid functionality is desired too I think it makes sense
> to provide it.
> Then, if static vector really can't be provided efficiently as a case
> of hybrid_vector could you implement static vector.

To implement a hybrid_vector fast as a static_vector for
null_allocator one should provide two versions of algorithms and
members (additional allocator object). The default one would work for
arbitrary allocators (hybrid_vector), the specialized one for
null_allocator, not checking unnecessary conditions. It would work
exactly like current implementation of the static_vector. The result
would be 2 containers with the interface of hybrid_vector.
This isn't much different than what we're proposing. In fact one of
our questions was: should the static_vector be moved to detail
namespace?

Regards,
Adam

[Andrew Hundt]

> Good. I'd encourage making it Boost.Move-compatible as well.

It supports Boost.Move.

> > I concur, while I'm fairly happy with the current code I too am not
> > 100% sold on the Strategy. I wrote more detail in Q4 of the Q&A
> > section of my original post. The proposed alternative is putting the
> > current version into the detail namespace and defining one or more
> > publicly available interfaces using partial specializations in which
> > the strategy is fully defined.
> >
>
> Or just offer one variant, period, which asserts on bounds errors. I'd lean
> toward that but I guess I might have a different philosophy on throwing
> than others (I'd say, by default, only provide a throwing interface when
> preconditions can't be reasonable checked by the calling code).

We could put everything into detail and only have one variant as the
public interface. However demand was so high for different behaviors
in different situations during the original discussion that we made it
strategy/policy defined. Even if it isn't part of the public
interface, it might be reasonable to leave them in for those that want
to mess with some of the internals a bit for their use case.

> > > - bounds checks are asserts by default but can be switched to
> > exceptions
> > >
> > > Is this true for static_vector::at as well, or does that throw regardless
> > > as with std::vector?
> >
> > static_vector::at() throws in the same manner as
> > boost::container::vector::at() by default. It is also possible to
> > disable exceptions so in that case there is an assert() when indexed
> > out of bounds. Perhaps the case where exceptions are disabled should
> > use BOOST_VERIFY so it triggers in release mode too for at()?
> >
>
> Eh, I don't really care;

Now that I think about it I believe when exceptions are disabled
BOOST_THROW_EXCEPTION calls a function that is supposed to deal with
whatever went wrong if possible, and that may be the most appropriate
behavior in that case.

> does anyone actually use std::vector::at in
> practice? Serious question (I haven't seen it yet, but I haven't been doing
> software development professionally for very long, either).

I haven't seen at() used but unfortunately it should still work.

> Interesting. I suppose the pointer type is indirectly specified by the
> Strategy?

Yes, the strategy defines the pointer type similarly to how an allocator does.

Cheers!
Andrew Hundt

[Krzysztof Czainski]

2013/1/17 Andrew Hundt <ath...@gmail.com>

> *static_vector is a hybrid of boost::container::vector and boost::array
> with fixed capacity.
>
> Adam Wulkiewicz and I have updated static_vector with improvements from the
> list discussion and reorganized it for possible inclusion into
> boost.container.
>
> Overview:
> static_vector is a sequence container with contiguous storage that can
> change in size like boost::container::vector. It also includes static
> allocation, low overhead, and fixed capacity similar to boost::array.
>

Hello,
Thanks for working on static_vector, I'm already using it.

Everything works, with a little fix I needed. Here's the problem
(disclamer: tested with a more complicated example, not the one below):

static_vector<int,3> v;
v.emplace_back(); // compile time error

My fix is adding an overload for static_vector_detail::construct, patch
attached.

Cheers,
Kris

[Adam Wulkiewicz]

2013/1/31 Krzysztof Czainski <1cza...@gmail.com>:
> 2013/1/17 Andrew Hundt <ath...@gmail.com>

>
> Hello,
> Thanks for working on static_vector, I'm already using it.
>
> Everything works, with a little fix I needed. Here's the problem
> (disclamer: tested with a more complicated example, not the one below):
>
> static_vector<int,3> v;
> v.emplace_back(); // compile time error
>
> My fix is adding an overload for static_vector_detail::construct, patch
> attached.

Ok, thanks. It's fixed now.

Furthermore I'd like to share some news.

We've decided to slightly change the character of this container and
highlight it's connection with array. Therefore we changed it's name
to varray (variable-size array). The implementation with "Strategy"
template parameter was moved to container_detail namespace. Exposed
class takes 2 template parameters, exactly like boost::array does.

boost::container::varray<T, N> va;

It may be found here:
http://svn.boost.org/svn/boost/sandbox/varray/

Regards,
Adam

[Krzysztof Czainski]

2013/2/1 Adam Wulkiewicz <adam.wu...@gmail.com>

> 2013/1/31 Krzysztof Czainski <1cza...@gmail.com>:
> > 2013/1/17 Andrew Hundt <ath...@gmail.com>
> >
> > Hello,
> > Thanks for working on static_vector, I'm already using it.
> >
> > Everything works, with a little fix I needed. Here's the problem
> > (disclamer: tested with a more complicated example, not the one below):
> >
> > static_vector<int,3> v;
> > v.emplace_back(); // compile time error
> >
> > My fix is adding an overload for static_vector_detail::construct, patch
> > attached.
>
> Ok, thanks. It's fixed now.
>

Thanks.

Furthermore I'd like to share some news.
>
> We've decided to slightly change the character of this container and
> highlight it's connection with array. Therefore we changed it's name
> to varray (variable-size array). The implementation with "Strategy"
> template parameter was moved to container_detail namespace. Exposed
> class takes 2 template parameters, exactly like boost::array does.
>
> boost::container::varray<T, N> va;
>
> It may be found here:
> http://svn.boost.org/svn/boost/sandbox/varray/

For the record, I'd rather the strategy was public. I can imagine using
static_vector in a few places in the same project with different strategies:
1) In most places I'd probably use the default strategy.
2) At the time of optimizations I might want to disable all checking
(asserts) only for one specific use. In practice we don't create separate
debug/release builds, since we need the debug version to be fast enough
anyway, and in some places this means disabling asserts.
3) In some cases temporary cases I might want logic errors to be thrown, so
that the crash of an early version of one module doesn't crash the whole
system.

Also, I prefer the name static_vector, but that's just my personal approach
- maybe I just got used to it ;-)

Although, now that I think of 0-arg emplace_back(), that doesn't
value-initialize types with a trivial constructor - does vector work like
this too? If not, then it's a good argument towards the name varray ;-)

Cheers,
Kris

[Adam Wulkiewicz]

Krzysztof Czainski wrote:
> 2013/2/1 Adam Wulkiewicz <adam.wu...@gmail.com>

> Furthermore I'd like to share some news.
>>
>> We've decided to slightly change the character of this container and
>> highlight it's connection with array. Therefore we changed it's name
>> to varray (variable-size array). The implementation with "Strategy"
>> template parameter was moved to container_detail namespace. Exposed
>> class takes 2 template parameters, exactly like boost::array does.
>>
>> boost::container::varray<T, N> va;

...

>
>
> For the record, I'd rather the strategy was public. I can imagine using
> static_vector in a few places in the same project with different strategies:
> 1) In most places I'd probably use the default strategy.
> 2) At the time of optimizations I might want to disable all checking
> (asserts) only for one specific use. In practice we don't create separate
> debug/release builds, since we need the debug version to be fast enough
> anyway, and in some places this means disabling asserts.
> 3) In some cases temporary cases I might want logic errors to be thrown, so
> that the crash of an early version of one module doesn't crash the whole
> system.
>
> Also, I prefer the name static_vector, but that's just my personal approach
> - maybe I just got used to it ;-)

After the release of 1.53 when everybody has more free time we should
probably do some voting.

> Although, now that I think of 0-arg emplace_back(), that doesn't
> value-initialize types with a trivial constructor - does vector work like
> this too? If not, then it's a good argument towards the name varray ;-)

Yes, now elements' default ctors aren't called when they're of type with
trivial ctor. This is the case when using:
- varray(n)
- resize(n)
- emplace_back()

This of course may be changed in the future or it may be tweakable with
traits.

Regards,
Adam

[Adam Wulkiewicz]

Krzysztof Czainski wrote:
> Although, now that I think of 0-arg emplace_back(), that doesn't
> value-initialize types with a trivial constructor - does vector work like
> this too? If not, then it's a good argument towards the name varray ;-)

After some thinking we decided that elements should be initialized
because this is what the user probably expects. This is true for all
varray methods/ctors constructing values using default ctor. Please
check the newest version.
In the future we may allow disabling it e.g. by use of traits.

Regards,
Adam