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

Subject: [boost] [container] static_vector: fixed capacity vector update
From: Andrew Hundt (athundt_at_[hidden])
Date: 2013-01-17 10:19:55

*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 <zeratul976_at_[hidden]>
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 <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?

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