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

[Ric Parkin]

From: "Kloss, Burkhard (IT)" > > Solutions
> > 1. Each kind of container in the standard C++ library chooses 
> > a different trade-off of space vs performance.
> > 
> > - A vector<T> stores T objects in a contiguous array and so 
> > has no per-element overhead at all.
> That is if the vector's capacity is the same as its size.  If you grow a
> vector with push_back, you can actually have an overhead of a 100% at
> times because the vector doubles its internal memory allocation when it
> reallocates.

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. 

Of course this is usual moot if your advice to pre-reserve is taken (although that can still lead to overhead - if it's taken notice of capacity will be at least the requested value)

Ric


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