stl_tree.h

symbian上STL模板库的实现

            {
                typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
                    _Node_allocator;

                protected:
                typedef _Rb_tree_node_base* _Base_ptr;
                typedef const _Rb_tree_node_base* _Const_Base_ptr;
                typedef _Rb_tree_node<_Val> _Rb_tree_node;

                public:
                typedef _Key key_type;
                typedef _Val value_type;
                typedef value_type* pointer;
                typedef const value_type* const_pointer;
                typedef value_type& reference;
                typedef const value_type& const_reference;
                typedef _Rb_tree_node* _Link_type;
                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->_M_impl); }

                protected:
                _Rb_tree_node*
                    _M_get_node()
                    { return _M_impl._Node_allocator::allocate(1); }

                void
                    _M_put_node(_Rb_tree_node* __p)
                    { _M_impl._Node_allocator::deallocate(__p, 1); }

                _Link_type
                    _M_create_node(const value_type& __x)
                    {
                        _Link_type __tmp = _M_get_node();
                        try
                        { std::_Construct(&__tmp->_M_value_field, __x); }
                        catch(...)
                        {
                            _M_put_node(__tmp);
                            __throw_exception_again;
                        }
                        return __tmp;
                    }

                _Link_type
                    _M_clone_node(_Const_Link_type __x)
                    {
                        _Link_type __tmp = _M_create_node(__x->_M_value_field);
                        __tmp->_M_color = __x->_M_color;
                        __tmp->_M_left = 0;
                        __tmp->_M_right = 0;
                        return __tmp;
                    }

                void
                    destroy_node(_Link_type __p)
                    {
                        std::_Destroy(&__p->_M_value_field);
                        _M_put_node(__p);
                    }

                protected:

                template<typename _Key_compare, 
                    bool _Is_pod_comparator 
                    #if !defined (__EPOC32__) || (__GNUC__ > 2)
                    = std::__is_pod<_Key_compare >::_M_type 
                    #endif
                    >
                        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_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;
                        }
                    };

#if !defined (__EPOC32__) || (__GNUC__ > 2)
                // 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;
                        }
                    };
#endif

#if !defined (__EPOC32__) || (__GNUC__ > 2)
                _Rb_tree_impl<_Compare> _M_impl;
#else
				_Rb_tree_impl<_Compare, std::__is_pod<_Compare >::_M_type > _M_impl;
#endif

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