57#define _STL_BVECTOR_H 1
59#if __cplusplus >= 201103L
64namespace std _GLIBCXX_VISIBILITY(default)
66_GLIBCXX_BEGIN_NAMESPACE_VERSION
67_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
69 typedef unsigned long _Bit_type;
70 enum { _S_word_bit = int(__CHAR_BIT__ *
sizeof(_Bit_type)) };
77 _Bit_reference(_Bit_type * __x, _Bit_type __y)
78 : _M_p(__x), _M_mask(__y) { }
80 _Bit_reference() _GLIBCXX_NOEXCEPT : _M_p(0), _M_mask(0) { }
82#if __cplusplus >= 201103L
83 _Bit_reference(
const _Bit_reference&) =
default;
86 operator bool() const _GLIBCXX_NOEXCEPT
87 {
return !!(*_M_p & _M_mask); }
90 operator=(
bool __x) _GLIBCXX_NOEXCEPT
100 operator=(
const _Bit_reference& __x) _GLIBCXX_NOEXCEPT
101 {
return *
this = bool(__x); }
104 operator==(
const _Bit_reference& __x)
const
105 {
return bool(*
this) == bool(__x); }
108 operator<(
const _Bit_reference& __x)
const
109 {
return !bool(*
this) && bool(__x); }
112 flip() _GLIBCXX_NOEXCEPT
113 { *_M_p ^= _M_mask; }
116#if __cplusplus >= 201103L
118 swap(_Bit_reference __x, _Bit_reference __y)
noexcept
126 swap(_Bit_reference __x,
bool& __y)
noexcept
134 swap(
bool& __x, _Bit_reference __y)
noexcept
142 struct _Bit_iterator_base
143 :
public std::iterator<std::random_access_iterator_tag, bool>
146 unsigned int _M_offset;
148 _Bit_iterator_base(_Bit_type * __x,
unsigned int __y)
149 : _M_p(__x), _M_offset(__y) { }
154 if (_M_offset++ ==
int(_S_word_bit) - 1)
164 if (_M_offset-- == 0)
166 _M_offset = int(_S_word_bit) - 1;
172 _M_incr(ptrdiff_t __i)
175 _M_p += __n / int(_S_word_bit);
176 __n = __n % int(_S_word_bit);
179 __n += int(_S_word_bit);
182 _M_offset =
static_cast<unsigned int>(__n);
186 operator==(
const _Bit_iterator_base& __i)
const
187 {
return _M_p == __i._M_p && _M_offset == __i._M_offset; }
190 operator<(
const _Bit_iterator_base& __i)
const
192 return _M_p < __i._M_p
193 || (_M_p == __i._M_p && _M_offset < __i._M_offset);
197 operator!=(
const _Bit_iterator_base& __i)
const
198 {
return !(*
this == __i); }
201 operator>(
const _Bit_iterator_base& __i)
const
202 {
return __i < *
this; }
205 operator<=(
const _Bit_iterator_base& __i)
const
206 {
return !(__i < *
this); }
209 operator>=(
const _Bit_iterator_base& __i)
const
210 {
return !(*
this < __i); }
214 operator-(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
216 return (
int(_S_word_bit) * (__x._M_p - __y._M_p)
217 + __x._M_offset - __y._M_offset);
220 struct _Bit_iterator :
public _Bit_iterator_base
222 typedef _Bit_reference reference;
223 typedef _Bit_reference* pointer;
224 typedef _Bit_iterator iterator;
226 _Bit_iterator() : _Bit_iterator_base(0, 0) { }
228 _Bit_iterator(_Bit_type * __x,
unsigned int __y)
229 : _Bit_iterator_base(__x, __y) { }
232 _M_const_cast()
const
237 {
return reference(_M_p, 1UL << _M_offset); }
249 iterator __tmp = *
this;
264 iterator __tmp = *
this;
286 iterator __tmp = *
this;
293 iterator __tmp = *
this;
299 {
return *(*
this + __i); }
303 operator+(ptrdiff_t __n,
const _Bit_iterator& __x)
304 {
return __x + __n; }
306 struct _Bit_const_iterator :
public _Bit_iterator_base
308 typedef bool reference;
309 typedef bool const_reference;
310 typedef const bool* pointer;
311 typedef _Bit_const_iterator const_iterator;
313 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
315 _Bit_const_iterator(_Bit_type * __x,
unsigned int __y)
316 : _Bit_iterator_base(__x, __y) { }
318 _Bit_const_iterator(
const _Bit_iterator& __x)
319 : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
322 _M_const_cast()
const
323 {
return _Bit_iterator(_M_p, _M_offset); }
327 {
return _Bit_reference(_M_p, 1UL << _M_offset); }
339 const_iterator __tmp = *
this;
354 const_iterator __tmp = *
this;
376 const_iterator __tmp = *
this;
383 const_iterator __tmp = *
this;
389 {
return *(*
this + __i); }
392 inline _Bit_const_iterator
393 operator+(ptrdiff_t __n,
const _Bit_const_iterator& __x)
394 {
return __x + __n; }
397 __fill_bvector(_Bit_type * __v,
398 unsigned int __first,
unsigned int __last,
bool __x)
400 const _Bit_type __fmask = ~0ul << __first;
401 const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last);
402 const _Bit_type __mask = __fmask & __lmask;
411 fill(_Bit_iterator __first, _Bit_iterator __last,
const bool& __x)
413 if (__first._M_p != __last._M_p)
415 _Bit_type* __first_p = __first._M_p;
416 if (__first._M_offset != 0)
417 __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x);
419 __builtin_memset(__first_p, __x ? ~0 : 0,
420 (__last._M_p - __first_p) * sizeof(_Bit_type));
422 if (__last._M_offset != 0)
423 __fill_bvector(__last._M_p, 0, __last._M_offset, __x);
425 else if (__first._M_offset != __last._M_offset)
426 __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x);
429 template<
typename _Alloc>
433 rebind<_Bit_type>::other _Bit_alloc_type;
436 typedef typename _Bit_alloc_traits::pointer _Bit_pointer;
438 struct _Bvector_impl_data
440 _Bit_iterator _M_start;
441 _Bit_iterator _M_finish;
442 _Bit_pointer _M_end_of_storage;
444 _Bvector_impl_data() _GLIBCXX_NOEXCEPT
445 : _M_start(), _M_finish(), _M_end_of_storage()
448#if __cplusplus >= 201103L
449 _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept
450 : _M_start(__x._M_start), _M_finish(__x._M_finish)
451 , _M_end_of_storage(__x._M_end_of_storage)
455 _M_move_data(_Bvector_impl_data&& __x)
noexcept
457 this->_M_start = __x._M_start;
458 this->_M_finish = __x._M_finish;
459 this->_M_end_of_storage = __x._M_end_of_storage;
465 _M_reset() _GLIBCXX_NOEXCEPT
467 _M_start = _M_finish = _Bit_iterator();
468 _M_end_of_storage = _Bit_pointer();
473 :
public _Bit_alloc_type,
public _Bvector_impl_data
476 _Bvector_impl() _GLIBCXX_NOEXCEPT_IF(
477 is_nothrow_default_constructible<_Bit_alloc_type>::value)
481 _Bvector_impl(
const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT
482 : _Bit_alloc_type(__a)
485#if __cplusplus >= 201103L
486 _Bvector_impl(_Bvector_impl&&) =
default;
490 _M_end_addr() const _GLIBCXX_NOEXCEPT
492 if (this->_M_end_of_storage)
499 typedef _Alloc allocator_type;
502 _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT
503 {
return this->_M_impl; }
505 const _Bit_alloc_type&
506 _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT
507 {
return this->_M_impl; }
510 get_allocator() const _GLIBCXX_NOEXCEPT
511 {
return allocator_type(_M_get_Bit_allocator()); }
513#if __cplusplus >= 201103L
514 _Bvector_base() =
default;
519 _Bvector_base(
const allocator_type& __a)
522#if __cplusplus >= 201103L
523 _Bvector_base(_Bvector_base&&) =
default;
527 { this->_M_deallocate(); }
530 _Bvector_impl _M_impl;
533 _M_allocate(
size_t __n)
539 if (_M_impl._M_start._M_p)
541 const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p;
543 _M_impl._M_end_of_storage - __n,
549#if __cplusplus >= 201103L
551 _M_move_data(_Bvector_base&& __x)
noexcept
552 { _M_impl._M_move_data(std::move(__x._M_impl)); }
557 {
return (__n +
int(_S_word_bit) - 1) / int(_S_word_bit); }
560_GLIBCXX_END_NAMESPACE_CONTAINER
561_GLIBCXX_END_NAMESPACE_VERSION
567namespace std _GLIBCXX_VISIBILITY(default)
569_GLIBCXX_BEGIN_NAMESPACE_VERSION
570_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
591 template<
typename _Alloc>
592 class vector<bool, _Alloc> :
protected _Bvector_base<_Alloc>
598#if __cplusplus >= 201103L
603 typedef bool value_type;
604 typedef size_t size_type;
606 typedef _Bit_reference reference;
607 typedef bool const_reference;
608 typedef _Bit_reference* pointer;
609 typedef const bool* const_pointer;
610 typedef _Bit_iterator iterator;
611 typedef _Bit_const_iterator const_iterator;
614 typedef _Alloc allocator_type;
618 {
return _Base::get_allocator(); }
621 using _Base::_M_allocate;
622 using _Base::_M_deallocate;
623 using _Base::_S_nword;
624 using _Base::_M_get_Bit_allocator;
627#if __cplusplus >= 201103L
634 vector(
const allocator_type& __a)
637#if __cplusplus >= 201103L
639 vector(size_type __n,
const allocator_type& __a = allocator_type())
643 vector(size_type __n,
const bool& __value,
644 const allocator_type& __a = allocator_type())
647 vector(size_type __n,
const bool& __value =
bool(),
648 const allocator_type& __a = allocator_type())
653 _M_initialize_value(__value);
657 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
659 _M_initialize(__x.
size());
660 _M_copy_aligned(__x.
begin(), __x.
end(),
this->_M_impl._M_start);
663#if __cplusplus >= 201103L
667 noexcept(_Bit_alloc_traits::_S_always_equal())
671 this->_M_move_data(std::move(__x));
674 _M_initialize(__x.
size());
683 _M_initialize(__x.
size());
684 _M_copy_aligned(__x.
begin(), __x.
end(),
this->_M_impl._M_start);
688 const allocator_type& __a = allocator_type())
691 _M_initialize_range(
__l.begin(),
__l.end(),
696#if __cplusplus >= 201103L
700 const allocator_type& __a = allocator_type())
702 { _M_initialize_dispatch(__first, __last, __false_type()); }
704 template<
typename _InputIterator>
706 const allocator_type& __a = allocator_type())
709 typedef typename std::__is_integer<_InputIterator>::__type
_Integral;
710 _M_initialize_dispatch(__first, __last,
_Integral());
721#if __cplusplus >= 201103L
722 if (_Bit_alloc_traits::_S_propagate_on_copy_assign())
724 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator())
726 this->_M_deallocate();
727 std::__alloc_on_copy(_M_get_Bit_allocator(),
728 __x._M_get_Bit_allocator());
729 _M_initialize(__x.
size());
732 std::__alloc_on_copy(_M_get_Bit_allocator(),
733 __x._M_get_Bit_allocator());
738 this->_M_deallocate();
739 _M_initialize(__x.
size());
741 this->_M_impl._M_finish = _M_copy_aligned(__x.
begin(), __x.
end(),
746#if __cplusplus >= 201103L
750 if (_Bit_alloc_traits::_S_propagate_on_move_assign()
751 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator())
753 this->_M_deallocate();
754 this->_M_move_data(std::move(__x));
755 std::__alloc_on_move(_M_get_Bit_allocator(),
756 __x._M_get_Bit_allocator());
762 this->_M_deallocate();
763 _M_initialize(__x.
size());
765 this->_M_impl._M_finish = _M_copy_aligned(__x.
begin(), __x.
end(),
785 assign(size_type __n,
const bool& __x)
786 { _M_fill_assign(__n, __x); }
788#if __cplusplus >= 201103L
795 template<
typename _InputIterator>
799 typedef typename std::__is_integer<_InputIterator>::__type
_Integral;
800 _M_assign_dispatch(__first, __last,
_Integral());
804#if __cplusplus >= 201103L
812 {
return iterator(this->_M_impl._M_start._M_p, 0); }
816 {
return const_iterator(this->_M_impl._M_start._M_p, 0); }
820 {
return this->_M_impl._M_finish; }
824 {
return this->_M_impl._M_finish; }
842#if __cplusplus >= 201103L
845 {
return const_iterator(this->_M_impl._M_start._M_p, 0); }
848 cend()
const noexcept
849 {
return this->_M_impl._M_finish; }
856 crend()
const noexcept
862 {
return size_type(
end() -
begin()); }
868 __gnu_cxx::__numeric_traits<difference_type>::__max
869 - int(_S_word_bit) + 1;
871 = _Bit_alloc_traits::max_size(_M_get_Bit_allocator());
878 {
return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
888 return *iterator(this->_M_impl._M_start._M_p
889 + __n /
int(_S_word_bit), __n %
int(_S_word_bit));
895 return *const_iterator(this->_M_impl._M_start._M_p
896 + __n /
int(_S_word_bit), __n %
int(_S_word_bit));
903 if (__n >= this->
size())
904 __throw_out_of_range_fmt(__N(
"vector<bool>::_M_range_check: __n "
905 "(which is %zu) >= this->size() "
916 at(size_type __n)
const
923 __throw_length_error(__N(
"vector::reserve"));
938 {
return *(
end() - 1); }
942 {
return *(
end() - 1); }
955 if (this->_M_impl._M_finish._M_p !=
this->_M_impl._M_end_addr())
956 *this->_M_impl._M_finish++ = __x;
958 _M_insert_aux(
end(), __x);
964 std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
965 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
966 std::swap(this->_M_impl._M_end_of_storage,
967 __x._M_impl._M_end_of_storage);
968 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(),
969 __x._M_get_Bit_allocator());
982#if __cplusplus >= 201103L
989 if (this->_M_impl._M_finish._M_p !=
this->_M_impl._M_end_addr()
991 *this->_M_impl._M_finish++ = __x;
993 _M_insert_aux(
__position._M_const_cast(), __x);
994 return begin() + __n;
997#if __cplusplus >= 201103L
1005 _M_insert_dispatch(
__position._M_const_cast(),
1006 __first, __last, __false_type());
1007 return begin() + __offset;
1010 template<
typename _InputIterator>
1015 typedef typename std::__is_integer<_InputIterator>::__type
_Integral;
1020#if __cplusplus >= 201103L
1025 _M_fill_insert(
__position._M_const_cast(), __n, __x);
1026 return begin() + __offset;
1034#if __cplusplus >= 201103L
1042 { --this->_M_impl._M_finish; }
1045#if __cplusplus >= 201103L
1050 {
return _M_erase(
__position._M_const_cast()); }
1053#if __cplusplus >= 201103L
1054 erase(const_iterator __first, const_iterator __last)
1056 erase(iterator __first, iterator __last)
1058 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1069#if __cplusplus >= 201103L
1072 { _M_shrink_to_fit(); }
1078 _Bit_type *
const __end = this->_M_impl._M_end_addr();
1079 for (
_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p)
1085 { _M_erase_at_end(
begin()); }
1087#if __cplusplus >= 201103L
1088 template<
typename...
_Args>
1089#if __cplusplus > 201402L
1097#if __cplusplus > 201402L
1102 template<
typename...
_Args>
1111 _M_copy_aligned(const_iterator __first, const_iterator __last,
1114 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
1115 return std::copy(const_iterator(__last._M_p, 0), __last,
1120 _M_initialize(size_type __n)
1125 this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1131 this->_M_impl._M_start = iterator(0, 0);
1133 this->_M_impl._M_finish = this->_M_impl._M_start +
difference_type(__n);
1138 _M_initialize_value(
bool __x)
1140 if (
_Bit_type* __p = this->_M_impl._M_start._M_p)
1142 (this->_M_impl._M_end_addr() - __p)
1147 _M_reallocate(size_type __n);
1149#if __cplusplus >= 201103L
1158 template<
typename _Integer>
1162 _M_initialize(
static_cast<size_type
>(__n));
1163 _M_initialize_value(__x);
1166 template<
typename _InputIterator>
1170 { _M_initialize_range(__first, __last,
1173 template<
typename _InputIterator>
1178 for (; __first != __last; ++__first)
1182 template<
typename _ForwardIterator>
1189 std::copy(__first, __last, this->_M_impl._M_start);
1192#if __cplusplus < 201103L
1195 template<
typename _Integer>
1198 { _M_fill_assign(__n, __val); }
1200 template<
class _InputIterator>
1208 _M_fill_assign(
size_t __n,
bool __x)
1212 _M_initialize_value(__x);
1217 _M_erase_at_end(
begin() + __n);
1218 _M_initialize_value(__x);
1222 template<
typename _InputIterator>
1230 if (__first == __last)
1231 _M_erase_at_end(
__cur);
1236 template<
typename _ForwardIterator>
1243 _M_erase_at_end(std::copy(__first, __last,
begin()));
1257 template<
typename _Integer>
1261 { _M_fill_insert(
__pos, __n, __x); }
1263 template<
typename _InputIterator>
1265 _M_insert_dispatch(iterator
__pos,
1268 { _M_insert_range(
__pos, __first, __last,
1272 _M_fill_insert(iterator
__position, size_type __n,
bool __x);
1274 template<
typename _InputIterator>
1279 for (; __first != __last; ++__first)
1286 template<
typename _ForwardIterator>
1292 _M_insert_aux(iterator
__position,
bool __x);
1295 _M_check_len(size_type __n,
const char*
__s)
const
1298 __throw_length_error(__N(
__s));
1305 _M_erase_at_end(iterator
__pos)
1306 { this->_M_impl._M_finish =
__pos; }
1309 _M_erase(iterator
__pos);
1312 _M_erase(iterator __first, iterator __last);
1315_GLIBCXX_END_NAMESPACE_CONTAINER
1316_GLIBCXX_END_NAMESPACE_VERSION
1319#if __cplusplus >= 201103L
1321namespace std _GLIBCXX_VISIBILITY(default)
1323_GLIBCXX_BEGIN_NAMESPACE_VERSION
1327 template<
typename _Alloc>
1329 :
public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1332 operator()(
const _GLIBCXX_STD_C::vector<bool, _Alloc>&)
const noexcept;
1335_GLIBCXX_END_NAMESPACE_VERSION
_GLIBCXX20_CONSTEXPR complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
_GLIBCXX20_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.
_GLIBCXX14_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.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Primary class template hash.
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.
_GLIBCXX_NODISCARD bool empty() const noexcept
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.
vector()=default
Creates a vector with no elements.
iterator erase(const_iterator __position)
Remove element at given position.
reverse_iterator rbegin() noexcept
const_reverse_iterator crbegin() const noexcept
reference front() noexcept
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
reverse_iterator rend() noexcept
void push_back(const value_type &__x)
Add data to the end of the vector.
size_type max_size() const noexcept
const_reverse_iterator crend() const noexcept
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.
void assign(size_type __n, const value_type &__val)
Assigns a given value to a vector.
void pop_back() noexcept
Removes last element.
vector & operator=(const vector &__x)
Vector assignment operator.
const_iterator cbegin() const noexcept
const_iterator cend() const noexcept
iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in vector before specified iterator.
iterator begin() noexcept
reference back() noexcept
iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into vector before specified iterator.
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.
Uniform interface to C++98 and C++11 allocators.
static void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
static _GLIBCXX_NODISCARD pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.