[PATCH] fixing libstdc++/737: Regression with maps

[Theodore Papadopoulo <Theodore dot Papadopoulo at sophia dot inria dot fr>]

Some more details:

Reverting the operators == and != in stl_tree.h to their values in 
the original sgi implementation cures the problem I see with the 
following code.

#include <map>
#include <iostream>

int
main()
{
    typedef std::map<int,const int> MapInt;

    MapInt m;

    for (unsigned i=0;i<10;++i)
        m.insert(MapInt::value_type(i,i));
    
    for (MapInt::const_iterator i=m.begin();i!=m.end();++i)
        std::cerr << i->second << ' ';
}

This was introduced with:

2000-09-07  Brad Garcia  <bgarcia@laurelnetworks.com>
	* bits/stl_tree.h: Make operators !=, == type safe for map, set.

Reverting that patch is not the best solution IMHO, because it would
reintroduce the problem depicted in:
http://sources.redhat.com/ml/libstdc++/2000-08/msg00144.html

The problem is that that patch only allowed for the comparisons 
(rb_tree::iterator,rb_tree::iterator) whereas the example above 
requires comparisons (rb_tree::const_iterator,rb_tree::iterator).
And of course, examples requiring comparisons 
(rb_tree::iterator,rb_tree::const_iterator) are easy to create.

I solved the problem by overloading the operators == and != to
allow comparisons (rb_tree::const_iterator,rb_tree::iterator) and
(rb_tree::iterator,rb_tree::const_iterator). I believe it is the
best solution unless more such special cases have to be added
(see PATCH below).

Finally, a regression test suite would have got that problem. So, 
maybe the following small test-case (which can certainly be 
simplified a little more) can be added to such a test suite (I do not 
know where libc++ tests must be added....).

EXAMPLE:

//  Build, don't link:
//  Origin: Theodore.Papadopoulo@sophia.inria.fr

#include <map>
#include <iostream>

int
main()
{
    typedef std::map<int,const int> MapInt;

    MapInt m;

    for (unsigned i=0;i<10;++i)
        m.insert(MapInt::value_type(i,i));

    for (MapInt::const_iterator i=m.begin();i!=m.end();++i)
        std::cerr << i->second << ' ';

    for (MapInt::const_iterator i=m.begin();m.end()!=i;++i)
        std::cerr << i->second << ' ';
}

PATCH:

ChangeLog:

2000-11-09 Theodore Papadopoulo <Theodore.Papadopoulo@sophia.inria.fr>

    * include/bits/stl_tree.h: Overload operators == and != to be able
    to handle the case (const_iterator,iterator) and (iterator,const_iterator),
    thus fixing libstdc++/737 and the like.

Index: stl_tree.h
===================================================================
RCS file: /cvs/gcc/egcs/libstdc++-v3/include/bits/stl_tree.h,v
retrieving revision 1.1
diff -c -3 -p -r1.1 stl_tree.h
*** stl_tree.h	2000/10/05 11:27:01	1.1
--- stl_tree.h	2000/11/07 19:52:16
*************** inline bool operator==(const _Rb_tree_it
*** 190,198 ****
--- 190,222 ----
    return __x._M_node == __y._M_node;
  }
  
+ template <class _Value>
+ inline bool operator==(const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __x,
+ 		       const _Rb_tree_iterator<_Value, _Value&, _Value*>& __y) {
+   return __x._M_node == __y._M_node;
+ }
+ 
+ template <class _Value>
+ inline bool operator==(const _Rb_tree_iterator<_Value, _Value&, _Value*>& __x,
+ 		       const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __y) {
+   return __x._M_node == __y._M_node;
+ }
+ 
  template <class _Value, class _Ref, class _Ptr>
  inline bool operator!=(const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __x,
  		       const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __y) {
+   return __x._M_node != __y._M_node;
+ }
+ 
+ template <class _Value>
+ inline bool operator!=(const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __x,
+ 		       const _Rb_tree_iterator<_Value, _Value&, _Value*>& __y) {
+   return __x._M_node != __y._M_node;
+ }
+ 
+ template <class _Value>
+ inline bool operator!=(const _Rb_tree_iterator<_Value, _Value&, _Value*>& __x,
+ 		       const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __y) {
    return __x._M_node != __y._M_node;
  }
  

 --------------------------------------------------------------------
 Theodore Papadopoulo
 Email: Theodore.Papadopoulo@sophia.inria.fr Tel: (33) 04 92 38 76 01
 --------------------------------------------------------------------

PGP signature