Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at