El 16/10/2017 a las 10:45, Thorsten Ottosen via Boost escribió:
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ó:
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?
Sorry, I missed that one. Yes, we use the insertion pattern after the last reallocation to estimate the new one. If the insertion pattern changes over time the policy will adapt with a delay of one reallocation.
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.
If we must guarantee that the buffer is full before reallocation, the resulting policy won't be optimal wrt number of movements. This is the tradeoff. I guess your reservation stems from the desire that capacity()-size() indicates the number of insertions before reallocation, to that I just answered Ion in another post. My (current) opinion is that capacity() should not be provided.
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.
This is superseded by the alternative formulation I described above.
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.
Much as I think capacity() should not be provided, reserve would probably better replaced by reserve_front_free/reserve_back_free or something similar. Joaquín M López Muñoz