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

[Chris Jefferson]

>>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.
> 
> 
> It seems to me that would result in 2x comparisons in common cases,
> even when the hint is "close".  This is because you would likely
> need to walk up the tree and then back down.

Yes you are right, when I get around to applying some thought to this 
idea, having a random node which you've checked is actually almost 
entirely useless :)

Chris