/*

**李坤昱

**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

class allocator;

/// allocator specialization.

template<>

class allocator

{

public:

typedef size_t size_type;

typedef ptrdiff_t difference_type;

typedef void* pointer;

typedef const void* const_pointer;

typedef void value_type;

template

struct rebind

{ typedef allocator<_tp1> other; };

};

template

class new_allocator//添加的数据类型分配原型 ，比如vector 每次分配一个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

struct rebind

{ typedef new_allocator<_tp1> other; };

new_allocator() throw() { }

new_allocator(const new_allocator&) throw() { }

template

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

void

construct(pointer __p, _Args&&... __args)

{ ::new((void *)__p) _Tp(forward<_args>(__args)...); }

#endif

void

destroy(pointer __p) { __p->~_Tp(); }//释放单个节点

};

template

inline bool

operator==(const new_allocator<_tp>&, const new_allocator<_tp>&)

{ return true; }

template

inline bool

operator!=(const new_allocator<_tp>&, const new_allocator<_tp>&)

{ return false; }

template

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

struct rebind

{ typedef allocator<_tp1> other; };

allocator() throw() { }

allocator(const allocator& __a) throw()

: __glibcxx_base_allocator<_tp>(__a) { }

template

allocator(const allocator<_tp1>&) throw() { }

~allocator() throw() { }

// Inherit everything else.

};

template

void

_Destroy(_ForwardIterator __first, _ForwardIterator __last,

_Allocator& __alloc)

{

for (; __first != __last; ++__first)

__alloc.destroy(&*__first);

}

template

inline void

_Destroy(_Tp* __pointer)

{ __pointer->~_Tp(); }

template

struct _Destroy_aux

{

template

static void

__destroy(_ForwardIterator __first, _ForwardIterator __last)

{

for (; __first != __last; ++__first)

_Destroy(&*__first);

}

};

template<>

struct _Destroy_aux

{

template

static void

__destroy(_ForwardIterator, _ForwardIterator) { }

};

template

inline void

_Destroy(_ForwardIterator __first, _ForwardIterator __last)

{

typedef typename iterator_traits<_forwarditerator>::value_type

_Value_type;

_Destroy_aux<__has_trivial_destructor>::

__destroy(__first, __last);

}

template

inline bool

operator==(const allocator<_t1>&, const allocator<_t2>&)

{ return true; }

template

inline bool

operator==(const allocator<_tp>&, const allocator<_tp>&)

{ return true; }

template

inline bool

operator!=(const allocator<_t1>&, const allocator<_t2>&)

{ return false; }

template

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;

extern template class allocator;

#endif

// Undefine.

#undef __glibcxx_base_allocator

// To implement Option 3 of DR 431.

template

struct __alloc_swap

{ static void _S_do_it(_Alloc&, _Alloc&) { } };

template

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

struct __alloc_neq

{

static bool

_S_do_it(const _Alloc&, const _Alloc&)

{ return false; }

};

template

struct __alloc_neq<_alloc false>

{

static bool

_S_do_it(const _Alloc& __one, const _Alloc& __two)

{ return __one != __two; }

};

template

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

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

struct iterator_traits

{

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

inline typename iterator_traits<_iter>::iterator_category

__iterator_category(const _Iter&)

{ return typename iterator_traits<_iter>::iterator_category(); }

template

struct __enable_if

{ };

struct __true_type { };

struct __false_type { };

template

struct __enable_if

{ typedef _Tp __type; };

// Compare for equality of types.

template

struct __are_same

{

enum { Test__value = 0 };

typedef __false_type __type;

};

template

struct __are_same<_tp _tp>

{

enum { Test__value = 1 };

typedef __true_type __type;

};

template

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

__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

inline bool

operator==(const __normal_iterator<_iteratorl _container>& __lhs,

const __normal_iterator<_iteratorr _container>& __rhs)

{ return __lhs.base() == __rhs.base(); }

template

inline bool

operator==(const __normal_iterator<_iterator _container>& __lhs,

const __normal_iterator<_iterator _container>& __rhs)

{ return __lhs.base() == __rhs.base(); }

template

inline bool

operator!=(const __normal_iterator<_iteratorl _container>& __lhs,

const __normal_iterator<_iteratorr _container>& __rhs)

{ return __lhs.base() != __rhs.base(); }

template

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

inline bool

operator& __lhs,

const __normal_iterator<_iteratorr _container>& __rhs)

{ return __lhs.base() < __rhs.base(); }

template

inline bool

operator& __lhs,

const __normal_iterator<_iterator _container>& __rhs)

{ return __lhs.base() < __rhs.base(); }

template

inline bool

operator>(const __normal_iterator<_iteratorl _container>& __lhs,

const __normal_iterator<_iteratorr _container>& __rhs)

{ return __lhs.base() > __rhs.base(); }

template

inline bool

operator>(const __normal_iterator<_iterator _container>& __lhs,

const __normal_iterator<_iterator _container>& __rhs)

{ return __lhs.base() > __rhs.base(); }

template

inline bool

operator<=(const __normal_iterator<_iteratorl _container>& __lhs,

const __normal_iterator<_iteratorr _container>& __rhs)

{ return __lhs.base() <= __rhs.base(); }

template

inline bool

operator<=(const __normal_iterator<_iterator _container>& __lhs,

const __normal_iterator<_iterator _container>& __rhs)

{ return __lhs.base() <= __rhs.base(); }

template

inline bool

operator>=(const __normal_iterator<_iteratorl _container>& __lhs,

const __normal_iterator<_iteratorr _container>& __rhs)

{ return __lhs.base() >= __rhs.base(); }

template

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

#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

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

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

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(&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 _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

class reverse_iterator

: public 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

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

inline bool

operator==(const reverse_iterator<_iterator>& __x,

const reverse_iterator<_iterator>& __y)

{ return __x.base() == __y.base(); }

template

inline bool

operator& __x,

const reverse_iterator<_iterator>& __y)

{ return __y.base() < __x.base(); }

template

inline bool

operator!=(const reverse_iterator<_iterator>& __x,

const reverse_iterator<_iterator>& __y)

{ return !(__x == __y); }

template

inline bool

operator>(const reverse_iterator<_iterator>& __x,

const reverse_iterator<_iterator>& __y)

{ return __y < __x; }

template

inline bool

operator<=(const reverse_iterator<_iterator>& __x,

const reverse_iterator<_iterator>& __y)

{ return !(__y < __x); }

template

inline bool

operator>=(const reverse_iterator<_iterator>& __x,

const reverse_iterator<_iterator>& __y)

{ return !(__x < __y); }

template

inline typename reverse_iterator<_iterator>::difference_type

operator-(const reverse_iterator<_iterator>& __x,

const reverse_iterator<_iterator>& __y)

{ return __y.base() - __x.base(); }

template

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

inline bool

operator==(const reverse_iterator<_iteratorl>& __x,

const reverse_iterator<_iteratorr>& __y)

{ return __x.base() == __y.base(); }

template

inline bool

operator& __x,

const reverse_iterator<_iteratorr>& __y)

{ return __y.base() < __x.base(); }

template

inline bool

operator!=(const reverse_iterator<_iteratorl>& __x,

const reverse_iterator<_iteratorr>& __y)

{ return !(__x == __y); }

template

inline bool

operator>(const reverse_iterator<_iteratorl>& __x,

const reverse_iterator<_iteratorr>& __y)

{ return __y < __x; }

template

inline bool

operator<=(const reverse_iterator<_iteratorl>& __x,

const reverse_iterator<_iteratorr>& __y)

{ return !(__y < __x); }

template

inline bool

operator>=(const reverse_iterator<_iteratorl>& __x,

const reverse_iterator<_iteratorr>& __y)

{ return !(__x < __y); }

template

#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

struct __is_integer

{

enum { Test__value = 0 };

typedef __false_type __type;

};

// Thir*** specializations (yes there are eleven standard integer

// types; 'long long' and 'unsigned long long' are supported as

// extensions)

template<>

struct __is_integer

{

enum { Test__value = 1 };

typedef __true_type __type;

};

template<>

struct __is_integer

{

enum { Test__value = 1 };

typedef __true_type __type;

};

template<>

struct __is_integer

{

enum { Test__value = 1 };

typedef __true_type __type;

};

template<>

struct __is_integer

{

enum { Test__value = 1 };

typedef __true_type __type;

};

# ifdef _GLIBCXX_USE_WCHAR_T

template<>

struct __is_integer

{

enum { Test__value = 1 };

typedef __true_type __type;

};

# endif

#ifdef __GXX_EXPERIMENTAL_CXX0X__

template<>

struct __is_integer

{

enum { Test__value = 1 };

typedef __true_type __type;

};

template<>

struct __is_integer

{

enum { Test__value = 1 };

typedef __true_type __type;

};

#endif

template<>

struct __is_integer

{

enum { Test__value = 1 };

typedef __true_type __type;

};

template<>

struct __is_integer

{

enum { Test__value = 1 };

typedef __true_type __type;

};

template<>

struct __is_integer

{

enum { Test__value = 1 };

typedef __true_type __type;

};

template<>

struct __is_integer