*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@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 <dave@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