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