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

[Kenneth Duda <ken dot duda at gmail dot com>]

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

I would define "amortized constant time" like this:

Consider some operation X(n) (such as, "insert into map of size n with hint").

Define Repeat(X(n),m) = repeat X(n) m times

Then, operation X(n) is amortized constant time iff Repeat(X(n),m) is O(m).

"Amortized constant time" differs from "constant time" in that it's a
bit more flexible.  It's okay if the operation occasionally takes
longer as long as on average it meets the performance bound.  For
example, consider a vector with n elements where appending an item is
usually constant time, but occasionally has to realloc and copy the
whole vector.  (Anyone know of a vector like that? :-)  The append
operation is usually O(1) but sometimes O(n).  If the vector doubles
its allocation size each time it reallocs, then you can prove that
even though the append operation is technically takes O(n) runtime
worst case, it is amortized constant time (because starting with an
empty vector and inserting m elements takes no more than 3m steps
total: m inserts plus 2m (or fewer) element copies).

    -Ken