[multiple changes]

2004-03-25  Gawain Bolton  <gp.bolton@computer.org>

	* include/bits/stl_tree.h (_Rb_tree_impl): Add _Node_allocator
	default argument in constructors.
	(_Rb_tree::_M_empty_initialize): Remove.

2004-03-25  Benjamin Kosnik  <bkoz@redhat.com>

	* testsuite/23_containers/map/operators/1_neg.cc: Adjust line numbers.
	* testsuite/23_containers/set/operators/1_neg.cc: Same.

2004-03-25  Dhruv Matani  <dhruvbird@gmx.net>

	* include/bits/cpp_type_traits.h: Changed __is_pod
	completely. Now, it does not use any of the previous type_traits
	to detect the pod types, and it also detects function pointers as
	POD types.

	* include/bits/stl_tree.h: Introduced a new class _Rb_tree_impl,
	which encapsulates the internal implementation of an rb_tree. Made
	the allocator a base class of this class instead of the rb_tree,
	which was not conforming. This _Rb_tree_impl class is also
	specialized on whether the _Compare parameter is a POD type or
	not. If so, then it maintains the comparison function as a data
	member, otherwise it makes the _Compare parameter a base class of
	itself. Also, _M_key_compare is now a function instead of a data
	member, so that the above trick can work properly. Delegated the
	initialization of the other data members to this newly created
	class. Also, now other member functions of rb_tree must refer to
	_M_key_compare as _M_impl._M_key_compare(). The other data members
	(*) can be referenced to as _M_impl.(*), where
	(*) includes _M_header, and _M_node_count.

From-SVN: r79977

5 files changed, 201 insertions, 132 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index c5c7fd9..2ca2d2a 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,36 @@
+2004-03-25  Gawain Bolton  <gp.bolton@computer.org>
+
+	* include/bits/stl_tree.h (_Rb_tree_impl): Add _Node_allocator
+	default argument in constructors.
+	(_Rb_tree::_M_empty_initialize): Remove.
+	
+2004-03-25  Benjamin Kosnik  <bkoz@redhat.com>
+	
+	* testsuite/23_containers/map/operators/1_neg.cc: Adjust line numbers.
+	* testsuite/23_containers/set/operators/1_neg.cc: Same.
+
+2004-03-25  Dhruv Matani  <dhruvbird@gmx.net>
+
+	* include/bits/cpp_type_traits.h: Changed __is_pod
+	completely. Now, it does not use any of the previous type_traits
+	to detect the pod types, and it also detects function pointers as
+	POD types.
+
+	* include/bits/stl_tree.h: Introduced a new class _Rb_tree_impl,
+	which encapsulates the internal implementation of an rb_tree. Made
+	the allocator a base class of this class instead of the rb_tree,
+	which was not conforming. This _Rb_tree_impl class is also
+	specialized on whether the _Compare parameter is a POD type or
+	not. If so, then it maintains the comparison function as a data
+	member, otherwise it makes the _Compare parameter a base class of
+	itself. Also, _M_key_compare is now a function instead of a data
+	member, so that the above trick can work properly. Delegated the
+	initialization of the other data members to this newly created
+	class. Also, now other member functions of rb_tree must refer to
+	_M_key_compare as _M_impl._M_key_compare(). The other data members
+	(*) can be referenced to as _M_impl.(*), where
+	(*) includes _M_header, and _M_node_count.
+
 2004-03-25  Paolo Carlini  <pcarlini@suse.de>
 
 	* include/ext/mt_allocator.h (__mt_alloc<>::tune):
diff --git a/libstdc++-v3/include/bits/cpp_type_traits.h b/libstdc++-v3/include/bits/cpp_type_traits.h
index 7a0e65f..d025c8f 100644
--- a/libstdc++-v3/include/bits/cpp_type_traits.h
+++ b/libstdc++-v3/include/bits/cpp_type_traits.h
@@ -317,12 +317,27 @@ namespace std
   //
   // For the immediate use, the following is a good approximation
   //
+
+  // NB: g++ can not compile these if declared within the class
+  // __is_pod itself.
+  namespace __gnu_internal
+  {
+    typedef char __one;
+    typedef char __two[2];
+
+    template <typename _Tp>
+    __one __test_type (int _Tp::*);
+    template <typename _Tp>
+    __two& __test_type (...);
+  }
+
+  
   template<typename _Tp>
   struct __is_pod
   {
     enum
     {
-      _M_type = __is_fundamental<_Tp>::_M_type
+      _M_type = (sizeof(__gnu_internal::__test_type<_Tp>(0)) != sizeof(__gnu_internal::__one))
     };
   };
 
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 35f1c08..6769873 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -63,33 +63,30 @@
 #ifndef _TREE_H
 #define _TREE_H 1
 
-/*
-
-Red-black tree class, designed for use in implementing STL
-associative containers (set, multiset, map, and multimap). The
-insertion and deletion algorithms are based on those in Cormen,
-Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
-except that
-
-(1) the header cell is maintained with links not only to the root
-but also to the leftmost node of the tree, to enable constant time
-begin(), and to the rightmost node of the tree, to enable linear time
-performance when used with the generic set algorithms (set_union,
-etc.);
-
-(2) when a node being deleted has two children its successor node is
-relinked into its place, rather than copied, so that the only
-iterators invalidated are those referring to the deleted node.
-
-*/
-
 #include <bits/stl_algobase.h>
 #include <bits/allocator.h>
 #include <bits/stl_construct.h>
 #include <bits/stl_function.h>
+#include <bits/cpp_type_traits.h>
 
 namespace std
 {
+  // Red-black tree class, designed for use in implementing STL
+  // associative containers (set, multiset, map, and multimap). The
+  // insertion and deletion algorithms are based on those in Cormen,
+  // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
+  // 1990), except that
+  //
+  // (1) the header cell is maintained with links not only to the root
+  // but also to the leftmost node of the tree, to enable constant
+  // time begin(), and to the rightmost node of the tree, to enable
+  // linear time performance when used with the generic set algorithms
+  // (set_union, etc.)
+  // 
+  // (2) when a node being deleted has two children its successor node
+  // is relinked into its place, rather than copied, so that the only
+  // iterators invalidated are those referring to the deleted node.
+
   enum _Rb_tree_color { _S_red = false, _S_black = true };
 
   struct _Rb_tree_node_base
@@ -164,10 +161,10 @@ namespace std
       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
       typedef _Rb_tree_node<_Tp>*           _Link_type;
 
-      _Rb_tree_iterator() {}
+      _Rb_tree_iterator() { }
 
       _Rb_tree_iterator(_Link_type __x)
-      : _M_node(__x) {}
+      : _M_node(__x) { }
 
       reference
       operator*() const
@@ -234,13 +231,13 @@ namespace std
       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
       typedef const _Rb_tree_node<_Tp>*           _Link_type;
 
-      _Rb_tree_const_iterator() {}
+      _Rb_tree_const_iterator() { }
 
       _Rb_tree_const_iterator(_Link_type __x)
-      : _M_node(__x) {}
+      : _M_node(__x) { }
 
       _Rb_tree_const_iterator(const iterator& __it)
-      : _M_node(__it._M_node) {}
+      : _M_node(__it._M_node) { }
 
       reference
       operator*() const
@@ -312,20 +309,19 @@ namespace std
                         _Rb_tree_node_base*& __root);
 
   void
-  _Rb_tree_insert_and_rebalance(const bool          __insert_left,
+  _Rb_tree_insert_and_rebalance(const bool __insert_left,
                                 _Rb_tree_node_base* __x,
                                 _Rb_tree_node_base* __p,
                                 _Rb_tree_node_base& __header);
 
   _Rb_tree_node_base*
   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
-			       _Rb_tree_node_base&	 __header);
+			       _Rb_tree_node_base& __header);
 
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc = allocator<_Val> >
     class _Rb_tree
-    : protected _Alloc::template rebind<_Rb_tree_node<_Val> >::other
     {
       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
               _Node_allocator;
@@ -346,19 +342,20 @@ namespace std
       typedef const _Rb_tree_node* _Const_Link_type;
       typedef size_t size_type;
       typedef ptrdiff_t difference_type;
-
       typedef _Alloc allocator_type;
-      allocator_type get_allocator() const
-      { return *static_cast<const _Node_allocator*>(this); }
+
+      allocator_type 
+      get_allocator() const
+      { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
 
     protected:
       _Rb_tree_node*
       _M_get_node()
-      { return _Node_allocator::allocate(1); }
+      { return _M_impl._Node_allocator::allocate(1); }
 
       void
       _M_put_node(_Rb_tree_node* __p)
-      { _Node_allocator::deallocate(__p, 1); }
+      { _M_impl._Node_allocator::deallocate(__p, 1); }
 
       _Link_type
       _M_create_node(const value_type& __x)
@@ -392,50 +389,87 @@ namespace std
       }
 
     protected:
-      _Rb_tree_node_base _M_header;
-      size_type _M_node_count; // keeps track of size of tree
-      _Compare _M_key_compare;
+      template<typename _Key_compare, 
+	       bool _Is_pod_comparator = std::__is_pod<_Key_compare>::_M_type>
+        struct _Rb_tree_impl : public _Node_allocator
+        {
+	  _Key_compare		_M_key_compare;
+	  _Rb_tree_node_base 	_M_header;
+	  size_type 		_M_node_count; // Keeps track of size of tree.
+
+	  _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
+			const _Key_compare& __comp = _Key_compare())
+	  : _Node_allocator(__a), _M_node_count(0), _M_key_compare(__comp)
+	  {
+	    this->_M_header._M_color = _S_red;
+	    this->_M_header._M_parent = 0;
+	    this->_M_header._M_left = &this->_M_header;
+	    this->_M_header._M_right = &this->_M_header;
+	  }
+	};
+
+      // Specialization for _Comparison types that are not capable of
+      // being base classes / super classes.
+      template<typename _Key_compare>
+        struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator 
+	{
+	  _Key_compare 		_M_key_compare;
+	  _Rb_tree_node_base 	_M_header;
+	  size_type 		_M_node_count; // Keeps track of size of tree.
+
+	  _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
+			const _Key_compare& __comp = _Key_compare())
+	  : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
+	  { 
+	    this->_M_header._M_color = _S_red;
+	    this->_M_header._M_parent = 0;
+	    this->_M_header._M_left = &this->_M_header;
+	    this->_M_header._M_right = &this->_M_header;
+	  }
+	};
+
+      _Rb_tree_impl<_Compare> _M_impl;
 
     protected:
       _Base_ptr&
       _M_root()
-      { return this->_M_header._M_parent; }
+      { return this->_M_impl._M_header._M_parent; }
 
       _Const_Base_ptr
       _M_root() const
-      { return this->_M_header._M_parent; }
+      { return this->_M_impl._M_header._M_parent; }
 
       _Base_ptr&
       _M_leftmost()
-      { return this->_M_header._M_left; }
+      { return this->_M_impl._M_header._M_left; }
 
       _Const_Base_ptr
       _M_leftmost() const
-      { return this->_M_header._M_left; }
+      { return this->_M_impl._M_header._M_left; }
 
       _Base_ptr&
       _M_rightmost()
-      { return this->_M_header._M_right; }
+      { return this->_M_impl._M_header._M_right; }
 
       _Const_Base_ptr
       _M_rightmost() const
-      { return this->_M_header._M_right; }
+      { return this->_M_impl._M_header._M_right; }
 
       _Link_type
       _M_begin()
-      { return static_cast<_Link_type>(this->_M_header._M_parent); }
+      { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 
       _Const_Link_type
       _M_begin() const
-      { return static_cast<_Const_Link_type>(this->_M_header._M_parent); }
+      { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_parent); }
 
       _Link_type
       _M_end()
-      { return static_cast<_Link_type>(&this->_M_header); }
+      { return static_cast<_Link_type>(&this->_M_impl._M_header); }
 
       _Const_Link_type
       _M_end() const
-      { return static_cast<_Const_Link_type>(&this->_M_header); }
+      { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
 
       static const_reference
       _S_value(_Const_Link_type __x)
@@ -505,38 +539,26 @@ namespace std
     public:
       // allocation/deallocation
       _Rb_tree()
-      : _Node_allocator(allocator_type()),
-	_M_node_count(0),
-	_M_key_compare()
-      { _M_empty_initialize(); }
+      { }
 
       _Rb_tree(const _Compare& __comp)
-      : _Node_allocator(allocator_type()),
-	_M_node_count(0),
-	_M_key_compare(__comp)
-      { _M_empty_initialize(); }
+      : _M_impl(allocator_type(), __comp)
+      { }
 
       _Rb_tree(const _Compare& __comp, const allocator_type& __a)
-      : _Node_allocator(__a),
-	_M_node_count(0),
-	_M_key_compare(__comp)
-      { _M_empty_initialize(); }
+      : _M_impl(__a, __comp)
+      { }
 
       _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
-      : _Node_allocator(__x.get_allocator()),
-	_M_node_count(0),
-	_M_key_compare(__x._M_key_compare)
+      : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
       {
-	if (__x._M_root() == 0)
-	  _M_empty_initialize();
-	else
+	if (__x._M_root() != 0)
 	  {
-	    this->_M_header._M_color = _S_red;
 	    _M_root() = _M_copy(__x._M_begin(), _M_end());
 	    _M_leftmost() = _S_minimum(_M_root());
 	    _M_rightmost() = _S_maximum(_M_root());
+	    _M_impl._M_node_count = __x._M_impl._M_node_count;
 	  }
-	_M_node_count = __x._M_node_count;
       }
 
       ~_Rb_tree()
@@ -545,37 +567,26 @@ namespace std
       _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
       operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);
 
-    private:
-      void _M_empty_initialize()
-      {
-	// Used to distinguish header from __root, in iterator.operator++.
-	this->_M_header._M_color = _S_red;
-	_M_root() = 0;
-	_M_leftmost() = _M_end();
-	_M_rightmost() = _M_end();
-      }
-
-    public:
       // Accessors.
       _Compare
       key_comp() const
-      { return _M_key_compare; }
+      { return _M_impl._M_key_compare; }
 
       iterator
       begin()
-      { return static_cast<_Link_type>(this->_M_header._M_left); }
+      { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }
 
       const_iterator
       begin() const
-      { return static_cast<_Const_Link_type>(this->_M_header._M_left); }
+      { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left); }
 
       iterator
       end()
-      { return static_cast<_Link_type>(&this->_M_header); }
+      { return static_cast<_Link_type>(&this->_M_impl._M_header); }
 
       const_iterator
       end() const
-      { return static_cast<_Const_Link_type>(&this->_M_header); }
+      { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
 
       reverse_iterator
       rbegin()
@@ -595,11 +606,11 @@ namespace std
 
       bool
       empty() const
-      { return _M_node_count == 0; }
+      { return _M_impl._M_node_count == 0; }
 
       size_type
       size() const
-      { return _M_node_count; }
+      { return _M_impl._M_node_count; }
 
       size_type
       max_size() const
@@ -648,7 +659,7 @@ namespace std
         _M_leftmost() = _M_end();
         _M_root() = 0;
         _M_rightmost() = _M_end();
-        _M_node_count = 0;
+        _M_impl._M_node_count = 0;
       }
 
       // Set operations.
@@ -700,7 +711,7 @@ namespace std
     operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
 	      const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
     {
-      return lexicographical_compare(__x.begin(), __x.end(),
+      return lexicographical_compare(__x.begin(), __x.end(), 
 				     __y.begin(), __y.end());
     }
 
@@ -749,13 +760,13 @@ namespace std
 	{
 	  // Note that _Key may be a constant type.
 	  clear();
-	  _M_key_compare = __x._M_key_compare;
+	  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 	  if (__x._M_root() != 0)
 	    {
 	      _M_root() = _M_copy(__x._M_begin(), _M_end());
 	      _M_leftmost() = _S_minimum(_M_root());
 	      _M_rightmost() = _S_maximum(_M_root());
-	      _M_node_count = __x._M_node_count;
+	      _M_impl._M_node_count = __x._M_impl._M_node_count;
 	    }
 	}
       return *this;
@@ -771,10 +782,12 @@ namespace std
       bool __insert_left;
 
       __insert_left = __x != 0 || __p == _M_end()
-	              || _M_key_compare(_KeyOfValue()(__v), _S_key(__p));
+	              || _M_impl._M_key_compare(_KeyOfValue()(__v), 
+						_S_key(__p));
 
-      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  this->_M_header);
-      ++_M_node_count;
+      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  
+				    this->_M_impl._M_header);
+      ++_M_impl._M_node_count;
       return iterator(__z);
     }
 
@@ -789,7 +802,7 @@ namespace std
       while (__x != 0)
 	{
 	  __y = __x;
-	  __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
+	  __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
 	        _S_left(__x) : _S_right(__x);
 	}
       return _M_insert(__x, __y, __v);
@@ -836,8 +849,8 @@ namespace std
 	__t._M_root()->_M_parent = __t._M_end();
       }
       // No need to swap header's color as it does not change.
-      std::swap(this->_M_node_count, __t._M_node_count);
-      std::swap(this->_M_key_compare, __t._M_key_compare);
+      std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
+      std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -853,7 +866,7 @@ namespace std
       while (__x != 0)
 	{
 	  __y = __x;
-	  __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
+	  __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
 	  __x = __comp ? _S_left(__x) : _S_right(__x);
 	}
       iterator __j = iterator(__y);
@@ -862,7 +875,7 @@ namespace std
 	  return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
 	else
 	  --__j;
-      if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
+      if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
 	return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
       return pair<iterator,bool>(__j, false);
     }
@@ -877,16 +890,18 @@ namespace std
 	{
 	  // begin()
 	  if (size() > 0
-	      && _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
+	      && _M_impl._M_key_compare(_KeyOfValue()(__v), 
+					_S_key(__position._M_node)))
 	    return _M_insert(__position._M_node, __position._M_node, __v);
-	  // first argument just needs to be non-null
+	  // First argument just needs to be non-null.
 	  else
 	    return insert_unique(__v).first;
 	}
       else if (__position._M_node == _M_end())
 	{
 	  // end()
-	  if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
+	  if (_M_impl._M_key_compare(_S_key(_M_rightmost()), 
+				     _KeyOfValue()(__v)))
 	    return _M_insert(0, _M_rightmost(), __v);
 	  else
 	    return insert_unique(__v).first;
@@ -895,14 +910,16 @@ namespace std
 	{
 	  iterator __before = __position;
 	  --__before;
-	  if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v))
-	      && _M_key_compare(_KeyOfValue()(__v),_S_key(__position._M_node)))
+	  if (_M_impl._M_key_compare(_S_key(__before._M_node), 
+				     _KeyOfValue()(__v))
+	      && _M_impl._M_key_compare(_KeyOfValue()(__v),
+					_S_key(__position._M_node)))
 	    {
 	      if (_S_right(__before._M_node) == 0)
 		return _M_insert(0, __before._M_node, __v);
 	      else
 		return _M_insert(__position._M_node, __position._M_node, __v);
-	      // first argument just needs to be non-null
+	      // First argument just needs to be non-null.
 	    }
 	  else
 	    return insert_unique(__v).first;
@@ -919,8 +936,8 @@ namespace std
 	{
 	  // begin()
 	  if (size() > 0
-	      && !_M_key_compare(_S_key(__position._M_node),
-				 _KeyOfValue()(__v)))
+	      && !_M_impl._M_key_compare(_S_key(__position._M_node),
+					 _KeyOfValue()(__v)))
 	    return _M_insert(__position._M_node, __position._M_node, __v);
 	  // first argument just needs to be non-null
 	  else
@@ -929,7 +946,8 @@ namespace std
       else if (__position._M_node == _M_end())
 	{
 	  // end()
-	  if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
+	  if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 
+				      _S_key(_M_rightmost())))
 	    return _M_insert(0, _M_rightmost(), __v);
 	  else
 	    return insert_equal(__v);
@@ -938,15 +956,16 @@ namespace std
 	{
 	  iterator __before = __position;
 	  --__before;
-	  if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))
-	      && !_M_key_compare(_S_key(__position._M_node),
-				 _KeyOfValue()(__v)))
+	  if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 
+				      _S_key(__before._M_node))
+	      && !_M_impl._M_key_compare(_S_key(__position._M_node),
+					 _KeyOfValue()(__v)))
 	    {
 	      if (_S_right(__before._M_node) == 0)
 		return _M_insert(0, __before._M_node, __v);
 	      else
 		return _M_insert(__position._M_node, __position._M_node, __v);
-	      // first argument just needs to be non-null
+	      // First argument just needs to be non-null.
 	    }
 	  else
 	    return insert_equal(__v);
@@ -982,9 +1001,9 @@ namespace std
     {
       _Link_type __y =
 	static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node,
-							     this->_M_header));
+							     this->_M_impl._M_header));
       destroy_node(__y);
-      --_M_node_count;
+      --_M_impl._M_node_count;
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1080,14 +1099,14 @@ namespace std
       _Link_type __y = _M_end(); // Last node which is not less than __k.
 
       while (__x != 0)
-	if (!_M_key_compare(_S_key(__x), __k))
+	if (!_M_impl._M_key_compare(_S_key(__x), __k))
 	  __y = __x, __x = _S_left(__x);
 	else
 	  __x = _S_right(__x);
 
       iterator __j = iterator(__y);
-      return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
-	end() : __j;
+      return (__j == end() 
+	  || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1101,14 +1120,14 @@ namespace std
 
      while (__x != 0)
        {
-	 if (!_M_key_compare(_S_key(__x), __k))
+	 if (!_M_impl._M_key_compare(_S_key(__x), __k))
 	   __y = __x, __x = _S_left(__x);
 	 else
 	   __x = _S_right(__x);
        }
      const_iterator __j = const_iterator(__y);
-     return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
-       end() : __j;
+     return (__j == end() 
+	  || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1132,7 +1151,7 @@ namespace std
       _Link_type __y = _M_end(); // Last node which is not less than __k.
 
       while (__x != 0)
-	if (!_M_key_compare(_S_key(__x), __k))
+	if (!_M_impl._M_key_compare(_S_key(__x), __k))
 	  __y = __x, __x = _S_left(__x);
 	else
 	  __x = _S_right(__x);
@@ -1150,7 +1169,7 @@ namespace std
       _Const_Link_type __y = _M_end(); // Last node which is not less than __k.
 
       while (__x != 0)
-	if (!_M_key_compare(_S_key(__x), __k))
+	if (!_M_impl._M_key_compare(_S_key(__x), __k))
 	  __y = __x, __x = _S_left(__x);
 	else
 	  __x = _S_right(__x);
@@ -1168,7 +1187,7 @@ namespace std
       _Link_type __y = _M_end(); // Last node which is greater than __k.
 
       while (__x != 0)
-	if (_M_key_compare(__k, _S_key(__x)))
+	if (_M_impl._M_key_compare(__k, _S_key(__x)))
 	  __y = __x, __x = _S_left(__x);
 	else
 	  __x = _S_right(__x);
@@ -1186,7 +1205,7 @@ namespace std
       _Const_Link_type __y = _M_end(); // Last node which is greater than __k.
 
       while (__x != 0)
-	if (_M_key_compare(__k, _S_key(__x)))
+	if (_M_impl._M_key_compare(__k, _S_key(__x)))
 	  __y = __x, __x = _S_left(__x);
 	else
 	  __x = _S_right(__x);
@@ -1224,10 +1243,10 @@ namespace std
     bool
     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
     {
-      if (_M_node_count == 0 || begin() == end())
-	return _M_node_count == 0 && begin() == end()
-	       && this->_M_header._M_left == _M_end()
-	       && this->_M_header._M_right == _M_end();
+      if (_M_impl._M_node_count == 0 || begin() == end())
+	return _M_impl._M_node_count == 0 && begin() == end()
+	       && this->_M_impl._M_header._M_left == _M_end()
+	       && this->_M_impl._M_header._M_right == _M_end();
 
       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
       for (const_iterator __it = begin(); __it != end(); ++__it)
@@ -1241,9 +1260,9 @@ namespace std
 		|| (__R && __R->_M_color == _S_red))
 	      return false;
 
-	  if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
+	  if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
 	    return false;
-	  if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
+	  if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
 	    return false;
 
 	  if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
@@ -1259,3 +1278,4 @@ namespace std
 } // namespace std
 
 #endif
+
diff --git a/libstdc++-v3/testsuite/23_containers/map/operators/1_neg.cc b/libstdc++-v3/testsuite/23_containers/map/operators/1_neg.cc
index 8430232..64a1d7d 100644
--- a/libstdc++-v3/testsuite/23_containers/map/operators/1_neg.cc
+++ b/libstdc++-v3/testsuite/23_containers/map/operators/1_neg.cc
@@ -41,5 +41,5 @@ void test01()
   test &= itr == mapByName.end(); // { dg-error "no" } 
 }
  
-// { dg-error "candidates are" "" { target *-*-* } 212 } 
-// { dg-error "candidates are" "" { target *-*-* } 216 }
+// { dg-error "candidates are" "" { target *-*-* } 209 } 
+// { dg-error "candidates are" "" { target *-*-* } 213 }
diff --git a/libstdc++-v3/testsuite/23_containers/set/operators/1_neg.cc b/libstdc++-v3/testsuite/23_containers/set/operators/1_neg.cc
index e178b8c..8af78f3 100644
--- a/libstdc++-v3/testsuite/23_containers/set/operators/1_neg.cc
+++ b/libstdc++-v3/testsuite/23_containers/set/operators/1_neg.cc
@@ -39,5 +39,6 @@ void test01()
   test &= itr == setByName.end(); // { dg-error "no" } 
 }
 
-// { dg-error "candidates are" "" { target *-*-* } 285 }
-// { dg-error "candidates are" "" { target *-*-* } 289 } 
+// { dg-error "candidates are" "" { target *-*-* } 282 } 
+// { dg-error "candidates are" "" { target *-*-* } 286 }
+