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

[Daniel K. O.]

Thank you all for the responses.

> Chris Jefferson wrote: Daniel K. O. wrote:
>
> A quick early comment, not specifically related to your code, is that 
> the C++ standard is quite tight on the requirements of various 
> functions. In particular, insert(t,p) (for a std::set), given value t 
> and iterator p must be "amoritzed constant time if t is inserted right 
> after p". Do AVL trees provide this? I thought that they didn't, but I 
> could be wrong..


I was searching on my copy of the Standard... and found it thanks to 
http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4
Then I decided to write another test for insertion with "hint", and 
found something strange.

 From the Standard:
(The complexity of insert(p, t) is) logarithmic in general but amortized 
constant time if t is inserted *right after* p.

 From the above link to the libstdc++ docs:
"The new item will be inserted between |h| (|h = *hint|) and |h|'s 
predecessor."

I'm confused, should the insertion go after or before the hint? The code 
in stl_tree.h seems to try to insert before the hint, not after.

Also, what's a good source for a precise definition of "amortized 
constant time" (at least the definition used by the Standard)?




Paolo Carlini wrote:

>I only want to add to Gaby and Chris comments that you may want to redo
>your benchmarks vs a snapshot of the forthcoming 4.0: recently we fixed
>a couple of serious bugs affecting performance in this area.
>  
>
Unfortunately the only machine where I can do meaningful benchmarks 
(where I can get all the CPU cycles to myself) is a Win98 SE box, so 
I'll depend on a MinGW release. :(
But I'll try on my friend's Ubuntu box as soon as possible.



Daniel K. O.