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

[Gabriel Dos Reis <gdr at integrable-solutions dot net>]

Jonathan Wakely <cow@compsoc.man.ac.uk> writes:

| On Thu, Mar 31, 2005 at 04:39:34PM +0200, Paolo Carlini wrote:
| 
| > Jonathan Wakely wrote:
| > 
| > >I don't think anything strange is going on, I just wonder if it would be
| > >better if we implemented the proposed resolution (as Dinkum already
| > >does) because
| > >  
| > >
| > But I have to remind you that, as a policy we do **not** implement
| > resolutions in the "Open" status.
| 
| Yes, I realise that. OK, so forget my reason (1), I still think it would
| be a nice QOI feature, for reasons given in (2).

Surely it is.  If you happen to have a patch around, please post it so
we can look at it.

| > What if the final resolution is different?
| 
| What if it's not?  ;)

More importantly, does anybody have any argument (for usefulness) for
requiring the "wrong" description?

| GCC 4.0 will cause performance regressions for any code which assumes the
| old meaning of the hint, irrespective of the final resolution.

Actually my colleague Jaakko and me have been through this recently (I
was maintaining that we have the wrong complexity) until he pointed me
to the "right" wording that makes things work "right".  The context of
the discussion was how to better support map<> in the STL? (Currently,
it you copy (into) a map, you have a high hit of balancing and we were
looking at alternative iteration abstractions).

-- Gaby