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: Gabriel Dos Reis <gdr at integrable-solutions dot net>
- To: Chris Jefferson <caj at cs dot york dot ac dot uk>
- Cc: "Daniel K. O." <danielosmari at yahoo dot com dot br>, libstdc++ at gcc dot gnu dot org
- Date: 28 Mar 2005 19:28:40 +0200
- Subject: Re: std::map and std::set based on AVL, not RB trees.
- Organization: Integrable Solutions
- References: <424749A0.9080100@yahoo.com.br> <424824FE.8040604@cs.york.ac.uk>
Chris Jefferson <caj@cs.york.ac.uk> writes:
| 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..
I think you're right. The standard requirements seem to have been
carefully crafter after RB tree behaviour. anyone inetrested in this
stuff may probably want to read the paper by Matt Austern et al.
-- Gaby