stl_tree.h

symbian上STL模板库的实现

                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()
                    && 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 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);
            }

    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)
            {
                if (__position._M_node == _M_leftmost())
                {
                    // begin()
                    if (size() > 0
                            && _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.
                    else
                        return insert_unique(__v).first;
                }
                else if (__position._M_node == _M_end())
                {
                    // end()
                    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;
                }
                else
                {
                    iterator __before = __position;
                    --__before;
                    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.
                    }
                    else
                        return insert_unique(__v).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>::
            insert_equal(iterator __position, const _Val& __v)
            {
                if (__position._M_node == _M_leftmost())
                {
                    // begin()
                    if (size() > 0
                            && !_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
                        return insert_equal(__v);
                }
                else if (__position._M_node == _M_end())
                {
                    // end()
                    if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 
                                _S_key(_M_rightmost())))
                        return _M_insert(0, _M_rightmost(), __v);
                    else
                        return insert_equal(__v);
                }
                else
                {
                    iterator __before = __position;
                    --__before;
                    if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 
                                _S_key(__before._M_node))
                            && !_M_impl._M_key_compare(_S_key(__position._M_node),