stl_deque.h

来自「symbian上STL模板库的实现」· C头文件 代码 · 共 1,143 行 · 第 1/5 页

                    _M_node = __new_node;
                    _M_first = *__new_node;
                    _M_last = _M_first + difference_type(_S_buffer_size());
                }
        };

    // Note: we also provide overloads whose operands are of the same type in
    // order to avoid ambiguous overload resolution when std::rel_ops operators
    // are in scope (for additional details, see libstdc++/3628)
    template<typename _Tp, typename _Ref, typename _Ptr>
        inline bool
        operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
        { return __x._M_cur == __y._M_cur; }

    template<typename _Tp, typename _RefL, typename _PtrL,
        typename _RefR, typename _PtrR>
            inline bool
            operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
                    const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
            { return __x._M_cur == __y._M_cur; }

    template<typename _Tp, typename _Ref, typename _Ptr>
        inline bool
        operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
        { return !(__x == __y); }

    template<typename _Tp, typename _RefL, typename _PtrL,
        typename _RefR, typename _PtrR>
            inline bool
            operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
                    const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
            { return !(__x == __y); }

    template<typename _Tp, typename _Ref, typename _Ptr>
        inline bool
        operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
        { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
            : (__x._M_node < __y._M_node); }

            template<typename _Tp, typename _RefL, typename _PtrL,
                typename _RefR, typename _PtrR>
                    inline bool
                    operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
                            const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
                    { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
                        : (__x._M_node < __y._M_node); }

                        template<typename _Tp, typename _Ref, typename _Ptr>
                            inline bool
                            operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
                                    const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
                            { return __y < __x; }

                        template<typename _Tp, typename _RefL, typename _PtrL,
                            typename _RefR, typename _PtrR>
                                inline bool
                                operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
                                        const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
                                { return __y < __x; }

                        template<typename _Tp, typename _Ref, typename _Ptr>
                            inline bool
                            operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
                                    const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
                            { return !(__y < __x); }

                        template<typename _Tp, typename _RefL, typename _PtrL,
                            typename _RefR, typename _PtrR>
                                inline bool
                                operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
                                        const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
                                { return !(__y < __x); }

                        template<typename _Tp, typename _Ref, typename _Ptr>
                            inline bool
                            operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
                                    const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
                            { return !(__x < __y); }

                        template<typename _Tp, typename _RefL, typename _PtrL,
                            typename _RefR, typename _PtrR>
                                inline bool
                                operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
                                        const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
                                { return !(__x < __y); }

                        // _GLIBCXX_RESOLVE_LIB_DEFECTS
                        // According to the resolution of DR179 not only the various comparison
                        // operators but also operator- must accept mixed iterator/const_iterator
                        // parameters.
                        template<typename _Tp, typename _RefL, typename _PtrL,
                            typename _RefR, typename _PtrR>
                                inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
                                operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
                                        const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
                                {
                                    return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
                                        (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
                                        * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
                                        + (__y._M_last - __y._M_cur);
                                }

                        template<typename _Tp, typename _Ref, typename _Ptr>
                            inline _Deque_iterator<_Tp, _Ref, _Ptr>
                            operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
                            { return __x + __n; }

                        /**
                         *  @if maint
                         *  Deque base class.  This class provides the unified face for %deque's
                         *  allocation.  This class's constructor and destructor allocate and
                         *  deallocate (but do not initialize) storage.  This makes %exception
                         *  safety easier.
                         *
                         *  Nothing in this class ever constructs or destroys an actual Tp element.
                         *  (Deque handles that itself.)  Only/All memory management is performed
                         *  here.
                         *  @endif
                         */
                        template<typename _Tp, typename _Alloc>
                            class _Deque_base
                            {
                                public:
                                    typedef _Alloc                  allocator_type;

                                    allocator_type
                                        get_allocator() const
                                        { return *static_cast<const _Alloc*>(&this->_M_impl); }

                                    typedef _Deque_iterator<_Tp,_Tp&,_Tp*>             iterator;
                                    typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;

                                    _Deque_base(const allocator_type& __a, size_t __num_elements)
                                        : _M_impl(__a)
                                    { _M_initialize_map(__num_elements); }

                                    _Deque_base(const allocator_type& __a)
                                        : _M_impl(__a)
                                    { }

                                    ~_Deque_base();

                                protected:
                                    //This struct encapsulates the implementation of the std::deque
                                    //standard container and at the same time makes use of the EBO
                                    //for empty allocators.
                                    struct _Deque_impl
                                        : public _Alloc {
                                            _Tp** _M_map;
                                            size_t _M_map_size;
                                            iterator _M_start;
                                            iterator _M_finish;

                                            _Deque_impl(const _Alloc& __a)
                                                : _Alloc(__a), _M_map(0), _M_map_size(0), _M_start(), _M_finish()
                                            { }
                                        };

                                    typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
                                    _Map_alloc_type _M_get_map_allocator() const
                                    { return _Map_alloc_type(this->get_allocator()); }

                                    _Tp*
                                        _M_allocate_node()
                                        { return _M_impl._Alloc::allocate(__deque_buf_size(sizeof(_Tp))); }

                                    void
                                        _M_deallocate_node(_Tp* __p)
                                        { _M_impl._Alloc::deallocate(__p, __deque_buf_size(sizeof(_Tp))); }

                                    _Tp**
                                        _M_allocate_map(size_t __n)
                                        { return _M_get_map_allocator().allocate(__n); }

                                    void
                                        _M_deallocate_map(_Tp** __p, size_t __n)
                                        { _M_get_map_allocator().deallocate(__p, __n); }

                                protected:
                                    void _M_initialize_map(size_t);
                                    void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
                                    void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
                                    enum { _S_initial_map_size = 8 };

                                    _Deque_impl _M_impl;
                            };

                        template<typename _Tp, typename _Alloc>
                            _Deque_base<_Tp,_Alloc>::~_Deque_base()
                            {
                                if (this->_M_impl._M_map)
                                {
                                    _M_destroy_nodes(this->_M_impl._M_start._M_node, this->_M_impl._M_finish._M_node + 1);
                                    _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
                                }
                            }

                        /**
                         *  @if maint
                         *  @brief Layout storage.
                         *  @param  num_elements  The count of T's for which to allocate space
                         *                        at first.
                         *  @return   Nothing.
                         *
                         *  The initial underlying memory layout is a bit complicated...
                         *  @endif
                         */
                        template<typename _Tp, typename _Alloc>
                            void
                            _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
                            {
                                size_t __num_nodes = __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;

                                this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
                                        __num_nodes + 2);
                                this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);

                                // For "small" maps (needing less than _M_map_size nodes), allocation
                                // starts in the middle elements and grows outwards.  So nstart may be
                                // the beginning of _M_map, but for small maps it may be as far in as
                                // _M_map+3.

                                _Tp** __nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size - __num_nodes) / 2;
                                _Tp** __nfinish = __nstart + __num_nodes;

                                try