"James Kanze" <james.kanze@gmail.com> wrote in message
news:1193911545.733761.171970@50g2000hsm.googlegroups.com...
On Oct 31, 10:55 pm, Erik Wikstr?? <Erik-wikst...@telia.com> wrote:
[...]
I do not know, and I do not think the standard says anything
about it. But a good implementation will probably use a
resizing scheme similar to the one used for vectors, such as
(at least) doubling the capacity every time it resizes.
Doubling is actually not a very good strategy; multiplying by
say 1.5 is considerably better. (As a general rule, the
multiplier should be less that (1+sqrt(5))/2---about 1.6. 1.5
is close enough, and easy to calculate.) In memory tight
situations, of course, the multiplier should be even smaller.
The original STL implementation did use 2, and I suspect that
many implementations still do, even though we now know that it
isn't such a good idea.
=====
I deciced to test my implementation so I wrote this:
#include <iostream>
#include <string>
int main()
{
std::string Foo;
std::string::size_type LastCapacity = Foo.capacity();
std::cout << "Initial Capacity:" << LastCapacity << "\n";
for ( int i = 0; i < 100; ++i )
{
Foo += "x";
if ( Foo.capacity() != LastCapacity )
{
std::cout << "Size:" << Foo.size() << " " << "Capacity:" <<
Foo.capacity() << "\n";
LastCapacity = Foo.capacity();
}
}
}
The output for my system is:
Initial Capacity:15
Size:16 Capacity:31
Size:32 Capacity:47
Size:48 Capacity:70
Size:71 Capacity:105
So as we can see, on my system if I did not initially .reserve() and added 1
character at a time then I would wind up with 4 extra memory reallocations.
the "less than 1.6 multiplication" rule. I have tried to google for it