stl_tree.h

linux下编程用 编译软件

	  if (size() > 0
	      && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
					_KeyOfValue()(__v)))
	    return _M_insert(0, _M_rightmost(), __v);
	  else
	    return const_iterator(insert_unique(__v).first);
	}
      else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
				      _S_key(__position._M_node)))
	{
	  // First, try before...
	  const_iterator __before = __position;
	  if (__position._M_node == _M_leftmost()) // begin()
	    return _M_insert(_M_leftmost(), _M_leftmost(), __v);
	  else if (_M_impl._M_key_compare(_S_key((--__before)._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);
	    }
	  else
	    return const_iterator(insert_unique(__v).first);
	}
      else if (_M_impl._M_key_compare(_S_key(__position._M_node),
				      _KeyOfValue()(__v)))
	{
	  // ... then try after.
	  const_iterator __after = __position;
	  if (__position._M_node == _M_rightmost())
	    return _M_insert(0, _M_rightmost(), __v);
	  else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
					  _S_key((++__after)._M_node)))
	    {
	      if (_S_right(__position._M_node) == 0)
		return _M_insert(0, __position._M_node, __v);
	      else
		return _M_insert(__after._M_node, __after._M_node, __v);
	    }
	  else
	    return const_iterator(insert_unique(__v).first);
	}
      else
	return __position; // Equivalent keys.
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    insert_equal(iterator __position, const _Val& __v)
    {
      // end()
      if (__position._M_node == _M_end())
	{
	  if (size() > 0
	      && !_M_impl._M_key_compare(_KeyOfValue()(__v),
					 _S_key(_M_rightmost())))
	    return _M_insert(0, _M_rightmost(), __v);
	  else
	    return insert_equal(__v);
	}
      else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
				       _KeyOfValue()(__v)))
	{
	  // First, try before...
	  iterator __before = __position;
	  if (__position._M_node == _M_leftmost()) // begin()
	    return _M_insert(_M_leftmost(), _M_leftmost(), __v);
	  else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
					   _S_key((--__before)._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);
	    }
	  else
	    return insert_equal(__v);
	}
      else
	{
	  // ... then try after.  
	  iterator __after = __position;
	  if (__position._M_node == _M_rightmost())
	    return _M_insert(0, _M_rightmost(), __v);
	  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
					   _KeyOfValue()(__v)))
	    {
	      if (_S_right(__position._M_node) == 0)
		return _M_insert(0, __position._M_node, __v);
	      else
		return _M_insert(__after._M_node, __after._M_node, __v);
	    }
	  else
	    return insert_equal(__v);
	}
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    insert_equal(const_iterator __position, const _Val& __v)
    {
      // end()
      if (__position._M_node == _M_end())
	{
	  if (size() > 0
	      && !_M_impl._M_key_compare(_KeyOfValue()(__v),
					 _S_key(_M_rightmost())))
	    return _M_insert(0, _M_rightmost(), __v);
	  else
	    return const_iterator(insert_equal(__v));
	}
      else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
				       _KeyOfValue()(__v)))
	{
	  // First, try before...
	  const_iterator __before = __position;
	  if (__position._M_node == _M_leftmost()) // begin()
	    return _M_insert(_M_leftmost(), _M_leftmost(), __v);
	  else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
					   _S_key((--__before)._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);
	    }
	  else
	    return const_iterator(insert_equal(__v));
	}
      else
	{
	  // ... then try after.  
	  const_iterator __after = __position;
	  if (__position._M_node == _M_rightmost())
	    return _M_insert(0, _M_rightmost(), __v);
	  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
					   _KeyOfValue()(__v)))
	    {
	      if (_S_right(__position._M_node) == 0)
		return _M_insert(0, __position._M_node, __v);
	      else
		return _M_insert(__after._M_node, __after._M_node, __v);
	    }
	  else
	    return const_iterator(insert_equal(__v));
	}
    }

  template<typename _Key, typename _Val, typename _KoV,
           typename _Cmp, typename _Alloc>
    template<class _II>
      void
      _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
      insert_equal(_II __first, _II __last)
      {
	for (; __first != __last; ++__first)
	  insert_equal(end(), *__first);
      }

  template<typename _Key, typename _Val, typename _KoV,
           typename _Cmp, typename _Alloc>
    template<class _II>
      void
      _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
      insert_unique(_II __first, _II __last)
      {
	for (; __first != __last; ++__first)
	  insert_unique(end(), *__first);
      }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    inline void
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    erase(iterator __position)
    {
      _Link_type __y =
	static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
				(__position._M_node,
				 this->_M_impl._M_header));
      destroy_node(__y);
      --_M_impl._M_node_count;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    inline void
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    erase(const_iterator __position)
    {
      _Link_type __y =
	static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
				(const_cast<_Base_ptr>(__position._M_node),
				 this->_M_impl._M_header));
      destroy_node(__y);
      --_M_impl._M_node_count;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    erase(const _Key& __x)
    {
      pair<iterator,iterator> __p = equal_range(__x);
      size_type __n = std::distance(__p.first, __p.second);
      erase(__p.first, __p.second);
      return __n;
    }

  template<typename _Key, typename _Val, typename _KoV,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
    _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
    _M_copy(_Const_Link_type __x, _Link_type __p)
    {
      // Structural copy.  __x and __p must be non-null.
      _Link_type __top = _M_clone_node(__x);
      __top->_M_parent = __p;

      try
	{
	  if (__x->_M_right)
	    __top->_M_right = _M_copy(_S_right(__x), __top);
	  __p = __top;
	  __x = _S_left(__x);

	  while (__x != 0)
	    {
	      _Link_type __y = _M_clone_node(__x);
	      __p->_M_left = __y;
	      __y->_M_parent = __p;
	      if (__x->_M_right)
		__y->_M_right = _M_copy(_S_right(__x), __y);
	      __p = __y;
	      __x = _S_left(__x);
	    }
	}
      catch(...)
	{
	  _M_erase(__top);
	  __throw_exception_again;
	}
      return __top;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    void
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_erase(_Link_type __x)
    {
      // Erase without rebalancing.
      while (__x != 0)
	{
	  _M_erase(_S_right(__x));
	  _Link_type __y = _S_left(__x);
	  destroy_node(__x);
	  __x = __y;
	}
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    void
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    erase(iterator __first, iterator __last)
    {
      if (__first == begin() && __last == end())
	clear();
      else
	while (__first != __last)
	  erase(__first++);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    void
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    erase(const_iterator __first, const_iterator __last)
    {
      if (__first == begin() && __last == end())
	clear();
      else
	while (__first != __last)
	  erase(__first++);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    void
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    erase(const _Key* __first, const _Key* __last)
    {
      while (__first != __last)
	erase(*__first++);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    find(const _Key& __k)
    {
      _Link_type __x = _M_begin(); // Current node.
      _Link_type __y = _M_end(); // Last node which is not less than __k.

      while (__x != 0)
	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_impl._M_key_compare(__k,
					_S_key(__j._M_node))) ? end() : __j;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    find(const _Key& __k) const
    {
      _Const_Link_type __x = _M_begin(); // Current node.
      _Const_Link_type __y = _M_end(); // Last node which is not less than __k.

     while (__x != 0)
       {
	 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_impl._M_key_compare(__k, 
				       _S_key(__j._M_node))) ? end() : __j;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    count(const _Key& __k) const
    {
      pair<const_iterator, const_iterator> __p = equal_range(__k);
      const size_type __n = std::distance(__p.first, __p.second);
      return __n;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    lower_bound(const _Key& __k)
    {
      _Link_type __x = _M_begin(); // Current node.
      _Link_type __y = _M_end(); // Last node which is not less than __k.

      while (__x != 0)
	if (!_M_impl._M_key_compare(_S_key(__x), __k))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);

      return iterator(__y);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    lower_bound(const _Key& __k) const
    {
      _Const_Link_type __x = _M_begin(); // Current node.
      _Const_Link_type __y = _M_end(); // Last node which is not less than __k.

      while (__x != 0)
	if (!_M_impl._M_key_compare(_S_key(__x), __k))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);

      return const_iterator(__y);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    upper_bound(const _Key& __k)
    {
      _Link_type __x = _M_begin(); // Current node.
      _Link_type __y = _M_end(); // Last node which is greater than __k.

      while (__x != 0)
	if (_M_impl._M_key_compare(__k, _S_key(__x)))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);

      return iterator(__y);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    upper_bound(const _Key& __k) const
    {
      _Const_Link_type __x = _M_begin(); // Current node.
      _Const_Link_type __y = _M_end(); // Last node which is greater than __k.

      while (__x != 0)
	if (_M_impl._M_key_compare(__k, _S_key(__x)))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);

      return const_iterator(__y);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    inline
    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
			   _Compare, _Alloc>::iterator,
	 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    equal_range(const _Key& __k)
    { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }

  template<typename _Key, typename _Val, typename _KoV,
           typename _Compare, typename _Alloc>
    inline
    pair<typename _Rb_tree<_Key, _Val, _KoV,
			   _Compare, _Alloc>::const_iterator,
	 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
    _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
    equal_range(const _Key& __k) const
    { return pair<const_iterator, const_iterator>(lower_bound(__k),
						  upper_bound(__k)); }

  unsigned int
  _Rb_tree_black_count(const _Rb_tree_node_base* __node,
                       const _Rb_tree_node_base* __root);

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    bool
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
    {
      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)
	{
	  _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
	  _Const_Link_type __L = _S_left(__x);
	  _Const_Link_type __R = _S_right(__x);

	  if (__x->_M_color == _S_red)
	    if ((__L && __L->_M_color == _S_red)
		|| (__R && __R->_M_color == _S_red))
	      return false;

	  if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
	    return false;
	  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)
	    return false;
	}

      if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
	return false;
      if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
	return false;
      return true;
    }
} // namespace std

#endif