El 16/10/2017 a las 1:45, Ion Gaztañaga via Boost escribió:
On 15/10/2017 17:59, Joaquin M López Muñoz via Boost wrote:
The assumption is of an ever growing sequence. That said, I recorgnize there are scenarios not falling under this, most notably FIFO queues. I've given the policy a little more thought and think we can twist it to also accommodate non-growing scenarios, please keep on reading.
Thougths?
I think that the default (we could have other policies) should be simple and similar to vector/string/stable_vector/etc.... In this sense, capacity() and reserve(), if provided, should make sense. If we reallocate depending on the free capacity of one side, then capacity() and reserve() make no sense to the user
I think the user expects capacity() as the maximum number of insertions, in any position, that will be accepted before reallocating. Making free_capacity = capacity() - size(), less than, say, back_free_capacity() will be really hard to understand by users.
I think providig capacity() will lead to confusion no matter the growing/insertion policy. For instance, users of vector/string/... expect capacity()-size() to be the number of push_back()'s accepted without iterator invalidation. Your policy below does break this expectation --as any policy other than the pathological case where front is given no free space ever.
I propose a simple strategy:
[...]
For any policy, there's a tradeoff between number of movements and wasted space --i.e. space not used before reallocation. Yours prioritizes the latter, mine the former.
Statistics based policies seem more complex, and I don't know how well they will adapt to pattern changes thorough the lifetime of the container, plus they impose a size cost to the container. I wouldn't make the the default choice, as the average user should easily understand the default policy.
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); used like this (pseudocode): auto new_free_space=query_for_insertion(pos,n); if(new_free_space.back+new_free_space.front>free_capacity()){ // allocate or request in-place extension // move and insert appropriately so that back_free_capacity()==new_free_space.back // and front_free_capacity()==new_free_space.front } else{ // free space rebalance assert(new_free_space.back+new_free_space.front==free_capacity()); // move and insert appropriately so that back_free_capacity()==new_free_space.back // and front_free_capacity()==new_free_space.front } Why don't we equip devector with such a customization point and test the different alternatives for real?
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. Joaquín M López Muñoz