57#define _STL_VECTOR_H 1
62#if __cplusplus >= 201103L
66namespace 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(), _M_finish(), _M_end_of_storage()
91 : _Tp_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage()
94#if __cplusplus >= 201103L
95 _Vector_impl(_Tp_alloc_type&& __a)
noexcept
96 : _Tp_alloc_type(std::move(__a)),
97 _M_start(), _M_finish(), _M_end_of_storage()
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;
114 {
return *
static_cast<_Tp_alloc_type*
>(&this->_M_impl); }
116 const _Tp_alloc_type&
118 {
return *
static_cast<const _Tp_alloc_type*
>(&this->_M_impl); }
122 {
return allocator_type(_M_get_Tp_allocator()); }
127 _Vector_base(
const allocator_type& __a) _GLIBCXX_NOEXCEPT
130 _Vector_base(
size_t __n)
132 { _M_create_storage(__n); }
134 _Vector_base(
size_t __n,
const allocator_type& __a)
136 { _M_create_storage(__n); }
138#if __cplusplus >= 201103L
139 _Vector_base(_Tp_alloc_type&& __a) noexcept
140 : _M_impl(std::move(__a)) { }
142 _Vector_base(_Vector_base&& __x) noexcept
143 : _M_impl(std::move(__x._M_get_Tp_allocator()))
144 { this->_M_impl._M_swap_data(__x._M_impl); }
146 _Vector_base(_Vector_base&& __x,
const allocator_type& __a)
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);
159 ~_Vector_base() _GLIBCXX_NOEXCEPT
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)
170 return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
174 _M_deallocate(pointer __p,
size_t __n)
178 _Tr::deallocate(_M_impl, __p, __n);
183 _M_create_storage(
size_t __n)
185 this->_M_impl._M_start = this->_M_allocate(__n);
186 this->_M_impl._M_finish = this->_M_impl._M_start;
187 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
213 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
217 typedef typename _Alloc::value_type _Alloc_value_type;
218#if __cplusplus < 201103L
219 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
221 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
224 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
228 typedef _Tp value_type;
229 typedef typename _Base::pointer pointer;
230 typedef typename _Alloc_traits::const_pointer const_pointer;
231 typedef typename _Alloc_traits::reference reference;
232 typedef typename _Alloc_traits::const_reference const_reference;
233 typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
234 typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
238 typedef size_t size_type;
240 typedef _Alloc allocator_type;
243 using _Base::_M_allocate;
244 using _Base::_M_deallocate;
245 using _Base::_M_impl;
246 using _Base::_M_get_Tp_allocator;
256#if __cplusplus >= 201103L
269#if __cplusplus >= 201103L
279 vector(size_type __n,
const allocator_type& __a = allocator_type())
281 { _M_default_initialize(__n); }
291 vector(size_type __n,
const value_type& __value,
292 const allocator_type& __a = allocator_type())
294 { _M_fill_initialize(__n, __value); }
305 vector(size_type __n,
const value_type& __value = value_type(),
306 const allocator_type& __a = allocator_type())
308 { _M_fill_initialize(__n, __value); }
323 { this->_M_impl._M_finish =
324 std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
325 this->_M_impl._M_start,
326 _M_get_Tp_allocator());
329#if __cplusplus >= 201103L
338 :
_Base(std::move(__x)) { }
343 { this->_M_impl._M_finish =
344 std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
345 this->_M_impl._M_start,
346 _M_get_Tp_allocator());
351 noexcept(_Alloc_traits::_S_always_equal())
354 if (
__rv.get_allocator() != __m)
356 this->_M_impl._M_finish =
357 std::__uninitialized_move_a(
__rv.begin(),
__rv.end(),
358 this->_M_impl._M_start,
359 _M_get_Tp_allocator());
376 const allocator_type& __a = allocator_type())
379 _M_range_initialize(
__l.begin(),
__l.end(),
400#if __cplusplus >= 201103L
404 const allocator_type& __a = allocator_type())
406 { _M_initialize_dispatch(__first, __last, __false_type()); }
408 template<
typename _InputIterator>
410 const allocator_type& __a = allocator_type())
414 typedef typename std::__is_integer<_InputIterator>::__type
_Integral;
415 _M_initialize_dispatch(__first, __last,
_Integral());
427 _M_get_Tp_allocator()); }
440#if __cplusplus >= 201103L
453 _Alloc_traits::_S_propagate_on_move_assign()
454 || _Alloc_traits::_S_always_equal();
489 assign(size_type __n,
const value_type& __val)
490 { _M_fill_assign(__n, __val); }
504#if __cplusplus >= 201103L
509 { _M_assign_dispatch(__first, __last, __false_type()); }
511 template<
typename _InputIterator>
516 typedef typename std::__is_integer<_InputIterator>::__type
_Integral;
517 _M_assign_dispatch(__first, __last,
_Integral());
521#if __cplusplus >= 201103L
535 { this->
assign(__l.begin(),
__l.end()); }
539 using _Base::get_allocator;
549 {
return iterator(this->_M_impl._M_start); }
558 {
return const_iterator(this->_M_impl._M_start); }
567 {
return iterator(this->_M_impl._M_finish); }
576 {
return const_iterator(this->_M_impl._M_finish); }
592 const_reverse_iterator
610 const_reverse_iterator
614#if __cplusplus >= 201103L
622 {
return const_iterator(this->_M_impl._M_start); }
631 {
return const_iterator(this->_M_impl._M_finish); }
638 const_reverse_iterator
647 const_reverse_iterator
656 {
return size_type(this->_M_impl._M_finish -
this->_M_impl._M_start); }
663#if __cplusplus >= 201103L
679 _M_erase_at_end(this->_M_impl._M_start +
__new_size);
699 _M_erase_at_end(this->_M_impl._M_start +
__new_size);
719 _M_erase_at_end(this->_M_impl._M_start +
__new_size);
723#if __cplusplus >= 201103L
727 { _M_shrink_to_fit(); }
736 {
return size_type(this->_M_impl._M_end_of_storage
737 -
this->_M_impl._M_start); }
781 {
return *(this->_M_impl._M_start + __n); }
796 {
return *(this->_M_impl._M_start + __n); }
803 if (__n >= this->
size())
804 __throw_out_of_range_fmt(__N(
"vector::_M_range_check: __n "
805 "(which is %zu) >= this->size() "
841 at(size_type __n)
const
869 {
return *(
end() - 1); }
877 {
return *(
end() - 1); }
886#if __cplusplus >= 201103L
892 {
return _M_data_ptr(this->_M_impl._M_start); }
894#if __cplusplus >= 201103L
900 {
return _M_data_ptr(this->_M_impl._M_start); }
916 if (this->_M_impl._M_finish !=
this->_M_impl._M_end_of_storage)
918 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
920 ++this->_M_impl._M_finish;
923#if __cplusplus >= 201103L
924 _M_emplace_back_aux(__x);
926 _M_insert_aux(
end(), __x);
930#if __cplusplus >= 201103L
933 { emplace_back(std::move(__x)); }
935 template<
typename... _Args>
937 emplace_back(_Args&&... __args);
952 --this->_M_impl._M_finish;
953 _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
956#if __cplusplus >= 201103L
969 template<
typename...
_Args>
1002#if __cplusplus >= 201103L
1033 {
return this->
insert(__position,
__l.begin(),
__l.end()); }
1036#if __cplusplus >= 201103L
1055 _M_fill_insert(
begin() + __offset, __n, __x);
1056 return begin() + __offset;
1077#if __cplusplus >= 201103L
1093 template<
typename _InputIterator,
1100 _M_insert_dispatch(
begin() + __offset,
1101 __first, __last, __false_type());
1102 return begin() + __offset;
1119 template<
typename _InputIterator>
1125 typedef typename std::__is_integer<_InputIterator>::__type
_Integral;
1146#if __cplusplus >= 201103L
1173#if __cplusplus >= 201103L
1174 erase(const_iterator __first, const_iterator __last)
1182 {
return _M_erase(__first, __last); }
1197 this->_M_impl._M_swap_data(__x._M_impl);
1198 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1199 __x._M_get_Tp_allocator());
1210 { _M_erase_at_end(this->_M_impl._M_start); }
1217 template<
typename _ForwardIterator>
1222 pointer
__result = this->_M_allocate(__n);
1225 std::__uninitialized_copy_a(__first, __last,
__result,
1226 _M_get_Tp_allocator());
1232 __throw_exception_again;
1243 template<
typename _Integer>
1247 this->_M_impl._M_start = _M_allocate(
static_cast<size_type
>(__n));
1248 this->_M_impl._M_end_of_storage =
1249 this->_M_impl._M_start +
static_cast<size_type
>(__n);
1250 _M_fill_initialize(
static_cast<size_type
>(__n), __value);
1254 template<
typename _InputIterator>
1256 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1260 iterator_category _IterCategory;
1261 _M_range_initialize(__first, __last, _IterCategory());
1265 template<
typename _InputIterator>
1267 _M_range_initialize(_InputIterator __first, _InputIterator __last,
1271 for (; __first != __last; ++__first)
1272#
if __cplusplus >= 201103L
1273 emplace_back(*__first);
1279 __throw_exception_again;
1284 template<
typename _ForwardIterator>
1286 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1290 this->_M_impl._M_start = this->_M_allocate(__n);
1291 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
1292 this->_M_impl._M_finish =
1293 std::__uninitialized_copy_a(__first, __last,
1294 this->_M_impl._M_start,
1295 _M_get_Tp_allocator());
1301 _M_fill_initialize(size_type __n,
const value_type& __value)
1303 this->_M_impl._M_finish =
1304 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1305 _M_get_Tp_allocator());
1308#if __cplusplus >= 201103L
1311 _M_default_initialize(size_type __n)
1313 this->_M_impl._M_finish =
1314 std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
1315 _M_get_Tp_allocator());
1326 template<
typename _Integer>
1328 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1329 { _M_fill_assign(__n, __val); }
1332 template<
typename _InputIterator>
1334 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1338 iterator_category _IterCategory;
1339 _M_assign_aux(__first, __last, _IterCategory());
1343 template<
typename _InputIterator>
1345 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1349 template<
typename _ForwardIterator>
1351 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1357 _M_fill_assign(size_type __n,
const value_type& __val);
1366 template<
typename _Integer>
1368 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
1370 { _M_fill_insert(__pos, __n, __val); }
1373 template<
typename _InputIterator>
1375 _M_insert_dispatch(iterator __pos, _InputIterator __first,
1376 _InputIterator __last, __false_type)
1379 iterator_category _IterCategory;
1380 _M_range_insert(__pos, __first, __last, _IterCategory());
1384 template<
typename _InputIterator>
1386 _M_range_insert(iterator __pos, _InputIterator __first,
1390 template<
typename _ForwardIterator>
1392 _M_range_insert(iterator __pos, _ForwardIterator __first,
1398 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
1400#if __cplusplus >= 201103L
1403 _M_default_append(size_type __n);
1410#if __cplusplus < 201103L
1412 _M_insert_aux(iterator __position,
const value_type& __x);
1414 template<
typename... _Args>
1416 _M_insert_aux(iterator __position, _Args&&... __args);
1418 template<
typename... _Args>
1420 _M_emplace_back_aux(_Args&&... __args);
1425 _M_check_len(size_type __n,
const char* __s)
const
1428 __throw_length_error(__N(__s));
1439 _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT
1441 std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
1442 this->_M_impl._M_finish = __pos;
1446 _M_erase(iterator __position);
1449 _M_erase(iterator __first, iterator __last);
1451#if __cplusplus >= 201103L
1460 this->_M_impl._M_swap_data(__tmp._M_impl);
1461 this->_M_impl._M_swap_data(__x._M_impl);
1462 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
1470 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
1476 this->
assign(std::__make_move_if_noexcept_iterator(__x.begin()),
1477 std::__make_move_if_noexcept_iterator(__x.end()));
1483#if __cplusplus >= 201103L
1484 template<
typename _Up>
1486 _M_data_ptr(_Up* __ptr)
const
1489 template<
typename _Ptr>
1491 _M_data_ptr(_Ptr __ptr)
const
1494 template<
typename _Ptr>
1496 _M_data_ptr(_Ptr __ptr)
const
1512 template<
typename _Tp,
typename _Alloc>
1515 {
return (__x.size() ==
__y.size()
1516 && std::equal(__x.begin(), __x.end(),
__y.begin())); }
1529 template<
typename _Tp,
typename _Alloc>
1532 {
return std::lexicographical_compare(__x.begin(), __x.end(),
1533 __y.begin(),
__y.end()); }
1536 template<
typename _Tp,
typename _Alloc>
1539 {
return !(__x ==
__y); }
1542 template<
typename _Tp,
typename _Alloc>
1545 {
return __y < __x; }
1548 template<
typename _Tp,
typename _Alloc>
1551 {
return !(
__y < __x); }
1554 template<
typename _Tp,
typename _Alloc>
1557 {
return !(__x <
__y); }
1560 template<
typename _Tp,
typename _Alloc>
1566_GLIBCXX_END_NAMESPACE_CONTAINER
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
ISO C++ entities toplevel namespace is std.
void _Destroy(_Tp *__pointer)
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Forward iterators support a superset of input iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.
See bits/stl_deque.h's _Deque_base for an explanation.
A standard container which offers fixed time access to individual elements in any order.
vector(const vector &__x)
Vector copy constructor.
vector(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a vector from an initializer list.
void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
reference at(size_type __n)
Provides access to the data contained in the vector.
iterator insert(const_iterator __position, initializer_list< value_type > __l)
Inserts an initializer_list into the vector.
const_reference front() const noexcept
iterator erase(const_iterator __position)
Remove element at given position.
vector & operator=(initializer_list< value_type > __l)
Vector list assignment operator.
reverse_iterator rbegin() noexcept
pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first, _ForwardIterator __last)
bool empty() const noexcept
const_reverse_iterator crbegin() const noexcept
vector(const vector &__x, const allocator_type &__a)
Copy constructor with alternative allocator.
iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the vector.
iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in vector before specified iterator.
reference front() noexcept
iterator insert(const_iterator __position, size_type __n, const value_type &__x)
Inserts a number of copies of given data into the vector.
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
vector(size_type __n, const value_type &__value, const allocator_type &__a=allocator_type())
Creates a vector with copies of an exemplar element.
reverse_iterator rend() noexcept
void resize(size_type __new_size, const value_type &__x)
Resizes the vector to the specified number of elements.
vector() noexcept(is_nothrow_default_constructible< _Alloc >::value)
Creates a vector with no elements.
vector(size_type __n, const allocator_type &__a=allocator_type())
Creates a vector with default constructed elements.
void push_back(const value_type &__x)
Add data to the end of the vector.
const_reference operator[](size_type __n) const noexcept
Subscript access to the data contained in the vector.
size_type max_size() const noexcept
const_reverse_iterator crend() const noexcept
iterator insert(const_iterator __position, value_type &&__x)
Inserts given rvalue into vector before specified iterator.
void _M_range_check(size_type __n) const
Safety check used only from at().
void reserve(size_type __n)
Attempt to preallocate enough memory for specified number of elements.
vector(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a vector from a range.
const_iterator begin() const noexcept
vector(vector &&__x) noexcept
Vector move constructor.
void assign(size_type __n, const value_type &__val)
Assigns a given value to a vector.
void swap(vector &__x) noexcept
Swaps data with another vector.
void pop_back() noexcept
Removes last element.
vector & operator=(const vector &__x)
Vector assignment operator.
const_reverse_iterator rend() const noexcept
const_iterator cbegin() const noexcept
const_reference at(size_type __n) const
Provides access to the data contained in the vector.
const_iterator cend() const noexcept
iterator erase(const_iterator __first, const_iterator __last)
Remove a range of elements.
vector(const allocator_type &__a) noexcept
Creates a vector with no elements.
const_reverse_iterator rbegin() const noexcept
iterator begin() noexcept
vector & operator=(vector &&__x) noexcept(_Alloc_traits::_S_nothrow_move())
Vector move assignment operator.
reference back() noexcept
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a vector.
void assign(initializer_list< value_type > __l)
Assigns an initializer list to a vector.
iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into vector before specified iterator.
const_reference back() const noexcept
const_iterator end() const noexcept
size_type size() const noexcept
size_type capacity() const noexcept
reference operator[](size_type __n) noexcept
Subscript access to the data contained in the vector.
vector(vector &&__rv, const allocator_type &__m) noexcept(_Alloc_traits::_S_always_equal())
Move constructor with alternative allocator.
Uniform interface to C++98 and C++11 allocators.
static size_type max_size(const _Tp_alloc_type &__a) noexcept
The maximum supported allocation size.