hi Joaquin, Thanks for this. Some comments below. Assumptions * The cost of allocating new memory is negligible when compared to the cost of moving elements around (either intra-buffer or when migrating to a new buffer); so, the growing/insertion policy should focus on minimizing number of elements moved. This implies fully occupying free space before reallocation is *not* the primary goal of the growing/insertion policy. ——- But in the real world allocations (+ the implied deallocation ) is not that cheap, especially not with non trivial destructors. For small containers, typical for flat containers, I’m not sure this is a good assumption. Facts * When a right insertion arrives, if there's free back capacity the optimum insertion policy is to shift elements to the right, as this involves fewer movements than the other way around. The symmetrical applies for left insertions. * If a right insertion at position N arrives and there's no free back capacity (but there is free front capacity), we have only two options: A. Reallocate to get back free capacity. B. Shift elements to the left. The key observation here is that A is cheaper in the long run: as the scenario is one of an ever-growing sequence, reallocation will happen eventually and we can just amortize it in our analysis, so reallocating early saves us the extra movements incurred when left shifting on a right insertion, namely N - (size()-N) = 2*N - size() —— How do you get that number ? I would say we save Incur 1/2 * size movements on average for shifting to the end with free space. Description of resulting policy * Fix the growing factor to G (this can be 1.5 or 2 or anything greater than one, the actual figure is orthogonal to the discussion). * Maintain a counter right_ of right insertions that gets incremented when a right insertion occurs and *decremented* when an erasure is issued past the middle of the devector. * Right insertions trigger right shifting except when there's no back free capacity, in which case a reallocation is performed. * Left insertions trigger left shifting except when there's no front free capacity, in which case a reallocation is performed. * Reallocation reserves space for G*size() elements: of the resulting G*size()-size() free space, a fraction right_/size() is devoted to back free capacity, the rest to front free capacity. In practice, we may want to keep some minimum space at each end as determined by some empirical threshold. And that's it. Comments welcome. —-____ Interesting analysis. Thanks. I agree if the sequence is ever growing, it’s better to allocate when one end is full. 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? 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 . 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. It will also make operations slower, but that can be tested. Kind regards Thorsten -- Sent from: http://boost.2283326.n4.nabble.com/Boost-Dev-f2600599.html