stl_bvector.h

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

            }

        const_iterator&
            operator--()
            {
                _M_bump_down();
                return *this;
            }

        const_iterator
            operator--(int)
            {
                const_iterator __tmp = *this;
                _M_bump_down();
                return __tmp;
            }

        const_iterator&
            operator+=(difference_type __i)
            {
                _M_incr(__i);
                return *this;
            }

        const_iterator&
            operator-=(difference_type __i)
            {
                *this += -__i;
                return *this;
            }

        const_iterator 
            operator+(difference_type __i) const {
                const_iterator __tmp = *this;
                return __tmp += __i;
            }

        const_iterator
            operator-(difference_type __i) const
            {
                const_iterator __tmp = *this;
                return __tmp -= __i;
            }

        const_reference
            operator[](difference_type __i)
            { return *(*this + __i); }
    };

    inline _Bit_const_iterator
        operator+(ptrdiff_t __n, const _Bit_const_iterator& __x)
        { return __x + __n; }

    template<class _Alloc>
        class _Bvector_base
        {
            typedef typename _Alloc::template rebind<_Bit_type>::other
                _Bit_alloc_type;

            struct _Bvector_impl : public _Bit_alloc_type
            {
                _Bit_iterator 	_M_start;
                _Bit_iterator 	_M_finish;
                _Bit_type* 	_M_end_of_storage;
                _Bvector_impl(const _Bit_alloc_type& __a)
                    : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
                { }
            };

            public:
            typedef _Alloc allocator_type;

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

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

            ~_Bvector_base() { this->_M_deallocate(); }

            protected:
            _Bvector_impl _M_impl;

            _Bit_type*
                _M_allocate(size_t __n)
                { return _M_impl.allocate((__n + _S_word_bit - 1) / _S_word_bit); }

            void
                _M_deallocate()
                {
                    if (_M_impl._M_start._M_p)
                        _M_impl.deallocate(_M_impl._M_start._M_p,
                                _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
                }
        };
} // namespace std

// Declare a partial specialization of vector<T, Alloc>.
#include <bits/stl_vector.h>

namespace _GLIBCXX_STD
{
    /**
     *  @brief  A specialization of vector for booleans which offers fixed time
     *  access to individual elements in any order.
     *
     *  Note that vector<bool> does not actually meet the requirements for being
     *  a container.  This is because the reference and pointer types are not
     *  really references and pointers to bool.  See DR96 for details.  @see
     *  vector for function documentation.
     *
     *  @ingroup Containers
     *  @ingroup Sequences
     *
     *  In some terminology a %vector can be described as a dynamic
     *  C-style array, it offers fast and efficient access to individual
     *  elements in any order and saves the user from worrying about
     *  memory and size allocation.  Subscripting ( @c [] ) access is
     *  also provided as with C-style arrays.
     */
    template<typename _Alloc>
        class vector<bool, _Alloc> : public _Bvector_base<_Alloc>
        {
            public:
                typedef bool value_type;
                typedef size_t size_type;
                typedef ptrdiff_t difference_type;
                typedef _Bit_reference reference;
                typedef bool const_reference;
                typedef _Bit_reference* pointer;
                typedef const bool* const_pointer;

                typedef _Bit_iterator                iterator;
                typedef _Bit_const_iterator          const_iterator;

                typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
                typedef std::reverse_iterator<iterator> reverse_iterator;

                typedef typename _Bvector_base<_Alloc>::allocator_type allocator_type;

                allocator_type get_allocator() const
                { return _Bvector_base<_Alloc>::get_allocator(); }

            protected:
                using _Bvector_base<_Alloc>::_M_allocate;
                using _Bvector_base<_Alloc>::_M_deallocate;

            protected:
                void _M_initialize(size_type __n)
                {
                    _Bit_type* __q = this->_M_allocate(__n);
                    this->_M_impl._M_end_of_storage = __q 
                        + (__n + _S_word_bit - 1) / _S_word_bit;
                    this->_M_impl._M_start = iterator(__q, 0);
                    this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
                }

                void _M_insert_aux(iterator __position, bool __x)
                {
                    if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
                    {
                        std::copy_backward(__position, this->_M_impl._M_finish, 
                                this->_M_impl._M_finish + 1);
                        *__position = __x;
                        ++this->_M_impl._M_finish;
                    }
                    else
                    {
                        const size_type __len = size() ? 2 * size()
                            : static_cast<size_type>(_S_word_bit);
                        _Bit_type * __q = this->_M_allocate(__len);
                        iterator __i = std::copy(begin(), __position, iterator(__q, 0));
                        *__i++ = __x;
                        this->_M_impl._M_finish = std::copy(__position, end(), __i);
                        this->_M_deallocate();
                        this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1)
                            / _S_word_bit;
                        this->_M_impl._M_start = iterator(__q, 0);
                    }
                }

                template<class _InputIterator>
                    void _M_initialize_range(_InputIterator __first, _InputIterator __last,
                            input_iterator_tag)
                    {
                        this->_M_impl._M_start = iterator();
                        this->_M_impl._M_finish = iterator();
                        this->_M_impl._M_end_of_storage = 0;
                        for ( ; __first != __last; ++__first)
                            push_back(*__first);
                    }

                template<class _ForwardIterator>
                    void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
                            forward_iterator_tag)
                    {
                        const size_type __n = std::distance(__first, __last);
                        _M_initialize(__n);
                        std::copy(__first, __last, this->_M_impl._M_start);
                    }

                template<class _InputIterator>
                    void _M_insert_range(iterator __pos, _InputIterator __first, 
                            _InputIterator __last, input_iterator_tag)
                    {
                        for ( ; __first != __last; ++__first)
                        {
                            __pos = insert(__pos, *__first);
                            ++__pos;
                        }
                    }

                template<class _ForwardIterator>
                    void _M_insert_range(iterator __position, _ForwardIterator __first, 
                            _ForwardIterator __last, forward_iterator_tag)
                    {
                        if (__first != __last)
                        {
                            size_type __n = std::distance(__first, __last);
                            if (capacity() - size() >= __n)
                            {
                                std::copy_backward(__position, end(),
                                        this->_M_impl._M_finish + difference_type(__n));
                                std::copy(__first, __last, __position);
                                this->_M_impl._M_finish += difference_type(__n);
                            }
                            else
                            {
                                const size_type __len = size() + std::max(size(), __n);
                                _Bit_type * __q = this->_M_allocate(__len);
                                iterator __i = std::copy(begin(), __position, iterator(__q, 0));
                                __i = std::copy(__first, __last, __i);
                                this->_M_impl._M_finish = std::copy(__position, end(), __i);
                                this->_M_deallocate();
                                this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1)
                                    / _S_word_bit;
                                this->_M_impl._M_start = iterator(__q, 0);
                            }
                        }
                    }

            public:
                iterator begin()
                { return this->_M_impl._M_start; }

                const_iterator begin() const
                { return this->_M_impl._M_start; }

                iterator end()
                { return this->_M_impl._M_finish; }

                const_iterator end() const
                { return this->_M_impl._M_finish; }

                reverse_iterator rbegin()
                { return reverse_iterator(end()); }

                const_reverse_iterator rbegin() const
                { return const_reverse_iterator(end()); }

                reverse_iterator rend()
                { return reverse_iterator(begin()); }

                const_reverse_iterator rend() const
                { return const_reverse_iterator(begin()); }

                size_type size() const
                { return size_type(end() - begin()); }

                size_type max_size() const
                { return size_type(-1); }

                size_type capacity() const
                { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
                        - begin()); }
                bool empty() const
                { return begin() == end(); }

                reference operator[](size_type __n)
                { return *(begin() + difference_type(__n)); }

                const_reference operator[](size_type __n) const
                { return *(begin() + difference_type(__n)); }

                void _M_range_check(size_type __n) const
                {
                    if (__n >= this->size())
                        __throw_out_of_range(__N("vector<bool>::_M_range_check"));
                }

                reference at(size_type __n)
                { _M_range_check(__n); return (*this)[__n]; }