58 #define _STL_VECTOR_H 1
65 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
68 template<typename _Tp, typename _Alloc>
71 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
74 :
public _Tp_alloc_type
76 typename _Tp_alloc_type::pointer _M_start;
77 typename _Tp_alloc_type::pointer _M_finish;
78 typename _Tp_alloc_type::pointer _M_end_of_storage;
81 : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0)
84 _Vector_impl(_Tp_alloc_type
const& __a)
85 : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
90 typedef _Alloc allocator_type;
94 {
return *
static_cast<_Tp_alloc_type*
>(&this->_M_impl); }
97 _M_get_Tp_allocator()
const
98 {
return *
static_cast<const _Tp_alloc_type*
>(&this->_M_impl); }
101 get_allocator()
const
102 {
return allocator_type(_M_get_Tp_allocator()); }
107 _Vector_base(
const allocator_type& __a)
110 _Vector_base(
size_t __n,
const allocator_type& __a)
113 this->_M_impl._M_start = this->_M_allocate(__n);
114 this->_M_impl._M_finish = this->_M_impl._M_start;
115 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
118 #ifdef __GXX_EXPERIMENTAL_CXX0X__
119 _Vector_base(_Vector_base&& __x)
120 : _M_impl(__x._M_get_Tp_allocator())
122 this->_M_impl._M_start = __x._M_impl._M_start;
123 this->_M_impl._M_finish = __x._M_impl._M_finish;
124 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
125 __x._M_impl._M_start = 0;
126 __x._M_impl._M_finish = 0;
127 __x._M_impl._M_end_of_storage = 0;
132 { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
133 - this->_M_impl._M_start); }
136 _Vector_impl _M_impl;
138 typename _Tp_alloc_type::pointer
139 _M_allocate(
size_t __n)
140 {
return __n != 0 ? _M_impl.allocate(__n) : 0; }
143 _M_deallocate(
typename _Tp_alloc_type::pointer __p,
size_t __n)
146 _M_impl.deallocate(__p, __n);
169 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
173 typedef typename _Alloc::value_type _Alloc_value_type;
174 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
175 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
178 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
181 typedef _Tp value_type;
182 typedef typename _Tp_alloc_type::pointer pointer;
183 typedef typename _Tp_alloc_type::const_pointer const_pointer;
184 typedef typename _Tp_alloc_type::reference reference;
185 typedef typename _Tp_alloc_type::const_reference const_reference;
186 typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
187 typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
191 typedef size_t size_type;
192 typedef ptrdiff_t difference_type;
193 typedef _Alloc allocator_type;
196 using _Base::_M_allocate;
197 using _Base::_M_deallocate;
198 using _Base::_M_impl;
199 using _Base::_M_get_Tp_allocator;
228 const allocator_type& __a = allocator_type())
230 { _M_fill_initialize(__n, __value); }
242 :
_Base(__x.size(), __x._M_get_Tp_allocator())
243 { this->_M_impl._M_finish =
244 std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
245 this->_M_impl._M_start,
246 _M_get_Tp_allocator());
249 #ifdef __GXX_EXPERIMENTAL_CXX0X__
272 const allocator_type& __a = allocator_type())
275 _M_range_initialize(__l.begin(), __l.end(),
296 template<
typename _InputIterator>
297 vector(_InputIterator __first, _InputIterator __last,
298 const allocator_type& __a = allocator_type())
302 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
303 _M_initialize_dispatch(__first, __last, _Integral());
313 {
std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
314 _M_get_Tp_allocator()); }
325 operator=(
const vector& __x);
327 #ifdef __GXX_EXPERIMENTAL_CXX0X__
358 this->assign(__l.begin(), __l.end());
375 { _M_fill_assign(__n, __val); }
389 template<
typename _InputIterator>
391 assign(_InputIterator __first, _InputIterator __last)
394 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
395 _M_assign_dispatch(__first, __last, _Integral());
398 #ifdef __GXX_EXPERIMENTAL_CXX0X__
412 { this->
assign(__l.begin(), __l.end()); }
416 using _Base::get_allocator;
426 {
return iterator(this->_M_impl._M_start); }
435 {
return const_iterator(this->_M_impl._M_start); }
444 {
return iterator(this->_M_impl._M_finish); }
453 {
return const_iterator(this->_M_impl._M_finish); }
469 const_reverse_iterator
487 const_reverse_iterator
491 #ifdef __GXX_EXPERIMENTAL_CXX0X__
499 {
return const_iterator(this->_M_impl._M_start); }
508 {
return const_iterator(this->_M_impl._M_finish); }
515 const_reverse_iterator
524 const_reverse_iterator
533 {
return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
538 {
return _M_get_Tp_allocator().max_size(); }
554 if (__new_size < size())
555 _M_erase_at_end(this->_M_impl._M_start + __new_size);
557 insert(end(), __new_size - size(), __x);
566 {
return size_type(this->_M_impl._M_end_of_storage
567 - this->_M_impl._M_start); }
575 {
return begin() == end(); }
595 reserve(size_type __n);
610 operator[](size_type __n)
611 {
return *(this->_M_impl._M_start + __n); }
625 operator[](size_type __n)
const
626 {
return *(this->_M_impl._M_start + __n); }
631 _M_range_check(size_type __n)
const
633 if (__n >= this->size())
634 __throw_out_of_range(__N(
"vector::_M_range_check"));
668 at(size_type __n)
const
696 {
return *(end() - 1); }
704 {
return *(end() - 1); }
715 {
return pointer(this->_M_impl._M_start); }
719 {
return const_pointer(this->_M_impl._M_start); }
735 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
737 this->_M_impl.construct(this->_M_impl._M_finish, __x);
738 ++this->_M_impl._M_finish;
741 _M_insert_aux(end(), __x);
744 #ifdef __GXX_EXPERIMENTAL_CXX0X__
746 push_back(value_type&& __x)
747 { emplace_back(std::move(__x)); }
749 template<
typename... _Args>
751 emplace_back(_Args&&... __args);
766 --this->_M_impl._M_finish;
767 this->_M_impl.destroy(this->_M_impl._M_finish);
770 #ifdef __GXX_EXPERIMENTAL_CXX0X__
783 template<
typename... _Args>
785 emplace(
iterator __position, _Args&&... __args);
800 insert(
iterator __position,
const value_type& __x);
802 #ifdef __GXX_EXPERIMENTAL_CXX0X__
816 {
return emplace(__position,
std::move(__x)); }
833 { this->
insert(__position, __l.begin(), __l.end()); }
850 insert(iterator __position, size_type __n,
const value_type& __x)
851 { _M_fill_insert(__position, __n, __x); }
867 template<
typename _InputIterator>
869 insert(iterator __position, _InputIterator __first,
870 _InputIterator __last)
873 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
874 _M_insert_dispatch(__position, __first, __last, _Integral());
926 #ifdef __GXX_EXPERIMENTAL_CXX0X__
932 std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
933 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
934 std::swap(this->_M_impl._M_end_of_storage,
935 __x._M_impl._M_end_of_storage);
939 std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(),
940 __x._M_get_Tp_allocator());
951 { _M_erase_at_end(this->_M_impl._M_start); }
958 template<
typename _ForwardIterator>
960 _M_allocate_and_copy(size_type __n,
961 _ForwardIterator __first, _ForwardIterator __last)
963 pointer __result = this->_M_allocate(__n);
966 std::__uninitialized_copy_a(__first, __last, __result,
967 _M_get_Tp_allocator());
972 _M_deallocate(__result, __n);
973 __throw_exception_again;
984 template<
typename _Integer>
986 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
988 this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n));
989 this->_M_impl._M_end_of_storage =
990 this->_M_impl._M_start +
static_cast<size_type
>(__n);
991 _M_fill_initialize(static_cast<size_type>(__n), __value);
995 template<
typename _InputIterator>
997 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1001 iterator_category _IterCategory;
1002 _M_range_initialize(__first, __last, _IterCategory());
1006 template<
typename _InputIterator>
1008 _M_range_initialize(_InputIterator __first,
1011 for (; __first != __last; ++__first)
1012 push_back(*__first);
1016 template<
typename _ForwardIterator>
1018 _M_range_initialize(_ForwardIterator __first,
1022 this->_M_impl._M_start = this->_M_allocate(__n);
1023 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1024 this->_M_impl._M_finish =
1025 std::__uninitialized_copy_a(__first, __last,
1026 this->_M_impl._M_start,
1027 _M_get_Tp_allocator());
1033 _M_fill_initialize(size_type __n,
const value_type& __value)
1035 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1036 _M_get_Tp_allocator());
1037 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
1048 template<
typename _Integer>
1050 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1051 { _M_fill_assign(__n, __val); }
1054 template<
typename _InputIterator>
1056 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1060 iterator_category _IterCategory;
1061 _M_assign_aux(__first, __last, _IterCategory());
1065 template<
typename _InputIterator>
1067 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1071 template<
typename _ForwardIterator>
1073 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1079 _M_fill_assign(size_type __n,
const value_type& __val);
1088 template<
typename _Integer>
1090 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1092 { _M_fill_insert(__pos, __n, __val); }
1095 template<
typename _InputIterator>
1097 _M_insert_dispatch(iterator __pos, _InputIterator __first,
1098 _InputIterator __last, __false_type)
1101 iterator_category _IterCategory;
1102 _M_range_insert(__pos, __first, __last, _IterCategory());
1106 template<
typename _InputIterator>
1108 _M_range_insert(iterator __pos, _InputIterator __first,
1112 template<
typename _ForwardIterator>
1114 _M_range_insert(iterator __pos, _ForwardIterator __first,
1120 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
1123 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1125 _M_insert_aux(iterator __position,
const value_type& __x);
1127 template<
typename... _Args>
1129 _M_insert_aux(iterator __position, _Args&&... __args);
1134 _M_check_len(size_type __n,
const char* __s)
const
1136 if (max_size() - size() < __n)
1137 __throw_length_error(__N(__s));
1139 const size_type __len = size() +
std::max(size(), __n);
1140 return (__len < size() || __len > max_size()) ? max_size() : __len;
1148 _M_erase_at_end(pointer __pos)
1150 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
1151 this->_M_impl._M_finish = __pos;
1166 template<
typename _Tp,
typename _Alloc>
1183 template<
typename _Tp,
typename _Alloc>
1187 __y.begin(), __y.end()); }
1190 template<
typename _Tp,
typename _Alloc>
1193 {
return !(__x == __y); }
1196 template<
typename _Tp,
typename _Alloc>
1199 {
return __y < __x; }
1202 template<
typename _Tp,
typename _Alloc>
1205 {
return !(__y < __x); }
1208 template<
typename _Tp,
typename _Alloc>
1211 {
return !(__x < __y); }
1214 template<
typename _Tp,
typename _Alloc>
1219 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1220 template<
typename _Tp,
typename _Alloc>
1222 swap(vector<_Tp, _Alloc>&& __x, vector<_Tp, _Alloc>& __y)
1225 template<
typename _Tp,
typename _Alloc>
1227 swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>&& __y)
1231 _GLIBCXX_END_NESTED_NAMESPACE