stl_tree.h

自己做的交叉编译工具！gcc-3.4.5,glibc-2.3.6在ubuntu8.04上做的面向kernel-2.6.28的交叉编译工具

	    this->_M_header._M_right = &this->_M_header;
	  }
	};

      _Rb_tree_impl<_Compare> _M_impl;

    protected:
      _Base_ptr&
      _M_root()
      { return this->_M_impl._M_header._M_parent; }

      _Const_Base_ptr
      _M_root() const
      { return this->_M_impl._M_header._M_parent; }

      _Base_ptr&
      _M_leftmost()
      { return this->_M_impl._M_header._M_left; }

      _Const_Base_ptr
      _M_leftmost() const
      { return this->_M_impl._M_header._M_left; }

      _Base_ptr&
      _M_rightmost()
      { return this->_M_impl._M_header._M_right; }

      _Const_Base_ptr
      _M_rightmost() const
      { return this->_M_impl._M_header._M_right; }

      _Link_type
      _M_begin()
      { 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_impl._M_header._M_parent); }

      _Link_type
      _M_end()
      { return static_cast<_Link_type>(&this->_M_impl._M_header); }

      _Const_Link_type
      _M_end() const
      { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }

      static const_reference
      _S_value(_Const_Link_type __x)
      { return __x->_M_value_field; }

      static const _Key&
      _S_key(_Const_Link_type __x)
      { return _KeyOfValue()(_S_value(__x)); }

      static _Link_type
      _S_left(_Base_ptr __x)
      { return static_cast<_Link_type>(__x->_M_left); }

      static _Const_Link_type
      _S_left(_Const_Base_ptr __x)
      { return static_cast<_Const_Link_type>(__x->_M_left); }

      static _Link_type
      _S_right(_Base_ptr __x)
      { return static_cast<_Link_type>(__x->_M_right); }

      static _Const_Link_type
      _S_right(_Const_Base_ptr __x)
      { return static_cast<_Const_Link_type>(__x->_M_right); }

      static const_reference
      _S_value(_Const_Base_ptr __x)
      { return static_cast<_Const_Link_type>(__x)->_M_value_field; }

      static const _Key&
      _S_key(_Const_Base_ptr __x)
      { return _KeyOfValue()(_S_value(__x)); }

      static _Base_ptr
      _S_minimum(_Base_ptr __x)
      { return _Rb_tree_node_base::_S_minimum(__x); }

      static _Const_Base_ptr
      _S_minimum(_Const_Base_ptr __x)
      { return _Rb_tree_node_base::_S_minimum(__x); }

      static _Base_ptr
      _S_maximum(_Base_ptr __x)
      { return _Rb_tree_node_base::_S_maximum(__x); }

      static _Const_Base_ptr
      _S_maximum(_Const_Base_ptr __x)
      { return _Rb_tree_node_base::_S_maximum(__x); }

    public:
      typedef _Rb_tree_iterator<value_type>       iterator;
      typedef _Rb_tree_const_iterator<value_type> const_iterator;

      typedef std::reverse_iterator<iterator>       reverse_iterator;
      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    private:
      iterator
      _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);

      _Link_type
      _M_copy(_Const_Link_type __x, _Link_type __p);

      void
      _M_erase(_Link_type __x);

    public:
      // allocation/deallocation
      _Rb_tree()
      { }

      _Rb_tree(const _Compare& __comp)
      : _M_impl(allocator_type(), __comp)
      { }

      _Rb_tree(const _Compare& __comp, const allocator_type& __a)
      : _M_impl(__a, __comp)
      { }

      _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
      : _M_impl(__x.get_allocator(), __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_impl._M_node_count = __x._M_impl._M_node_count;
	  }
      }

      ~_Rb_tree()
      { _M_erase(_M_begin()); }

      _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
      operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);

      // Accessors.
      _Compare
      key_comp() const
      { return _M_impl._M_key_compare; }

      iterator
      begin()
      { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }

      const_iterator
      begin() const
      { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left); }

      iterator
      end()
      { return static_cast<_Link_type>(&this->_M_impl._M_header); }

      const_iterator
      end() const
      { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }

      reverse_iterator
      rbegin()
      { return reverse_iterator(end()); }

      const_reverse_iterator
      rbegin() const
      { return const_reverse_iterator(end()); }

      reverse_iterator
      rend()
      { return reverse_iterator(begin()); }

      const_reverse_iterator
      rend() const
      { return const_reverse_iterator(begin()); }

      bool
      empty() const
      { return _M_impl._M_node_count == 0; }

      size_type
      size() const
      { return _M_impl._M_node_count; }

      size_type
      max_size() const
      { return size_type(-1); }

      void
      swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t);

      // Insert/erase.
      pair<iterator,bool>
      insert_unique(const value_type& __x);

      iterator
      insert_equal(const value_type& __x);

      iterator
      insert_unique(iterator __position, const value_type& __x);

      iterator
      insert_equal(iterator __position, const value_type& __x);

      template<typename _InputIterator>
      void
      insert_unique(_InputIterator __first, _InputIterator __last);

      template<typename _InputIterator>
      void
      insert_equal(_InputIterator __first, _InputIterator __last);

      void
      erase(iterator __position);

      size_type
      erase(const key_type& __x);

      void
      erase(iterator __first, iterator __last);

      void
      erase(const key_type* __first, const key_type* __last);

      void
      clear()
      {
        _M_erase(_M_begin());
        _M_leftmost() = _M_end();
        _M_root() = 0;
        _M_rightmost() = _M_end();
        _M_impl._M_node_count = 0;
      }

      // Set operations.
      iterator
      find(const key_type& __x);

      const_iterator
      find(const key_type& __x) const;

      size_type
      count(const key_type& __x) const;

      iterator
      lower_bound(const key_type& __x);

      const_iterator
      lower_bound(const key_type& __x) const;

      iterator
      upper_bound(const key_type& __x);

      const_iterator
      upper_bound(const key_type& __x) const;

      pair<iterator,iterator>
      equal_range(const key_type& __x);

      pair<const_iterator, const_iterator>
      equal_range(const key_type& __x) const;

      // Debugging.
      bool
      __rb_verify() const;
    };

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    inline bool
    operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
	       const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
    {
      return __x.size() == __y.size()
	     && std::equal(__x.begin(), __x.end(), __y.begin());
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    inline bool
    operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
	      const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
    {
      return std::lexicographical_compare(__x.begin(), __x.end(), 
					  __y.begin(), __y.end());
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    inline bool
    operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
	       const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
    { return !(__x == __y); }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    inline bool
    operator>(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
	      const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
    { return __y < __x; }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    inline bool
    operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
	       const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
    { return !(__y < __x); }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    inline bool
    operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
	       const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
    { return !(__x < __y); }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    inline void
    swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
	 _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
    { __x.swap(__y); }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
    {
      if (this != &__x)
	{
	  // Note that _Key may be a constant type.
	  clear();
	  _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_impl._M_node_count = __x._M_impl._M_node_count;
	    }
	}
      return *this;
    }

  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>::
    _M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
    {
      _Link_type __z = _M_create_node(__v);
      bool __insert_left;

      __insert_left = __x != 0 || __p == _M_end()
	              || _M_impl._M_key_compare(_KeyOfValue()(__v), 
						_S_key(__p));

      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  
				    this->_M_impl._M_header);
      ++_M_impl._M_node_count;
      return iterator(__z);
    }

  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(const _Val& __v)
    {
      _Link_type __x = _M_begin();
      _Link_type __y = _M_end();
      while (__x != 0)
	{
	  __y = __x;
	  __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
	        _S_left(__x) : _S_right(__x);
	}
      return _M_insert(__x, __y, __v);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    void
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t)
    {
      if (_M_root() == 0)
      {
	if (__t._M_root() != 0)
	{
	  _M_root() = __t._M_root();
	  _M_leftmost() = __t._M_leftmost();
	  _M_rightmost() = __t._M_rightmost();
          _M_root()->_M_parent = _M_end();

	  __t._M_root() = 0;
	  __t._M_leftmost() = __t._M_end();
	  __t._M_rightmost() = __t._M_end();
	}
      }
      else if (__t._M_root() == 0)
      {
	__t._M_root() = _M_root();
	__t._M_leftmost() = _M_leftmost();
	__t._M_rightmost() = _M_rightmost();
        __t._M_root()->_M_parent = __t._M_end();

	_M_root() = 0;
	_M_leftmost() = _M_end();
	_M_rightmost() = _M_end();
      }
      else
      {
	std::swap(_M_root(),__t._M_root());
	std::swap(_M_leftmost(),__t._M_leftmost());
	std::swap(_M_rightmost(),__t._M_rightmost());

	_M_root()->_M_parent = _M_end();
	__t._M_root()->_M_parent = __t._M_end();
      }
      // No need to swap header's color as it does not change.
      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);
    }