[Exceptional C++ Style] Item 26 -- Data Formats and Effic iency

[Ric Parkin]

From: "Harris, Richard" <richard.harris at csfb.com>
> Ric Parkin wrote:
> <snip>
> Even more minor point, it doesn't have to double to achieve the complexity
> requirements - IIRC there's some minimum value that is enough (somewhere
> around 1.3? - sqrt(5)/2 has popped into my head, but may be wildly wrong) but
> *anything* above that will work. And some implementations take advantage of
> this - I think Dinkumware changed to 1.5 in order to reduce memory overhead. 
> </snip>
> 
> I suspect you're talking about the Golden Ratio which is equal to
> (1+sqrt(5))/2 and turns up all over the place.

That sounds very familiar.

> However, I was under the impression that any reservation (constant
> proportionally) greater than that required by push_back would lead to
> amortized constant time.

Thinking about it, you're right - so long as push_back reallocates with space for roundup(old*X) where X > 1 then eventually it'll get to the stage of amortized constant.

Might be rubbish to start with unless it's a reasonable amount bigger than 1.

I've remembered where the golden ratio came from - to do with choosing the expansion factor to minimize memory fragmentation, which is yet another kettle of performance fish.

Ric


-----------------------------------------
Email provided by http://www.ntlhome.com/