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.

From: Chris Jefferson <caj at cs dot york dot ac dot uk>
Cc: libstdc++ at gcc dot gnu dot org
Date: Fri, 01 Apr 2005 07:58:29 +0100
Subject: Re: std::map and std::set based on AVL, not RB trees.
References: <20050331135422.GB24185@compsoc.man.ac.uk> <424C028F.70203@suse.de> <20050331143509.GA33095@compsoc.man.ac.uk> <424C0BA6.7010608@suse.de> <m3hdires81.fsf@uniton.integrable-solutions.net> <424C0F1D.5080006@suse.de> <m34qereqje.fsf@uniton.integrable-solutions.net> <424C1B50.7070902@suse.de> <424C1E45.3080206@suse.de> <424C4EA8.7050204@cs.york.ac.uk> <20050331230257.GA31757@tofu.dreamhost.com>

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

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