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