# Boost :

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-09-27 18:50:35

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