This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: std::map and std::set based on AVL, not RB trees.
- From: Chris Jefferson <caj at cs dot york dot ac dot uk>
- To: "Daniel K. O." <danielosmari at yahoo dot com dot br>
- Cc: libstdc++ at gcc dot gnu dot org
- Date: Mon, 28 Mar 2005 16:38:38 +0100
- Subject: Re: std::map and std::set based on AVL, not RB trees.
- References: <424749A0.9080100@yahoo.com.br>
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