57 #define _STL_VECTOR_H 1
62 #if __cplusplus >= 201103L
66 namespace std _GLIBCXX_VISIBILITY(default)
68 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
71 template<
typename _Tp,
typename _Alloc>
75 rebind<_Tp>::other _Tp_alloc_type;
76 typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
80 :
public _Tp_alloc_type
84 pointer _M_end_of_storage;
87 : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0)
90 _Vector_impl(_Tp_alloc_type
const& __a)
91 : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
94 #if __cplusplus >= 201103L
95 _Vector_impl(_Tp_alloc_type&& __a)
96 : _Tp_alloc_type(std::move(__a)),
97 _M_start(0), _M_finish(0), _M_end_of_storage(0)
101 void _M_swap_data(_Vector_impl& __x)
103 std::swap(_M_start, __x._M_start);
104 std::swap(_M_finish, __x._M_finish);
105 std::swap(_M_end_of_storage, __x._M_end_of_storage);
110 typedef _Alloc allocator_type;
113 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
114 {
return *
static_cast<_Tp_alloc_type*
>(&this->_M_impl); }
116 const _Tp_alloc_type&
117 _M_get_Tp_allocator()
const _GLIBCXX_NOEXCEPT
118 {
return *
static_cast<const _Tp_alloc_type*
>(&this->_M_impl); }
121 get_allocator()
const _GLIBCXX_NOEXCEPT
122 {
return allocator_type(_M_get_Tp_allocator()); }
132 { _M_create_storage(__n); }
136 { _M_create_storage(__n); }
138 #if __cplusplus >= 201103L
140 : _M_impl(std::move(__a)) { }
143 : _M_impl(std::move(__x._M_get_Tp_allocator()))
144 { this->_M_impl._M_swap_data(__x._M_impl); }
149 if (__x.get_allocator() == __a)
150 this->_M_impl._M_swap_data(__x._M_impl);
153 size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
154 _M_create_storage(__n);
160 { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
161 - this->_M_impl._M_start); }
164 _Vector_impl _M_impl;
167 _M_allocate(
size_t __n)
168 {
return __n != 0 ? _M_impl.allocate(__n) : 0; }
171 _M_deallocate(pointer __p,
size_t __n)
174 _M_impl.deallocate(__p, __n);
179 _M_create_storage(
size_t __n)
181 this->_M_impl._M_start = this->_M_allocate(__n);
182 this->_M_impl._M_finish = this->_M_impl._M_start;
183 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
209 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
213 typedef typename _Alloc::value_type _Alloc_value_type;
214 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
215 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
218 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
222 typedef _Tp value_type;
223 typedef typename _Base::pointer pointer;
224 typedef typename _Alloc_traits::const_pointer const_pointer;
225 typedef typename _Alloc_traits::reference reference;
226 typedef typename _Alloc_traits::const_reference const_reference;
227 typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
228 typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
232 typedef size_t size_type;
233 typedef ptrdiff_t difference_type;
234 typedef _Alloc allocator_type;
237 using _Base::_M_allocate;
238 using _Base::_M_deallocate;
239 using _Base::_M_impl;
240 using _Base::_M_get_Tp_allocator;
259 #if __cplusplus >= 201103L
271 { _M_default_initialize(__n); }
281 vector(size_type __n,
const value_type& __value,
284 { _M_fill_initialize(__n, __value); }
295 vector(size_type __n,
const value_type& __value = value_type(),
296 const allocator_type& __a = allocator_type())
298 { _M_fill_initialize(__n, __value); }
313 { this->_M_impl._M_finish =
314 std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
315 this->_M_impl._M_start,
316 _M_get_Tp_allocator());
319 #if __cplusplus >= 201103L
328 :
_Base(std::move(__x)) { }
333 { this->_M_impl._M_finish =
334 std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
335 this->_M_impl._M_start,
336 _M_get_Tp_allocator());
341 :
_Base(std::move(__rv), __m)
343 if (__rv.get_allocator() != __m)
345 this->_M_impl._M_finish =
346 std::__uninitialized_move_a(__rv.begin(), __rv.end(),
347 this->_M_impl._M_start,
348 _M_get_Tp_allocator());
368 _M_range_initialize(__l.begin(), __l.end(),
389 #if __cplusplus >= 201103L
390 template<
typename _InputIterator,
391 typename = std::_RequireInputIter<_InputIterator>>
392 vector(_InputIterator __first, _InputIterator __last,
395 { _M_initialize_dispatch(__first, __last, __false_type()); }
397 template<
typename _InputIterator>
398 vector(_InputIterator __first, _InputIterator __last,
399 const allocator_type& __a = allocator_type())
403 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
404 _M_initialize_dispatch(__first, __last, _Integral());
415 {
std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
416 _M_get_Tp_allocator()); }
429 #if __cplusplus >= 201103L
441 constexpr
bool __move_storage =
442 _Alloc_traits::_S_propagate_on_move_assign()
443 || _Alloc_traits::_S_always_equal();
444 _M_move_assign(std::move(__x),
463 this->
assign(__l.begin(), __l.end());
479 assign(size_type __n,
const value_type& __val)
480 { _M_fill_assign(__n, __val); }
494 #if __cplusplus >= 201103L
495 template<
typename _InputIterator,
496 typename = std::_RequireInputIter<_InputIterator>>
498 assign(_InputIterator __first, _InputIterator __last)
499 { _M_assign_dispatch(__first, __last, __false_type()); }
501 template<
typename _InputIterator>
503 assign(_InputIterator __first, _InputIterator __last)
506 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
507 _M_assign_dispatch(__first, __last, _Integral());
511 #if __cplusplus >= 201103L
525 { this->
assign(__l.begin(), __l.end()); }
529 using _Base::get_allocator;
539 {
return iterator(this->_M_impl._M_start); }
548 {
return const_iterator(this->_M_impl._M_start); }
557 {
return iterator(this->_M_impl._M_finish); }
565 end() const _GLIBCXX_NOEXCEPT
566 {
return const_iterator(this->_M_impl._M_finish); }
582 const_reverse_iterator
600 const_reverse_iterator
604 #if __cplusplus >= 201103L
612 {
return const_iterator(this->_M_impl._M_start); }
621 {
return const_iterator(this->_M_impl._M_finish); }
628 const_reverse_iterator
637 const_reverse_iterator
646 {
return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
653 #if __cplusplus >= 201103L
666 if (__new_size >
size())
667 _M_default_append(__new_size -
size());
668 else if (__new_size <
size())
669 _M_erase_at_end(this->_M_impl._M_start + __new_size);
684 resize(size_type __new_size,
const value_type& __x)
686 if (__new_size >
size())
688 else if (__new_size <
size())
689 _M_erase_at_end(this->_M_impl._M_start + __new_size);
704 resize(size_type __new_size, value_type __x = value_type())
706 if (__new_size >
size())
708 else if (__new_size <
size())
709 _M_erase_at_end(this->_M_impl._M_start + __new_size);
713 #if __cplusplus >= 201103L
717 { _M_shrink_to_fit(); }
726 {
return size_type(this->_M_impl._M_end_of_storage
727 - this->_M_impl._M_start); }
771 {
return *(this->_M_impl._M_start + __n); }
786 {
return *(this->_M_impl._M_start + __n); }
793 if (__n >= this->
size())
794 __throw_out_of_range(__N(
"vector::_M_range_check"));
828 at(size_type __n)
const
856 {
return *(
end() - 1); }
864 {
return *(
end() - 1); }
873 #if __cplusplus >= 201103L
881 #if __cplusplus >= 201103L
886 data() const _GLIBCXX_NOEXCEPT
903 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
905 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
907 ++this->_M_impl._M_finish;
910 #if __cplusplus >= 201103L
911 _M_emplace_back_aux(__x);
913 _M_insert_aux(
end(), __x);
917 #if __cplusplus >= 201103L
920 { emplace_back(std::move(__x)); }
922 template<
typename... _Args>
924 emplace_back(_Args&&... __args);
939 --this->_M_impl._M_finish;
940 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
943 #if __cplusplus >= 201103L
956 template<
typename... _Args>
975 #if __cplusplus >= 201103L
988 insert(iterator __position, value_type&& __x)
989 {
return emplace(__position, std::move(__x)); }
1006 { this->
insert(__position, __l.begin(), __l.end()); }
1023 insert(iterator __position, size_type __n,
const value_type& __x)
1024 { _M_fill_insert(__position, __n, __x); }
1040 #if __cplusplus >= 201103L
1041 template<
typename _InputIterator,
1042 typename = std::_RequireInputIter<_InputIterator>>
1044 insert(iterator __position, _InputIterator __first,
1045 _InputIterator __last)
1046 { _M_insert_dispatch(__position, __first, __last, __false_type()); }
1048 template<
typename _InputIterator>
1051 _InputIterator __last)
1054 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1055 _M_insert_dispatch(__position, __first, __last, _Integral());
1075 erase(iterator __position);
1096 erase(iterator __first, iterator __last);
1109 #if __cplusplus >= 201103L
1110 noexcept(_Alloc_traits::_S_nothrow_swap())
1113 this->_M_impl._M_swap_data(__x._M_impl);
1114 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1115 __x._M_get_Tp_allocator());
1126 { _M_erase_at_end(this->_M_impl._M_start); }
1133 template<
typename _ForwardIterator>
1136 _ForwardIterator __first, _ForwardIterator __last)
1138 pointer __result = this->_M_allocate(__n);
1141 std::__uninitialized_copy_a(__first, __last, __result,
1142 _M_get_Tp_allocator());
1147 _M_deallocate(__result, __n);
1148 __throw_exception_again;
1159 template<
typename _Integer>
1161 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
1163 this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n));
1164 this->_M_impl._M_end_of_storage =
1165 this->_M_impl._M_start +
static_cast<size_type
>(__n);
1166 _M_fill_initialize(static_cast<size_type>(__n), __value);
1170 template<
typename _InputIterator>
1172 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1175 typedef typename std::iterator_traits<_InputIterator>::
1176 iterator_category _IterCategory;
1177 _M_range_initialize(__first, __last, _IterCategory());
1181 template<
typename _InputIterator>
1183 _M_range_initialize(_InputIterator __first,
1186 for (; __first != __last; ++__first)
1187 #
if __cplusplus >= 201103L
1188 emplace_back(*__first);
1195 template<
typename _ForwardIterator>
1197 _M_range_initialize(_ForwardIterator __first,
1201 this->_M_impl._M_start = this->_M_allocate(__n);
1202 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1203 this->_M_impl._M_finish =
1204 std::__uninitialized_copy_a(__first, __last,
1205 this->_M_impl._M_start,
1206 _M_get_Tp_allocator());
1212 _M_fill_initialize(size_type __n,
const value_type& __value)
1214 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1215 _M_get_Tp_allocator());
1216 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
1219 #if __cplusplus >= 201103L
1222 _M_default_initialize(size_type __n)
1224 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1225 _M_get_Tp_allocator());
1226 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
1237 template<
typename _Integer>
1239 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1240 { _M_fill_assign(__n, __val); }
1243 template<
typename _InputIterator>
1245 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1248 typedef typename std::iterator_traits<_InputIterator>::
1249 iterator_category _IterCategory;
1250 _M_assign_aux(__first, __last, _IterCategory());
1254 template<
typename _InputIterator>
1256 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1260 template<
typename _ForwardIterator>
1262 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1268 _M_fill_assign(size_type __n,
const value_type& __val);
1277 template<
typename _Integer>
1279 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1281 { _M_fill_insert(__pos, __n, __val); }
1284 template<
typename _InputIterator>
1286 _M_insert_dispatch(iterator __pos, _InputIterator __first,
1287 _InputIterator __last, __false_type)
1289 typedef typename std::iterator_traits<_InputIterator>::
1290 iterator_category _IterCategory;
1291 _M_range_insert(__pos, __first, __last, _IterCategory());
1295 template<
typename _InputIterator>
1297 _M_range_insert(iterator __pos, _InputIterator __first,
1301 template<
typename _ForwardIterator>
1303 _M_range_insert(iterator __pos, _ForwardIterator __first,
1309 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
1311 #if __cplusplus >= 201103L
1314 _M_default_append(size_type __n);
1321 #if __cplusplus < 201103L
1323 _M_insert_aux(iterator __position,
const value_type& __x);
1325 template<
typename... _Args>
1327 _M_insert_aux(iterator __position, _Args&&... __args);
1329 template<
typename... _Args>
1331 _M_emplace_back_aux(_Args&&... __args);
1336 _M_check_len(size_type __n,
const char* __s)
const
1339 __throw_length_error(__N(__s));
1350 _M_erase_at_end(pointer __pos)
1352 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
1353 this->_M_impl._M_finish = __pos;
1356 #if __cplusplus >= 201103L
1364 const vector __tmp(std::move(*
this));
1365 this->_M_impl._M_swap_data(__x._M_impl);
1366 if (_Alloc_traits::_S_propagate_on_move_assign())
1367 std::__alloc_on_move(_M_get_Tp_allocator(),
1368 __x._M_get_Tp_allocator());
1376 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
1382 this->
assign(std::__make_move_if_noexcept_iterator(__x.
begin()),
1383 std::__make_move_if_noexcept_iterator(__x.
end()));
1401 template<
typename _Tp,
typename _Alloc>
1418 template<
typename _Tp,
typename _Alloc>
1422 __y.begin(), __y.end()); }
1425 template<
typename _Tp,
typename _Alloc>
1428 {
return !(__x == __y); }
1431 template<
typename _Tp,
typename _Alloc>
1434 {
return __y < __x; }
1437 template<
typename _Tp,
typename _Alloc>
1440 {
return !(__y < __x); }
1443 template<
typename _Tp,
typename _Alloc>
1446 {
return !(__x < __y); }
1449 template<
typename _Tp,
typename _Alloc>
1454 _GLIBCXX_END_NAMESPACE_CONTAINER