Den 26-09-2017 kl. 19:30 skrev Thorsten Ottosen via Boost:
Hi Degski,
we are multiplying by 4, this will become more and more skewed.
Yeah, but would it not become more and more skewed no matter what number
1 we multiply with?
Is there any way to avoid that? Is it desirable to avoid that? The analog for vector is that it has (with a growth factor of 2) on average 25% unused objects. As the container grows, so does the wasted space in absolute terms.
Let's try something different. Let's say the growth factor is 2. Your example was: "Starting from let's say initial front and back capacities of each 4, now adding 5 elements in front and 5 elements in the back (so 10), now gives me a devector with capacity 128". With 2 as the growth factor we get 8 * 2 = 16 16 * 2 = 32; the front_free_capacity is 15 the back_free_capacity is 7 Now, this is when the new capacity is defined as 2 * old capacity. What if we use the following instead? Capacity = old capacity + size; We get 8 + 4 = 12 12 + 9 = 21 the front_free_capacity is 8 the back_free_capacity is 3 so doesn't change much in terms of skewness. We could start moving things around instead of allocating, but I think that strategy can be manipulated to destroy the amortized O(1) property. kind regards Thorsten