std::map and std::set based on AVL, not RB trees.

[Paolo Carlini]

Daniel K. O. wrote:

> I was searching on my copy of the Standard... and found it thanks to
> http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4
> Then I decided to write another test for insertion with "hint", and
> found something strange.
>
> From the Standard:
> (The complexity of insert(p, t) is) logarithmic in general but
> amortized constant time if t is inserted *right after* p.
>
> From the above link to the libstdc++ docs:
> "The new item will be inserted between |h| (|h = *hint|) and |h|'s
> predecessor."
>
> I'm confused, should the insertion go after or before the hint? The
> code in stl_tree.h seems to try to insert before the hint, not after.

That is exactly one of the two bugs I was talking about: according to
the standard in force, Table 69, first row, the complexity shall be
amortized constant if t is inserted right *after* p, not before p. This
is fixed for 4.0, see PR libstdc++/19433. Actually, we fixed also
another bug, libstdc++/19422, where we didn't guarantee linear
complexity for insertions of sorted ranges.

An important note: when hints are at issue we are only talking about
complexity, not correctness of the insertion, which is guaranteed to end
up in the proper place even if the hint is completely wrong.

> Also, what's a good source for a precise definition of "amortized
> constant time" (at least the definition used by the Standard)?

I'm not sure whether there is really a definition in the standard, those
are well known technical terms from computer science. Basically,
"amortized constant time" is O(1) and so on, for linear, O(n), quadratic
O(n^2):

    http://en.wikipedia.org/wiki/Big_O_notation

Paolo.