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

[Paolo Carlini <pcarlini at suse dot de>]

Chris Jefferson wrote:

> While I'm personally in the "lets not implement what we don't have to"
> camp, I believe what comparisons we perform and in what order are
> entirely up to us and not defined by the standard, as long as there is
> a logarithmic number of them.

Indeed, you are right. But my point is slightly different (assuming you
are alluding to my point): if we want to compare also with "before", not
only with "after", before falling back to the general search, we must
know that this has a cost, and is a change of behavior. Same for my
other detailed points. In nutshell, the proposed change is not an
*obvious* and absolute improvement wrt the current situation. That's why
I would not implement it with a light heart missing an official decision
of the commitee which would essentially "force" us to do so.

> For example, at some point I'd like to change the current code so if
> we are given a hint and it is wrong, then we only search either
> [begin,hint) or (hint,end), depending on what the result of checking
> the hint was.

That's a good idea, which, notice, would *not* change by itself the
initial number and kind of comparisons before the general search algorithm.

Paolo.