[container] static_vector: fixed capacity vector update
*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
On Thu, Jan 17, 2013 at 7:19 AM, Andrew Hundt <athundt@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!
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...
<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]
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
On Fri, Jan 18, 2013 at 4:17 PM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung@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).
Also, I'm not 100% sold on the Strategy template parameter. I think
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. 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
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
On Sun, Jan 20, 2013 at 5:53 PM, Dave Abrahams <dave@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
On Mon, Jan 21, 2013 at 4:39 PM, Andrew Hundt <athundt@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
On Mon, Jan 21, 2013 at 10:45 AM, Olaf van der Spek <ml@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 <ml@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 <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?
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
On 21 January 2013 11:19, Andrew Hundt <athundt@gmail.com> wrote:
On Mon, Jan 21, 2013 at 10:45 AM, Olaf van der Spek <ml@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:nevin@eviloverlord.com> (847) 691-1404
On Mon, Jan 21, 2013 at 10:29 AM, Nevin Liber <nevin@eviloverlord.com>wrote:
On 21 January 2013 11:19, Andrew Hundt <athundt@gmail.com> wrote:
On Mon, Jan 21, 2013 at 10:45 AM, Olaf van der Spek <ml@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
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
On Mon, Jan 21, 2013 at 10:29 AM, Nevin Liber <nevin@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.wulkiewicz@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
On Mon, Jan 21, 2013 at 9:50 PM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung@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
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
On Tue, Jan 22, 2013 at 2:33 PM, Adam Wulkiewicz <adam.wulkiewicz@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
2013/1/22 Olaf van der Spek <ml@vdspek.org>:
On Tue, Jan 22, 2013 at 2:33 PM, Adam Wulkiewicz <adam.wulkiewicz@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
2013/1/22 Olaf van der Spek <ml@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
On Sun, Jan 20, 2013 at 12:59 PM, Andrew Hundt <athundt@gmail.com> wrote:
On Fri, Jan 18, 2013 at 4:17 PM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung@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
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
2013/1/17 Andrew Hundt <athundt@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
2013/1/31 Krzysztof Czainski <1czajnik@gmail.com>:
2013/1/17 Andrew Hundt <athundt@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
2013/2/1 Adam Wulkiewicz <adam.wulkiewicz@gmail.com>
2013/1/31 Krzysztof Czainski <1czajnik@gmail.com>:
2013/1/17 Andrew Hundt <athundt@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
Krzysztof Czainski wrote:
2013/2/1 Adam Wulkiewicz <adam.wulkiewicz@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
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
participants (7)
-
Adam Wulkiewicz -
Andrew Hundt -
Dave Abrahams -
Jeffrey Lee Hellrung, Jr. -
Krzysztof Czainski -
Nevin Liber -
Olaf van der Spek