stl_tree.h

symbian上STL模板库的实现

                                _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);
                        // First argument just needs to be non-null.
                    }
                    else
                        return 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(*__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(*__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>
            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 _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