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

[Jonathan Wakely]

On Wed, Mar 30, 2005 at 09:20:51PM -0300, Daniel K. O. wrote:

> Thank you all for the responses.
> 
> >Chris Jefferson wrote: Daniel K. O. wrote:
> >
> >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 was searching on my copy of the Standard... and found it thanks to 
> http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4

That text describes how the traditional STL worked (and how Matt Austern
describes the hint on p160 of his book) but is apparently incorrect
w.r.t. the current standard and GCC 4.x

Paolo, Chris, was the resolution to PR19433 the right one?

DR233 says insertion should be constant if inserting to the position
before, OR after the hint. Dinkum already implement this.  If
that interpretation is added to the working paper then we'll have to
change libstdc++ again.

If you take the spec from Table 69, rather than the traditional STL,
how do you hint that insertion should happen at the start of the
container?  You could call insert() with no hint, but that requires
a special case.  The interpretation of the hint is asymmetrical, you can
represent "at the end" but not "at the beginning", and there are two
iterators that mean "at the end" when used as a hint: end() and end()-1

See library issue 246 (marked as a dup of the open issue 233) for other
reasons the requirement in table 69 is odd.

I believe we should do the same as Dinkum, preserving compatibility with
code written to the traditional HP/SGI spec and also code written to the
(dubious) standard spec.  That would also be right if DR 233 is accepted
in its present form. (Apologies if that's what you did implement, the
changelog implies otherwise).

jon

-- 
"I find television very educating. Every time somebody turns on the set, 
 I go into the other room and read a book."
	- Groucho Marx