stl_tree.h

linux下编程用 编译软件

      { 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);

      const_iterator
      _M_insert(_Const_Base_ptr __x, _Const_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 iterator(static_cast<_Link_type>
			(this->_M_impl._M_header._M_left));
      }

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

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

      const_iterator
      end() const
      { 
	return const_iterator(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);

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

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

      const_iterator
      insert_equal(const_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);

      void
      erase(const_iterator __position);

      size_type
      erase(const key_type& __x);

      void
      erase(iterator __first, iterator __last);

      void
      erase(const_iterator __first, const_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)
    {
      bool __insert_left = (__x != 0 || __p == _M_end()
			    || _M_impl._M_key_compare(_KeyOfValue()(__v), 
						      _S_key(__p)));

      _Link_type __z = _M_create_node(__v);

      _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>::const_iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
    {
      bool __insert_left = (__x != 0 || __p == _M_end()
			    || _M_impl._M_key_compare(_KeyOfValue()(__v), 
						      _S_key(__p)));

      _Link_type __z = _M_create_node(__v);

      _Rb_tree_insert_and_rebalance(__insert_left, __z,
				    const_cast<_Base_ptr>(__p),  
				    this->_M_impl._M_header);
      ++_M_impl._M_node_count;
      return const_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);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
			   _Compare, _Alloc>::iterator, bool>
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    insert_unique(const _Val& __v)
    {
      _Link_type __x = _M_begin();
      _Link_type __y = _M_end();
      bool __comp = true;
      while (__x != 0)
	{
	  __y = __x;
	  __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
	  __x = __comp ? _S_left(__x) : _S_right(__x);
	}
      iterator __j = iterator(__y);
      if (__comp)
	if (__j == begin())
	  return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
	else
	  --__j;
      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);
    }

  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_unique(iterator __position, const _Val& __v)
    {
      // end()
      if (__position._M_node == _M_end())
	{
	  if (size() > 0
	      && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
					_KeyOfValue()(__v)))
	    return _M_insert(0, _M_rightmost(), __v);
	  else
	    return insert_unique(__v).first;
	}
      else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
				      _S_key(__position._M_node)))
	{
	  // 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(_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 insert_unique(__v).first;
	}
      else if (_M_impl._M_key_compare(_S_key(__position._M_node),
				      _KeyOfValue()(__v)))
	{
	  // ... 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(_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 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>::const_iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    insert_unique(const_iterator __position, const _Val& __v)
    {
      // end()
      if (__position._M_node == _M_end())
	{