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:37:39

El 18/10/2017 a las 16:28, Joaquin M López Muñoz escribió:
> 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. 

Writing this has led me to realize that a generic growing/insertion 
policy also
needs a member function to indicate what to do on erasure:

 Â  struct free_space{std::size_t back,front;};
 Â  free_space query_for_insertion(std::size_t pos,std::size_t n);
 Â  free_space query_for_erasure(std::size_t pos,std::size_t n);

(clear would be the case where erasure happens at begin() and n==size()).

Joaquín M López Muñoz