Speed of string += string

[Alex Martelli]

Ben Hutchings wrote:

> 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.

I don't know if a std::string implementation would be *ALLOWED* to
"waste" arbitrary amounts of memory to achieve amortized O(1)
performance [I think I recall it is -- there being no O() constraints
on std::string memory OR runtime performances, I believe], but it's
certainly not *REQUIRED* to do so (sometimes an std::vector<char>
gives you much better performance than an std::string does...).

For an interestingly-off-mainstream implementation strategy I
suggest reading:
http://www.sgi.com/tech/stl/Rope.html
http://www.sgi.com/tech/stl/ropeimpl.html


Alex