Speed of string += string

[Ben Hutchings]

In article <mailman.1050173000.12088.python-list at python.org>,
Alan McIntyre wrote:
> Just off the cuff here, it seems to me that the time required to do 
> "string += string" is going to be proportional to the size of the 
> original string whether you do it in Python or with the STL's 
> std::string or with C strings (so long as you don't know beforehand how 
> long the final string will be).
<snip>

Mutable string implementations may allocate more memory than their
current contents require, in order to avoid future reallocation and
copying.  A string implementation that grows its buffer exponentially
(e.g. doubling it every time it needs to grow) will have amortised
linear time complexity for additions, just like the STL vector or
Python list.