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.
On Thu, Mar 31, 2005 at 08:25:28PM +0100, Chris Jefferson wrote:
>
> While I'm personally in the "lets not implement what we don't have to"
> camp, I believe what comparisons we perform and in what order are
> entirely up to us and not defined by the standard, as long as there is a
> logarithmic number of them.
Some of the algorithms are specified that way, others say exactly
how many of each operation must occur.
> 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.
Nathan Myers
ncm@codesourcery.com
- References:
- Re: std::map and std::set based on AVL, not RB trees.
- Re: std::map and std::set based on AVL, not RB trees.
- Re: std::map and std::set based on AVL, not RB trees.
- Re: std::map and std::set based on AVL, not RB trees.
- Re: std::map and std::set based on AVL, not RB trees.
- Re: std::map and std::set based on AVL, not RB trees.
- Re: std::map and std::set based on AVL, not RB trees.
- Re: std::map and std::set based on AVL, not RB trees.
- Re: std::map and std::set based on AVL, not RB trees.
- Re: std::map and std::set based on AVL, not RB trees.