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