stl_list.h

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

        using _Base::_M_impl;
        using _Base::_M_put_node;
        using _Base::_M_get_node;

        /**
         *  @if maint
         *  @param  x  An instance of user data.
         *
         *  Allocates space for a new node and constructs a copy of @a x in it.
         *  @endif
         */
        _Node*
            _M_create_node(const value_type& __x)
            {
                _Node* __p = this->_M_get_node();
                try
                {
                    std::_Construct(&__p->_M_data, __x);
                }
                catch(...)
                {
                    _M_put_node(__p);
                    __throw_exception_again;
                }
                return __p;
            }

        /**
         *  @if maint
         *  Allocates space for a new node and default-constructs a new
         *  instance of @c value_type in it.
         *  @endif
         */
        _Node*
            _M_create_node()
            {
                _Node* __p = this->_M_get_node();
                try
                {
                    std::_Construct(&__p->_M_data);
                }
                catch(...)
                {
                    _M_put_node(__p);
                    __throw_exception_again;
                }
                return __p;
            }

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

        /**
         *  @brief  Create a %list 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 %list with @a n copies of @a value.
         */
        list(size_type __n, const value_type& __value,
                const allocator_type& __a = allocator_type())
            : _Base(__a)
        { this->insert(begin(), __n, __value); }

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

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

        /**
         *  @brief  Builds a %list from a range.
         *  @param  first  An input iterator.
         *  @param  last  An input iterator.
         *
         *  Create a %list consisting of copies of the elements from
         *  [@a first,@a last).  This is linear in N (where N is
         *  distance(@a first,@a last)).
         *
         *  @if maint
         *  We don't need any dispatching tricks here, because insert does all of
         *  that anyway.
         *  @endif
         */
        template<typename _InputIterator>
            list(_InputIterator __first, _InputIterator __last,
                    const allocator_type& __a = allocator_type())
            : _Base(__a)
            { this->insert(begin(), __first, __last); }

        /**
         *  No explicit dtor needed as the _Base dtor takes care of
         *  things.  The _Base dtor only erases the elements, and note
         *  that if the elements themselves are pointers, the pointed-to
         *  memory is not touched in any way.  Managing the pointer is
         *  the user's responsibilty.
         */

        /**
         *  @brief  %List assignment operator.
         *  @param  x  A %list of identical element and allocator types.
         *
         *  All the elements of @a x are copied, but unlike the copy
         *  constructor, the allocator object is not copied.
         */
        list&
            operator=(const list& __x);

        /**
         *  @brief  Assigns a given value to a %list.
         *  @param  n  Number of elements to be assigned.
         *  @param  val  Value to be assigned.
         *
         *  This function fills a %list with @a n copies of the given
         *  value.  Note that the assignment completely changes the %list
         *  and that the resulting %list's size is the same as the number
         *  of elements assigned.  Old data may be lost.
         */
        void
            assign(size_type __n, const value_type& __val)
            { _M_fill_assign(__n, __val); }

        /**
         *  @brief  Assigns a range to a %list.
         *  @param  first  An input iterator.
         *  @param  last   An input iterator.
         *
         *  This function fills a %list with copies of the elements in the
         *  range [@a first,@a last).
         *
         *  Note that the assignment completely changes the %list and
         *  that the resulting %list's size is the same as the number of
         *  elements assigned.  Old data may be lost.
         */
        template<typename _InputIterator>
            void
            assign(_InputIterator __first, _InputIterator __last)
            {
                // Check whether it's an integral type.  If so, it's not an iterator.
                typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
                _M_assign_dispatch(__first, __last, _Integral());
            }

        /// Get a copy of the memory allocation object.
        allocator_type
            get_allocator() const
            { return _Base::get_allocator(); }

        // iterators
        /**
         *  Returns a read/write iterator that points to the first element in the
         *  %list.  Iteration is done in ordinary element order.
         */
        iterator
            begin()
            { return this->_M_impl._M_node._M_next; }

        /**
         *  Returns a read-only (constant) iterator that points to the
         *  first element in the %list.  Iteration is done in ordinary
         *  element order.
         */
        const_iterator
            begin() const
            { return this->_M_impl._M_node._M_next; }

        /**
         *  Returns a read/write iterator that points one past the last
         *  element in the %list.  Iteration is done in ordinary element
         *  order.
         */
        iterator
            end() { return &this->_M_impl._M_node; }

        /**
         *  Returns a read-only (constant) iterator that points one past
         *  the last element in the %list.  Iteration is done in ordinary
         *  element order.
         */
        const_iterator
            end() const
            { return &this->_M_impl._M_node; }

        /**
         *  Returns a read/write reverse iterator that points to the last
         *  element in the %list.  Iteration is done in reverse element
         *  order.
         */
        reverse_iterator
            rbegin()
            { return reverse_iterator(end()); }

        /**
         *  Returns a read-only (constant) reverse iterator that points to
         *  the last element in the %list.  Iteration is done in reverse
         *  element order.
         */
        const_reverse_iterator
            rbegin() const
            { return const_reverse_iterator(end()); }

        /**
         *  Returns a read/write reverse iterator that points to one
         *  before the first element in the %list.  Iteration is done in
         *  reverse element order.
         */
        reverse_iterator
            rend()
            { return reverse_iterator(begin()); }

        /**
         *  Returns a read-only (constant) reverse iterator that points to one
         *  before the first element in the %list.  Iteration is done in reverse
         *  element order.
         */
        const_reverse_iterator
            rend() const
            { return const_reverse_iterator(begin()); }

        // [23.2.2.2] capacity
        /**
         *  Returns true if the %list is empty.  (Thus begin() would equal
         *  end().)
         */
        bool
            empty() const
            { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }

        /**  Returns the number of elements in the %list.  */
        size_type
            size() const
            { return std::distance(begin(), end()); }

        /**  Returns the size() of the largest possible %list.  */
        size_type
            max_size() const
            { return size_type(-1); }

        /**
         *  @brief Resizes the %list to the specified number of elements.
         *  @param new_size Number of elements the %list should contain.
         *  @param x Data with which new elements should be populated.
         *
         *  This function will %resize the %list to the specified number
         *  of elements.  If the number is smaller than the %list's
         *  current size the %list is truncated, otherwise the %list is
         *  extended and new elements are populated with given data.
         */
        void
            resize(size_type __new_size, const value_type& __x);

        /**
         *  @brief  Resizes the %list to the specified number of elements.
         *  @param  new_size  Number of elements the %list should contain.
         *
         *  This function will resize the %list to the specified number of
         *  elements.  If the number is smaller than the %list's current
         *  size the %list is truncated, otherwise the %list is extended
         *  and new elements are default-constructed.
         */
        void
            resize(size_type __new_size)
            { this->resize(__new_size, value_type()); }

        // element access
        /**
         *  Returns a read/write reference to the data at the first
         *  element of the %list.
         */
        reference
            front()
            { return *begin(); }

        /**
         *  Returns a read-only (constant) reference to the data at the first
         *  element of the %list.
         */
        const_reference
            front() const
            { return *begin(); }

        /**
         *  Returns a read/write reference to the data at the last element
         *  of the %list.
         */
        reference
            back()
            { return *(--end()); }

        /**
         *  Returns a read-only (constant) reference to the data at the last
         *  element of the %list.
         */
        const_reference
            back() const
            { return *(--end()); }

        // [23.2.2.3] modifiers
        /**
         *  @brief  Add data to the front of the %list.
         *  @param  x  Data to be added.
         *
         *  This is a typical stack operation.  The function creates an
         *  element at the front of the %list and assigns the given data
         *  to it.  Due to the nature of a %list this operation can be
         *  done in constant time, and does not invalidate iterators and
         *  references.
         */
        void
            push_front(const value_type& __x)
            { this->_M_insert(begin(), __x); }

        /**
         *  @brief  Removes first element.
         *
         *  This is a typical stack operation.  It shrinks the %list by
         *  one.  Due to the nature of a %list this operation can be done
         *  in constant time, and only invalidates iterators/references to
         *  the element being removed.
         *
         *  Note that no data is returned, and if the first element's data
         *  is needed, it should be retrieved before pop_front() is
         *  called.
         */
        void
            pop_front()
            { this->_M_erase(begin()); }

        /**
         *  @brief  Add data to the end of the %list.
         *  @param  x  Data to be added.
         *
         *  This is a typical stack operation.  The function creates an
         *  element at the end of the %list and assigns the given data to
         *  it.  Due to the nature of a %list this operation can be done
         *  in constant time, and does not invalidate iterators and
         *  references.
         */
        void
            push_back(const value_type& __x)
            { this->_M_insert(end(), __x); }

        /**
         *  @brief  Removes last element.
         *
         *  This is a typical stack operation.  It shrinks the %list by
         *  one.  Due to the nature of a %list this operation can be done
         *  in constant time, and only invalidates iterators/references to
         *  the element being removed.
         *
         *  Note that no data is returned, and if the last element's data
         *  is needed, it should be retrieved before pop_back() is called.
         */
        void
            pop_back()
            { this->_M_erase(this->_M_impl._M_node._M_prev); }

        /**
         *  @brief  Inserts given value into %list before specified iterator.
         *  @param  position  An iterator into the %list.
         *  @param  x  Data to be inserted.
         *  @return  An iterator that points to the inserted data.
         *
         *  This function will insert a copy of the given value before
         *  the specified location.  Due to the nature of a %list this
         *  operation can be done in constant time, and does not
         *  invalidate iterators and references.
         */
        iterator
            insert(iterator __position, const value_type& __x);

        /**
         *  @brief  Inserts a number of copies of given data into the %list.
         *  @param  position  An iterator into the %list.
         *  @param  n  Number of elements to be inserted.
         *  @param  x  Data to be inserted.
         *
         *  This function will insert a specified number of copies of the
         *  given data before the location specified by @a position.
         *
         *  Due to the nature of a %list this operation can be done in
         *  constant time, and does not invalidate iterators and
         *  references.
         */
        void
            insert(iterator __position, size_type __n, const value_type& __x)
            { _M_fill_insert(__position, __n, __x); }

        /**
         *  @brief  Inserts a range into the %list.
         *  @param  position  An iterator into the %list.
         *  @param  first  An input iterator.
         *  @param  last   An input iterator.
         *