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
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
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk