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

[Chris Jefferson <caj at cs dot york dot ac dot uk>]

Paolo Carlini wrote:
> Paolo Carlini wrote:
>
>
> > Then, you don't have my consensus. Because, if we implement that
> > behavior we have additional complexity (not abstract complexity) in the
> > code dealing with insertions, i.e., two comparisons (before and after)
> > instead of one. Also, people following the standard in force may rightly
> > assume that only one specific comparison is carried out before the full
> > blown search.
>
> Also notice that (as we learned recently) people actually use operators that
> throw: the behavior when using such operators can be potentially completely
> different if we follow the standard or implement something else.

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.

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.

Chris