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

[Chris Jefferson]

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