746 class vector<bool, _Alloc> :
protected _Bvector_base<_Alloc>
748 typedef _Bvector_base<_Alloc> _Base;
749 typedef typename _Base::_Bit_pointer _Bit_pointer;
750 typedef typename _Base::_Bit_alloc_traits _Bit_alloc_traits;
752#if __cplusplus >= 201103L
757 typedef bool value_type;
758 typedef size_t size_type;
759 typedef ptrdiff_t difference_type;
760 typedef _Bit_reference reference;
761 typedef bool const_reference;
762 typedef _Bit_reference* pointer;
763 typedef const bool* const_pointer;
764 typedef _Bit_iterator iterator;
765 typedef _Bit_const_iterator const_iterator;
768 typedef _Alloc allocator_type;
773 {
return _Base::get_allocator(); }
776 using _Base::_M_allocate;
777 using _Base::_M_deallocate;
778 using _Base::_S_nword;
779 using _Base::_M_get_Bit_allocator;
782#if __cplusplus >= 201103L
790 vector(
const allocator_type& __a) _GLIBCXX_NOEXCEPT
793#if __cplusplus >= 201103L
796 vector(size_type __n,
const allocator_type& __a = allocator_type())
801 vector(size_type __n,
const bool& __value,
802 const allocator_type& __a = allocator_type())
805 vector(size_type __n,
const bool& __value =
bool(),
806 const allocator_type& __a = allocator_type())
811 _M_initialize_value(__value);
816 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
818 const_iterator __xbegin = __x.
begin(), __xend = __x.
end();
819 _M_initialize(__x.
size());
820 _M_copy_aligned(__xbegin, __xend,
begin());
823#if __cplusplus >= 201103L
824 vector(vector&&) =
default;
840 _M_initialize(__x.
size());
841 _M_copy_aligned(__x.
begin(), __x.
end(), begin());
848 vector(vector&& __x,
const __type_identity_t<allocator_type>& __a)
849 noexcept(_Bit_alloc_traits::_S_always_equal())
855 vector(
const vector& __x,
const __type_identity_t<allocator_type>& __a)
858 _M_initialize(__x.
size());
859 _M_copy_aligned(__x.
begin(), __x.
end(), begin());
864 const allocator_type& __a = allocator_type())
867 _M_initialize_range(__l.begin(), __l.end(),
872#if __cplusplus >= 201103L
873 template<
typename _InputIterator,
874 typename = std::_RequireInputIter<_InputIterator>>
876 vector(_InputIterator __first, _InputIterator __last,
877 const allocator_type& __a = allocator_type())
880 _M_initialize_range(__first, __last,
884 template<
typename _InputIterator>
885 vector(_InputIterator __first, _InputIterator __last,
886 const allocator_type& __a = allocator_type())
890 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
891 _M_initialize_dispatch(__first, __last, _Integral());
895#if __glibcxx_ranges_to_container
900 template<__detail::__container_compatible_range<
bool> _Rg>
902 vector(from_range_t, _Rg&& __rg,
const _Alloc& __a = _Alloc())
905 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
907 _M_initialize(size_type(ranges::distance(__rg)));
908 ranges::copy(__rg,
begin());
912 auto __first = ranges::begin(__rg);
913 const auto __last = ranges::end(__rg);
914 for (; __first != __last; ++__first)
915 emplace_back(*__first);
921 ~vector() _GLIBCXX_NOEXCEPT { }
929#if __cplusplus >= 201103L
930 if (_Bit_alloc_traits::_S_propagate_on_copy_assign())
932 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator())
934 this->_M_deallocate();
935 std::__alloc_on_copy(_M_get_Bit_allocator(),
936 __x._M_get_Bit_allocator());
937 _M_initialize(__x.
size());
940 std::__alloc_on_copy(_M_get_Bit_allocator(),
941 __x._M_get_Bit_allocator());
944 if (__x.
size() > capacity())
946 this->_M_deallocate();
947 _M_initialize(__x.
size());
949 this->_M_impl._M_finish = _M_copy_aligned(__x.
begin(), __x.
end(),
954#if __cplusplus >= 201103L
957 operator=(vector&& __x)
noexcept(_Bit_alloc_traits::_S_nothrow_move())
959 if (_Bit_alloc_traits::_S_propagate_on_move_assign()
960 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator())
962 this->_M_deallocate();
964 std::__alloc_on_move(_M_get_Bit_allocator(),
965 __x._M_get_Bit_allocator());
969 if (__x.
size() > capacity())
971 this->_M_deallocate();
972 _M_initialize(__x.
size());
974 this->_M_impl._M_finish = _M_copy_aligned(__x.
begin(), __x.
end(),
985 this->
assign(__l.begin(), __l.end());
996 assign(size_type __n,
const bool& __x)
997 { _M_fill_assign(__n, __x); }
999#if __cplusplus >= 201103L
1000 template<
typename _InputIterator,
1001 typename = std::_RequireInputIter<_InputIterator>>
1002 _GLIBCXX20_CONSTEXPR
1004 assign(_InputIterator __first, _InputIterator __last)
1007 template<
typename _InputIterator>
1009 assign(_InputIterator __first, _InputIterator __last)
1012 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1013 _M_assign_dispatch(__first, __last, _Integral());
1017#if __cplusplus >= 201103L
1018 _GLIBCXX20_CONSTEXPR
1024#if __glibcxx_ranges_to_container
1029 template<__detail::__container_compatible_range<
bool> _Rg>
1031 assign_range(_Rg&& __rg)
1033 static_assert(assignable_from<bool&, ranges::range_reference_t<_Rg>>);
1039 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1041 begin() _GLIBCXX_NOEXCEPT
1042 {
return iterator(this->_M_impl._M_start._M_p, 0); }
1044 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1046 begin()
const _GLIBCXX_NOEXCEPT
1047 {
return const_iterator(this->_M_impl._M_start._M_p, 0); }
1049 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1051 end() _GLIBCXX_NOEXCEPT
1052 {
return this->_M_impl._M_finish; }
1054 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1056 end()
const _GLIBCXX_NOEXCEPT
1057 {
return this->_M_impl._M_finish; }
1059 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1061 rbegin() _GLIBCXX_NOEXCEPT
1062 {
return reverse_iterator(
end()); }
1064 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1065 const_reverse_iterator
1066 rbegin()
const _GLIBCXX_NOEXCEPT
1067 {
return const_reverse_iterator(
end()); }
1069 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1071 rend() _GLIBCXX_NOEXCEPT
1072 {
return reverse_iterator(
begin()); }
1074 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1075 const_reverse_iterator
1076 rend()
const _GLIBCXX_NOEXCEPT
1077 {
return const_reverse_iterator(
begin()); }
1079#if __cplusplus >= 201103L
1080 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1083 {
return const_iterator(this->_M_impl._M_start._M_p, 0); }
1085 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1087 cend()
const noexcept
1088 {
return this->_M_impl._M_finish; }
1090 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1091 const_reverse_iterator
1093 {
return const_reverse_iterator(
end()); }
1095 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1096 const_reverse_iterator
1097 crend()
const noexcept
1098 {
return const_reverse_iterator(
begin()); }
1101 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1103 size()
const _GLIBCXX_NOEXCEPT
1104 {
return size_type(
end() -
begin()); }
1106 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1110 const size_type __isize =
1111 __gnu_cxx::__numeric_traits<difference_type>::__max
1112 - int(_S_word_bit) + 1;
1113 const size_type __asize
1115 return (__asize <= __isize /
int(_S_word_bit)
1116 ? __asize *
int(_S_word_bit) : __isize);
1119 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1122 {
return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
1125 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1127 empty()
const _GLIBCXX_NOEXCEPT
1130 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1134 __glibcxx_requires_subscript(__n);
1135 return _Bit_reference (this->_M_impl._M_start._M_p
1136 + __n /
int(_S_word_bit),
1137 1UL << __n %
int(_S_word_bit));
1140 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1144 __glibcxx_requires_subscript(__n);
1145 return _Bit_reference (this->_M_impl._M_start._M_p
1146 + __n /
int(_S_word_bit),
1147 1UL << __n %
int(_S_word_bit));
1151 _GLIBCXX20_CONSTEXPR
1155 if (__n >= this->
size())
1156 __throw_out_of_range_fmt(__N(
"vector<bool>::_M_range_check: __n "
1157 "(which is %zu) >= this->size() "
1163 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1168 return (*
this)[__n];
1171 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1173 at(size_type __n)
const
1176 return (*
this)[__n];
1179 _GLIBCXX20_CONSTEXPR
1184 __throw_length_error(__N(
"vector::reserve"));
1189 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1193 __glibcxx_requires_nonempty();
1197 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1201 __glibcxx_requires_nonempty();
1205 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1209 __glibcxx_requires_nonempty();
1210 return *(
end() - 1);
1213 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1217 __glibcxx_requires_nonempty();
1218 return *(
end() - 1);
1221 _GLIBCXX20_CONSTEXPR
1225 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
1226 *this->_M_impl._M_finish++ = __x;
1228 _M_insert_aux(
end(), __x);
1231 _GLIBCXX20_CONSTEXPR
1233 swap(vector& __x) _GLIBCXX_NOEXCEPT
1235#if __cplusplus >= 201103L
1236 __glibcxx_assert(_Bit_alloc_traits::propagate_on_container_swap::value
1237 || _M_get_Bit_allocator() == __x._M_get_Bit_allocator());
1239 this->_M_impl._M_swap_data(__x._M_impl);
1240 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(),
1241 __x._M_get_Bit_allocator());
1245 _GLIBCXX20_CONSTEXPR
1247 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
1254 _GLIBCXX20_CONSTEXPR
1256#if __cplusplus >= 201103L
1257 insert(const_iterator __position,
const bool& __x)
1259 insert(iterator __position,
const bool& __x)
1262 const difference_type __n = __position -
begin();
1263 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()
1264 && __position == end())
1265 *this->_M_impl._M_finish++ = __x;
1267 _M_insert_aux(__position._M_const_cast(), __x);
1268 return begin() + __n;
1271#if _GLIBCXX_USE_DEPRECATED
1272 _GLIBCXX_DEPRECATED_SUGGEST(
"insert(position, false)")
1274 insert(const_iterator __position)
1275 {
return this->
insert(__position._M_const_cast(),
false); }
1278#if __cplusplus >= 201103L
1279 template<
typename _InputIterator,
1280 typename = std::_RequireInputIter<_InputIterator>>
1281 _GLIBCXX20_CONSTEXPR
1283 insert(const_iterator __position,
1284 _InputIterator __first, _InputIterator __last)
1286 difference_type __offset = __position -
cbegin();
1287 _M_insert_range(__position._M_const_cast(),
1290 return begin() + __offset;
1293 template<
typename _InputIterator>
1295 insert(iterator __position,
1296 _InputIterator __first, _InputIterator __last)
1299 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1300 _M_insert_dispatch(__position, __first, __last, _Integral());
1304#if __cplusplus >= 201103L
1305 _GLIBCXX20_CONSTEXPR
1307 insert(const_iterator __position, size_type __n,
const bool& __x)
1309 difference_type __offset = __position -
cbegin();
1310 _M_fill_insert(__position._M_const_cast(), __n, __x);
1311 return begin() + __offset;
1315 insert(iterator __position, size_type __n,
const bool& __x)
1316 { _M_fill_insert(__position, __n, __x); }
1319#if __cplusplus >= 201103L
1320 _GLIBCXX20_CONSTEXPR
1323 {
return this->
insert(__p, __l.begin(), __l.end()); }
1326#if __glibcxx_ranges_to_container
1331 template<__detail::__container_compatible_range<
bool> _Rg>
1333 insert_range(const_iterator __pos, _Rg&& __rg)
1335 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1337 if (
auto __n = size_type(ranges::distance(__rg)))
1341 std::copy_backward(__pos._M_const_cast(), end(),
1342 this->_M_impl._M_finish
1343 + difference_type(__n));
1344 auto __i = ranges::copy(__rg, __pos._M_const_cast()).out;
1345 this->_M_impl._M_finish += difference_type(__n);
1350 const size_type __len =
1351 _M_check_len(__n,
"vector<bool>::insert_range");
1352 const iterator __begin =
begin(), __end =
end();
1353 _Bit_pointer __q = this->_M_allocate(__len);
1355 iterator __i = _M_copy_aligned(__begin,
1356 __pos._M_const_cast(),
1358 __i = ranges::copy(__rg, __i).out;
1359 iterator __finish = std::copy(__pos._M_const_cast(),
1361 this->_M_deallocate();
1362 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
1363 this->_M_impl._M_start = __start;
1364 this->_M_impl._M_finish = __finish;
1369 return __pos._M_const_cast();
1372 return insert_range(__pos,
1380 template<__detail::__container_compatible_range<
bool> _Rg>
1382 append_range(_Rg&& __rg)
1384 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1386 reserve(
size() + size_type(ranges::distance(__rg)));
1387 this->_M_impl._M_finish = ranges::copy(__rg,
end()).out;
1391 auto __first = ranges::begin(__rg);
1392 const auto __last = ranges::end(__rg);
1393 size_type __n =
size();
1394 const size_type __cap =
capacity();
1395 for (; __first != __last && __n < __cap; ++__first, (void)++__n)
1396 emplace_back(*__first);
1397 if (__first != __last)
1406 _GLIBCXX20_CONSTEXPR
1409 { --this->_M_impl._M_finish; }
1411 _GLIBCXX20_CONSTEXPR
1413#if __cplusplus >= 201103L
1414 erase(const_iterator __position)
1416 erase(iterator __position)
1418 {
return _M_erase(__position._M_const_cast()); }
1420 _GLIBCXX20_CONSTEXPR
1422#if __cplusplus >= 201103L
1423 erase(const_iterator __first, const_iterator __last)
1425 erase(iterator __first, iterator __last)
1427 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1429 _GLIBCXX20_CONSTEXPR
1431 resize(size_type __new_size,
bool __x =
bool())
1433 if (__new_size <
size())
1434 _M_erase_at_end(
begin() + difference_type(__new_size));
1439#if __cplusplus >= 201103L
1440 _GLIBCXX20_CONSTEXPR
1443 { _M_shrink_to_fit(); }
1446 _GLIBCXX20_CONSTEXPR
1448 flip() _GLIBCXX_NOEXCEPT
1450 _Bit_type *
const __end = this->_M_impl._M_end_addr();
1451 for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p)
1455 _GLIBCXX20_CONSTEXPR
1457 clear() _GLIBCXX_NOEXCEPT
1458 { _M_erase_at_end(
begin()); }
1460#if __cplusplus >= 201103L
1461 template<
typename... _Args>
1462#if __cplusplus > 201402L
1463 _GLIBCXX20_CONSTEXPR
1468 emplace_back(_Args&&... __args)
1471#if __cplusplus > 201402L
1476 template<
typename... _Args>
1477 _GLIBCXX20_CONSTEXPR
1479 emplace(const_iterator __pos, _Args&&... __args)
1485 _GLIBCXX20_CONSTEXPR
1487 _M_copy_aligned(const_iterator __first, const_iterator __last,
1490 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
1491 return std::copy(const_iterator(__last._M_p, 0), __last,
1495 _GLIBCXX20_CONSTEXPR
1497 _M_initialize(size_type __n)
1501 _Bit_pointer __q = this->_M_allocate(__n);
1502 this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1504 this->_M_impl._M_start = __start;
1505 this->_M_impl._M_finish = __start + difference_type(__n);
1509 _GLIBCXX20_CONSTEXPR
1511 _M_initialize_value(
bool __x) _GLIBCXX_NOEXCEPT
1513 if (_Bit_type* __p = this->_M_impl._M_start._M_p)
1514 __fill_bvector_n(__p, this->_M_impl._M_end_addr() - __p, __x);
1517 _GLIBCXX20_CONSTEXPR
1519 _M_reallocate(size_type __n);
1521#if __cplusplus >= 201103L
1522 _GLIBCXX20_CONSTEXPR
1527#if __cplusplus < 201103L
1530 template<
typename _Integer>
1532 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1534 _M_initialize(
static_cast<size_type
>(__n));
1535 _M_initialize_value(__x);
1538 template<
typename _InputIterator>
1540 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1542 { _M_initialize_range(__first, __last,
1546 template<
typename _InputIterator>
1547 _GLIBCXX20_CONSTEXPR
1549 _M_initialize_range(_InputIterator __first, _InputIterator __last,
1552 for (; __first != __last; ++__first)
1556 template<
typename _ForwardIterator>
1557 _GLIBCXX20_CONSTEXPR
1559 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
1564 std::copy(__first, __last,
begin());
1567#if __cplusplus < 201103L
1570 template<
typename _Integer>
1572 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1573 { _M_fill_assign(__n, __val); }
1575 template<
class _InputIterator>
1577 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1582 _GLIBCXX20_CONSTEXPR
1584 _M_fill_assign(
size_t __n,
bool __x)
1588 _M_initialize_value(__x);
1593 _M_erase_at_end(
begin() + __n);
1594 _M_initialize_value(__x);
1598 template<
typename _InputIterator>
1599 _GLIBCXX20_CONSTEXPR
1601 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1604 iterator __cur =
begin();
1605 for (; __first != __last && __cur !=
end(); ++__cur, (void)++__first)
1607 if (__first == __last)
1608 _M_erase_at_end(__cur);
1613 template<
typename _ForwardIterator>
1614 _GLIBCXX20_CONSTEXPR
1616 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1621 _M_erase_at_end(std::copy(__first, __last,
begin()));
1624 _ForwardIterator __mid = __first;
1626 std::copy(__first, __mid,
begin());
1631#if __cplusplus < 201103L
1634 template<
typename _Integer>
1636 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1638 { _M_fill_insert(__pos, __n, __x); }
1640 template<
typename _InputIterator>
1642 _M_insert_dispatch(iterator __pos,
1643 _InputIterator __first, _InputIterator __last,
1645 { _M_insert_range(__pos, __first, __last,
1649 _GLIBCXX20_CONSTEXPR
1651 _M_fill_insert(iterator __position, size_type __n,
bool __x);
1653 template<
typename _InputIterator>
1654 _GLIBCXX20_CONSTEXPR
1656 _M_insert_range(iterator __pos, _InputIterator __first,
1659 for (; __first != __last; ++__first)
1661 __pos =
insert(__pos, *__first);
1666 template<
typename _ForwardIterator>
1667 _GLIBCXX20_CONSTEXPR
1669 _M_insert_range(iterator __position, _ForwardIterator __first,
1672 _GLIBCXX20_CONSTEXPR
1674 _M_insert_aux(iterator __position,
bool __x);
1676 _GLIBCXX20_CONSTEXPR
1678 _M_check_len(size_type __n,
const char* __s)
const
1681 __throw_length_error(__N(__s));
1687 _GLIBCXX20_CONSTEXPR
1689 _M_erase_at_end(iterator __pos)
1690 { this->_M_impl._M_finish = __pos; }
1692 _GLIBCXX20_CONSTEXPR
1694 _M_erase(iterator __pos);
1696 _GLIBCXX20_CONSTEXPR
1698 _M_erase(iterator __first, iterator __last);
1706#if __cplusplus >= 201103L
1707 void data() =
delete;