56 #ifndef _STL_BVECTOR_H
57 #define _STL_BVECTOR_H 1
59 #if __cplusplus >= 201103L
64 namespace std _GLIBCXX_VISIBILITY(default)
66 _GLIBCXX_BEGIN_NAMESPACE_VERSION
68 typedef unsigned long _Bit_type;
69 enum { _S_word_bit = int(__CHAR_BIT__ *
sizeof(_Bit_type)) };
71 __attribute__((__nonnull__))
74 __fill_bvector_n(_Bit_type*,
size_t,
bool) _GLIBCXX_NOEXCEPT;
76 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
84 _Bit_reference(_Bit_type * __x, _Bit_type __y)
85 : _M_p(__x), _M_mask(__y) { }
88 _Bit_reference() _GLIBCXX_NOEXCEPT : _M_p(0), _M_mask(0) { }
90 #if __cplusplus >= 201103L
91 _Bit_reference(
const _Bit_reference&) =
default;
94 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
95 operator bool() const _GLIBCXX_NOEXCEPT
96 {
return !!(*_M_p & _M_mask); }
100 operator=(
bool __x) _GLIBCXX_NOEXCEPT
111 operator=(
const _Bit_reference& __x) _GLIBCXX_NOEXCEPT
112 {
return *
this = bool(__x); }
114 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
116 operator==(
const _Bit_reference& __x)
const
117 {
return bool(*
this) == bool(__x); }
119 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
121 operator<(
const _Bit_reference& __x)
const
122 {
return !bool(*
this) && bool(__x); }
126 flip() _GLIBCXX_NOEXCEPT
127 { *_M_p ^= _M_mask; }
129 #if __cplusplus >= 201103L
132 swap(_Bit_reference __x, _Bit_reference __y) noexcept
141 swap(_Bit_reference __x,
bool& __y) noexcept
150 swap(
bool& __x, _Bit_reference __y) noexcept
159 struct _Bit_iterator_base
160 :
public std::iterator<std::random_access_iterator_tag, bool>
163 unsigned int _M_offset;
166 _Bit_iterator_base(_Bit_type * __x,
unsigned int __y)
167 : _M_p(__x), _M_offset(__y) { }
173 if (_M_offset++ ==
int(_S_word_bit) - 1)
184 if (_M_offset-- == 0)
186 _M_offset = int(_S_word_bit) - 1;
193 _M_incr(ptrdiff_t __i)
196 _M_p += __n / int(_S_word_bit);
197 __n = __n % int(_S_word_bit);
200 __n += int(_S_word_bit);
203 _M_offset =
static_cast<unsigned int>(__n);
207 friend _GLIBCXX20_CONSTEXPR
bool
208 operator==(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
209 {
return __x._M_p == __y._M_p && __x._M_offset == __y._M_offset; }
211 #if __cpp_lib_three_way_comparison
213 friend constexpr strong_ordering
214 operator<=>(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
217 if (
const auto __cmp = __x._M_p <=> __y._M_p; __cmp != 0)
219 return __x._M_offset <=> __y._M_offset;
224 operator<(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
226 return __x._M_p < __y._M_p
227 || (__x._M_p == __y._M_p && __x._M_offset < __y._M_offset);
232 operator!=(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
233 {
return !(__x == __y); }
237 operator>(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
238 {
return __y < __x; }
242 operator<=(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
243 {
return !(__y < __x); }
247 operator>=(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
248 {
return !(__x < __y); }
251 friend _GLIBCXX20_CONSTEXPR ptrdiff_t
252 operator-(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
254 return (
int(_S_word_bit) * (__x._M_p - __y._M_p)
255 + __x._M_offset - __y._M_offset);
259 struct _Bit_iterator :
public _Bit_iterator_base
261 typedef _Bit_reference reference;
262 #if __cplusplus > 201703L
263 typedef void pointer;
265 typedef _Bit_reference* pointer;
267 typedef _Bit_iterator iterator;
270 _Bit_iterator() : _Bit_iterator_base(0, 0) { }
273 _Bit_iterator(_Bit_type * __x,
unsigned int __y)
274 : _Bit_iterator_base(__x, __y) { }
278 _M_const_cast()
const
281 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
284 {
return reference(_M_p, 1UL << _M_offset); }
298 iterator __tmp = *
this;
315 iterator __tmp = *
this;
322 operator+=(difference_type __i)
330 operator-=(difference_type __i)
336 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
338 operator[](difference_type __i)
const
339 {
return *(*
this + __i); }
342 friend _GLIBCXX20_CONSTEXPR iterator
343 operator+(
const iterator& __x, difference_type __n)
345 iterator __tmp = __x;
351 friend _GLIBCXX20_CONSTEXPR iterator
352 operator+(difference_type __n,
const iterator& __x)
353 {
return __x + __n; }
356 friend _GLIBCXX20_CONSTEXPR iterator
357 operator-(
const iterator& __x, difference_type __n)
359 iterator __tmp = __x;
365 struct _Bit_const_iterator :
public _Bit_iterator_base
367 typedef bool reference;
368 typedef bool const_reference;
369 #if __cplusplus > 201703L
370 typedef void pointer;
372 typedef const bool* pointer;
374 typedef _Bit_const_iterator const_iterator;
377 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
380 _Bit_const_iterator(_Bit_type * __x,
unsigned int __y)
381 : _Bit_iterator_base(__x, __y) { }
384 _Bit_const_iterator(
const _Bit_iterator& __x)
385 : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
389 _M_const_cast()
const
390 {
return _Bit_iterator(_M_p, _M_offset); }
392 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
395 {
return _Bit_reference(_M_p, 1UL << _M_offset); }
409 const_iterator __tmp = *
this;
426 const_iterator __tmp = *
this;
433 operator+=(difference_type __i)
441 operator-=(difference_type __i)
447 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
449 operator[](difference_type __i)
const
450 {
return *(*
this + __i); }
453 friend _GLIBCXX20_CONSTEXPR const_iterator
454 operator+(
const const_iterator& __x, difference_type __n)
456 const_iterator __tmp = __x;
462 friend _GLIBCXX20_CONSTEXPR const_iterator
463 operator-(
const const_iterator& __x, difference_type __n)
465 const_iterator __tmp = __x;
471 friend _GLIBCXX20_CONSTEXPR const_iterator
472 operator+(difference_type __n,
const const_iterator& __x)
473 {
return __x + __n; }
476 template<
typename _Alloc>
480 rebind<_Bit_type>::other _Bit_alloc_type;
483 typedef typename _Bit_alloc_traits::pointer _Bit_pointer;
485 struct _Bvector_impl_data
487 #if !_GLIBCXX_INLINE_VERSION
488 _Bit_iterator _M_start;
495 void operator=(_Bit_iterator __it) { _M_p = __it._M_p; }
498 _Bit_iterator _M_finish;
499 _Bit_pointer _M_end_of_storage;
502 _Bvector_impl_data() _GLIBCXX_NOEXCEPT
503 : _M_start(), _M_finish(), _M_end_of_storage()
506 #if __cplusplus >= 201103L
507 _Bvector_impl_data(
const _Bvector_impl_data&) =
default;
510 operator=(
const _Bvector_impl_data&) =
default;
513 _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept
514 : _Bvector_impl_data(__x)
519 _M_move_data(_Bvector_impl_data&& __x) noexcept
528 _M_reset() _GLIBCXX_NOEXCEPT
529 { *
this = _Bvector_impl_data(); }
533 _M_swap_data(_Bvector_impl_data& __x) _GLIBCXX_NOEXCEPT
542 :
public _Bit_alloc_type,
public _Bvector_impl_data
545 _Bvector_impl() _GLIBCXX_NOEXCEPT_IF(
546 is_nothrow_default_constructible<_Bit_alloc_type>::value)
551 _Bvector_impl(
const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT
552 : _Bit_alloc_type(__a)
555 #if __cplusplus >= 201103L
559 _Bvector_impl(_Bvector_impl&& __x) noexcept
564 _Bvector_impl(_Bit_alloc_type&& __a, _Bvector_impl&& __x) noexcept
571 _M_end_addr() const _GLIBCXX_NOEXCEPT
573 if (this->_M_end_of_storage)
580 typedef _Alloc allocator_type;
584 _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT
585 {
return this->_M_impl; }
588 const _Bit_alloc_type&
589 _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT
590 {
return this->_M_impl; }
594 get_allocator() const _GLIBCXX_NOEXCEPT
595 {
return allocator_type(_M_get_Bit_allocator()); }
597 #if __cplusplus >= 201103L
598 _Bvector_base() =
default;
604 _Bvector_base(
const allocator_type& __a)
607 #if __cplusplus >= 201103L
608 _Bvector_base(_Bvector_base&&) =
default;
611 _Bvector_base(_Bvector_base&& __x,
const allocator_type& __a) noexcept
612 : _M_impl(_Bit_alloc_type(__a),
std::move(__x._M_impl))
618 { this->_M_deallocate(); }
621 _Bvector_impl _M_impl;
625 _M_allocate(
size_t __n)
628 #if __has_builtin(__builtin_is_constant_evaluated)
629 if (__builtin_is_constant_evaluated())
632 for (
size_t __i = 0; __i < __n; ++__i)
643 if (_M_impl._M_start._M_p)
645 const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p;
647 _M_impl._M_end_of_storage - __n,
653 #if __cplusplus >= 201103L
656 _M_move_data(_Bvector_base&& __x) noexcept
657 { _M_impl._M_move_data(
std::move(__x._M_impl)); }
663 {
return (__n +
int(_S_word_bit) - 1) / int(_S_word_bit); }
685 template<
typename _Alloc>
686 class vector<bool, _Alloc> :
protected _Bvector_base<_Alloc>
688 typedef _Bvector_base<_Alloc> _Base;
689 typedef typename _Base::_Bit_pointer _Bit_pointer;
692 #if __cplusplus >= 201103L
697 typedef bool value_type;
698 typedef size_t size_type;
699 typedef ptrdiff_t difference_type;
700 typedef _Bit_reference reference;
701 typedef bool const_reference;
702 typedef _Bit_reference* pointer;
703 typedef const bool* const_pointer;
704 typedef _Bit_iterator iterator;
705 typedef _Bit_const_iterator const_iterator;
708 typedef _Alloc allocator_type;
713 {
return _Base::get_allocator(); }
716 using _Base::_M_allocate;
717 using _Base::_M_deallocate;
718 using _Base::_S_nword;
719 using _Base::_M_get_Bit_allocator;
722 #if __cplusplus >= 201103L
730 vector(
const allocator_type& __a)
733 #if __cplusplus >= 201103L
736 vector(size_type __n,
const allocator_type& __a = allocator_type())
741 vector(size_type __n,
const bool& __value,
742 const allocator_type& __a = allocator_type())
745 vector(size_type __n,
const bool& __value =
bool(),
746 const allocator_type& __a = allocator_type())
751 _M_initialize_value(__value);
756 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
758 _M_initialize(__x.
size());
762 #if __cplusplus >= 201103L
779 _M_initialize(__x.
size());
787 vector(
vector&& __x,
const __type_identity_t<allocator_type>& __a)
788 noexcept(_Bit_alloc_traits::_S_always_equal())
794 vector(
const vector& __x,
const __type_identity_t<allocator_type>& __a)
797 _M_initialize(__x.
size());
803 const allocator_type& __a = allocator_type())
806 _M_initialize_range(__l.begin(), __l.end(),
811 #if __cplusplus >= 201103L
812 template<
typename _InputIterator,
813 typename = std::_RequireInputIter<_InputIterator>>
815 vector(_InputIterator __first, _InputIterator __last,
816 const allocator_type& __a = allocator_type())
819 _M_initialize_range(__first, __last,
823 template<
typename _InputIterator>
824 vector(_InputIterator __first, _InputIterator __last,
825 const allocator_type& __a = allocator_type())
829 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
830 _M_initialize_dispatch(__first, __last, _Integral());
835 ~vector() _GLIBCXX_NOEXCEPT { }
843 #if __cplusplus >= 201103L
844 if (_Bit_alloc_traits::_S_propagate_on_copy_assign())
846 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator())
848 this->_M_deallocate();
849 std::__alloc_on_copy(_M_get_Bit_allocator(),
850 __x._M_get_Bit_allocator());
851 _M_initialize(__x.
size());
854 std::__alloc_on_copy(_M_get_Bit_allocator(),
855 __x._M_get_Bit_allocator());
860 this->_M_deallocate();
861 _M_initialize(__x.
size());
863 this->_M_impl._M_finish = _M_copy_aligned(__x.
begin(), __x.
end(),
868 #if __cplusplus >= 201103L
873 if (_Bit_alloc_traits::_S_propagate_on_move_assign()
874 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator())
876 this->_M_deallocate();
878 std::__alloc_on_move(_M_get_Bit_allocator(),
879 __x._M_get_Bit_allocator());
885 this->_M_deallocate();
886 _M_initialize(__x.
size());
888 this->_M_impl._M_finish = _M_copy_aligned(__x.
begin(), __x.
end(),
899 this->
assign(__l.begin(), __l.end());
910 assign(size_type __n,
const bool& __x)
911 { _M_fill_assign(__n, __x); }
913 #if __cplusplus >= 201103L
914 template<
typename _InputIterator,
915 typename = std::_RequireInputIter<_InputIterator>>
918 assign(_InputIterator __first, _InputIterator __last)
921 template<
typename _InputIterator>
923 assign(_InputIterator __first, _InputIterator __last)
926 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
927 _M_assign_dispatch(__first, __last, _Integral());
931 #if __cplusplus >= 201103L
938 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
940 begin() _GLIBCXX_NOEXCEPT
941 {
return iterator(this->_M_impl._M_start._M_p, 0); }
943 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
945 begin()
const _GLIBCXX_NOEXCEPT
946 {
return const_iterator(this->_M_impl._M_start._M_p, 0); }
948 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
950 end() _GLIBCXX_NOEXCEPT
951 {
return this->_M_impl._M_finish; }
953 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
955 end()
const _GLIBCXX_NOEXCEPT
956 {
return this->_M_impl._M_finish; }
958 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
960 rbegin() _GLIBCXX_NOEXCEPT
963 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
965 rbegin()
const _GLIBCXX_NOEXCEPT
968 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
970 rend() _GLIBCXX_NOEXCEPT
973 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
975 rend()
const _GLIBCXX_NOEXCEPT
978 #if __cplusplus >= 201103L
979 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
982 {
return const_iterator(this->_M_impl._M_start._M_p, 0); }
984 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
986 cend()
const noexcept
987 {
return this->_M_impl._M_finish; }
989 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
994 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
996 crend()
const noexcept
1000 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1002 size()
const _GLIBCXX_NOEXCEPT
1003 {
return size_type(
end() -
begin()); }
1005 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1009 const size_type __isize =
1010 __gnu_cxx::__numeric_traits<difference_type>::__max
1011 - int(_S_word_bit) + 1;
1012 const size_type __asize
1013 = _Bit_alloc_traits::max_size(_M_get_Bit_allocator());
1014 return (__asize <= __isize /
int(_S_word_bit)
1015 ? __asize *
int(_S_word_bit) : __isize);
1018 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1021 {
return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
1024 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1026 empty()
const _GLIBCXX_NOEXCEPT
1029 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1032 {
return begin()[__n]; }
1034 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1037 {
return begin()[__n]; }
1040 _GLIBCXX20_CONSTEXPR
1044 if (__n >= this->
size())
1045 __throw_out_of_range_fmt(__N(
"vector<bool>::_M_range_check: __n "
1046 "(which is %zu) >= this->size() "
1052 _GLIBCXX20_CONSTEXPR
1057 return (*
this)[__n];
1060 _GLIBCXX20_CONSTEXPR
1062 at(size_type __n)
const
1065 return (*
this)[__n];
1068 _GLIBCXX20_CONSTEXPR
1073 __throw_length_error(__N(
"vector::reserve"));
1078 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1081 {
return *
begin(); }
1083 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1086 {
return *
begin(); }
1088 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1091 {
return *(
end() - 1); }
1093 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1096 {
return *(
end() - 1); }
1098 _GLIBCXX20_CONSTEXPR
1102 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
1103 *this->_M_impl._M_finish++ = __x;
1105 _M_insert_aux(
end(), __x);
1108 _GLIBCXX20_CONSTEXPR
1112 #if __cplusplus >= 201103L
1113 __glibcxx_assert(_Bit_alloc_traits::propagate_on_container_swap::value
1114 || _M_get_Bit_allocator() == __x._M_get_Bit_allocator());
1116 this->_M_impl._M_swap_data(__x._M_impl);
1117 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(),
1118 __x._M_get_Bit_allocator());
1122 _GLIBCXX20_CONSTEXPR
1124 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
1131 _GLIBCXX20_CONSTEXPR
1133 #if __cplusplus >= 201103L
1134 insert(const_iterator __position,
const bool& __x =
bool())
1136 insert(iterator __position,
const bool& __x =
bool())
1139 const difference_type __n = __position -
begin();
1140 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()
1141 && __position ==
end())
1142 *this->_M_impl._M_finish++ = __x;
1144 _M_insert_aux(__position._M_const_cast(), __x);
1145 return begin() + __n;
1148 #if __cplusplus >= 201103L
1149 template<
typename _InputIterator,
1150 typename = std::_RequireInputIter<_InputIterator>>
1151 _GLIBCXX20_CONSTEXPR
1153 insert(const_iterator __position,
1154 _InputIterator __first, _InputIterator __last)
1156 difference_type __offset = __position -
cbegin();
1157 _M_insert_range(__position._M_const_cast(),
1160 return begin() + __offset;
1163 template<
typename _InputIterator>
1165 insert(iterator __position,
1166 _InputIterator __first, _InputIterator __last)
1169 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1170 _M_insert_dispatch(__position, __first, __last, _Integral());
1174 #if __cplusplus >= 201103L
1175 _GLIBCXX20_CONSTEXPR
1177 insert(const_iterator __position, size_type __n,
const bool& __x)
1179 difference_type __offset = __position -
cbegin();
1180 _M_fill_insert(__position._M_const_cast(), __n, __x);
1181 return begin() + __offset;
1185 insert(iterator __position, size_type __n,
const bool& __x)
1186 { _M_fill_insert(__position, __n, __x); }
1189 #if __cplusplus >= 201103L
1190 _GLIBCXX20_CONSTEXPR
1193 {
return this->
insert(__p, __l.begin(), __l.end()); }
1196 _GLIBCXX20_CONSTEXPR
1199 { --this->_M_impl._M_finish; }
1201 _GLIBCXX20_CONSTEXPR
1203 #if __cplusplus >= 201103L
1204 erase(const_iterator __position)
1206 erase(iterator __position)
1208 {
return _M_erase(__position._M_const_cast()); }
1210 _GLIBCXX20_CONSTEXPR
1212 #if __cplusplus >= 201103L
1213 erase(const_iterator __first, const_iterator __last)
1215 erase(iterator __first, iterator __last)
1217 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1219 _GLIBCXX20_CONSTEXPR
1221 resize(size_type __new_size,
bool __x =
bool())
1223 if (__new_size <
size())
1224 _M_erase_at_end(
begin() + difference_type(__new_size));
1229 #if __cplusplus >= 201103L
1230 _GLIBCXX20_CONSTEXPR
1233 { _M_shrink_to_fit(); }
1236 _GLIBCXX20_CONSTEXPR
1238 flip() _GLIBCXX_NOEXCEPT
1240 _Bit_type *
const __end = this->_M_impl._M_end_addr();
1241 for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p)
1245 _GLIBCXX20_CONSTEXPR
1247 clear() _GLIBCXX_NOEXCEPT
1248 { _M_erase_at_end(
begin()); }
1250 #if __cplusplus >= 201103L
1251 template<
typename... _Args>
1252 #if __cplusplus > 201402L
1253 _GLIBCXX20_CONSTEXPR
1258 emplace_back(_Args&&... __args)
1261 #if __cplusplus > 201402L
1266 template<
typename... _Args>
1267 _GLIBCXX20_CONSTEXPR
1269 emplace(const_iterator __pos, _Args&&... __args)
1270 {
return insert(__pos,
bool(__args...)); }
1275 _GLIBCXX20_CONSTEXPR
1277 _M_copy_aligned(const_iterator __first, const_iterator __last,
1280 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
1281 return std::copy(const_iterator(__last._M_p, 0), __last,
1285 _GLIBCXX20_CONSTEXPR
1287 _M_initialize(size_type __n)
1291 _Bit_pointer __q = this->_M_allocate(__n);
1292 this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1294 this->_M_impl._M_start = __start;
1295 this->_M_impl._M_finish = __start + difference_type(__n);
1299 _GLIBCXX20_CONSTEXPR
1301 _M_initialize_value(
bool __x) _GLIBCXX_NOEXCEPT
1303 if (_Bit_type* __p = this->_M_impl._M_start._M_p)
1304 __fill_bvector_n(__p, this->_M_impl._M_end_addr() - __p, __x);
1307 _GLIBCXX20_CONSTEXPR
1309 _M_reallocate(size_type __n);
1311 #if __cplusplus >= 201103L
1312 _GLIBCXX20_CONSTEXPR
1317 #if __cplusplus < 201103L
1320 template<
typename _Integer>
1322 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1324 _M_initialize(
static_cast<size_type
>(__n));
1325 _M_initialize_value(__x);
1328 template<
typename _InputIterator>
1330 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1332 { _M_initialize_range(__first, __last,
1336 template<
typename _InputIterator>
1337 _GLIBCXX20_CONSTEXPR
1339 _M_initialize_range(_InputIterator __first, _InputIterator __last,
1342 for (; __first != __last; ++__first)
1346 template<
typename _ForwardIterator>
1347 _GLIBCXX20_CONSTEXPR
1349 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
1354 std::copy(__first, __last,
begin());
1357 #if __cplusplus < 201103L
1360 template<
typename _Integer>
1362 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1363 { _M_fill_assign(__n, __val); }
1365 template<
class _InputIterator>
1367 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1372 _GLIBCXX20_CONSTEXPR
1374 _M_fill_assign(
size_t __n,
bool __x)
1378 _M_initialize_value(__x);
1383 _M_erase_at_end(
begin() + __n);
1384 _M_initialize_value(__x);
1388 template<
typename _InputIterator>
1389 _GLIBCXX20_CONSTEXPR
1391 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1394 iterator __cur =
begin();
1395 for (; __first != __last && __cur !=
end(); ++__cur, (void)++__first)
1397 if (__first == __last)
1398 _M_erase_at_end(__cur);
1403 template<
typename _ForwardIterator>
1404 _GLIBCXX20_CONSTEXPR
1406 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1411 _M_erase_at_end(std::copy(__first, __last,
begin()));
1414 _ForwardIterator __mid = __first;
1416 std::copy(__first, __mid,
begin());
1421 #if __cplusplus < 201103L
1424 template<
typename _Integer>
1426 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1428 { _M_fill_insert(__pos, __n, __x); }
1430 template<
typename _InputIterator>
1432 _M_insert_dispatch(iterator __pos,
1433 _InputIterator __first, _InputIterator __last,
1435 { _M_insert_range(__pos, __first, __last,
1439 _GLIBCXX20_CONSTEXPR
1441 _M_fill_insert(iterator __position, size_type __n,
bool __x);
1443 template<
typename _InputIterator>
1444 _GLIBCXX20_CONSTEXPR
1446 _M_insert_range(iterator __pos, _InputIterator __first,
1449 for (; __first != __last; ++__first)
1451 __pos =
insert(__pos, *__first);
1456 template<
typename _ForwardIterator>
1457 _GLIBCXX20_CONSTEXPR
1459 _M_insert_range(iterator __position, _ForwardIterator __first,
1462 _GLIBCXX20_CONSTEXPR
1464 _M_insert_aux(iterator __position,
bool __x);
1466 _GLIBCXX20_CONSTEXPR
1468 _M_check_len(size_type __n,
const char* __s)
const
1471 __throw_length_error(__N(__s));
1477 _GLIBCXX20_CONSTEXPR
1479 _M_erase_at_end(iterator __pos)
1480 { this->_M_impl._M_finish = __pos; }
1482 _GLIBCXX20_CONSTEXPR
1484 _M_erase(iterator __pos);
1486 _GLIBCXX20_CONSTEXPR
1488 _M_erase(iterator __first, iterator __last);
1496 #if __cplusplus >= 201103L
1497 void data() =
delete;
1503 _GLIBCXX_END_NAMESPACE_CONTAINER
1506 _GLIBCXX20_CONSTEXPR
1508 __fill_bvector(_Bit_type* __v,
unsigned int __first,
unsigned int __last,
1509 bool __x) _GLIBCXX_NOEXCEPT
1511 const _Bit_type __fmask = ~0ul << __first;
1512 const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last);
1513 const _Bit_type __mask = __fmask & __lmask;
1522 __attribute__((__nonnull__))
1523 _GLIBCXX20_CONSTEXPR
1525 __fill_bvector_n(_Bit_type* __p,
size_t __n,
bool __x) _GLIBCXX_NOEXCEPT
1527 #if __has_builtin(__builtin_is_constant_evaluated)
1528 if (__builtin_is_constant_evaluated())
1530 for (
size_t __i = 0; __i < __n; ++__i)
1531 __p[__i] = __x ? ~0ul : 0ul;
1535 __builtin_memset(__p, __x ? ~0 : 0, __n *
sizeof(_Bit_type));
1539 _GLIBCXX20_CONSTEXPR
1541 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator __first,
1542 _GLIBCXX_STD_C::_Bit_iterator __last,
const bool& __x)
1544 if (__first._M_p != __last._M_p)
1546 _Bit_type* __first_p = __first._M_p;
1547 if (__first._M_offset != 0)
1548 __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x);
1550 __fill_bvector_n(__first_p, __last._M_p - __first_p, __x);
1552 if (__last._M_offset != 0)
1553 __fill_bvector(__last._M_p, 0, __last._M_offset, __x);
1555 else if (__first._M_offset != __last._M_offset)
1556 __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x);
1559 #if __cplusplus >= 201103L
1562 template<
typename _Alloc>
1564 :
public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1567 operator()(
const _GLIBCXX_STD_C::vector<bool, _Alloc>&)
const noexcept;
1571 _GLIBCXX_END_NAMESPACE_VERSION
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
constexpr complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
constexpr complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Primary class template hash.
__detected_or_t< typename is_empty< _Alloc >::type, __equal, _Alloc > is_always_equal
Whether all instances of the allocator type compare equal.
Forward iterators support a superset of input iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.
ptrdiff_t difference_type
Distance between iterators is represented as this type.
A standard container which offers fixed time access to individual elements in any order.
constexpr iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into vector before specified iterator.
constexpr void push_back(const value_type &__x)
Add data to the end of the vector.
constexpr reverse_iterator rbegin() noexcept
constexpr iterator end() noexcept
vector()=default
Creates a vector with no elements.
constexpr iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in vector before specified iterator.
constexpr iterator begin() noexcept
constexpr size_type capacity() const noexcept
constexpr ~vector() noexcept
constexpr void assign(size_type __n, const value_type &__val)
Assigns a given value to a vector.
constexpr void swap(vector &__x) noexcept
Swaps data with another vector.
constexpr _Tp * data() noexcept
constexpr void pop_back() noexcept
Removes last element.
constexpr void reserve(size_type __n)
Attempt to preallocate enough memory for specified number of elements.
constexpr reference at(size_type __n)
Provides access to the data contained in the vector.
constexpr void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
constexpr void _M_range_check(size_type __n) const
Safety check used only from at().
constexpr reference front() noexcept
constexpr iterator erase(const_iterator __position)
Remove element at given position.
constexpr bool empty() const noexcept
constexpr reverse_iterator rend() noexcept
constexpr const_reverse_iterator crbegin() const noexcept
constexpr const_iterator cbegin() const noexcept
constexpr void clear() noexcept
constexpr allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
constexpr size_type size() const noexcept
constexpr vector & operator=(const vector &__x)
Vector assignment operator.
constexpr reference back() noexcept
constexpr const_reverse_iterator crend() const noexcept
constexpr const_iterator cend() const noexcept
constexpr reference operator[](size_type __n) noexcept
Subscript access to the data contained in the vector.
constexpr void shrink_to_fit()
constexpr size_type max_size() const noexcept
Uniform interface to C++98 and C++11 allocators.
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.