stl_deque.h

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

                                { _M_create_nodes(__nstart, __nfinish); }
                                catch(...)
                                {
                                    _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
                                    this->_M_impl._M_map = 0;
                                    this->_M_impl._M_map_size = 0;
                                    __throw_exception_again;
                                }

                                this->_M_impl._M_start._M_set_node(__nstart);
                                this->_M_impl._M_finish._M_set_node(__nfinish - 1);
                                this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
                                this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first + __num_elements
                                    % __deque_buf_size(sizeof(_Tp));
                            }

                        template<typename _Tp, typename _Alloc>
                            void
                            _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
                            {
                                _Tp** __cur;
                                try
                                {
                                    for (__cur = __nstart; __cur < __nfinish; ++__cur)
                                        *__cur = this->_M_allocate_node();
                                }
                                catch(...)
                                {
                                    _M_destroy_nodes(__nstart, __cur);
                                    __throw_exception_again;
                                }
                            }

                        template<typename _Tp, typename _Alloc>
                            void
                            _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
                            {
                                for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
                                    _M_deallocate_node(*__n);
                            }

                        /**
                         *  @brief  A standard container using fixed-size memory allocation and
                         *  constant-time manipulation of elements at either end.
                         *
                         *  @ingroup Containers
                         *  @ingroup Sequences
                         *
                         *  Meets the requirements of a <a href="tables.html#65">container</a>, a
                         *  <a href="tables.html#66">reversible container</a>, and a
                         *  <a href="tables.html#67">sequence</a>, including the
                         *  <a href="tables.html#68">optional sequence requirements</a>.
                         *
                         *  In previous HP/SGI versions of deque, there was an extra template
                         *  parameter so users could control the node size.  This extension turned
                         *  out to violate the C++ standard (it can be detected using template
                         *  template parameters), and it was removed.
                         *
                         *  @if maint
                         *  Here's how a deque<Tp> manages memory.  Each deque has 4 members:
                         *
                         *  - Tp**        _M_map
                         *  - size_t      _M_map_size
                         *  - iterator    _M_start, _M_finish
                         *
                         *  map_size is at least 8.  %map is an array of map_size pointers-to-"nodes".
                         *  (The name %map has nothing to do with the std::map class, and "nodes"
                         *  should not be confused with std::list's usage of "node".)
                         *
                         *  A "node" has no specific type name as such, but it is referred to as
                         *  "node" in this file.  It is a simple array-of-Tp.  If Tp is very large,
                         *  there will be one Tp element per node (i.e., an "array" of one).
                         *  For non-huge Tp's, node size is inversely related to Tp size:  the
                         *  larger the Tp, the fewer Tp's will fit in a node.  The goal here is to
                         *  keep the total size of a node relatively small and constant over different
                         *  Tp's, to improve allocator efficiency.
                         *
                         *  **** As I write this, the nodes are /not/ allocated using the high-speed
                         *  memory pool.  There are 20 hours left in the year; perhaps I can fix
                         *  this before 2002.
                         *
                         *  Not every pointer in the %map array will point to a node.  If the initial
                         *  number of elements in the deque is small, the /middle/ %map pointers will
                         *  be valid, and the ones at the edges will be unused.  This same situation
                         *  will arise as the %map grows:  available %map pointers, if any, will be on
                         *  the ends.  As new nodes are created, only a subset of the %map's pointers
                         *  need to be copied "outward".
                         *
                         *  Class invariants:
                         * - For any nonsingular iterator i:
                         *    - i.node points to a member of the %map array.  (Yes, you read that
                         *      correctly:  i.node does not actually point to a node.)  The member of
                         *      the %map array is what actually points to the node.
                         *    - i.first == *(i.node)    (This points to the node (first Tp element).)
                         *    - i.last  == i.first + node_size
                         *    - i.cur is a pointer in the range [i.first, i.last).  NOTE:
                         *      the implication of this is that i.cur is always a dereferenceable
                         *      pointer, even if i is a past-the-end iterator.
                         * - Start and Finish are always nonsingular iterators.  NOTE: this means that
                         *   an empty deque must have one node, a deque with <N elements (where N is
                         *   the node buffer size) must have one node, a deque with N through (2N-1)
                         *   elements must have two nodes, etc.
                         * - For every node other than start.node and finish.node, every element in
                         *   the node is an initialized object.  If start.node == finish.node, then
                         *   [start.cur, finish.cur) are initialized objects, and the elements outside
                         *   that range are uninitialized storage.  Otherwise, [start.cur, start.last)
                         *   and [finish.first, finish.cur) are initialized objects, and [start.first,
                         *   start.cur) and [finish.cur, finish.last) are uninitialized storage.
                         * - [%map, %map + map_size) is a valid, non-empty range.
                         * - [start.node, finish.node] is a valid range contained within
                         *   [%map, %map + map_size).
                         * - A pointer in the range [%map, %map + map_size) points to an allocated
                        *   node if and only if the pointer is in the range
                            *   [start.node, finish.node].
                            *
                            *  Here's the magic:  nothing in deque is "aware" of the discontiguous
                            *  storage!
                            *
                            *  The memory setup and layout occurs in the parent, _Base, and the iterator
                            *  class is entirely responsible for "leaping" from one node to the next.
                            *  All the implementation routines for deque itself work only through the
                            *  start and finish iterators.  This keeps the routines simple and sane,
                            *  and we can use other standard algorithms as well.
                                *  @endif
                                */
                                template<typename _Tp, typename _Alloc = allocator<_Tp> >
                                class deque : protected _Deque_base<_Tp, _Alloc>
                                {
                                    // concept requirements
                                    __glibcxx_class_requires(_Tp, _SGIAssignableConcept)

                                        typedef _Deque_base<_Tp, _Alloc>           _Base;

                                    public:
                                    typedef _Tp                                value_type;
                                    typedef typename _Alloc::pointer           pointer;
                                    typedef typename _Alloc::const_pointer     const_pointer;
                                    typedef typename _Alloc::reference         reference;
                                    typedef typename _Alloc::const_reference   const_reference;
                                    typedef typename _Base::iterator           iterator;
                                    typedef typename _Base::const_iterator     const_iterator;
                                    typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;
                                    typedef std::reverse_iterator<iterator>         reverse_iterator;
                                    typedef size_t                             size_type;
                                    typedef ptrdiff_t                          difference_type;
                                    typedef typename _Base::allocator_type     allocator_type;

                                    protected:
                                    typedef pointer*                           _Map_pointer;

                                    static size_t _S_buffer_size()
                                    { return __deque_buf_size(sizeof(_Tp)); }

                                    // Functions controlling memory layout, and nothing else.
                                    using _Base::_M_initialize_map;
                                    using _Base::_M_create_nodes;
                                    using _Base::_M_destroy_nodes;
                                    using _Base::_M_allocate_node;
                                    using _Base::_M_deallocate_node;
                                    using _Base::_M_allocate_map;
                                    using _Base::_M_deallocate_map;

                                    /** @if maint
                                     *  A total of four data members accumulated down the heirarchy.
                                     *  May be accessed via _M_impl.*
                                     *  @endif
                                     */
                                    using _Base::_M_impl;

                                    public:
                                    // [23.2.1.1] construct/copy/destroy
                                    // (assign() and get_allocator() are also listed in this section)
                                    /**
                                     *  @brief  Default constructor creates no elements.
                                     */
                                    explicit
                                        deque(const allocator_type& __a = allocator_type())
                                        : _Base(__a, 0) {}

                                    /**
                                     *  @brief  Create a %deque with copies of an exemplar element.
                                     *  @param  n  The number of elements to initially create.
                                     *  @param  value  An element to copy.
                                     *
                                     *  This constructor fills the %deque with @a n copies of @a value.
                                     */
                                    deque(size_type __n, const value_type& __value,
                                            const allocator_type& __a = allocator_type())
                                        : _Base(__a, __n)
                                    { _M_fill_initialize(__value); }

                                    /**
                                     *  @brief  Create a %deque with default elements.
                                     *  @param  n  The number of elements to initially create.
                                     *
                                     *  This constructor fills the %deque with @a n copies of a
                                     *  default-constructed element.
                                     */
                                    explicit
                                        deque(size_type __n)
                                        : _Base(allocator_type(), __n)
                                        { _M_fill_initialize(value_type()); }

                                    /**
                                     *  @brief  %Deque copy constructor.
                                     *  @param  x  A %deque of identical element and allocator types.
                                     *
                                     *  The newly-created %deque uses a copy of the allocation object used
                                     *  by @a x.
                                     */
                                    deque(const deque& __x)
                                        : _Base(__x.get_allocator(), __x.size())
                                    { std::uninitialized_copy(__x.begin(), __x.end(), this->_M_impl._M_start); }

                                    /**
                                     *  @brief  Builds a %deque from a range.
                                     *  @param  first  An input iterator.
                                     *  @param  last  An input iterator.
                                     *
                                     *  Create a %deque consisting of copies of the elements from [first,
                                     *  last).
                                     *
                                     *  If the iterators are forward, bidirectional, or random-access, then
                                     *  this will call the elements' copy constructor N times (where N is
                                     *  distance(first,last)) and do no memory reallocation.  But if only
                                     *  input iterators are used, then this will do at most 2N calls to the
                                     *  copy constructor, and logN memory reallocations.
                                     */
                                    template<typename _InputIterator>