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 09:26:38

El 18/10/2017 a las 10:36, Thorsten Ottosen via Boost escribió:
> Den 17-10-2017 kl. 14:08 skrev Joaquin M López Muñoz via Boost:
>
>> Any policy can in principle be implemented behind the following 
>> interface:
>>
>> Â Â  struct free_space{std::size_t back,front;};
>> Â Â  free_space query_for_insertion(std::size_t pos,std::size_t n);
>
> n is the current size of the container or the capacity?

n is meant to indicate the number of elements being inserted at once.

> [...]
>
>>> For a FIFO, I think a deque that reuses free segment capacity on one 
>>> side and transfers
>>> it to the other side before allocating new memory would be the best 
>>> choice. Currently
>>> boost::container::deque does not do this, but pull requests are 
>>> welcome ;-) 
>>
>> Or a circular buffer, but devector is the only structure that would 
>> additionally
>> guarantee memory contiguity.
>
> Right. So it may be worth considering. Note as we have discussed 
> previously, that if we shift all the way to the front, a subsequent 
> push_front shifts all the way to the back, and a subsequent push_back 
> shifts all the way to the front. This can in principle go on until the 
> size is again larger than the threshold used for shifting. 

Right, ths is why I suggest rebalance includes some safeguards (minimum 
free space
on each side) to avoid thrashing.

Joaquín M López Muñoz