El 18/10/2017 a las 16:28, Joaquin M López Muñoz escribió:
Ummm... I wrote too fast, the answer is not obvious :-) Say our devector looks like
FF···FMM···MBB···B
and we want to erase MM···M. We have these three options:
1. Move BB...B right after FF···F, so that only back free capacity grows. 2. Move FF···F right before BB···B, so that only front free capacity grows. 3. Make FF···F meet BB···B at a middle position within the buffer so that the ratio between back and front free capacity is kept.
In my opinion, the best option is to do 1 or 2 depending on which of the two subsequences BB···B and FF···F is smaller (respectively), which minimizes the number of movements. This is consistent with the expected behavior for push_[back|front]. 3 always implies more movements.
Writing this has led me to realize that a generic growing/insertion policy also needs a member function to indicate what to do on erasure: struct free_space{std::size_t back,front;}; free_space query_for_insertion(std::size_t pos,std::size_t n); free_space query_for_erasure(std::size_t pos,std::size_t n); (clear would be the case where erasure happens at begin() and n==size()). Joaquín M López Muñoz