56 #ifndef _STL_BVECTOR_H 57 #define _STL_BVECTOR_H 1 59 #ifndef _GLIBCXX_ALWAYS_INLINE 60 #define _GLIBCXX_ALWAYS_INLINE inline __attribute__((__always_inline__)) 63 #if __cplusplus >= 201103L 68 namespace std _GLIBCXX_VISIBILITY(default)
70 _GLIBCXX_BEGIN_NAMESPACE_VERSION
72 typedef unsigned long _Bit_type;
73 enum { _S_word_bit = int(__CHAR_BIT__ *
sizeof(_Bit_type)) };
75 __attribute__((__nonnull__))
78 __fill_bvector_n(_Bit_type*,
size_t,
bool) _GLIBCXX_NOEXCEPT;
80 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
85 template<
typename,
typename>
friend class vector;
86 friend struct _Bit_iterator;
87 friend struct _Bit_const_iterator;
90 _Bit_reference() _GLIBCXX_NOEXCEPT : _M_p(0), _M_mask(0) { }
96 _Bit_reference(_Bit_type * __x, _Bit_type __y)
97 : _M_p(__x), _M_mask(__y) { }
100 #if __cplusplus >= 201103L 101 _Bit_reference(
const _Bit_reference&) =
default;
104 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
105 operator bool() const _GLIBCXX_NOEXCEPT
106 {
return !!(*_M_p & _M_mask); }
110 operator=(
bool __x) _GLIBCXX_NOEXCEPT
119 #if __cplusplus > 202002L 120 constexpr
const _Bit_reference&
121 operator=(
bool __x)
const noexcept
133 operator=(
const _Bit_reference& __x) _GLIBCXX_NOEXCEPT
134 {
return *
this = bool(__x); }
136 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
138 operator==(
const _Bit_reference& __x)
const 139 {
return bool(*
this) == bool(__x); }
141 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
143 operator<(
const _Bit_reference& __x)
const 144 {
return !bool(*
this) && bool(__x); }
148 flip() _GLIBCXX_NOEXCEPT
149 { *_M_p ^= _M_mask; }
151 #if __cplusplus >= 201103L 154 swap(_Bit_reference __x, _Bit_reference __y) noexcept
163 swap(_Bit_reference __x,
bool& __y) noexcept
172 swap(
bool& __x, _Bit_reference __y) noexcept
182 #pragma GCC diagnostic push 183 #pragma GCC diagnostic ignored "-Wdeprecated-declarations" 184 struct _Bit_iterator_base
185 :
public std::iterator<std::random_access_iterator_tag, bool>
188 unsigned int _M_offset;
190 _GLIBCXX20_CONSTEXPR _GLIBCXX_ALWAYS_INLINE
192 _M_assume_normalized()
const 194 #if __has_attribute(__assume__) && !defined(_GLIBCXX_CLANG) 195 unsigned int __ofst = _M_offset;
196 __attribute__ ((__assume__ (__ofst <
unsigned(_S_word_bit))));
201 _Bit_iterator_base(_Bit_type * __x,
unsigned int __y)
202 : _M_p(__x), _M_offset(__y) { }
208 _M_assume_normalized();
209 if (_M_offset++ ==
int(_S_word_bit) - 1)
220 _M_assume_normalized();
221 if (_M_offset-- == 0)
223 _M_offset = int(_S_word_bit) - 1;
230 _M_incr(ptrdiff_t __i)
232 _M_assume_normalized();
234 _M_p += __n / int(_S_word_bit);
235 __n = __n % int(_S_word_bit);
238 __n += int(_S_word_bit);
241 _M_offset =
static_cast<unsigned int>(__n);
245 friend _GLIBCXX20_CONSTEXPR
bool 246 operator==(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
248 __x._M_assume_normalized();
249 __y._M_assume_normalized();
250 return __x._M_p == __y._M_p && __x._M_offset == __y._M_offset;
253 #if __cpp_lib_three_way_comparison 255 friend constexpr strong_ordering
256 operator<=>(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
259 __x._M_assume_normalized();
260 __y._M_assume_normalized();
261 if (
const auto __cmp = __x._M_p <=> __y._M_p; __cmp != 0)
263 return __x._M_offset <=> __y._M_offset;
268 operator<(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
270 __x._M_assume_normalized();
271 __y._M_assume_normalized();
272 return __x._M_p < __y._M_p
273 || (__x._M_p == __y._M_p && __x._M_offset < __y._M_offset);
278 operator!=(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
279 {
return !(__x == __y); }
283 operator>(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
284 {
return __y < __x; }
288 operator<=(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
289 {
return !(__y < __x); }
293 operator>=(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
294 {
return !(__x < __y); }
295 #endif // three-way comparison 297 friend _GLIBCXX20_CONSTEXPR ptrdiff_t
298 operator-(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
300 __x._M_assume_normalized();
301 __y._M_assume_normalized();
302 return (
int(_S_word_bit) * (__x._M_p - __y._M_p)
303 + __x._M_offset - __y._M_offset);
306 #pragma GCC diagnostic pop 308 struct _Bit_iterator :
public _Bit_iterator_base
310 typedef _Bit_reference reference;
311 #if __cplusplus > 201703L 312 typedef void pointer;
314 typedef _Bit_reference* pointer;
316 typedef _Bit_iterator iterator;
319 _Bit_iterator() : _Bit_iterator_base(0, 0) { }
322 _Bit_iterator(_Bit_type * __x,
unsigned int __y)
323 : _Bit_iterator_base(__x, __y) { }
327 _M_const_cast()
const 330 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
334 _M_assume_normalized();
335 return reference(_M_p, 1UL << _M_offset);
350 iterator __tmp = *
this;
367 iterator __tmp = *
this;
374 operator+=(difference_type __i)
382 operator-=(difference_type __i)
388 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
390 operator[](difference_type __i)
const 391 {
return *(*
this + __i); }
394 friend _GLIBCXX20_CONSTEXPR iterator
395 operator+(
const iterator& __x, difference_type __n)
397 iterator __tmp = __x;
403 friend _GLIBCXX20_CONSTEXPR iterator
404 operator+(difference_type __n,
const iterator& __x)
405 {
return __x + __n; }
408 friend _GLIBCXX20_CONSTEXPR iterator
409 operator-(
const iterator& __x, difference_type __n)
411 iterator __tmp = __x;
417 struct _Bit_const_iterator :
public _Bit_iterator_base
419 typedef bool reference;
420 typedef bool const_reference;
421 #if __cplusplus > 201703L 422 typedef void pointer;
424 typedef const bool* pointer;
426 typedef _Bit_const_iterator const_iterator;
429 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
432 _Bit_const_iterator(_Bit_type * __x,
unsigned int __y)
433 : _Bit_iterator_base(__x, __y) { }
436 _Bit_const_iterator(
const _Bit_iterator& __x)
437 : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
441 _M_const_cast()
const 442 {
return _Bit_iterator(_M_p, _M_offset); }
444 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
448 _M_assume_normalized();
449 return _Bit_reference(_M_p, 1UL << _M_offset);
464 const_iterator __tmp = *
this;
481 const_iterator __tmp = *
this;
488 operator+=(difference_type __i)
496 operator-=(difference_type __i)
502 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
504 operator[](difference_type __i)
const 505 {
return *(*
this + __i); }
508 friend _GLIBCXX20_CONSTEXPR const_iterator
509 operator+(
const const_iterator& __x, difference_type __n)
511 const_iterator __tmp = __x;
517 friend _GLIBCXX20_CONSTEXPR const_iterator
518 operator-(
const const_iterator& __x, difference_type __n)
520 const_iterator __tmp = __x;
526 friend _GLIBCXX20_CONSTEXPR const_iterator
527 operator+(difference_type __n,
const const_iterator& __x)
528 {
return __x + __n; }
531 template<
typename _Alloc>
535 rebind<_Bit_type>::other _Bit_alloc_type;
538 typedef typename _Bit_alloc_traits::pointer _Bit_pointer;
540 struct _Bvector_impl_data
542 #if !_GLIBCXX_INLINE_VERSION 543 _Bit_iterator _M_start;
550 void operator=(_Bit_iterator __it) { _M_p = __it._M_p; }
553 _Bit_iterator _M_finish;
554 _Bit_pointer _M_end_of_storage;
557 _Bvector_impl_data() _GLIBCXX_NOEXCEPT
558 : _M_start(), _M_finish(), _M_end_of_storage()
561 #if __cplusplus >= 201103L 562 _Bvector_impl_data(
const _Bvector_impl_data&) =
default;
565 operator=(
const _Bvector_impl_data&) =
default;
568 _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept
569 : _Bvector_impl_data(__x)
574 _M_move_data(_Bvector_impl_data&& __x) noexcept
583 _M_reset() _GLIBCXX_NOEXCEPT
584 { *
this = _Bvector_impl_data(); }
588 _M_swap_data(_Bvector_impl_data& __x) _GLIBCXX_NOEXCEPT
592 std::swap(*
this, __x);
597 :
public _Bit_alloc_type,
public _Bvector_impl_data
600 _Bvector_impl() _GLIBCXX_NOEXCEPT_IF(
601 is_nothrow_default_constructible<_Bit_alloc_type>::value)
602 #if __cpp_concepts && __glibcxx_type_trait_variable_templates 603 requires is_default_constructible_v<_Bit_alloc_type>
609 _Bvector_impl(
const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT
610 : _Bit_alloc_type(__a)
613 #if __cplusplus >= 201103L 617 _Bvector_impl(_Bvector_impl&& __x) noexcept
622 _Bvector_impl(_Bit_alloc_type&& __a, _Bvector_impl&& __x) noexcept
629 _M_end_addr() const _GLIBCXX_NOEXCEPT
631 if (this->_M_end_of_storage)
638 typedef _Alloc allocator_type;
642 _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT
643 {
return this->_M_impl; }
646 const _Bit_alloc_type&
647 _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT
648 {
return this->_M_impl; }
652 get_allocator() const _GLIBCXX_NOEXCEPT
653 {
return allocator_type(_M_get_Bit_allocator()); }
655 #if __cplusplus >= 201103L 656 _Bvector_base() =
default;
662 _Bvector_base(
const allocator_type& __a)
663 : _M_impl(_Bit_alloc_type(__a)) { }
665 #if __cplusplus >= 201103L 666 _Bvector_base(_Bvector_base&&) =
default;
669 _Bvector_base(_Bvector_base&& __x,
const allocator_type& __a) noexcept
670 : _M_impl(_Bit_alloc_type(__a),
std::move(__x._M_impl))
676 { this->_M_deallocate(); }
679 _Bvector_impl _M_impl;
683 _M_allocate(
size_t __n)
686 #if __cpp_lib_is_constant_evaluated && __cpp_constexpr_dynamic_alloc 687 if (std::is_constant_evaluated())
690 for (
size_t __i = 0; __i < __n; ++__i)
701 if (_M_impl._M_start._M_p)
703 const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p;
705 _M_impl._M_end_of_storage - __n,
711 #if __cplusplus >= 201103L 714 _M_move_data(_Bvector_base&& __x) noexcept
715 { _M_impl._M_move_data(
std::move(__x._M_impl)); }
722 {
return (__n +
int(_S_word_bit) - 1) / int(_S_word_bit); }
746 template<
typename _Alloc>
747 class vector<bool, _Alloc> :
protected _Bvector_base<_Alloc>
749 typedef _Bvector_base<_Alloc> _Base;
750 typedef typename _Base::_Bit_pointer _Bit_pointer;
753 #if __cplusplus >= 201103L 755 # if __cplusplus > 201703L // || defined __STRICT_ANSI__ 757 "std::vector must have the same value_type as its allocator");
762 typedef bool value_type;
763 typedef size_t size_type;
764 typedef ptrdiff_t difference_type;
765 typedef _Bit_reference reference;
766 typedef bool const_reference;
767 typedef _Bit_reference* pointer;
768 typedef const bool* const_pointer;
769 typedef _Bit_iterator iterator;
770 typedef _Bit_const_iterator const_iterator;
773 typedef _Alloc allocator_type;
777 get_allocator()
const 778 {
return _Base::get_allocator(); }
781 using _Base::_M_allocate;
782 using _Base::_M_deallocate;
783 using _Base::_S_nword;
784 using _Base::_M_get_Bit_allocator;
787 #if __cplusplus >= 201103L 795 vector(
const allocator_type& __a) _GLIBCXX_NOEXCEPT
798 #if __cplusplus >= 201103L 801 vector(size_type __n,
const allocator_type& __a = allocator_type())
806 vector(size_type __n,
const bool& __value,
807 const allocator_type& __a = allocator_type())
810 vector(size_type __n,
const bool& __value =
bool(),
811 const allocator_type& __a = allocator_type())
815 _M_check_and_initialize(__n);
816 _M_initialize_value(__value);
821 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
823 const_iterator __xbegin = __x.
begin(), __xend = __x.
end();
824 _M_initialize(__x.
size());
825 _M_copy_aligned(__xbegin, __xend,
begin());
828 #if __cplusplus >= 201103L 845 _M_initialize(__x.
size());
853 vector(
vector&& __x,
const __type_identity_t<allocator_type>& __a)
854 noexcept(_Bit_alloc_traits::_S_always_equal())
860 vector(
const vector& __x,
const __type_identity_t<allocator_type>& __a)
863 _M_initialize(__x.
size());
869 const allocator_type& __a = allocator_type())
872 _M_initialize_range(__l.begin(), __l.end(),
877 #if __cplusplus >= 201103L 878 template<
typename _InputIterator,
879 typename = std::_RequireInputIter<_InputIterator>>
881 vector(_InputIterator __first, _InputIterator __last,
882 const allocator_type& __a = allocator_type())
885 _M_initialize_range(__first, __last,
889 template<
typename _InputIterator>
890 vector(_InputIterator __first, _InputIterator __last,
891 const allocator_type& __a = allocator_type())
895 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
896 _M_initialize_dispatch(__first, __last, _Integral());
900 #if __glibcxx_containers_ranges // C++ >= 23 906 template<__detail::__container_compatible_range<
bool> _Rg>
908 vector(from_range_t, _Rg&& __rg,
const _Alloc& __a = _Alloc())
911 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
914 ranges::copy(__rg,
begin());
920 for (; __first != __last; ++__first)
921 emplace_back(*__first);
927 ~vector() _GLIBCXX_NOEXCEPT { }
935 #if __cplusplus >= 201103L 936 if (_Bit_alloc_traits::_S_propagate_on_copy_assign())
938 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator())
940 this->_M_deallocate();
941 std::__alloc_on_copy(_M_get_Bit_allocator(),
942 __x._M_get_Bit_allocator());
943 _M_initialize(__x.
size());
946 std::__alloc_on_copy(_M_get_Bit_allocator(),
947 __x._M_get_Bit_allocator());
952 this->_M_deallocate();
953 _M_initialize(__x.
size());
955 this->_M_impl._M_finish = _M_copy_aligned(__x.
begin(), __x.
end(),
960 #if __cplusplus >= 201103L 965 if (_Bit_alloc_traits::_S_propagate_on_move_assign()
966 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator())
968 this->_M_deallocate();
970 std::__alloc_on_move(_M_get_Bit_allocator(),
971 __x._M_get_Bit_allocator());
977 this->_M_deallocate();
978 _M_initialize(__x.
size());
980 this->_M_impl._M_finish = _M_copy_aligned(__x.
begin(), __x.
end(),
991 this->
assign(__l.begin(), __l.end());
1000 _GLIBCXX20_CONSTEXPR
1002 assign(size_type __n,
const bool& __x)
1003 { _M_fill_assign(__n, __x); }
1005 #if __cplusplus >= 201103L 1006 template<
typename _InputIterator,
1007 typename = std::_RequireInputIter<_InputIterator>>
1008 _GLIBCXX20_CONSTEXPR
1010 assign(_InputIterator __first, _InputIterator __last)
1013 template<
typename _InputIterator>
1015 assign(_InputIterator __first, _InputIterator __last)
1018 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1019 _M_assign_dispatch(__first, __last, _Integral());
1023 #if __cplusplus >= 201103L 1024 _GLIBCXX20_CONSTEXPR
1030 #if __glibcxx_containers_ranges // C++ >= 23 1037 template<__detail::__container_compatible_range<
bool> _Rg>
1039 assign_range(_Rg&& __rg)
1041 static_assert(assignable_from<
bool&, ranges::range_reference_t<_Rg>>);
1042 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1047 this->_M_impl._M_finish
1048 = ranges::copy(std::forward<_Rg>(__rg),
begin()).out;
1058 for (; __first != __last; ++__first)
1059 emplace_back(*__first);
1064 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1066 begin() _GLIBCXX_NOEXCEPT
1067 {
return iterator(this->_M_impl._M_start._M_p, 0); }
1069 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1071 begin()
const _GLIBCXX_NOEXCEPT
1072 {
return const_iterator(this->_M_impl._M_start._M_p, 0); }
1074 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1076 end() _GLIBCXX_NOEXCEPT
1077 {
return this->_M_impl._M_finish; }
1079 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1081 end()
const _GLIBCXX_NOEXCEPT
1082 {
return this->_M_impl._M_finish; }
1084 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1086 rbegin() _GLIBCXX_NOEXCEPT
1089 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1091 rbegin()
const _GLIBCXX_NOEXCEPT
1094 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1096 rend() _GLIBCXX_NOEXCEPT
1099 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1101 rend()
const _GLIBCXX_NOEXCEPT
1104 #if __cplusplus >= 201103L 1105 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1108 {
return const_iterator(this->_M_impl._M_start._M_p, 0); }
1110 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1112 cend()
const noexcept
1113 {
return this->_M_impl._M_finish; }
1115 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1120 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1122 crend()
const noexcept
1126 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1128 size()
const _GLIBCXX_NOEXCEPT
1129 {
return size_type(
end() -
begin()); }
1131 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1135 const size_type __isize =
1136 __gnu_cxx::__numeric_traits<difference_type>::__max
1137 - int(_S_word_bit) + 1;
1138 const size_type __asize
1139 = _Bit_alloc_traits::max_size(_M_get_Bit_allocator());
1140 return (__asize <= __isize /
int(_S_word_bit)
1141 ? __asize *
int(_S_word_bit) : __isize);
1144 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1147 {
return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
1150 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1152 empty()
const _GLIBCXX_NOEXCEPT
1155 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1159 __glibcxx_requires_subscript(__n);
1160 return _Bit_reference (this->_M_impl._M_start._M_p
1161 + __n /
int(_S_word_bit),
1162 1UL << __n %
int(_S_word_bit));
1165 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1169 __glibcxx_requires_subscript(__n);
1170 return _Bit_reference (this->_M_impl._M_start._M_p
1171 + __n /
int(_S_word_bit),
1172 1UL << __n %
int(_S_word_bit));
1176 _GLIBCXX20_CONSTEXPR
1180 if (__n >= this->
size())
1181 __throw_out_of_range_fmt(__N(
"vector<bool>::_M_range_check: __n " 1182 "(which is %zu) >= this->size() " 1188 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1193 return (*
this)[__n];
1196 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1198 at(size_type __n)
const 1201 return (*
this)[__n];
1204 _GLIBCXX20_CONSTEXPR
1209 __throw_length_error(__N(
"vector::reserve"));
1214 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1218 __glibcxx_requires_nonempty();
1222 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1226 __glibcxx_requires_nonempty();
1230 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1234 __glibcxx_requires_nonempty();
1235 return *(
end() - 1);
1238 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1242 __glibcxx_requires_nonempty();
1243 return *(
end() - 1);
1246 _GLIBCXX20_CONSTEXPR
1250 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
1251 *this->_M_impl._M_finish++ = __x;
1253 _M_insert_aux(
end(), __x);
1256 _GLIBCXX20_CONSTEXPR
1260 #if __cplusplus >= 201103L 1261 __glibcxx_assert(_Bit_alloc_traits::propagate_on_container_swap::value
1262 || _M_get_Bit_allocator() == __x._M_get_Bit_allocator());
1264 this->_M_impl._M_swap_data(__x._M_impl);
1265 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(),
1266 __x._M_get_Bit_allocator());
1270 _GLIBCXX20_CONSTEXPR
1272 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
1279 _GLIBCXX20_CONSTEXPR
1281 #if __cplusplus >= 201103L 1282 insert(const_iterator __position,
const bool& __x)
1284 insert(iterator __position,
const bool& __x)
1287 const difference_type __n = __position -
begin();
1288 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()
1289 && __position ==
end())
1290 *this->_M_impl._M_finish++ = __x;
1292 _M_insert_aux(__position._M_const_cast(), __x);
1293 return begin() + __n;
1296 #if _GLIBCXX_USE_DEPRECATED 1297 _GLIBCXX_DEPRECATED_SUGGEST(
"insert(position, false)")
1299 insert(const_iterator __position)
1300 {
return this->
insert(__position._M_const_cast(),
false); }
1303 #if __cplusplus >= 201103L 1304 template<
typename _InputIterator,
1305 typename = std::_RequireInputIter<_InputIterator>>
1306 _GLIBCXX20_CONSTEXPR
1308 insert(const_iterator __position,
1309 _InputIterator __first, _InputIterator __last)
1311 difference_type __offset = __position -
cbegin();
1312 _M_insert_range(__position._M_const_cast(),
1315 return begin() + __offset;
1318 template<
typename _InputIterator>
1320 insert(iterator __position,
1321 _InputIterator __first, _InputIterator __last)
1324 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1325 _M_insert_dispatch(__position, __first, __last, _Integral());
1329 #if __cplusplus >= 201103L 1330 _GLIBCXX20_CONSTEXPR
1332 insert(const_iterator __position, size_type __n,
const bool& __x)
1334 difference_type __offset = __position -
cbegin();
1335 _M_fill_insert(__position._M_const_cast(), __n, __x);
1336 return begin() + __offset;
1340 insert(iterator __position, size_type __n,
const bool& __x)
1341 { _M_fill_insert(__position, __n, __x); }
1344 #if __cplusplus >= 201103L 1345 _GLIBCXX20_CONSTEXPR
1348 {
return this->
insert(__p, __l.begin(), __l.end()); }
1351 #if __glibcxx_containers_ranges // C++ >= 23 1360 template<__detail::__container_compatible_range<
bool> _Rg>
1362 insert_range(const_iterator __pos, _Rg&& __rg)
1364 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1371 this->_M_impl._M_finish
1372 + difference_type(__n));
1373 ranges::copy(__rg, __pos._M_const_cast());
1374 this->_M_impl._M_finish += difference_type(__n);
1375 return __pos._M_const_cast();
1379 const size_type __len =
1380 _M_check_len(__n,
"vector<bool>::insert_range");
1381 const iterator __begin =
begin(), __end =
end();
1382 _Bit_pointer __q = this->_M_allocate(__len);
1384 iterator __i = _M_copy_aligned(__begin,
1385 __pos._M_const_cast(),
1387 iterator __j = ranges::copy(__rg, __i).out;
1388 iterator __finish = std::copy(__pos._M_const_cast(),
1390 this->_M_deallocate();
1391 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
1392 this->_M_impl._M_start = __start;
1393 this->_M_impl._M_finish = __finish;
1398 return __pos._M_const_cast();
1401 return insert_range(__pos,
1402 vector(from_range, __rg, get_allocator()));
1409 template<__detail::__container_compatible_range<
bool> _Rg>
1411 append_range(_Rg&& __rg)
1416 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1425 const auto __sz =
size();
1426 const auto __capacity =
capacity();
1427 if ((__capacity - __sz) >= __n)
1429 this->_M_impl._M_finish
1430 = ranges::copy(std::forward<_Rg>(__rg),
end()).out;
1434 vector __tmp(get_allocator());
1435 __tmp.
reserve(_M_check_len(__n,
"vector::append_range"));
1436 __tmp._M_impl._M_finish
1438 __tmp._M_impl._M_finish
1439 = ranges::copy(std::forward<_Rg>(__rg), __tmp.
end()).out;
1449 __first != __last && __free > 0;
1450 ++__first, (void) --__free)
1451 emplace_back(*__first);
1453 if (__first == __last)
1457 ranges::subrange __rest(
std::move(__first), __last);
1458 vector __tmp(from_range, __rest, get_allocator());
1462 #endif // containers_ranges 1464 _GLIBCXX20_CONSTEXPR
1467 { --this->_M_impl._M_finish; }
1469 _GLIBCXX20_CONSTEXPR
1471 #if __cplusplus >= 201103L 1472 erase(const_iterator __position)
1474 erase(iterator __position)
1476 {
return _M_erase(__position._M_const_cast()); }
1478 _GLIBCXX20_CONSTEXPR
1480 #if __cplusplus >= 201103L 1481 erase(const_iterator __first, const_iterator __last)
1483 erase(iterator __first, iterator __last)
1485 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1487 _GLIBCXX20_CONSTEXPR
1489 resize(size_type __new_size,
bool __x =
bool())
1491 if (__new_size <
size())
1492 _M_erase_at_end(
begin() + difference_type(__new_size));
1497 #if __cplusplus >= 201103L 1498 _GLIBCXX20_CONSTEXPR
1501 { _M_shrink_to_fit(); }
1504 _GLIBCXX20_CONSTEXPR
1506 flip() _GLIBCXX_NOEXCEPT
1508 _Bit_type *
const __end = this->_M_impl._M_end_addr();
1509 for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p)
1513 _GLIBCXX20_CONSTEXPR
1515 clear() _GLIBCXX_NOEXCEPT
1516 { _M_erase_at_end(
begin()); }
1518 #if __cplusplus >= 201103L 1519 template<
typename... _Args>
1520 #if __cplusplus > 201402L 1521 _GLIBCXX20_CONSTEXPR
1526 emplace_back(_Args&&... __args)
1528 push_back(
bool(std::forward<_Args>(__args)...));
1529 #if __cplusplus > 201402L 1534 template<
typename... _Args>
1535 _GLIBCXX20_CONSTEXPR
1537 emplace(const_iterator __pos, _Args&&... __args)
1538 {
return insert(__pos,
bool(std::forward<_Args>(__args)...)); }
1543 _GLIBCXX20_CONSTEXPR
1545 _M_copy_aligned(const_iterator __first, const_iterator __last,
1548 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
1549 return std::copy(const_iterator(__last._M_p, 0), __last,
1553 _GLIBCXX20_CONSTEXPR
1555 _M_initialize(size_type __n)
1558 _GLIBCXX_DEBUG_ASSERT(__n <= (
size_t)-_S_word_bit);
1562 _Bit_pointer __q = this->_M_allocate(__n);
1563 this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1565 this->_M_impl._M_start = __start;
1566 this->_M_impl._M_finish = __start + difference_type(__n);
1570 template<
typename _SizeT>
1571 _GLIBCXX20_CONSTEXPR
1573 _M_check_and_initialize(_SizeT __n)
1576 __throw_length_error(
1577 __N(
"Cannot create std::vector<bool> larger than max_size()"));
1578 _M_initialize(static_cast<size_type>(__n));
1581 _GLIBCXX20_CONSTEXPR
1583 _M_initialize_value(
bool __x) _GLIBCXX_NOEXCEPT
1585 if (_Bit_type* __p = this->_M_impl._M_start._M_p)
1586 __fill_bvector_n(__p, this->_M_impl._M_end_addr() - __p, __x);
1589 _GLIBCXX20_CONSTEXPR
1591 _M_reallocate(size_type __n);
1593 #if __cplusplus >= 201103L 1594 _GLIBCXX20_CONSTEXPR
1599 #if __cplusplus < 201103L 1602 template<
typename _Integer>
1604 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1606 _M_check_and_initialize(static_cast<size_type>(__n));
1607 _M_initialize_value(__x);
1610 template<
typename _InputIterator>
1612 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1614 { _M_initialize_range(__first, __last,
1618 template<
typename _InputIterator>
1619 _GLIBCXX20_CONSTEXPR
1621 _M_initialize_range(_InputIterator __first, _InputIterator __last,
1624 for (; __first != __last; ++__first)
1628 template<
typename _ForwardIterator>
1629 _GLIBCXX20_CONSTEXPR
1631 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
1635 std::copy(__first, __last,
begin());
1638 #if __cplusplus < 201103L 1641 template<
typename _Integer>
1643 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1644 { _M_fill_assign(__n, __val); }
1646 template<
class _InputIterator>
1648 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1653 _GLIBCXX20_CONSTEXPR
1655 _M_fill_assign(
size_t __n,
bool __x)
1659 _M_initialize_value(__x);
1664 _M_erase_at_end(
begin() + __n);
1665 _M_initialize_value(__x);
1669 template<
typename _InputIterator>
1670 _GLIBCXX20_CONSTEXPR
1672 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1675 iterator __cur =
begin();
1676 for (; __first != __last && __cur !=
end(); ++__cur, (void)++__first)
1678 if (__first == __last)
1679 _M_erase_at_end(__cur);
1684 template<
typename _ForwardIterator>
1685 _GLIBCXX20_CONSTEXPR
1687 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1692 _M_erase_at_end(std::copy(__first, __last,
begin()));
1695 _ForwardIterator __mid = __first;
1697 std::copy(__first, __mid,
begin());
1702 #if __cplusplus < 201103L 1705 template<
typename _Integer>
1707 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1709 { _M_fill_insert(__pos, __n, __x); }
1711 template<
typename _InputIterator>
1713 _M_insert_dispatch(iterator __pos,
1714 _InputIterator __first, _InputIterator __last,
1716 { _M_insert_range(__pos, __first, __last,
1720 _GLIBCXX20_CONSTEXPR
1722 _M_fill_insert(iterator __position, size_type __n,
bool __x);
1724 template<
typename _InputIterator>
1725 _GLIBCXX20_CONSTEXPR
1727 _M_insert_range(iterator __pos, _InputIterator __first,
1730 for (; __first != __last; ++__first)
1732 __pos =
insert(__pos, *__first);
1737 template<
typename _ForwardIterator>
1738 _GLIBCXX20_CONSTEXPR
1740 _M_insert_range(iterator __position, _ForwardIterator __first,
1743 _GLIBCXX20_CONSTEXPR
1745 _M_insert_aux(iterator __position,
bool __x);
1747 _GLIBCXX20_CONSTEXPR
1749 _M_check_len(size_type __n,
const char* __s)
const 1752 __throw_length_error(__N(__s));
1758 _GLIBCXX20_CONSTEXPR
1760 _M_erase_at_end(iterator __pos)
1761 { this->_M_impl._M_finish = __pos; }
1763 _GLIBCXX20_CONSTEXPR
1765 _M_erase(iterator __pos);
1767 _GLIBCXX20_CONSTEXPR
1769 _M_erase(iterator __first, iterator __last);
1777 #if __cplusplus >= 201103L 1778 void data() =
delete;
1784 _GLIBCXX_END_NAMESPACE_CONTAINER
1787 _GLIBCXX20_CONSTEXPR
1789 __fill_bvector(_Bit_type* __v,
unsigned int __first,
unsigned int __last,
1790 bool __x) _GLIBCXX_NOEXCEPT
1792 const _Bit_type __fmask = ~0ul << __first;
1793 const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last);
1794 const _Bit_type __mask = __fmask & __lmask;
1803 __attribute__((__nonnull__))
1804 _GLIBCXX20_CONSTEXPR
1806 __fill_bvector_n(_Bit_type* __p,
size_t __n,
bool __x) _GLIBCXX_NOEXCEPT
1808 #if __cpp_lib_is_constant_evaluated 1809 if (std::is_constant_evaluated())
1811 for (
size_t __i = 0; __i < __n; ++__i)
1812 __p[__i] = __x ? ~0ul : 0ul;
1816 __builtin_memset(__p, __x ? ~0 : 0, __n *
sizeof(_Bit_type));
1820 _GLIBCXX20_CONSTEXPR
1822 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator __first,
1823 _GLIBCXX_STD_C::_Bit_iterator __last,
const bool& __x)
1825 if (__first._M_p != __last._M_p)
1827 _Bit_type* __first_p = __first._M_p;
1828 if (__first._M_offset != 0)
1829 __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x);
1831 __fill_bvector_n(__first_p, __last._M_p - __first_p, __x);
1833 if (__last._M_offset != 0)
1834 __fill_bvector(__last._M_p, 0, __last._M_offset, __x);
1836 else if (__first._M_offset != __last._M_offset)
1837 __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x);
1840 #if __cplusplus >= 201103L 1843 template<
typename _Alloc>
1845 :
public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1848 operator()(
const _GLIBCXX_STD_C::vector<bool, _Alloc>&)
const noexcept;
1852 _GLIBCXX_END_NAMESPACE_VERSION
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
constexpr iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in vector before specified iterator.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
constexpr void clear() noexcept
constexpr size_type capacity() const noexcept
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
constexpr _Tp * data() noexcept
A standard container which offers fixed time access to individual elements in any order...
constexpr ~vector() noexcept
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr void assign(size_type __n, const value_type &__val)
Assigns a given value to a vector.
constexpr vector & operator=(const vector &__x)
Vector assignment operator.
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr void pop_back() noexcept
Removes last element.
constexpr void push_back(const value_type &__x)
Add data to the end of the vector.
constexpr complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
typename __detected_or_t< is_empty< _Alloc >, __equal, _Alloc >::type is_always_equal
Whether all instances of the allocator type compare equal.
constexpr iterator erase(const_iterator __position)
Remove element at given position.
constexpr complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
constexpr reference at(size_type __n)
Provides access to the data contained in the vector.
constexpr size_type max_size() const noexcept
constexpr size_type size() const noexcept
constexpr _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Copies the range [first,last) into result.
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
constexpr reverse_iterator rend() noexcept
vector()=default
Creates a vector with no elements.
constexpr allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
constexpr void shrink_to_fit()
constexpr const_iterator cend() const noexcept
constexpr const_iterator cbegin() const noexcept
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
constexpr bool empty() const noexcept
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
constexpr void reserve(size_type __n)
Attempt to preallocate enough memory for specified number of elements.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
ISO C++ entities toplevel namespace is std.
constexpr iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into vector before specified iterator.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr void swap(vector &__x) noexcept
Swaps data with another vector.
ptrdiff_t difference_type
Distance between iterators is represented as this type.
constexpr iterator begin() noexcept
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
constexpr reference operator[](size_type __n) noexcept
Subscript access to the data contained in the vector.
constexpr reverse_iterator rbegin() noexcept
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
Forward iterators support a superset of input iterator operations.
constexpr const_reverse_iterator crbegin() const noexcept
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr const_reverse_iterator crend() const noexcept
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
constexpr iterator end() noexcept
constexpr void _M_range_check(size_type __n) const
Safety check used only from at().
constexpr reference back() noexcept
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Primary class template hash.
Random-access iterators support a superset of bidirectional iterator operations.
Uniform interface to C++98 and C++11 allocators.
constexpr void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
constexpr reference front() noexcept
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.