El 18/10/2017 a las 15:18, Thorsten Ottosen via Boost escribió:
Den 18-10-2017 kl. 15:10 skrev Joaquin M López Muñoz via Boost:
El 18/10/2017 a las 13:48, Thorsten Ottosen via Boost escribió:
Den 18-10-2017 kl. 11:36 skrev Joaquin M López Muñoz via Boost:
El 16/10/2017 a las 19:38, Thorsten Ottosen via Boost escribió:
Maybe this is lost to me in the details, but given code that works for vector:
vector<int> v; ... v.reserve( v.size() + N );
which guarantees no exceptions and no reallocations, how would that work with your policy?
Yes, sorry for being unclear, I'm talking about the guarantee given to push_back() and insert() of N elements after the call to reserve().
OK, now I get it. Well, my position is that reserve should be replaced by some mechanism for explicitly controlling free space at each end. Then the user can rely on the guarantee that she can do as many as [back|front]_free_capacity() push_[back|front] ops without rellocation.
and what about insert()? Do we then say if you want to avoid reallocations, you must allocate twice the needed memory?
For vector we do not reallocate on insert().
(I'm not saying that is the wrong answer, I would just like to know that the answer is).
My proposed policy consumes back free capacity if we have a right insertion (past the middle of the devector) and front free capacity in the case of a left insertion (before the middle of the devector). If you want to guarantee N no-reallocation insertions at any position so, yes, both front and back free capacity has to be >=N. For the benefit of the readers, allow me to paste here the policy description: * Fix the growing factor to G. * The right balancing factor B is defined as the ratio between back free capacity and total free capacity. Let's say this is 50% at the start, that is, we have front_free_capacity()= back_free_capacity(). * Right insertions and left insertions shift to the right and left, respectively (as before). * When reallocation is needed, calculate the new balance factor as a function of front and back space consumption just prior to reallocation. Pseudocode follows: struct free_space { std::size_t back,front }; free_space new_space(free_space original,free_space remaining) { float balance=(float)std::max(original.back-remaining.back,0)/ (std::max(original.back-remaining.back,0)+std::max(original.front-remaining.front,0)); std::size_t new_space=std::max(size()*G,size()+remaining.back+remaining.front), new_free_space=new_space-size(); return {balance*new_free_space,(1-balance)*new_free_space}; } Joaquín M López Muñoz