Speed of string += string

[Martin v. Löwis]

Alex Martelli <aleax at aleax.it> writes:

> The crucial difference is that Python dicts are hashtables, while the
> std::map in the standard library of C++ can't be, because it's based
> on an order relationship, NOT on hashing.  So, std::map has an order,
> but its O(...) performance just can't be as good as a dict's.

Nit-pickers (like myself) will point out that the complexity of a
hash-table depends on the distribution of the hash function (in
addition to depending on the complexity of the hash function).  With a
carefully-chosen hash O(1) function, all dictionary operations will be
O(n). For std::map, O(log n) is the worst-case performance.

Regards,
Martin