Bug in map & set iterators (& fix)

[Brad Garcia <bgarcia at laurelnetworks dot com>]

There is a bug in bits/stl_tree.h that allows you to compare two iterators
(map or set iterators) of arbitrary types.  An example program containing
incorrect code that compiles and runs is included at the end of this
email.

The problem is that operator==() and operator!=() are defined to take
_Rb_tree_base_iterator arguments.  The fix is to make these functions
templates that take _Rb_tree_iterator<> arguments instead.  This should
not result in any less efficiency, since in both cases these functions
are declared inline.

The appropriate diff for libstdc++-2.90.8 follows.  The CVS version of the
file does not appear to have changed significantly, so this should also
be applicable to the head-of-line code.

*** original/bits/stl_tree.h        Mon May  8 09:57:34 2000
--- new/bits/stl_tree.h             Fri Aug 25 08:02:47 2000
***************
*** 184,196 ****
    }
  };
  
! inline bool operator==(const _Rb_tree_base_iterator& __x,
!                        const _Rb_tree_base_iterator& __y) {
    return __x._M_node == __y._M_node;
  }
  
! inline bool operator!=(const _Rb_tree_base_iterator& __x,
!                        const _Rb_tree_base_iterator& __y) {
    return __x._M_node != __y._M_node;
  }
  
--- 184,198 ----
    }
  };
  
! 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, 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;
  }


----------------------------------

And here's a little test program that exposes the bug:

#include <map>
#include <iostream>
#include <string>

int main(int argc, char** argv)
{
    std::map<unsigned, int> mapByIndex;
    std::map<std::string, unsigned> mapByName;

    (void)mapByIndex.insert(std::pair<unsigned, int>(0,1));
    (void)mapByIndex.insert(std::pair<unsigned, int>(6,5));

    unsigned i(0);

    std::map<unsigned, int>::iterator itr(mapByIndex.begin());

    while (itr != mapByName.end())  // XXX - notice, it's not mapByIndex!!
    {
	std::cout << "In loop, " << i << std::endl;
	std::cout.flush();
	++i;
	++itr;
    }

    return 0;
}

Brad Garcia