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?
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?
I can try that, but won't be until next week. In the mean time, people can post their favorite policy and answer what it does in the following situations (so it is easier to follow): A. what is the front_free_capacity/back_free_capacity after reserve() on an empty devector? B. what is the front_free_capacity/back_free_capacity after clear() C. what is the front_free_capacity/back_free_capacity after push_back on an empty devector? D. what is the front_free_capacity/back_free_capacity after push_front on an empty devector? E. what is the front_free_capacity/back_free_capacity after insert on an empty devector? F. what is the front_free_capacity/back_free_capacity after reserve on a non-empty empty devector?
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. kind regards Thorsten