This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


Daniel K. O. wrote:
Hello.

Some months ago, while having nothing special to do, I modified the libstdc++'s RB tree - used in the associative containers - into an AVL tree.

First of all, let me say I found this interesting, and I intend to look into it more carefully when I have some time :)


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..

Chris


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]