basic_string capacity strategy < 128 characters

[Paolo Carlini]

Joachim Schurig wrote:

> Hi Paolo,
>
>> A quick comment (more later): the standard requires asymptotic (i.e., 
>> amortized) linear behavior, not linear behavior tout court, and the 
>> v3 strategy for sure guarantees that, since december 2001. See f.i.:
>>
>>    http://gcc.gnu.org/ml/libstdc++/2001-12/msg00144.html 
>
> But how do you explain the fact that the libstdc++-v3 allocates a new 
> buffer with size += 1 for each added character, then copies the whole 
> existing buffer, and then frees the existing buffer?
>
> Is this what you understand by amortized linear? For me, amortized 
> means something like "expect a performance penalty every some 
> characters", but for sure not with every new character.

A quick comment (more later): asymptotic (i.e., amortized) linear 
bahavior is something very precisely defined, as the concept of 
asymptote is in basic calculus. It means that does not matter what 
happens for small numbers, only what happens when the number becomes 
larger and larger. This is only to point out that our implementation, as 
far as this issue is concerned, is _absolutely_ conforming.

That the behavior for small strings, a well defined allocator, a well 
defined architecture and a well defined application can be improved is 
another matter.

Paolo.