Den 15-10-2017 kl. 17:59 skrev Joaquin M López Muñoz via Boost:
El 15/10/2017 a las 15:50, thorsten.ottosen via Boost escribió:
hi Joaquin,
Thanks for this. Some comments below.
Facts
— How do you get that number ? I would say we save Incur 1/2 * size movements on average for shifting to the end with free space.
The number follows from: assume right insertion is at position N, that means that under normal conditions (there's back free capacity) we need to make size()-N movements to the right. If instead of that we shift to the left the resulting number of movements is N, so the penalty for taking the "wrong" decision is the difference N - (size()-N) = 2*N - size(). Did I explain myself now?
yes, I somehow got confused.
Description of resulting policy
The idea of keeping track of left right insertions also interesting. It does assume additionally that the insert pattern in the future is the same as in the past, right?
Did you see this question?
I think in the case where the user has called reserve, it’s a little problematic that insert may allocate anyway. That is, for many uses there is no infinitely growing sequence .
And this one? I'm still not sure we want to allocate on insert before the buffer is full.
The right_ member can become larger than size if elects are added to the right and removed from the left, not sure what to do about that.
Yes, you're right. right_ becoming greater thatn size() can't happen under the ever- growing assumtion, but it certainly can in the real world.
minor remark: If one goes with this approach, I think the member should be left_ so as to not penalize normal push_back.
Let's slightly adjust the policy as follows. I think this copes with the ever-growing and fixed-size scenarios equally well. Let us remember that the goal when reserving new free space at both front and back is to make it so that both ends get exhausted at the same time --if they ever are.
This has the effect that if no insertions happened at one end (more precisely, more erasures than insertions took place at that end) then the new reserved space for that end will be zero. Safe guards may be applied. * When reallocation results in the same total space being reserved (this happens when the size at reallocation time is equal or less than the size() at the last reallocation), there is no need to request memory and we can simply shift the sequence so that back and front free capacity are adjusted according to new_space calculations. This nicely handles the FIFO scenario, for instance: when the growing side meets its end, reallocaton resolves to shifting the entire sequence within the current buffer so that space is kept at that end: this keeps cycling forever with no memory allocation and minimal element shifting.
So if no elements are added to the left but only to the right, the live elements are shifted all the way to the left? That would certainly be optimal, and letting the user decide the initial memory consumption let him control how often the shifting is needed. kind regards Thorsten