Speed of string += string

[Chris Tavares]

"Roy Smith" <roy at panix.com> wrote in message
news:roy-06B012.20145112042003 at reader1.panix.com...
[ ... snip ... ]
>
> As another example, I can guess that Python dictionaries work like STL
> maps on the inside, but that would be just a guess.  Is inserting an
> element logN?  Is keys() linear?  Is del on an element logN?  Is
> has_key() logN?  Those would be my guesses.  But they're just guesses.
>

STL maps are implemented using binary trees (red-black trees usually), so
that's why they have their logN performance numbers.

Python dicts are implemented using a hash table. As a result, their typical
behavior is O(1) - constant time to get any key. Unless there are hash
collisions of course.

The big difference besides performance is that STL maps store the keys in
sorted order, where Python dict keys are "randomly" ordered.

-Chris