58 #define _STL_VECTOR_H 1
63 #ifdef __GXX_EXPERIMENTAL_CXX0X__
67 namespace std _GLIBCXX_VISIBILITY(default)
69 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
72 template<
typename _Tp,
typename _Alloc>
76 rebind<_Tp>::other _Tp_alloc_type;
81 :
public _Tp_alloc_type
85 pointer _M_end_of_storage;
88 : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0)
91 _Vector_impl(_Tp_alloc_type
const& __a)
92 : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
95 #ifdef __GXX_EXPERIMENTAL_CXX0X__
96 _Vector_impl(_Tp_alloc_type&& __a)
97 : _Tp_alloc_type(std::move(__a)),
98 _M_start(0), _M_finish(0), _M_end_of_storage(0)
102 void _M_swap_data(_Vector_impl& __x)
104 std::swap(_M_start, __x._M_start);
105 std::swap(_M_finish, __x._M_finish);
106 std::swap(_M_end_of_storage, __x._M_end_of_storage);
111 typedef _Alloc allocator_type;
114 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
115 {
return *
static_cast<_Tp_alloc_type*
>(&this->_M_impl); }
117 const _Tp_alloc_type&
118 _M_get_Tp_allocator()
const _GLIBCXX_NOEXCEPT
119 {
return *
static_cast<const _Tp_alloc_type*
>(&this->_M_impl); }
122 get_allocator()
const _GLIBCXX_NOEXCEPT
123 {
return allocator_type(_M_get_Tp_allocator()); }
133 { _M_create_storage(__n); }
137 { _M_create_storage(__n); }
139 #ifdef __GXX_EXPERIMENTAL_CXX0X__
141 : _M_impl(std::move(__a)) { }
144 : _M_impl(std::move(__x._M_get_Tp_allocator()))
145 { this->_M_impl._M_swap_data(__x._M_impl); }
150 if (__x.get_allocator() == __a)
151 this->_M_impl._M_swap_data(__x._M_impl);
154 size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
155 _M_create_storage(__n);
161 { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
162 - this->_M_impl._M_start); }
165 _Vector_impl _M_impl;
168 _M_allocate(
size_t __n)
169 {
return __n != 0 ? _M_impl.allocate(__n) : 0; }
172 _M_deallocate(pointer __p,
size_t __n)
175 _M_impl.deallocate(__p, __n);
180 _M_create_storage(
size_t __n)
182 this->_M_impl._M_start = this->_M_allocate(__n);
183 this->_M_impl._M_finish = this->_M_impl._M_start;
184 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
207 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
211 typedef typename _Alloc::value_type _Alloc_value_type;
212 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
213 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
216 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
220 typedef _Tp value_type;
221 typedef typename _Base::pointer pointer;
223 typedef typename _Alloc_traits::reference reference;
224 typedef typename _Alloc_traits::const_reference const_reference;
225 typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
226 typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
230 typedef size_t size_type;
231 typedef ptrdiff_t difference_type;
232 typedef _Alloc allocator_type;
235 using _Base::_M_allocate;
236 using _Base::_M_deallocate;
237 using _Base::_M_impl;
238 using _Base::_M_get_Tp_allocator;
257 #ifdef __GXX_EXPERIMENTAL_CXX0X__
268 { _M_default_initialize(__n); }
281 { _M_fill_initialize(__n, __value); }
292 vector(size_type __n,
const value_type& __value = value_type(),
293 const allocator_type& __a = allocator_type())
295 { _M_fill_initialize(__n, __value); }
310 { this->_M_impl._M_finish =
311 std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
312 this->_M_impl._M_start,
313 _M_get_Tp_allocator());
316 #ifdef __GXX_EXPERIMENTAL_CXX0X__
325 :
_Base(std::move(__x)) { }
330 { this->_M_impl._M_finish =
331 std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
332 this->_M_impl._M_start,
333 _M_get_Tp_allocator());
338 :
_Base(std::move(__rv), __m)
340 if (__rv.get_allocator() != __m)
342 this->_M_impl._M_finish =
343 std::__uninitialized_move_a(__rv.begin(), __rv.end(),
344 this->_M_impl._M_start,
345 _M_get_Tp_allocator());
365 _M_range_initialize(__l.begin(), __l.end(),
386 template<
typename _InputIterator>
387 vector(_InputIterator __first, _InputIterator __last,
392 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
393 _M_initialize_dispatch(__first, __last, _Integral());
403 {
std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
404 _M_get_Tp_allocator()); }
417 #ifdef __GXX_EXPERIMENTAL_CXX0X__
429 constexpr
bool __move_storage =
430 _Alloc_traits::_S_propagate_on_move_assign()
431 || _Alloc_traits::_S_always_equal();
432 _M_move_assign(std::move(__x),
451 this->
assign(__l.begin(), __l.end());
468 { _M_fill_assign(__n, __val); }
482 template<
typename _InputIterator>
484 assign(_InputIterator __first, _InputIterator __last)
487 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
488 _M_assign_dispatch(__first, __last, _Integral());
491 #ifdef __GXX_EXPERIMENTAL_CXX0X__
505 { this->
assign(__l.begin(), __l.end()); }
509 using _Base::get_allocator;
519 {
return iterator(this->_M_impl._M_start); }
528 {
return const_iterator(this->_M_impl._M_start); }
537 {
return iterator(this->_M_impl._M_finish); }
545 end() const _GLIBCXX_NOEXCEPT
546 {
return const_iterator(this->_M_impl._M_finish); }
562 const_reverse_iterator
580 const_reverse_iterator
584 #ifdef __GXX_EXPERIMENTAL_CXX0X__
592 {
return const_iterator(this->_M_impl._M_start); }
601 {
return const_iterator(this->_M_impl._M_finish); }
608 const_reverse_iterator
617 const_reverse_iterator
626 {
return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
633 #ifdef __GXX_EXPERIMENTAL_CXX0X__
646 if (__new_size >
size())
647 _M_default_append(__new_size -
size());
648 else if (__new_size <
size())
649 _M_erase_at_end(this->_M_impl._M_start + __new_size);
666 if (__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, value_type __x = value_type())
686 if (__new_size >
size())
688 else if (__new_size <
size())
689 _M_erase_at_end(this->_M_impl._M_start + __new_size);
693 #ifdef __GXX_EXPERIMENTAL_CXX0X__
697 { _M_shrink_to_fit(); }
706 {
return size_type(this->_M_impl._M_end_of_storage
707 - this->_M_impl._M_start); }
751 {
return *(this->_M_impl._M_start + __n); }
766 {
return *(this->_M_impl._M_start + __n); }
773 if (__n >= this->
size())
774 __throw_out_of_range(__N(
"vector::_M_range_check"));
808 at(size_type __n)
const
836 {
return *(
end() - 1); }
844 {
return *(
end() - 1); }
853 #ifdef __GXX_EXPERIMENTAL_CXX0X__
861 #ifdef __GXX_EXPERIMENTAL_CXX0X__
866 data() const _GLIBCXX_NOEXCEPT
883 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
885 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
887 ++this->_M_impl._M_finish;
890 #ifdef __GXX_EXPERIMENTAL_CXX0X__
891 _M_emplace_back_aux(__x);
893 _M_insert_aux(
end(), __x);
897 #ifdef __GXX_EXPERIMENTAL_CXX0X__
900 { emplace_back(std::move(__x)); }
902 template<
typename... _Args>
904 emplace_back(_Args&&... __args);
919 --this->_M_impl._M_finish;
920 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
923 #ifdef __GXX_EXPERIMENTAL_CXX0X__
936 template<
typename... _Args>
955 #ifdef __GXX_EXPERIMENTAL_CXX0X__
969 {
return emplace(__position, std::move(__x)); }
986 { this->
insert(__position, __l.begin(), __l.end()); }
1004 { _M_fill_insert(__position, __n, __x); }
1020 template<
typename _InputIterator>
1022 insert(iterator __position, _InputIterator __first,
1023 _InputIterator __last)
1026 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1027 _M_insert_dispatch(__position, __first, __last, _Integral());
1080 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1081 noexcept(_Alloc_traits::_S_nothrow_swap())
1084 this->_M_impl._M_swap_data(__x._M_impl);
1085 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1086 __x._M_get_Tp_allocator());
1097 { _M_erase_at_end(this->_M_impl._M_start); }
1104 template<
typename _ForwardIterator>
1107 _ForwardIterator __first, _ForwardIterator __last)
1109 pointer __result = this->_M_allocate(__n);
1112 std::__uninitialized_copy_a(__first, __last, __result,
1113 _M_get_Tp_allocator());
1118 _M_deallocate(__result, __n);
1119 __throw_exception_again;
1130 template<
typename _Integer>
1132 _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
1134 this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n));
1135 this->_M_impl._M_end_of_storage =
1136 this->_M_impl._M_start +
static_cast<size_type
>(__n);
1137 _M_fill_initialize(static_cast<size_type>(__n), __value);
1141 template<
typename _InputIterator>
1143 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1146 typedef typename std::iterator_traits<_InputIterator>::
1147 iterator_category _IterCategory;
1148 _M_range_initialize(__first, __last, _IterCategory());
1152 template<
typename _InputIterator>
1154 _M_range_initialize(_InputIterator __first,
1157 for (; __first != __last; ++__first)
1162 template<
typename _ForwardIterator>
1164 _M_range_initialize(_ForwardIterator __first,
1168 this->_M_impl._M_start = this->_M_allocate(__n);
1169 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1170 this->_M_impl._M_finish =
1171 std::__uninitialized_copy_a(__first, __last,
1172 this->_M_impl._M_start,
1173 _M_get_Tp_allocator());
1179 _M_fill_initialize(size_type __n,
const value_type& __value)
1181 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1182 _M_get_Tp_allocator());
1183 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
1186 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1189 _M_default_initialize(size_type __n)
1191 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1192 _M_get_Tp_allocator());
1193 this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
1204 template<
typename _Integer>
1206 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1207 { _M_fill_assign(__n, __val); }
1210 template<
typename _InputIterator>
1212 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1215 typedef typename std::iterator_traits<_InputIterator>::
1216 iterator_category _IterCategory;
1217 _M_assign_aux(__first, __last, _IterCategory());
1221 template<
typename _InputIterator>
1223 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1227 template<
typename _ForwardIterator>
1229 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1235 _M_fill_assign(size_type __n,
const value_type& __val);
1244 template<
typename _Integer>
1246 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1248 { _M_fill_insert(__pos, __n, __val); }
1251 template<
typename _InputIterator>
1253 _M_insert_dispatch(iterator __pos, _InputIterator __first,
1254 _InputIterator __last, __false_type)
1256 typedef typename std::iterator_traits<_InputIterator>::
1257 iterator_category _IterCategory;
1258 _M_range_insert(__pos, __first, __last, _IterCategory());
1262 template<
typename _InputIterator>
1264 _M_range_insert(iterator __pos, _InputIterator __first,
1268 template<
typename _ForwardIterator>
1270 _M_range_insert(iterator __pos, _ForwardIterator __first,
1276 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
1278 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1281 _M_default_append(size_type __n);
1288 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1290 _M_insert_aux(iterator __position,
const value_type& __x);
1292 template<
typename... _Args>
1294 _M_insert_aux(iterator __position, _Args&&... __args);
1296 template<
typename... _Args>
1298 _M_emplace_back_aux(_Args&&... __args);
1303 _M_check_len(size_type __n,
const char* __s)
const
1306 __throw_length_error(__N(__s));
1317 _M_erase_at_end(pointer __pos)
1319 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
1320 this->_M_impl._M_finish = __pos;
1323 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1331 const vector __tmp(std::move(*
this));
1332 this->_M_impl._M_swap_data(__x._M_impl);
1333 if (_Alloc_traits::_S_propagate_on_move_assign())
1334 std::__alloc_on_move(_M_get_Tp_allocator(),
1335 __x._M_get_Tp_allocator());
1343 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
1349 this->
assign(std::__make_move_if_noexcept_iterator(__x.
begin()),
1350 std::__make_move_if_noexcept_iterator(__x.
end()));
1368 template<
typename _Tp,
typename _Alloc>
1385 template<
typename _Tp,
typename _Alloc>
1389 __y.begin(), __y.end()); }
1392 template<
typename _Tp,
typename _Alloc>
1395 {
return !(__x == __y); }
1398 template<
typename _Tp,
typename _Alloc>
1401 {
return __y < __x; }
1404 template<
typename _Tp,
typename _Alloc>
1407 {
return !(__y < __x); }
1410 template<
typename _Tp,
typename _Alloc>
1413 {
return !(__x < __y); }
1416 template<
typename _Tp,
typename _Alloc>
1421 _GLIBCXX_END_NAMESPACE_CONTAINER