精华内容
下载资源
问答
  • Linux C++ vector

    2018-12-26 22:59:56
    vector> using namespace std; int main() {  vector<int>::iterator it;  vector<int > v;  int i;  for(i=0;i<10;i++)//添加10个元素 1,2,3.... ...

    #include<iostream>
    #include<vector>
    using namespace std;
    int main()
    {
        vector<int>::iterator it;
        vector<int >  v;
        int i;
        for(i=0;i<10;i++)//添加10个元素 1,2,3.... 
        {
            v.push_back(i);
        }
        
        for(it=v.begin();it!=v.end();it++)//遍历一下整个数组 
        cout<<*it<<" ";
        cout<<endl;
        
        v.erase(v.begin()+1);//删除的是第一个元素(下标从0开始)
                            // 也就是1 ,所以现在是0,2,4...9 
        v.insert(v.begin()+1,1);//把删除的再加进去 
        v.erase(v.begin()+1,v.begin()+4);//删除的第1,2,3 的元素共三个元素
        //也就是剩下的是 0,4,5,6,7,8,9
        for(it=v.begin();it!=v.end();it++)//遍历一下整个数组 
        cout<<*it<<" ";
        cout<<endl;     
        
        cout<<v.size()<<endl;//看一下数组的大小
        
        v.clear();
        
        cout<<v.size()<<endl;
        return 0;
                 
        
        
                            
        
    }

    展开全文
  • STL之Vector(Linux内核)完整实现

    千次阅读 2017-04-14 22:15:01
    自上次写了map之后对Vector比较感兴趣,由于对Vector理解不是很深刻,利用业余时间从Linux系统中拷贝出完整的Vector代码进行学习参考,并对一部分做了修改可以在Windows系统运行。 下面简单介绍下Vector的实现方式...

    自上次写了map之后对Vector比较感兴趣,由于对Vector理解不是很深刻,利用业余时间从Linux系统中拷贝出完整的Vector代码进行学习参考,并对一部分做了修改可以在Windows系统运行。
    下面简单介绍下Vector的实现方式:
    1.Vector的内存分配方式采用了标准STL的一贯做法——每增加一个节点动态分配一个节点需要的内存;。
    2.Vector分配的内存是连续的,比如保存的节点1可以通过增加地址到节点2及更高,也可以表达为动态数组;
    3.Vector迭代器通过iterator_traits(迭代器性质类)表达了迭代器可能需要用到的几种形式(指针、引用等);
    4.当用到迭代器修改Vector数据时,传入Vector对象通过内部_Base结构进行修改数据;
    5.Vector删除节点的时候是从前到后一个节点的删除,一直删除完全为止。

    下面贴上完整代码(带部分注释):

    /*
    **李坤昱
    **326087275@qq.com
    **Vector完整版
    */
    ///  Marking input iterators.
    struct input_iterator_tag { }; //输入迭代器可用于顺序输入操作,其中的每个值指出的迭代器只读一次然后迭代器递增。
    ///  Marking output iterators.
    struct output_iterator_tag { };//输出迭代器可用于连续输出操作,其中每个元素指向的迭代器是写一个价值只有一次,则迭代器递增
    /// Forward iterators support a superset of input iterator operations.
    struct forward_iterator_tag : public input_iterator_tag { };
    /// Bidirectional iterators support a superset of forward iterator
    /// operations.
    struct bidirectional_iterator_tag : public forward_iterator_tag { };
    /// Random-access iterators support a superset of bidirectional iterator
    /// operations.
    struct random_access_iterator_tag : public bidirectional_iterator_tag { };
    
    
    
    
    
      template<typename _Tp>
        class allocator;
    
      /// allocator<void> specialization.
      template<>
        class allocator<void>
        {
        public:
          typedef size_t      size_type;
          typedef ptrdiff_t   difference_type;
          typedef void*       pointer;
          typedef const void* const_pointer;
          typedef void        value_type;
    
          template<typename _Tp1>
            struct rebind
            { typedef allocator<_Tp1> other; };
        };
    
    
    
    
        template<typename _Tp>
        class new_allocator//添加的数据类型分配原型 ,比如vector<int> 每次分配一个int内存 (4字节),
            //每个节点都是连续的比如push第一次为地址4,push第二次地址为8,可以通过第一个节点++到达第二个节点,相等于动态数组
        {
        public:
            typedef size_t     size_type;
            typedef ptrdiff_t  difference_type;
            typedef _Tp*       pointer;
            typedef const _Tp* const_pointer;
            typedef _Tp&       reference;
            typedef const _Tp& const_reference;
            typedef _Tp        value_type;
    
            template<typename _Tp1>
            struct rebind
            { typedef new_allocator<_Tp1> other; };
    
            new_allocator() throw() { }
    
            new_allocator(const new_allocator&) throw() { }
    
            template<typename _Tp1>
            new_allocator(const new_allocator<_Tp1>&) throw() { }
    
            ~new_allocator() throw() { }
    
            pointer
                address(reference __x) const { return &__x; }
    
            const_pointer
                address(const_reference __x) const { return &__x; }
    
            // NB: __n is permitted to be 0.  The C++ standard says nothing
            // about what the return value is when __n == 0.
            pointer
                allocate(size_type __n, const void* = 0)
            { 
                /*if (__builtin_expect(__n > this->max_size(), false))
                __throw_bad_alloc();*/
    
                return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
            }
    
            // __p is not permitted to be a null pointer.
            void
                deallocate(pointer __p, size_type)
            { ::operator delete(__p); }
    
            size_type
                max_size() const throw() 
            { return size_t(-1) / sizeof(_Tp); }
    
            // _GLIBCXX_RESOLVE_LIB_DEFECTS
            // 402. wrong new expression in [some_] allocator::construct
            void 
                construct(pointer __p, const _Tp& __val) 
            { ::new((void *)__p) _Tp(__val); }
    
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
            template<typename... _Args>
            void
                construct(pointer __p, _Args&&... __args)
            { ::new((void *)__p) _Tp(forward<_Args>(__args)...); }
    #endif
    
            void 
                destroy(pointer __p) { __p->~_Tp(); }//释放单个节点
        };
    
        template<typename _Tp>
        inline bool
            operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
        { return true; }
    
        template<typename _Tp>
        inline bool
            operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
        { return false; }
    
    
      template<typename _Tp>
        class allocator: public new_allocator<_Tp>
        {
       public:
          typedef size_t     size_type;
          typedef ptrdiff_t  difference_type;
          typedef _Tp*       pointer;
          typedef const _Tp* const_pointer;
          typedef _Tp&       reference;
          typedef const _Tp& const_reference;
          typedef _Tp        value_type;
    
          template<typename _Tp1>
            struct rebind
            { typedef allocator<_Tp1> other; };
    
          allocator() throw() { }
    
          allocator(const allocator& __a) throw()
          : __glibcxx_base_allocator<_Tp>(__a) { }
    
          template<typename _Tp1>
            allocator(const allocator<_Tp1>&) throw() { }
    
          ~allocator() throw() { }
    
          // Inherit everything else.
        };
    
        template<typename _ForwardIterator, typename _Allocator>
        void
            _Destroy(_ForwardIterator __first, _ForwardIterator __last,
            _Allocator& __alloc)
        {
            for (; __first != __last; ++__first)
                __alloc.destroy(&*__first);
        }
    
    
        template<typename _Tp>
        inline void
            _Destroy(_Tp* __pointer)
        { __pointer->~_Tp(); }
    
    
    
        template<bool>
        struct _Destroy_aux
        {
            template<typename _ForwardIterator>
            static void
                __destroy(_ForwardIterator __first, _ForwardIterator __last)
            {
                for (; __first != __last; ++__first)
                    _Destroy(&*__first);
            }
        };
    
        template<>
        struct _Destroy_aux<true>
        {
            template<typename _ForwardIterator>
            static void
                __destroy(_ForwardIterator, _ForwardIterator) { }
        };
    
    
    
        template<typename _ForwardIterator>
        inline void
            _Destroy(_ForwardIterator __first, _ForwardIterator __last)
        {
            typedef typename iterator_traits<_ForwardIterator>::value_type
                _Value_type;
            _Destroy_aux<__has_trivial_destructor(_Value_type)>::
                __destroy(__first, __last);
        }
    
    
      template<typename _T1, typename _T2>
        inline bool
        operator==(const allocator<_T1>&, const allocator<_T2>&)
        { return true; }
    
      template<typename _Tp>
        inline bool
        operator==(const allocator<_Tp>&, const allocator<_Tp>&)
        { return true; }
    
      template<typename _T1, typename _T2>
        inline bool
        operator!=(const allocator<_T1>&, const allocator<_T2>&)
        { return false; }
    
      template<typename _Tp>
        inline bool
        operator!=(const allocator<_Tp>&, const allocator<_Tp>&)
        { return false; }
    
      // Inhibit implicit instantiations for required instantiations,
      // which are defined via explicit instantiations elsewhere.
      // NB: This syntax is a GNU extension.
    #if _GLIBCXX_EXTERN_TEMPLATE
      extern template class allocator<char>;
      extern template class allocator<wchar_t>;
    #endif
    
      // Undefine.
    #undef __glibcxx_base_allocator
    
      // To implement Option 3 of DR 431.
      template<typename _Alloc, bool = __is_empty(_Alloc)>
        struct __alloc_swap
        { static void _S_do_it(_Alloc&, _Alloc&) { } };
    
      template<typename _Alloc>
        struct __alloc_swap<_Alloc, false>
        {
          static void
          _S_do_it(_Alloc& __one, _Alloc& __two)
          {
        // Precondition: swappable allocators.
        if (__one != __two)
          swap(__one, __two);
          }
        };
    
      // Optimize for stateless allocators.
      template<typename _Alloc, bool = __is_empty(_Alloc)>
        struct __alloc_neq
        {
          static bool
          _S_do_it(const _Alloc&, const _Alloc&)
          { return false; }
        };
    
      template<typename _Alloc>
        struct __alloc_neq<_Alloc, false>
        {
          static bool
          _S_do_it(const _Alloc& __one, const _Alloc& __two)
          { return __one != __two; }
        };
    
    
    
    
    
    
    
     template<typename _Iterator>
        struct iterator_traits//迭代性质类,Vectord迭代器用到的各种数据情况 比如引用、指针类型等
        {
          typedef typename _Iterator::iterator_category iterator_category;
          typedef typename _Iterator::value_type        value_type;
          typedef typename _Iterator::difference_type   difference_type;
          typedef typename _Iterator::pointer           pointer;
          typedef typename _Iterator::reference         reference;
        };
    
      template<typename _Tp>
        struct iterator_traits<_Tp*>
        {
          typedef random_access_iterator_tag iterator_category;
          typedef _Tp                         value_type;
          typedef ptrdiff_t                   difference_type;
          typedef _Tp*                        pointer;
          typedef _Tp&                        reference;
        };
    
      template<typename _Tp>
        struct iterator_traits<const _Tp*>
        {
          typedef random_access_iterator_tag iterator_category;
          typedef _Tp                         value_type;
          typedef ptrdiff_t                   difference_type;
          typedef const _Tp*                  pointer;
          typedef const _Tp&                  reference;
        };
    
      /**
       *  This function is not a part of the C++ standard but is syntactic
       *  sugar for internal library use only.
      */
      template<typename _Iter>
        inline typename iterator_traits<_Iter>::iterator_category
        __iterator_category(const _Iter&)
        { return typename iterator_traits<_Iter>::iterator_category(); }
    
    
    
        template<bool, typename>
        struct __enable_if 
        { };
    
    
        struct __true_type { };
        struct __false_type { };
    
        template<typename _Tp>
        struct __enable_if<true, _Tp>
        { typedef _Tp __type; };
    
    
        // Compare for equality of types.
        template<typename, typename>
        struct __are_same
        {
            enum { Test__value = 0 };
            typedef __false_type __type;
        };
    
        template<typename _Tp>
        struct __are_same<_Tp, _Tp>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
    
    template<typename _Iterator, typename _Container>
    class __normal_iterator//迭代器数据储存类
    {
    protected:
        _Iterator _M_current;//迭代对象 迭代到当前的节点
    
    public:
        typedef _Iterator                        iterator_type;
        typedef typename iterator_traits<_Iterator>::iterator_category
            iterator_category;
        typedef typename iterator_traits<_Iterator>::value_type  value_type;
        typedef typename iterator_traits<_Iterator>::difference_type
            difference_type;
        typedef typename iterator_traits<_Iterator>::reference reference;
        typedef typename iterator_traits<_Iterator>::pointer   pointer;
    
        __normal_iterator() : _M_current(_Iterator()) { }
    
        explicit
            __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
    
        // Allow iterator to const_iterator conversion
        template<typename _Iter>
        __normal_iterator(const __normal_iterator<_Iter,
            typename __enable_if<
            (__are_same<_Iter, typename _Container::pointer>::Test__value),
            _Container>::__type>& __i)
            : _M_current(__i.base()) { }
    
        // Forward iterator requirements
        reference
            operator*() const
        { return *_M_current; }
    
        pointer
            operator->() const
        { return _M_current; }
    
        __normal_iterator&
            operator++()
        {
            ++_M_current;
            return *this;
        }
    
        __normal_iterator
            operator++(int)
        { return __normal_iterator(_M_current++); }
    
        // Bidirectional iterator requirements
        __normal_iterator&
            operator--()
        {
            --_M_current;
            return *this;
        }
    
        __normal_iterator
            operator--(int)
        { return __normal_iterator(_M_current--); }
    
        // Random access iterator requirements
        reference
            operator[](const difference_type& __n) const
        { return _M_current[__n]; }
    
        __normal_iterator&
            operator+=(const difference_type& __n)
        { _M_current += __n; return *this; }
    
        __normal_iterator
            operator+(const difference_type& __n) const
        { return __normal_iterator(_M_current + __n); }
    
        __normal_iterator&
            operator-=(const difference_type& __n)
        { _M_current -= __n; return *this; }
    
        __normal_iterator
            operator-(const difference_type& __n) const
        { return __normal_iterator(_M_current - __n); }
    
        const _Iterator&
            base() const
        { return _M_current; }
    };
    
    // Note: In what follows, the left- and right-hand-side iterators are
    // allowed to vary in types (conceptually in cv-qualification) so that
    // comparison between cv-qualified and non-cv-qualified iterators be
    // valid.  However, the greedy and unfriendly operators in rel_ops
    // will make overload resolution ambiguous (when in scope) if we don't
    // provide overloads whose operands are of the same type.  Can someone
    // remind me what generic programming is about? -- Gaby
    
    // Forward iterator requirements
    template<typename _IteratorL, typename _IteratorR, typename _Container>
    inline bool
        operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
        const __normal_iterator<_IteratorR, _Container>& __rhs)
    { return __lhs.base() == __rhs.base(); }
    
    template<typename _Iterator, typename _Container>
    inline bool
        operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
        const __normal_iterator<_Iterator, _Container>& __rhs)
    { return __lhs.base() == __rhs.base(); }
    
    template<typename _IteratorL, typename _IteratorR, typename _Container>
    inline bool
        operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
        const __normal_iterator<_IteratorR, _Container>& __rhs)
    { return __lhs.base() != __rhs.base(); }
    
    template<typename _Iterator, typename _Container>
    inline bool
        operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
        const __normal_iterator<_Iterator, _Container>& __rhs)
    { return __lhs.base() != __rhs.base(); }
    
    // Random access iterator requirements
    template<typename _IteratorL, typename _IteratorR, typename _Container>
    inline bool
        operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
        const __normal_iterator<_IteratorR, _Container>& __rhs)
    { return __lhs.base() < __rhs.base(); }
    
    template<typename _Iterator, typename _Container>
    inline bool
        operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
        const __normal_iterator<_Iterator, _Container>& __rhs)
    { return __lhs.base() < __rhs.base(); }
    
    template<typename _IteratorL, typename _IteratorR, typename _Container>
    inline bool
        operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
        const __normal_iterator<_IteratorR, _Container>& __rhs)
    { return __lhs.base() > __rhs.base(); }
    
    template<typename _Iterator, typename _Container>
    inline bool
        operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
        const __normal_iterator<_Iterator, _Container>& __rhs)
    { return __lhs.base() > __rhs.base(); }
    
    template<typename _IteratorL, typename _IteratorR, typename _Container>
    inline bool
        operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
        const __normal_iterator<_IteratorR, _Container>& __rhs)
    { return __lhs.base() <= __rhs.base(); }
    
    template<typename _Iterator, typename _Container>
    inline bool
        operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
        const __normal_iterator<_Iterator, _Container>& __rhs)
    { return __lhs.base() <= __rhs.base(); }
    
    template<typename _IteratorL, typename _IteratorR, typename _Container>
    inline bool
        operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
        const __normal_iterator<_IteratorR, _Container>& __rhs)
    { return __lhs.base() >= __rhs.base(); }
    
    template<typename _Iterator, typename _Container>
    inline bool
        operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
        const __normal_iterator<_Iterator, _Container>& __rhs)
    { return __lhs.base() >= __rhs.base(); }
    
    // _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 _IteratorL, typename _IteratorR, typename _Container>
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
    // DR 685.
    inline auto
        operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
        const __normal_iterator<_IteratorR, _Container>& __rhs)
        -> decltype(__lhs.base() - __rhs.base())
    #else
    inline typename __normal_iterator<_IteratorL, _Container>::difference_type
        operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
        const __normal_iterator<_IteratorR, _Container>& __rhs)
    #endif
    { return __lhs.base() - __rhs.base(); }
    
    template<typename _Iterator, typename _Container>
    inline typename __normal_iterator<_Iterator, _Container>::difference_type
        operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
        const __normal_iterator<_Iterator, _Container>& __rhs)
    { return __lhs.base() - __rhs.base(); }
    
    template<typename _Iterator, typename _Container>
    inline __normal_iterator<_Iterator, _Container>
        operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
        __n, const __normal_iterator<_Iterator, _Container>& __i)
    { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
    
    
    
    
    
    
    
    
    template<typename _Tp, typename _Alloc>
    struct _Vector_base//Vector结构原型
    {
        typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
    
        struct _Vector_impl //装载结构,数据的增删改调用此结构实现
            : public _Tp_alloc_type
        {
            typename _Tp_alloc_type::pointer _M_start;
            typename _Tp_alloc_type::pointer _M_finish;
            typename _Tp_alloc_type::pointer _M_end_of_storage;
    
            _Vector_impl()
                : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0)
            { }
    
            _Vector_impl(_Tp_alloc_type const& __a)
                : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
            { }
        };
    
    public:
        typedef _Alloc allocator_type;
    
        _Tp_alloc_type&
            _M_get_Tp_allocator()
        { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
    
        const _Tp_alloc_type&
            _M_get_Tp_allocator() const
        { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
    
        allocator_type
            get_allocator() const
        { return allocator_type(_M_get_Tp_allocator()); }
    
        _Vector_base()
            : _M_impl() { }
    
        _Vector_base(const allocator_type& __a)
            : _M_impl(__a) { }
    
        _Vector_base(size_t __n, const allocator_type& __a)
            : _M_impl(__a)
        {
            this->_M_impl._M_start = this->_M_allocate(__n);
            this->_M_impl._M_finish = this->_M_impl._M_start;
            this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
        }
    
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
        _Vector_base(_Vector_base&& __x)
            : _M_impl(__x._M_get_Tp_allocator())
        {
            this->_M_impl._M_start = __x._M_impl._M_start;
            this->_M_impl._M_finish = __x._M_impl._M_finish;
            this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
            __x._M_impl._M_start = 0;
            __x._M_impl._M_finish = 0;
            __x._M_impl._M_end_of_storage = 0;
        }
    #endif
    
        ~_Vector_base()
        { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
        - this->_M_impl._M_start); }
    
    public:
        _Vector_impl _M_impl;
    
        typename _Tp_alloc_type::pointer
            _M_allocate(size_t __n)
        { return __n != 0 ? _M_impl.allocate(__n) : 0; }
    
        void
            _M_deallocate(typename _Tp_alloc_type::pointer __p, size_t __n)
        {
            if (__p)
                _M_impl.deallocate(__p, __n);
        }
    };
    
    
    template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
        typename _Pointer = _Tp*, typename _Reference = _Tp&>
    struct iterator//迭代器内部几种表现形式
    {
        /// One of the @link iterator_tags tag types@endlink.
        typedef _Category  iterator_category;
        /// The type "pointed to" by the iterator.
        typedef _Tp        value_type;
        /// Distance between iterators is represented as this type.
        typedef _Distance  difference_type;
        /// This type represents a pointer-to-value_type.
        typedef _Pointer   pointer;
        /// This type represents a reference-to-value_type.
        typedef _Reference reference;
    };
    
    
    template<typename _Iterator>
        class reverse_iterator
        : public iterator<typename iterator_traits<_Iterator>::iterator_category,
                  typename iterator_traits<_Iterator>::value_type,
                  typename iterator_traits<_Iterator>::difference_type,
                  typename iterator_traits<_Iterator>::pointer,
                  typename iterator_traits<_Iterator>::reference>
    
        {
        protected:
          _Iterator current;//迭代器当前节点参数
    
        public:
          typedef _Iterator                        iterator_type;
          typedef typename iterator_traits<_Iterator>::difference_type
                                       difference_type;
          typedef typename iterator_traits<_Iterator>::reference   reference;
          typedef typename iterator_traits<_Iterator>::pointer     pointer;
          typedef typename iterator_traits<_Iterator>::const_reference   const_reference;//临时增加```,之前调试Vector遇到Const返回类型错误, 调试发现与它没有关系
          typedef typename iterator_traits<_Iterator>::const_pointer     const_pointer;
        public:
          /**
           *  The default constructor default-initializes member @p current.
           *  If it is a pointer, that means it is zero-initialized.
          */
          // _GLIBCXX_RESOLVE_LIB_DEFECTS
          // 235 No specification of default ctor for reverse_iterator
          reverse_iterator() : current() { }
    
          /**
           *  This %iterator will move in the opposite direction that @p x does.
          */
          explicit
          reverse_iterator(iterator_type __x) : current(__x) { }
    
          /**
           *  The copy constructor is normal.
          */
          reverse_iterator(const reverse_iterator& __x)
          : current(__x.current) { }
    
          /**
           *  A reverse_iterator across other types can be copied in the normal
           *  fashion.
          */
          template<typename _Iter>
            reverse_iterator(const reverse_iterator<_Iter>& __x)
        : current(__x.base()) { }
    
          /**
           *  @return  @c current, the %iterator used for underlying work.
          */
          iterator_type
          base() const
          { return current; }
    
          /**
           *  @return  TODO
           *
           *  @doctodo
          */
          reference
          operator*() const
          {
        _Iterator __tmp = current;
        return *--__tmp;
          }
    
          /**
           *  @return  TODO
           *
           *  @doctodo
          */
          pointer
          operator->() const
          { return &(operator*()); }
    
          /**
           *  @return  TODO
           *
           *  @doctodo
          */
          reverse_iterator&
          operator++()
          {
        --current;
        return *this;
          }
    
          /**
           *  @return  TODO
           *
           *  @doctodo
          */
          reverse_iterator
          operator++(int)
          {
        reverse_iterator __tmp = *this;
        --current;
        return __tmp;
          }
    
          /**
           *  @return  TODO
           *
           *  @doctodo
          */
          reverse_iterator&
          operator--()
          {
        ++current;
        return *this;
          }
    
          /**
           *  @return  TODO
           *
           *  @doctodo
          */
          reverse_iterator
          operator--(int)
          {
        reverse_iterator __tmp = *this;
        ++current;
        return __tmp;
          }
    
          /**
           *  @return  TODO
           *
           *  @doctodo
          */
          reverse_iterator
          operator+(difference_type __n) const
          { return reverse_iterator(current - __n); }
    
          /**
           *  @return  TODO
           *
           *  @doctodo
          */
          reverse_iterator&
          operator+=(difference_type __n)
          {
        current -= __n;
        return *this;
          }
    
          /**
           *  @return  TODO
           *
           *  @doctodo
          */
          reverse_iterator
          operator-(difference_type __n) const
          { return reverse_iterator(current + __n); }
    
          /**
           *  @return  TODO
           *
           *  @doctodo
          */
          reverse_iterator&
          operator-=(difference_type __n)
          {
        current += __n;
        return *this;
          }
    
          /**
           *  @return  TODO
           *
           *  @doctodo
          */
          reference
          operator[](difference_type __n) const
          { return *(*this + __n); }
        };
    
      //@{
      /**
       *  @param  x  A %reverse_iterator.
       *  @param  y  A %reverse_iterator.
       *  @return  A simple bool.
       *
       *  Reverse iterators forward many operations to their underlying base()
       *  iterators.  Others are implemented in terms of one another.
       *
      */
      template<typename _Iterator>
        inline bool
        operator==(const reverse_iterator<_Iterator>& __x,
               const reverse_iterator<_Iterator>& __y)
        { return __x.base() == __y.base(); }
    
      template<typename _Iterator>
        inline bool
        operator<(const reverse_iterator<_Iterator>& __x,
              const reverse_iterator<_Iterator>& __y)
        { return __y.base() < __x.base(); }
    
      template<typename _Iterator>
        inline bool
        operator!=(const reverse_iterator<_Iterator>& __x,
               const reverse_iterator<_Iterator>& __y)
        { return !(__x == __y); }
    
      template<typename _Iterator>
        inline bool
        operator>(const reverse_iterator<_Iterator>& __x,
              const reverse_iterator<_Iterator>& __y)
        { return __y < __x; }
    
      template<typename _Iterator>
        inline bool
        operator<=(const reverse_iterator<_Iterator>& __x,
               const reverse_iterator<_Iterator>& __y)
        { return !(__y < __x); }
    
      template<typename _Iterator>
        inline bool
        operator>=(const reverse_iterator<_Iterator>& __x,
               const reverse_iterator<_Iterator>& __y)
        { return !(__x < __y); }
    
      template<typename _Iterator>
        inline typename reverse_iterator<_Iterator>::difference_type
        operator-(const reverse_iterator<_Iterator>& __x,
              const reverse_iterator<_Iterator>& __y)
        { return __y.base() - __x.base(); }
    
      template<typename _Iterator>
        inline reverse_iterator<_Iterator>
        operator+(typename reverse_iterator<_Iterator>::difference_type __n,
              const reverse_iterator<_Iterator>& __x)
        { return reverse_iterator<_Iterator>(__x.base() - __n); }
    
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // DR 280. Comparison of reverse_iterator to const reverse_iterator.
      template<typename _IteratorL, typename _IteratorR>
        inline bool
        operator==(const reverse_iterator<_IteratorL>& __x,
               const reverse_iterator<_IteratorR>& __y)
        { return __x.base() == __y.base(); }
    
      template<typename _IteratorL, typename _IteratorR>
        inline bool
        operator<(const reverse_iterator<_IteratorL>& __x,
              const reverse_iterator<_IteratorR>& __y)
        { return __y.base() < __x.base(); }
    
      template<typename _IteratorL, typename _IteratorR>
        inline bool
        operator!=(const reverse_iterator<_IteratorL>& __x,
               const reverse_iterator<_IteratorR>& __y)
        { return !(__x == __y); }
    
      template<typename _IteratorL, typename _IteratorR>
        inline bool
        operator>(const reverse_iterator<_IteratorL>& __x,
              const reverse_iterator<_IteratorR>& __y)
        { return __y < __x; }
    
      template<typename _IteratorL, typename _IteratorR>
        inline bool
        operator<=(const reverse_iterator<_IteratorL>& __x,
               const reverse_iterator<_IteratorR>& __y)
        { return !(__y < __x); }
    
      template<typename _IteratorL, typename _IteratorR>
        inline bool
        operator>=(const reverse_iterator<_IteratorL>& __x,
               const reverse_iterator<_IteratorR>& __y)
        { return !(__x < __y); }
    
      template<typename _IteratorL, typename _IteratorR>
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
        // DR 685.
        inline auto
        operator-(const reverse_iterator<_IteratorL>& __x,
              const reverse_iterator<_IteratorR>& __y)
        -> decltype(__y.base() - __x.base())
    #else
        inline typename reverse_iterator<_IteratorL>::difference_type
        operator-(const reverse_iterator<_IteratorL>& __x,
              const reverse_iterator<_IteratorR>& __y)
    #endif
        { return __y.base() - __x.base(); }
    
    
    
    
    
    
    
    
    
        //
        // Integer types
        //
        template<typename _Tp>
        struct __is_integer
        {
            enum { Test__value = 0 };
            typedef __false_type __type;
        };
    
        // Thirteen specializations (yes there are eleven standard integer
        // types; 'long long' and 'unsigned long long' are supported as
        // extensions)
        template<>
        struct __is_integer<bool>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
        template<>
        struct __is_integer<char>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
        template<>
        struct __is_integer<signed char>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
        template<>
        struct __is_integer<unsigned char>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
    # ifdef _GLIBCXX_USE_WCHAR_T
        template<>
        struct __is_integer<wchar_t>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    # endif
    
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
        template<>
        struct __is_integer<char16_t>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
        template<>
        struct __is_integer<char32_t>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    #endif
    
        template<>
        struct __is_integer<short>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
        template<>
        struct __is_integer<unsigned short>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
        template<>
        struct __is_integer<int>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
        template<>
        struct __is_integer<unsigned int>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
        template<>
        struct __is_integer<long>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
        template<>
        struct __is_integer<unsigned long>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
        template<>
        struct __is_integer<long long>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
        template<>
        struct __is_integer<unsigned long long>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
    
    
    
        //
        // Pointer types
        //
        template<typename _Tp>
        struct __is_pointer
        {
            enum { Test__value = 0 };
            typedef __false_type __type;
        };
    
        template<typename _Tp>
        struct __is_pointer<_Tp*>
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
    
    
    
        template<typename _II1, typename _II2>
        inline bool
            __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
        {
            typedef typename iterator_traits<_II1>::value_type _ValueType1;
            typedef typename iterator_traits<_II2>::value_type _ValueType2;
            const bool __simple = (__is_integer<_ValueType1>::Test__value
                && __is_pointer<_II1>::Test__value
                && __is_pointer<_II2>::Test__value
                && __are_same<_ValueType1, _ValueType2>::Test__value);
    
            return __equal<__simple>::equal(__first1, __last1, __first2);
        }
    
    
        //
        // Normal iterator type
        //
        template<typename _Tp>
        struct __is_normal_iterator
        {
            enum { Test__value = 0 };
            typedef __false_type __type;
        };
    
        template<typename _Iterator, typename _Container>
        struct __is_normal_iterator< __normal_iterator<_Iterator,
            _Container> >
        {
            enum { Test__value = 1 };
            typedef __true_type __type;
        };
    
    
    
    
        // If _Iterator is a __normal_iterator return its base (a plain pointer,
        // normally) otherwise return it untouched.  See copy, fill, ... 
        template<typename _Iterator,
            bool _IsNormal = __is_normal_iterator<_Iterator>::Test__value>
        struct __niter_base
        {
            static _Iterator
                __b(_Iterator __it)
            { return __it; }
        };
    
        template<typename _Iterator>
        struct __niter_base<_Iterator, true>
        {
            static typename _Iterator::iterator_type
                __b(_Iterator __it)
            { return __it.base(); }
        };
    
    
    
        template<typename _II1, typename _II2>
        inline bool
            equal(_II1 __first1, _II1 __last1, _II2 __first2)
        {
            // concept requirements
            /*__glibcxx_function_requires(_InputIteratorConcept<_II1>)//没发现什么实际用处
                __glibcxx_function_requires(_InputIteratorConcept<_II2>)
                __glibcxx_function_requires(_EqualOpConcept<
                typename iterator_traits<_II1>::value_type,
                typename iterator_traits<_II2>::value_type>)
                __glibcxx_requires_valid_range(__first1, __last1);*/
    
            return __equal_aux(__niter_base<_II1>::__b(__first1),
                __niter_base<_II1>::__b(__last1),
                __niter_base<_II2>::__b(__first2));
        }
    
    
    #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) copy(_Tp, _Up, _Vp)
    
    
    template<typename _Tp, typename _Alloc = allocator<_Tp> >
        class Test_vector : protected _Vector_base<_Tp, _Alloc>//Vector调用类
        {
          // Concept requirements.
          typedef typename _Alloc::value_type                _Alloc_value_type;
    
          typedef _Vector_base<_Tp, _Alloc>          _Base;
          typedef typename _Base::_Tp_alloc_type         _Tp_alloc_type;
    
        public:
          typedef _Tp                    value_type;
          typedef typename _Tp_alloc_type::pointer           pointer;
          typedef typename _Tp_alloc_type::const_pointer     const_pointer;
          typedef typename _Tp_alloc_type::reference         reference;
          typedef typename _Tp_alloc_type::const_reference   const_reference;
          typedef __normal_iterator<pointer, Test_vector> iterator;
          typedef __normal_iterator<const_pointer, Test_vector>  const_iterator;
          typedef reverse_iterator<const_iterator>  Test__const_reverse_iterator;
          typedef reverse_iterator<iterator>         reverse_iterator;
          typedef size_t                     size_type;
          typedef ptrdiff_t                  difference_type;
          typedef _Alloc                                 allocator_type;
    
        protected:
          using _Base::_M_allocate;
          using _Base::_M_deallocate;
          using _Base::_M_impl;
          using _Base::_M_get_Tp_allocator;
    
        public:
          // [23.2.4.1] construct/copy/destroy
          // (assign() and get_allocator() are also listed in this section)
          /**
           *  @brief  Default constructor creates no elements.
           */
          Test_vector()
          : _Base() { }
    
          /**
           *  @brief  Creates a %Test_vector with no elements.
           *  @param  a  An allocator object.
           */
          explicit
          Test_vector(const allocator_type& __a)
          : _Base(__a) { }
    
          /**
           *  @brief  Creates a %Test_vector with copies of an exemplar element.
           *  @param  n  The number of elements to initially create.
           *  @param  value  An element to copy.
           *  @param  a  An allocator.
           *
           *  This constructor fills the %Test_vector with @a n copies of @a value.
           */
          explicit
          Test_vector(size_type __n, const value_type& Test__value = value_type(),
             const allocator_type& __a = allocator_type())
          : _Base(__n, __a)
          { _M_fill_initialize(__n, Test__value); }
    
          /**
           *  @brief  %Test_vector copy constructor.
           *  @param  x  A %Test_vector of identical element and allocator types.
           *
           *  The newly-created %Test_vector uses a copy of the allocation
           *  object used by @a x.  All the elements of @a x are copied,
           *  but any extra memory in
           *  @a x (for fast expansion) will not be copied.
           */
          Test_vector(const Test_vector& __x)
          : _Base(__x.size(), __x._M_get_Tp_allocator())
          { this->_M_impl._M_finish =
          __uninitialized_copy_a(__x.begin(), __x.end(),
                          this->_M_impl._M_start,
                          _M_get_Tp_allocator());
          }
    
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
          /**
           *  @brief  %Test_vector move constructor.
           *  @param  x  A %Test_vector of identical element and allocator types.
           *
           *  The newly-created %Test_vector contains the exact contents of @a x.
           *  The contents of @a x are a valid, but unspecified %Test_vector.
           */
          Test_vector(Test_vector&& __x)
          : _Base(forward<_Base>(__x)) { }
    
          /**
           *  @brief  Builds a %Test_vector from an initializer list.
           *  @param  l  An initializer_list.
           *  @param  a  An allocator.
           *
           *  Create a %Test_vector consisting of copies of the elements in the
           *  initializer_list @a l.
           *
           *  This will call the element type's copy constructor N times
           *  (where N is @a l.size()) and do no memory reallocation.
           */
          Test_vector(initializer_list<value_type> __l,
             const allocator_type& __a = allocator_type())
          : _Base(__a)
          {
        _M_range_initialize(__l.begin(), __l.end(),
                    random_access_iterator_tag());
          }
    #endif
    
          /**
           *  @brief  Builds a %Test_vector from a range.
           *  @param  first  An input iterator.
           *  @param  last  An input iterator.
           *  @param  a  An allocator.
           *
           *  Create a %Test_vector 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>
            Test_vector(_InputIterator __first, _InputIterator __last,
               const allocator_type& __a = allocator_type())
        : _Base(__a)
            {
          // Check whether it's an integral type.  If so, it's not an iterator.
          typedef typename __is_integer<_InputIterator>::__type _Integral;
          _M_initialize_dispatch(__first, __last, _Integral());
        }
    
          /**
           *  The 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
           *  responsibility.
           */
          ~Test_vector()
          { _Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
                  _M_get_Tp_allocator()); }
    
          /**
           *  @brief  %Test_vector assignment operator.
           *  @param  x  A %Test_vector of identical element and allocator types.
           *
           *  All the elements of @a x are copied, but any extra memory in
           *  @a x (for fast expansion) will not be copied.  Unlike the
           *  copy constructor, the allocator object is not copied.
           */
          Test_vector&
          operator=(const Test_vector& __x);
    
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
          /**
           *  @brief  %Test_vector move assignment operator.
           *  @param  x  A %Test_vector of identical element and allocator types.
           *
           *  The contents of @a x are moved into this %Test_vector (without copying).
           *  @a x is a valid, but unspecified %Test_vector.
           */
          Test_vector&
          operator=(Test_vector&& __x)
          {
        // NB: DR 675.
        this->clear();
        this->swap(__x); 
        return *this;
          }
    
          /**
           *  @brief  %Test_vector list assignment operator.
           *  @param  l  An initializer_list.
           *
           *  This function fills a %Test_vector with copies of the elements in the
           *  initializer list @a l.
           *
           *  Note that the assignment completely changes the %Test_vector and
           *  that the resulting %Test_vector's size is the same as the number
           *  of elements assigned.  Old data may be lost.
           */
          Test_vector&
          operator=(initializer_list<value_type> __l)
          {
        this->assign(__l.begin(), __l.end());
        return *this;
          }
    #endif
    
          /**
           *  @brief  Assigns a given value to a %Test_vector.
           *  @param  n  Number of elements to be assigned.
           *  @param  val  Value to be assigned.
           *
           *  This function fills a %Test_vector with @a n copies of the given
           *  value.  Note that the assignment completely changes the
           *  %Test_vector and that the resulting %Test_vector'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 %Test_vector.
           *  @param  first  An input iterator.
           *  @param  last   An input iterator.
           *
           *  This function fills a %Test_vector with copies of the elements in the
           *  range [first,last).
           *
           *  Note that the assignment completely changes the %Test_vector and
           *  that the resulting %Test_vector'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>::__type _Integral;
          _M_assign_dispatch(__first, __last, _Integral());
        }
    
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
    
          void
          assign(initializer_list<value_type> __l)
          { this->assign(__l.begin(), __l.end()); }
    #endif
    
          /// Get a copy of the memory allocation object.
          using _Base::get_allocator;
    
          // iterators
          /**
           *  Returns a read/write iterator that points to the first
           *  element in the %Test_vector.  Iteration is done in ordinary
           *  element order.
           */
          iterator
          begin()
          { return iterator(this->_M_impl._M_start); }
    
          /**
           *  Returns a read-only (constant) iterator that points to the
           *  first element in the %Test_vector.  Iteration is done in ordinary
           *  element order.
           */
          const_iterator
          begin() const
          { return const_iterator(this->_M_impl._M_start); }
    
          /**
           *  Returns a read/write iterator that points one past the last
           *  element in the %Test_vector.  Iteration is done in ordinary
           *  element order.
           */
          iterator
          end()
          { return iterator(this->_M_impl._M_finish); }
    
          /**
           *  Returns a read-only (constant) iterator that points one past
           *  the last element in the %Test_vector.  Iteration is done in
           *  ordinary element order.
           */
          const_iterator
          end() const
          { return const_iterator(this->_M_impl._M_finish); }
    
          /**
           *  Returns a read/write reverse iterator that points to the
           *  last element in the %Test_vector.  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 %Test_vector.  Iteration is done in
           *  reverse element order.
           */
          Test__const_reverse_iterator rbegin() const
          { return Test__const_reverse_iterator(end()); }
    
          /**
           *  Returns a read/write reverse iterator that points to one
           *  before the first element in the %Test_vector.  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 %Test_vector.  Iteration
           *  is done in reverse element order.
           */
          Test__const_reverse_iterator
          rend() const
          { return Test__const_reverse_iterator(begin()); }
    
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
          /**
           *  Returns a read-only (constant) iterator that points to the
           *  first element in the %Test_vector.  Iteration is done in ordinary
           *  element order.
           */
          const_iterator
          cbegin() const
          { return const_iterator(this->_M_impl._M_start); }
    
          /**
           *  Returns a read-only (constant) iterator that points one past
           *  the last element in the %Test_vector.  Iteration is done in
           *  ordinary element order.
           */
          const_iterator
          cend() const
          { return const_iterator(this->_M_impl._M_finish); }
    
          /**
           *  Returns a read-only (constant) reverse iterator that points
           *  to the last element in the %Test_vector.  Iteration is done in
           *  reverse element order.
           */
          Test__const_reverse_iterator
          crbegin() const
          { return Test__const_reverse_iterator(end()); }
    
          /**
           *  Returns a read-only (constant) reverse iterator that points
           *  to one before the first element in the %Test_vector.  Iteration
           *  is done in reverse element order.
           */
          Test__const_reverse_iterator
          crend() const
          { return Test__const_reverse_iterator(begin()); }
    #endif
    
          // [23.2.4.2] capacity
          /**  Returns the number of elements in the %Test_vector.  */
          size_type
          size() const
          { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
    
          /**  Returns the size() of the largest possible %Test_vector.  */
          size_type
          max_size() const
          { return _M_get_Tp_allocator().max_size(); }
    
          /**
           *  @brief  Resizes the %Test_vector to the specified number of elements.
           *  @param  new_size  Number of elements the %Test_vector should contain.
           *  @param  x  Data with which new elements should be populated.
           *
           *  This function will %resize the %Test_vector to the specified
           *  number of elements.  If the number is smaller than the
           *  %Test_vector's current size the %Test_vector is truncated, otherwise
           *  the %Test_vector is extended and new elements are populated with
           *  given data.
           */
          void
          resize(size_type __new_size, value_type __x = value_type())
          {
        if (__new_size < size())
          _M_erase_at_end(this->_M_impl._M_start + __new_size);
        else
          insert(end(), __new_size - size(), __x);
          }
    
          /**
           *  Returns the total number of elements that the %Test_vector can
           *  hold before needing to allocate more memory.
           */
          size_type
          capacity() const
          { return size_type(this->_M_impl._M_end_of_storage
                 - this->_M_impl._M_start); }
    
          /**
           *  Returns true if the %Test_vector is empty.  (Thus begin() would
           *  equal end().)
           */
          bool
          empty() const
          { return begin() == end(); }
    
          /**
           *  @brief  Attempt to preallocate enough memory for specified number of
           *          elements.
           *  @param  n  Number of elements required.
           *  @throw  length_error  If @a n exceeds @c max_size().
           *
           *  This function attempts to reserve enough memory for the
           *  %Test_vector to hold the specified number of elements.  If the
           *  number requested is more than max_size(), length_error is
           *  thrown.
           *
           *  The advantage of this function is that if optimal code is a
           *  necessity and the user can determine the number of elements
           *  that will be required, the user can reserve the memory in
           *  %advance, and thus prevent a possible reallocation of memory
           *  and copying of %Test_vector data.
           */
          void
          reserve(size_type __n);
    
          // element access
          /**
           *  @brief  Subscript access to the data contained in the %Test_vector.
           *  @param n The index of the element for which data should be
           *  accessed.
           *  @return  Read/write reference to data.
           *
           *  This operator allows for easy, array-style, data access.
           *  Note that data access with this operator is unchecked and
           *  out_of_range lookups are not defined. (For checked lookups
           *  see at().)
           */
          reference
          operator[](size_type __n)
          { return *(this->_M_impl._M_start + __n); }
    
          /**
           *  @brief  Subscript access to the data contained in the %Test_vector.
           *  @param n The index of the element for which data should be
           *  accessed.
           *  @return  Read-only (constant) reference to data.
           *
           *  This operator allows for easy, array-style, data access.
           *  Note that data access with this operator is unchecked and
           *  out_of_range lookups are not defined. (For checked lookups
           *  see at().)
           */
          const_reference
          operator[](size_type __n) const
          { return *(this->_M_impl._M_start + __n); }
    
        protected:
          /// Safety check used only from at().
          void
          _M_range_check(size_type __n) const
          {
        if (__n >= this->size())
          __throw_out_of_range(__N("Test_vector::_M_range_check"));
          }
    
        public:
          /**
           *  @brief  Provides access to the data contained in the %Test_vector.
           *  @param n The index of the element for which data should be
           *  accessed.
           *  @return  Read/write reference to data.
           *  @throw  out_of_range  If @a n is an invalid index.
           *
           *  This function provides for safer data access.  The parameter
           *  is first checked that it is in the range of the Test_vector.  The
           *  function throws out_of_range if the check fails.
           */
          reference
          at(size_type __n)
          {
        _M_range_check(__n);
        return (*this)[__n]; 
          }
    
          /**
           *  @brief  Provides access to the data contained in the %Test_vector.
           *  @param n The index of the element for which data should be
           *  accessed.
           *  @return  Read-only (constant) reference to data.
           *  @throw  out_of_range  If @a n is an invalid index.
           *
           *  This function provides for safer data access.  The parameter
           *  is first checked that it is in the range of the Test_vector.  The
           *  function throws out_of_range if the check fails.
           */
          const_reference
          at(size_type __n) const
          {
        _M_range_check(__n);
        return (*this)[__n];
          }
    
          /**
           *  Returns a read/write reference to the data at the first
           *  element of the %Test_vector.
           */
          reference
          front()
          { return *begin(); }
    
          /**
           *  Returns a read-only (constant) reference to the data at the first
           *  element of the %Test_vector.
           */
          const_reference
          front() const
          { return *begin(); }
    
          /**
           *  Returns a read/write reference to the data at the last
           *  element of the %Test_vector.
           */
          reference
          back()
          { return *(end() - 1); }
    
          /**
           *  Returns a read-only (constant) reference to the data at the
           *  last element of the %Test_vector.
           */
          const_reference
          back() const
          { return *(end() - 1); }
    
          // _GLIBCXX_RESOLVE_LIB_DEFECTS
          // DR 464. Suggestion for new member functions in standard containers.
          // data access
          /**
           *   Returns a pointer such that [data(), data() + size()) is a valid
           *   range.  For a non-empty %Test_vector, data() == &front().
           */
          pointer
          data()
          { return pointer(this->_M_impl._M_start); }
    
          const_pointer
          data() const
          { return const_pointer(this->_M_impl._M_start); }
    
          // [23.2.4.3] modifiers
          /**
           *  @brief  Add data to the end of the %Test_vector.
           *  @param  x  Data to be added.
           *
           *  This is a typical stack operation.  The function creates an
           *  element at the end of the %Test_vector and assigns the given data
           *  to it.  Due to the nature of a %Test_vector this operation can be
           *  done in constant time if the %Test_vector has preallocated space
           *  available.
           */
          void
          push_back(const value_type& __x)
          {
        if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
          {
            this->_M_impl.construct(this->_M_impl._M_finish, __x);
            ++this->_M_impl._M_finish;
          }
        else
          _M_insert_aux(end(), __x);
          }
    
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
          void
          push_back(value_type&& __x)
          { emplace_back(move(__x)); }
    
          template<typename... _Args>
            void
            emplace_back(_Args&&... __args);
    #endif
    
          /**
           *  @brief  Removes last element.
           *
           *  This is a typical stack operation. It shrinks the %Test_vector by one.
           *
           *  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_impl._M_finish;
        this->_M_impl.destroy(this->_M_impl._M_finish);
          }
    
    
      //    template<typename... _Args>
      //      iterator
      //      emplace(iterator __position, _Args&&... __args)//从外部移到内部
            //{
            //      const size_type __n = __position - begin();
            //      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
            //          && __position == end())
            //      {
            //          this->_M_impl.construct(this->_M_impl._M_finish,
            //              forward<_Args>(__args)...);
            //          ++this->_M_impl._M_finish;
            //      }
            //      else
            //          _M_insert_aux(__position, forward<_Args>(__args)...);
            //      return iterator(this->_M_impl._M_start + __n);
            //}
    
          /**
           *  @brief  Inserts given value into %Test_vector before specified iterator.
           *  @param  position  An iterator into the %Test_vector.
           *  @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.  Note that this kind of operation
           *  could be expensive for a %Test_vector and if it is frequently
           *  used the user should consider using list.
           */
          iterator
          insert(iterator __position, const value_type& __x)//2参数改为内部实现
          {
              const size_type __n = __position - begin();
              if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
                  && __position == end())
              {
                  this->_M_impl.construct(this->_M_impl._M_finish, __x);
                  ++this->_M_impl._M_finish;
              }
              else
              {
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
                  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
                  {
                      _Tp __x_copy = __x;
                      _M_insert_aux(__position, std::move(__x_copy));
                  }
                  else
    #endif
                      _M_insert_aux(__position, __x);
              }
              return iterator(this->_M_impl._M_start + __n);
          }
    
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
          /**
           *  @brief  Inserts given rvalue into %Test_vector before specified iterator.
           *  @param  position  An iterator into the %Test_vector.
           *  @param  x  Data to be inserted.
           *  @return  An iterator that points to the inserted data.
           *
           *  This function will insert a copy of the given rvalue before
           *  the specified location.  Note that this kind of operation
           *  could be expensive for a %Test_vector and if it is frequently
           *  used the user should consider using list.
           */
          iterator
          insert(iterator __position, value_type&& __x)
          { return emplace(__position, move(__x)); }
    
          /**
           *  @brief  Inserts an initializer_list into the %Test_vector.
           *  @param  position  An iterator into the %Test_vector.
           *  @param  l  An initializer_list.
           *
           *  This function will insert copies of the data in the 
           *  initializer_list @a l into the %Test_vector before the location
           *  specified by @a position.
           *
           *  Note that this kind of operation could be expensive for a
           *  %Test_vector and if it is frequently used the user should
           *  consider using list.
           */
          void
          insert(iterator __position, initializer_list<value_type> __l)
          { this->insert(__position, __l.begin(), __l.end()); }
    #endif
    
          /**
           *  @brief  Inserts a number of copies of given data into the %Test_vector.
           *  @param  position  An iterator into the %Test_vector.
           *  @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.
           *
           *  Note that this kind of operation could be expensive for a
           *  %Test_vector and if it is frequently used the user should
           *  consider using list.
           */
          void
          insert(iterator __position, size_type __n, const value_type& __x)
          { _M_fill_insert(__position, __n, __x); }
    
          /**
           *  @brief  Inserts a range into the %Test_vector.
           *  @param  position  An iterator into the %Test_vector.
           *  @param  first  An input iterator.
           *  @param  last   An input iterator.
           *
           *  This function will insert copies of the data in the range
           *  [first,last) into the %Test_vector before the location specified
           *  by @a pos.
           *
           *  Note that this kind of operation could be expensive for a
           *  %Test_vector and if it is frequently used the user should
           *  consider using list.
           */
          template<typename _InputIterator>
            void
            insert(iterator __position, _InputIterator __first,
               _InputIterator __last)
            {
          // Check whether it's an integral type.  If so, it's not an iterator.
          typedef typename __is_integer<_InputIterator>::__type _Integral;
          _M_insert_dispatch(__position, __first, __last, _Integral());
        }
    
          /**
           *  @brief  Remove element at given position.
           *  @param  position  Iterator pointing to element to be erased.
           *  @return  An iterator pointing to the next element (or end()).
           *
           *  This function will erase the element at the given position and thus
           *  shorten the %Test_vector by one.
           *
           *  Note This operation could be expensive and if it is
           *  frequently used the user should consider using list.
           *  The user is also cautioned that this function only erases
           *  the element, and that if the element is itself a pointer,
           *  the pointed-to memory is not touched in any way.  Managing
           *  the pointer is the user's responsibility.
           */
          iterator
          erase(iterator __position)//改为内部实现
          {
              if (__position + 1 != end())
                  _GLIBCXX_MOVE3(__position + 1, end(), __position);
              --this->_M_impl._M_finish;
              this->_M_impl.destroy(this->_M_impl._M_finish);
              return __position;
          }
    
          /**
           *  @brief  Remove a range of elements.
           *  @param  first  Iterator pointing to the first element to be erased.
           *  @param  last  Iterator pointing to one past the last element to be
           *                erased.
           *  @return  An iterator pointing to the element pointed to by @a last
           *           prior to erasing (or end()).
           *
           *  This function will erase the elements in the range [first,last) and
           *  shorten the %Test_vector accordingly.
           *
           *  Note This operation could be expensive and if it is
           *  frequently used the user should consider using list.
           *  The user is also cautioned that this function only erases
           *  the elements, and that if the elements themselves are
           *  pointers, the pointed-to memory is not touched in any way.
           *  Managing the pointer is the user's responsibility.
           */
          iterator
          erase(iterator __first, iterator __last)//改为内部实现
          {
              if (__last != end())
                  _GLIBCXX_MOVE3(__last, end(), __first);
              _M_erase_at_end(__first.base() + (end() - __last));
              return __first;
          }
    
          /**
           *  @brief  Swaps data with another %Test_vector.
           *  @param  x  A %Test_vector of the same element and allocator types.
           *
           *  This exchanges the elements between two vectors in constant time.
           *  (Three pointers, so it should be quite fast.)
           *  Note that the global swap() function is specialized such that
           *  swap(v1,v2) will feed to this function.
           */
          void
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
          swap(Test_vector&& __x)
    #else
          swap(Test_vector& __x)
    #endif
          {
        swap(this->_M_impl._M_start, __x._M_impl._M_start);
        swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
        swap(this->_M_impl._M_end_of_storage,
              __x._M_impl._M_end_of_storage);
    
        // _GLIBCXX_RESOLVE_LIB_DEFECTS
        // 431. Swapping containers with unequal allocators.
        __alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(),
                                __x._M_get_Tp_allocator());
          }
    
          /**
           *  Erases all the elements.  Note that this function only erases the
           *  elements, and that if the elements themselves are pointers, the
           *  pointed-to memory is not touched in any way.  Managing the pointer is
           *  the user's responsibility.
           */
          void
          clear()
          { _M_erase_at_end(this->_M_impl._M_start); }
    
        protected:
          /**
           *  Memory expansion handler.  Uses the member allocation function to
           *  obtain @a n bytes of memory, and then copies [first,last) into it.
           */
          template<typename _ForwardIterator>
            pointer
            _M_allocate_and_copy(size_type __n,
                     _ForwardIterator __first, _ForwardIterator __last)
            {
          pointer __result = this->_M_allocate(__n);
          __try
            {
              __uninitialized_copy_a(__first, __last, __result,
                          _M_get_Tp_allocator());
              return __result;
            }
          __catch(...)
            {
              _M_deallocate(__result, __n);
              __throw_exception_again;
            }
        }
    
    
          // Internal constructor functions follow.
    
          // Called by the range constructor to implement [23.1.1]/9
    
          // _GLIBCXX_RESOLVE_LIB_DEFECTS
          // 438. Ambiguity in the "do the right thing" clause
          template<typename _Integer>
            void
            _M_initialize_dispatch(_Integer __n, _Integer Test__value, __true_type)
            {
          this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n));
          this->_M_impl._M_end_of_storage =
            this->_M_impl._M_start + static_cast<size_type>(__n);
          _M_fill_initialize(static_cast<size_type>(__n), Test__value);
        }
    
          // Called by the range constructor to implement [23.1.1]/9
          template<typename _InputIterator>
            void
            _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
                       __false_type)
            {
          typedef typename iterator_traits<_InputIterator>::
            iterator_category _IterCategory;
          _M_range_initialize(__first, __last, _IterCategory());
        }
    
          // Called by the second initialize_dispatch above
          template<typename _InputIterator>
            void
            _M_range_initialize(_InputIterator __first,
                    _InputIterator __last, input_iterator_tag)
            {
          for (; __first != __last; ++__first)
            push_back(*__first);
        }
    
          // Called by the second initialize_dispatch above
          template<typename _ForwardIterator>
            void
            _M_range_initialize(_ForwardIterator __first,
                    _ForwardIterator __last, forward_iterator_tag)
            {
          const size_type __n = distance(__first, __last);
          this->_M_impl._M_start = this->_M_allocate(__n);
          this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
          this->_M_impl._M_finish =
            __uninitialized_copy_a(__first, __last,
                        this->_M_impl._M_start,
                        _M_get_Tp_allocator());
        }
    
          // Called by the first initialize_dispatch above and by the
          // Test_vector(n,value,a) constructor.
          void
          _M_fill_initialize(size_type __n, const value_type& Test__value)
          {
        __uninitialized_fill_n_a(this->_M_impl._M_start, __n, Test__value, 
                          _M_get_Tp_allocator());
        this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
          }
    
    
          // Internal assign functions follow.  The *_aux functions do the actual
          // assignment work for the range versions.
    
          // Called by the range assign to implement [23.1.1]/9
    
          // _GLIBCXX_RESOLVE_LIB_DEFECTS
          // 438. Ambiguity in the "do the right thing" clause
          template<typename _Integer>
            void
            _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
            { _M_fill_assign(__n, __val); }
    
          // Called by the range assign to implement [23.1.1]/9
          template<typename _InputIterator>
            void
            _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
                   __false_type)
            {
          typedef typename iterator_traits<_InputIterator>::
            iterator_category _IterCategory;
          _M_assign_aux(__first, __last, _IterCategory());
        }
    
          // Called by the second assign_dispatch above
          template<typename _InputIterator>
            void
            _M_assign_aux(_InputIterator __first, _InputIterator __last,
                  input_iterator_tag);
    
          // Called by the second assign_dispatch above
          template<typename _ForwardIterator>
            void
            _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
                  forward_iterator_tag);
    
          // Called by assign(n,t), and the range assign when it turns out
          // to be the same thing.
          void
          _M_fill_assign(size_type __n, const value_type& __val);
    
    
          // Internal insert functions follow.
    
          // Called by the range insert to implement [23.1.1]/9
    
          // _GLIBCXX_RESOLVE_LIB_DEFECTS
          // 438. Ambiguity in the "do the right thing" clause
          template<typename _Integer>
            void
            _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
                   __true_type)
            { _M_fill_insert(__pos, __n, __val); }
    
          // Called by the range insert to implement [23.1.1]/9
          template<typename _InputIterator>
            void
            _M_insert_dispatch(iterator __pos, _InputIterator __first,
                   _InputIterator __last, __false_type)
            {
          typedef typename iterator_traits<_InputIterator>::
            iterator_category _IterCategory;
          _M_range_insert(__pos, __first, __last, _IterCategory());
        }
    
          // Called by the second insert_dispatch above
          template<typename _InputIterator>
            void
            _M_range_insert(iterator __pos, _InputIterator __first,
                _InputIterator __last, input_iterator_tag);
    
          // Called by the second insert_dispatch above
          template<typename _ForwardIterator>
            void
            _M_range_insert(iterator __pos, _ForwardIterator __first,
                _ForwardIterator __last, forward_iterator_tag);
    
          // Called by insert(p,n,x), and the range insert when it turns out to be
          // the same thing.
          void
          _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
    
          // Called by insert(p,x)
    #ifndef __GXX_EXPERIMENTAL_CXX0X__
          void
          _M_insert_aux(iterator __position, const value_type& __x);
    #else
          template<typename... _Args>
            void
            _M_insert_aux(iterator __position, _Args&&... __args);
    #endif
    
          // Called by the latter.
          size_type
          _M_check_len(size_type __n, const char* __s) const
          {
        /*if (max_size() - size() < __n)
          __throw_length_error(__N(__s));*/
    
        const size_type __len = size() + max(size(), __n);
        return (__len < size() || __len > max_size()) ? max_size() : __len;
          }
    
          // Internal erase functions follow.
    
          // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
          // _M_assign_aux.
          void
          _M_erase_at_end(pointer __pos)
          {
        _Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
        this->_M_impl._M_finish = __pos;
          }
    
        };
    
    
    
    
    
    #define _GLIBCXX_MOVE(_Tp) move(_Tp)
    
    
        template<typename _Tp>
        struct identity
        {
            typedef _Tp type;
        };
    
        template<typename _Tp>
        inline _Tp&&
            forward(typename identity<_Tp>::type&& __t)
        { return __t; }
    
    template<typename _Tp>
        class remove_reference
        {
        public:
            typedef _Tp& type;
        };
    template<typename _Tp>
    inline typename remove_reference<_Tp>::type&&
        move(_Tp&& __t)
    { return __t; }
    
    
    
    
    
    template<typename _InputIterator, typename _ForwardIterator>
    inline _ForwardIterator
        uninitialized_copy(_InputIterator __first, _InputIterator __last,
        _ForwardIterator __result)
    {
        typedef typename iterator_traits<_InputIterator>::value_type
            _ValueType1;
        typedef typename iterator_traits<_ForwardIterator>::value_type
            _ValueType2;
    
        return __uninitialized_copy<(__is_pod(_ValueType1)
            && __is_pod(_ValueType2))>::
            uninitialized_copy(__first, __last, __result);
    }
    
    
    
    
    template<bool>
    struct __uninitialized_copy
    {
        template<typename _InputIterator, typename _ForwardIterator>
        static _ForwardIterator
            uninitialized_copy(_InputIterator __first, _InputIterator __last,
            _ForwardIterator __result)
        {
            _ForwardIterator __cur = __result;
            try
            {
                for (; __first != __last; ++__first, ++__cur)
                    ::new(static_cast<void*>(&*__cur)) typename
                    iterator_traits<_ForwardIterator>::value_type(*__first);
                return __cur;
            }
            catch(...)
            {
                _Destroy(__result, __cur);
            }
        }
    };
    
    template<bool, bool, typename>
    struct __copy_move
    {
        template<typename _II, typename _OI>
        static _OI
            __copy_m(_II __first, _II __last, _OI __result)
        {
            for (; __first != __last; ++__result, ++__first)
                *__result = *__first;
            return __result;
        }
    };
    
    template<bool _IsMove, typename _II, typename _OI>
    inline _OI
        __copy_move_a(_II __first, _II __last, _OI __result)
    {
        typedef typename iterator_traits<_II>::value_type _ValueTypeI;
        typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
        typedef typename iterator_traits<_II>::iterator_category _Category;
        const bool __simple = (__is_pod(_ValueTypeI)
            && __is_pointer<_II>::Test__value
            && __is_pointer<_OI>::Test__value
            && __are_same<_ValueTypeI, _ValueTypeO>::Test__value);
    
        return __copy_move<_IsMove, __simple,
            _Category>::__copy_m(__first, __last, __result);
    }
    
    
    template<bool _IsMove, typename _II, typename _OI>
    inline _OI
        __copy_move_a2(_II __first, _II __last, _OI __result)
    {
        return _OI(__copy_move_a<_IsMove>
            (__niter_base<_II>::__b(__first),
            __niter_base<_II>::__b(__last),
            __niter_base<_OI>::__b(__result)));
    }
    
    template<typename _II, typename _OI>
    inline _OI
        copy(_II __first, _II __last, _OI __result)
    {
        // concept requirements
    
    
        return (__copy_move_a2<__is_move_iterator<_II>::Test__value>
            (__miter_base<_II>::__b(__first),
            __miter_base<_II>::__b(__last), __result));
    }
    
    
    template<>
    struct __uninitialized_copy<true>
    {
        template<typename _InputIterator, typename _ForwardIterator>
        static _ForwardIterator
            uninitialized_copy(_InputIterator __first, _InputIterator __last,
            _ForwardIterator __result)
        { return copy(__first, __last, __result); }
    };
    
    
    
    
    
    #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
    
    
    template<typename _InputIterator, typename _ForwardIterator, typename _Tp>
    inline _ForwardIterator
        __uninitialized_copy_a(_InputIterator __first, _InputIterator __last,
        _ForwardIterator __result, allocator<_Tp>&)
    { return uninitialized_copy(__first, __last, __result); }
    
    template<typename _InputIterator, typename _ForwardIterator,
        typename _Allocator>
        inline _ForwardIterator
        __uninitialized_move_a(_InputIterator __first, _InputIterator __last,
        _ForwardIterator __result, _Allocator& __alloc)
    {
        return __uninitialized_copy_a(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
            _GLIBCXX_MAKE_MOVE_ITERATOR(__last),
            __result, __alloc);
    }
    
    
    
    
    #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) copy_backward(_Tp, _Up, _Vp)
    
    
    
    //
    // Move iterator type
    //
    template<typename _Tp>
    struct __is_move_iterator
    {
        enum { Test__value = 0 };
        typedef __false_type __type;
    };
    
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
    template<typename _Iterator>
    class move_iterator;
    
    template<typename _Iterator>
    struct __is_move_iterator< move_iterator<_Iterator> >
    {
        enum { Test__value = 1 };
        typedef __true_type __type;
    };
    #endif
    
    
    
    
    // Likewise, for move_iterator.
    template<typename _Iterator,
        bool _IsMove = __is_move_iterator<_Iterator>::Test__value>
    struct __miter_base
    {
        static _Iterator
            __b(_Iterator __it)
        { return __it; }
    };
    
    template<typename _Iterator>
    struct __miter_base<_Iterator, true>
    {
        static typename _Iterator::iterator_type
            __b(_Iterator __it)
        { return __it.base(); }
    };
    
    
    
    
    template<bool, bool, typename>
    struct __copy_move_backward
    {
        template<typename _BI1, typename _BI2>
        static _BI2
            __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
        {
            while (__first != __last)
                *--__result = *--__last;
            return __result;
        }
    };
    
    
    template<bool _IsMove, typename _BI1, typename _BI2>
    inline _BI2
        __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)
    {
        typedef typename iterator_traits<_BI1>::value_type _ValueType1;
        typedef typename iterator_traits<_BI2>::value_type _ValueType2;
        typedef typename iterator_traits<_BI1>::iterator_category _Category;
        const bool __simple = (__is_pod(_ValueType1)
            && __is_pointer<_BI1>::Test__value
            && __is_pointer<_BI2>::Test__value
            && __are_same<_ValueType1, _ValueType2>::Test__value);
    
        return __copy_move_backward<_IsMove, __simple,
            _Category>::__copy_move_b(__first,
            __last,
            __result);
    }
    
    
    
    
    
    
    template<bool _IsMove, typename _BI1, typename _BI2>
    inline _BI2
        __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
    {
        return _BI2(__copy_move_backward_a<_IsMove>
            (__niter_base<_BI1>::__b(__first),
            __niter_base<_BI1>::__b(__last),
            __niter_base<_BI2>::__b(__result)));
    }
    
    
    
    template<typename _BI1, typename _BI2>
    inline _BI2
        copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
    {
        // concept requirements
        /*__glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
            __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
            __glibcxx_function_requires(_ConvertibleConcept<
            typename iterator_traits<_BI1>::value_type,
            typename iterator_traits<_BI2>::value_type>)
            __glibcxx_requires_valid_range(__first, __last);*/
    
        return (__copy_move_backward_a2<__is_move_iterator<_BI1>::Test__value>
            (__miter_base<_BI1>::__b(__first),
            __miter_base<_BI1>::__b(__last), __result));
    }
    
    
    
        template<typename _Tp, typename _Alloc>
        void
            Test_vector<_Tp, _Alloc>::
            _M_insert_aux(iterator __position, const _Tp& __x)
        {
            if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
            {
                this->_M_impl.construct(this->_M_impl._M_finish,
                    _GLIBCXX_MOVE(*(this->_M_impl._M_finish
                    - 1)));
                ++this->_M_impl._M_finish;
    #ifndef __GXX_EXPERIMENTAL_CXX0X__
                _Tp __x_copy = __x;
    #endif
                _GLIBCXX_MOVE_BACKWARD3(__position.base(),
                    this->_M_impl._M_finish - 2,
                    this->_M_impl._M_finish - 1);
    #ifndef __GXX_EXPERIMENTAL_CXX0X__
                *__position = __x_copy;
    #else
                *__position = _Tp(std::forward<_Args>(__args)...);
    #endif
            }
            else
            {
                const size_type __len =
                    _M_check_len(size_type(1), "Test_vector::_M_insert_aux");
                const size_type __elems_before = __position - begin();
                pointer __new_start(this->_M_allocate(__len));
                pointer __new_finish(__new_start);
                try
                {
                    // The order of the three operations is dictated by the C++0x
                    // case, where the moves could alter a new element belonging
                    // to the existing Test_vector.  This is an issue only for callers
                    // taking the element by const lvalue ref (see 23.1/13).
                    this->_M_impl.construct(__new_start + __elems_before,
    #ifdef __GXX_EXPERIMENTAL_CXX0X__
                        std::forward<_Args>(__args)...);
    #else
                        __x);
    #endif
                    __new_finish = 0;
    
                    __new_finish =
                        __uninitialized_move_a(this->_M_impl._M_start,
                        __position.base(), __new_start,
                        _M_get_Tp_allocator());
                    ++__new_finish;
    
                    __new_finish =
                        __uninitialized_move_a(__position.base(),
                        this->_M_impl._M_finish,
                        __new_finish,
                        _M_get_Tp_allocator());
                }
                catch(...)
                {
                    if (!__new_finish)
                        this->_M_impl.destroy(__new_start + __elems_before);
                    else
                        _Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
                    _M_deallocate(__new_start, __len);
                }
                _Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
                    _M_get_Tp_allocator());
                _M_deallocate(this->_M_impl._M_start,
                    this->_M_impl._M_end_of_storage
                    - this->_M_impl._M_start);
                this->_M_impl._M_start = __new_start;
                this->_M_impl._M_finish = __new_finish;
                this->_M_impl._M_end_of_storage = __new_start + __len;
            }
        }

    在这个完整代码中注释稍少,如有见解者还望不吝赐教!

    展开全文
  • 关于vector的erase删除操作的两种不同方法,在linux与visual studio的实现讨论1.前言:最近在做某一个题时,用到了vector删除操作,利用的是erase()函数删除符合条件的函数,然后和同学讨论的时候,同学给了一个...

    #关于vector的erase删除操作的两种不同方法,在linux与visual studio的实现讨论


    ##1.前言:
    最近在做某一个题时,用到了vector的删除操作,利用的是erase()函数删除符合条件的函数,然后和同学讨论的时候,同学给了一个写法,网上也搜到了一个写法,但是发现了问题。


    ##2.测试代码:
    定义一个vector 删除指定元素, 这里是删除1

    #include <vector>
    #include <iostream>
    using namespace std;
    
    int main() {
    	vector <int> arr; 
    	arr.push_back(1);
    	arr.push_back(2);
    	arr.push_back(3);
    	arr.push_back(4);
    	arr.push_back(5);
    
    	for (auto i = arr.begin(); i != arr.end(); i++) {           // 第一种写法
    		if (*i == 1) {
    			i = arr.erase(i);
    			i--;
    		}
    	}
    
    	 for (auto i = arr.begin(); i != arr.end();) {           // 第二种写法
    	 	if (*i == 1) {
    	 		i = arr.erase(i);
    	 	} else {
    	 		i++;
    	 	}
    	 }
    
    
    
    	for (auto i = arr.begin(); i != arr.end(); i++) {        //输出
    		cout << *i << " ";
    	}
    	cout << endl;
    
    
    
    	return 0;
    }
    

    ##3.讨论

    这两种写法, 看起来是基本相同的,基本想法就是每一次循环 删除了迭代器那么不自增迭代器,反之,则自增迭代器, 实则不然,如果一上来就删除首元素, 那么问题就来了 方法一的i在自减之后不是出了小于arr.begin()了吗。别急我们看下面的实践。


    ##4.测试

    ubuntu

    在ubuntu下可以运行而且不出错
    这里写图片描述

    这里进入gdb调试 查看迭代器i的变化

    这里写图片描述
    在删除元素后 迭代器自减后竟然是有地址的 此时地址是arr.begin()的前面一个地址, 也就是说i可以变成
    arr.begin() - 1

    这里写图片描述
    迭代器自加后 迭代器变成了arr.begin()

    这里写图片描述
    ###visual studio

    运行时错误,出错在 i–;
    因为i–后 i变成了arr.begin() - 1 而visual studio不支持这样的写法,所以报错
    这里写图片描述

    这里写图片描述

    ##5.总结
    vector如果简单想象成数组arr的话,在首元素i–,i = (arr - 1),但我们并没有在这个状态下解引用。然后i++加回去又回到可解引用的地址值,不出事也是可以理解的, gnu对list的实现是双向循环链表 ++list.end() 后就变成 list.begin()。但vs会assert说越界

    展开全文
  • 工作8年,第一次遇到这种问题,百思不得其解,使用erase删除vector元素,删除正常,但后面打印数据发现,元素居然依然存在。当然其实最终发现原因也是不注意代码细节引起的。先上代码。 注:以下代码在windows环境...

    工作8年,第一次遇到这种问题,百思不得其解,使用erase删除vector元素,删除正常,但后面打印数据发现,元素居然依然存在。当然其实最终发现原因也是不注意代码细节引起的。先上代码。
    注:以下代码在windows环境直接报错,而linux居然正常输出。

    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main()
    {
    	std::vector<int> vec;
    	for (int i = 0; i < 10; ++i)
    	{
    		vec.push_back(i);
    	}
    
    	vec.push_back(1);
    	vec.push_back(1);
    	vec.push_back(1);
    	vec.push_back(1);
    	for (auto it = vec.begin(); it != vec.end();)
    	{
    		cout << *it << endl;
    		it++;
    	}
    	cout << "*************line******************" << endl;
    	int nSize = vec.size();
    	for (auto it = vec.begin(); it != vec.end();)
    	{
    		if (1 == *it) {
    			it = vec.erase(it);
    		}
    		else {
    			++it;
    		}
    	}
    
    	auto it = vec.begin();
    	for (int n = 0; n < nSize;n++)
    	{
    		cout << *it << endl;
    		it++;
    	}
    	system("pause");
    	return 0;
    }
    

    在上输出数据:
    图一
    看到没,删除的元素居然依然存在,其实是因为野指针原因引起的,由于编译器的差异,还真不一定会报错。
    所以在开发过程中一定要注意细节,最后修改如下:

    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main()
    {
    	std::vector<int> vec;
    	for (int i = 0; i < 10; ++i)
    	{
    		vec.push_back(i);
    	}
    
    	vec.push_back(1);
    	vec.push_back(1);
    	vec.push_back(1);
    	vec.push_back(1);
    	for (auto it = vec.begin(); it != vec.end();)
    	{
    		cout << *it << endl;
    		it++;
    	}
    	cout << "*************line******************" << endl;
    	
    	for (auto it = vec.begin(); it != vec.end();)
    	{
    		if (1 == *it) {
    			it = vec.erase(it);
    		}
    		else {
    			++it;
    		}
    	}
    	//将size位置变动
    	int nSize = vec.size();
    	auto it = vec.begin();
    	for (int n = 0; n < nSize;n++)
    	{
    		cout << *it << endl;
    		it++;
    	}
    	system("pause");
    	return 0;
    }
    

    修改后输出如下:
    图二

    展开全文
  • C++ vector中实际删除元素使用的是容器vecrot中std::vector::erase()方法。 C++ 中std::remove()并不删除元素,因为容器的size()没有变化,只是元素的替换。 1.std::vector::erase()  函数原型:iterator erase ...
  • Vector

    2021-02-18 12:22:41
    Vector 本节内容 vector的介绍及使用 vector深度剖析及模拟实现 vector的介绍及使用 vector的介绍 vector是表示可变大小数组的序列容器。 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以...
  • vector

    2021-05-06 00:21:30
    string:专门用来管理字符串,底层结构是动态类型的 顺序表,存放char类型元素 vector的底层结构也是动态类型的顺序表,任何元素都可以存放
  • 1-vector.cpp #include <iostream> #include <vector> using namespace std; int main() { int data[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; vector<int> v1; //创建数组对象(模板类) 无参...
  • STL—vector删除重复元素

    千次阅读 2013-09-12 09:37:50
    删除重复元素,首先将vector排序。 sort( vecSrc.begin(), vecSrc.end() );   然后使用unique算法。  vecSrc.erase( unique( vecSrc.begin(), vecSrc.end() ), vecSrc.end() ); unique返回值是重
  • STL中map/vector删除元素操作

    千次阅读 2017-04-07 23:37:45
    在我们使用C++中的STL的时候,可以使用迭代器iterator进行遍历,但是当我们通过iterator对vector和map删除元素的时候,要格外的小心,往往操作不当,导致iterator失效,后果就是程序奔溃。    1. 对于vector,...
  • 这是我自己写的一个拥有线程安全和阻塞功能的vector类SemVector(LINUX平台),欢迎大家使用 //semvector.h #ifndef SEMVECTOR_H_ #define SEMVECTOR_H_ #include #include #include #include template class...
  • vector的实现

    2019-03-06 16:23:56
    个月终于吧vector的实现给写了一遍 = = /* * Vector.h * * Created on: Dec 6, 2018 * Author: clh01s */ #ifndef VECTOR_H_ #define VECTOR_H_ //#include &lt;vector&gt; #include &lt;bits/...
  • vector资料

    2016-02-23 21:08:13
    一、概述vector是C++标准模板库中的部分内容,它是一个多功能的,能够操作多种数据结构和算法的模板类和函数库。vector是一个容器,它能够存放各种类型的对象,简单地说,vector是一个能够存放任意类型的动态数组,...
  • std::vector是顺序容器,当用erase成员函数删除一个迭代器指向的元素时,会自动移动(不是std::move)后面的元素到前面来,而迭代器的指向不变(如果是std::map、std::list这类关联型容器,迭代器会失效),并且不会...
  • 删除指定目录下所有文件代码样例:///////////////////////////////////////////////////////Name: DeleteFile//Purpose: Delete file in the special directory//Author: xxxxxxxx//Created: 2011-...
  • vector使用方法

    2020-08-23 19:01:17
    目录一、vector概念二、使用方法1、头文件2、初始化3、读取元素4、插入、赋值元素 一、vector概念 vector是一种可存放任意类型(类型声明时指定)、自行扩展(加倍方式)、连续存储的容器,类似于可存放任意类型动态...
  • C++ stl vector

    2019-09-12 10:24:53
    2.3.vector删除元素 2.4.vector重要的迭代器 2.5.vector其他函数 3.vector使用实例 3.1.初始化vector中的元素 3.2.遍历vector中的元素 3.3.vector中的元素排序(这里只是简单介绍一些对stl的算法,详细了解...
  • C++ vector 内存释放

    2021-04-08 09:22:28
    C++ STL容器 vector 的工作原理 vector容器的元素以连续方式存放,每一个元素都紧挨着...但是为了防止大量分配连续内存的开销,在使用clear和erase删除数据的时候,它只做了数据清除工作,没有释放内存,所以vector
  • 访问Vector中的任意元素或从末尾添加元素都可以在常量级时间复杂度内完成,而查找特定值的元素所处的位置或是在Vector中插入元素则是线性时间复杂度。 Vectors 包含着一系列连续存储的元素,其行为和数组类似。访问...
  • 容器——vector

    2021-03-29 09:42:11
    vector是表示可变大小数组的序列容器,在使用时需要包含#include<vector>头文件; vector和string一样也采用了连续存储空间来存储元素,只不过它是一种泛型编程,也就是说该容器可以存储不同类型的元素,并不...
  • linux 删除.svn 目录

    千次阅读 2012-07-27 16:13:58
    删除所有.svn目录 这也是我当初查找 Linux find 命令的目的。 1) find . -type d -name ‘.svn’ | xargs rm -rf #先(递归)找到当前路径下含有 .svn的文件目录,再经 xargs逐个干掉 #(处理方式是逐个,并...
  • C++ vector简介

    2016-08-15 17:23:05
    简介vector是C++中的一个容器,它是一个能够存放任意类型的动态数组,能够增加和压缩数据。基本操作首先包含头文件:#include <vector> 定义vector对象:vector<int> vec ...删除尾部的一个对象:vec.pop_back()
  • C++ vector 容器中删除第i项

    万次阅读 2014-12-05 16:44:30
    今天用到了C++的Vector ,需要查找到制定元素后另存然后删除,查找了很多vector的erase()函数,发现都用到了迭代器iterator,本人实在是不擅长用迭代的,所以经过实验,发现不用iterator也可以直接删除Vector中的第i个...
  • vector的用法、vector模拟实现、vector中迭代器失效1. vector用法2. 模拟实现vector3. 迭代器失效问题 1. vector用法 2. 模拟实现vector 3. 迭代器失效问题
  • vector向量容器

    2021-07-15 20:42:58
    vector向量容器vector向量容器包含头文件使用迭代器相关两个重要方法创建vector对象尾部元素扩张使用下标方式访问vector元素用迭代器访问vector元素元素的插入元素的删除向量的大小使用reverse()反向排列算法使用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,746
精华内容 7,898
关键字:

linuxvector删除

linux 订阅