Den 12-10-2017 kl. 11:42 skrev degski via Boost:
On 11 October 2017 at 18:07, Thorsten Ottosen via Boost < boost@lists.boost.org> wrote:
Sure, and we have certainly floated various ideas. I leaning towards the following principles:
A. insert never allocates if it can avoid it B. insert, when allocation is needed, balances the free capacity C. a push at either end by default does not balance the free capacity
That is how I would do it as well, relocation should re-balance, though.
That would mean a series of push_back or push_front creates more and more free space in the end that is not used, wouldn't it?
D. in certain situations push at either end may choose to balance the free
capacity, say of the free capacity in the opposite end is larger than size() or perhaps larger or equal to size().
resize and reserve are also candidates for having such a consideration. One could imagine resize_back/resize_front/reserve_back/reserve_front and let resize and reserve always re-balance (when appropriate).
Yeah. There is a better design screaming to get out here. The whole
discussion of reserve/capacity/clear has made me wonder if we can
actually do it all with one class. Said differently, we need a policy.
I can see two obvious use cases of devector:
A. a better vector (many push_backs, but also erase and inserts)
B. the default container for flat_set/flat_map
The differences belong to GrowthPolicy. (I think I like the name
ResizingPolicy a little better.)
Say we had this:
struct balanced_resizing_policy {
static balancing_strategy = balancing_strategy::balance_middle;
static size_type new_capacity(size_type);
static bool should_shrink(size_type, size_type, size_type);
};
struct vector_resizing_policy {
static balancing_strategy = balancing_strategy::balance_left;
static size_type new_capacity(size_type);
static bool should_shrink(size_type, size_type, size_type);
};
Then we could have
template< class T, class A >
using balanced_devector = devector
The only pointer is the end pointer, so push_back can be fast. Since one doesn't need the pointer to the allocated memory all the time, it can be calculated on the fly, when needed. For iteration there is hardly a penalty (one subtraction, for begin()), but for indexed access there *is* a penalty (of one subtraction per access), so to be avoided (with iterators).
I see. Clever. kind regards Thorsten