Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

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