Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-10-12 12:49:25

Den 12-10-2017 kl. 11:42 skrev degski via Boost:
> On 11 October 2017 at 18:07, Thorsten Ottosen via Boost <
> boost_at_[hidden]> 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<T,A,balanced_resizing_policy>;

template< class T, class A >
using unbalanced_devector = devector<T,A,balanced_resizing_policy>;

The balancing_strategy will then affect

- reserve
- clear
- resize (perhaps)
> 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