On 23/03/2011 11:03, Mickael Wolff wrote:
> On 23/03/11 10:52, Tomalak Geret'kal wrote:
>
>> The standard specifies only that, after a re-allocation,
>> .capacity() >=
>> .size(). It says nothing about specifically doubling
>> capacity.
>
> It's why I spoke about a common optimization, not a standard
> specification. As I said, you should read the valuable
> material I mentioned.
>
"Optimisation" is the wrong word here. This is a library
feature that explicitly defines the language's semantics,
not an optimisation.
Anyway, your original claim was:
> Keep in mind also the behavior of std::vector, which
StoreQueryResult is based on. (More or less, it is a 2D
vector of mysqlpp::String.) It doubles in size each time
you exceed its size, so it can keep growing.
This is just patently false, unless you qualify it with "on
some implementations, sometimes".
I have read Meyers's books. Please stop assuming that I have
not read the popular books, or that I do not have C++
experience, just because I am disagreeing with something
that you have said.
Talking of assumptions, I will assume here that you meant
"Effective STL", as "Effective C++" does not cover vector
re-allocations. And in "Effective STL", Meyers says "in most
implementations, vector and string capacities grow by a
factor of two each time. i.e. their capacity is doubled each
time the container must be expanded." Presumably this is the
passage to which you refer. Critically, he clarifies that
this rule is only "in most implementations". Some
implementation may not use a doubling multiplier.
In fact, the strategy with _doubling_ the memory has certain
flaws (Andrew Koenig). Paraphrasing Andrey Tarasevich:
"Multiplying the
capacity by any value above (1 + sqrt(5))/2 might lead to
extremely inefficient memory usage in typical
implementation. AFAIK, most modern implementations tend to
use 1.6 as a multiplier value."
The counter-argument is that one might say exponential
growth is "effectively guaranteed by the standard, as it's
the only reasonable way to get amortized O(1) behavior for
push_back." (Salters)
A third-party stdlib implementation that we occasionally use
on an embedded platform uses a 1.5 multiplier.
I'm sorry if you feel that I'm attacking you: I'm certainly
not; I just feel that the OP may very well benefit from
these clarifications. Having made them I will now retreat
back into lurkdom.. :P
Tom
