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

Subject: Re: [boost] [devector] optimum growing/insertion policy
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-10-26 15:08:48

Den 18-10-2017 kl. 16:37 skrev Joaquin M López Muñoz via Boost:
> 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. 

Agreed, in a move-minimizing policy, one would want erase to do the 
least work.

> 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()).

But the policy does not know size() unless we pass it that too.

kind regards

Thorsten