Re: [boost] [devector] optimum growing/insertion policy

Subject: Re: [boost] [devector] optimum growing/insertion policy
From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2017-10-18 14:28:06

El 18/10/2017 a las 15:21, Thorsten Ottosen via Boost escribió:
> Den 18-10-2017 kl. 15:07 skrev Joaquin M López Muñoz via Boost:
>> El 18/10/2017 a las 13:52, Thorsten Ottosen via Boost escribió:
>
>>> We need an additional interface function for handling clear, don't we?
>>
>> Umm... yes, we need something for clear(), right. In the rest of 
>> erasure scenarios
>> there's an obvious way to give free space back to both ends.
>
> Obvious as in "erase never moves elements within the buffer"? or did 
> you mean, leave front_free_capacity and back_free_capacity as they 
> would for any call to erase?
>

Ummm... I wrote too fast, the answer is not obvious :-) Say our devector 
looks like

FF···FMM···MBB···B

and we want to erase MM···M. We have these three options:

1. Move BB...B right after FF···F, so that only back free capacity grows.
2. Move FF···F right before BB···B, so that only front free capacity grows.
3. Make FF···F meet BB···B at a middle position within the buffer so that
the ratio between back and front free capacity is kept.

In my opinion, the best option is to do 1 or 2 depending on which of the
two subsequences BB···B and FF···F is smaller (respectively), which 
minimizes
the number of movements. This is consistent with the expected behavior for
push_[back|front]. 3 always implies more movements.

Joaquín M López Muñoz