57#define _STL_BVECTOR_H 1
59#if __cplusplus >= 201103L
63namespace std _GLIBCXX_VISIBILITY(default)
65_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
67 typedef unsigned long _Bit_type;
68 enum { _S_word_bit = int(__CHAR_BIT__ *
sizeof(_Bit_type)) };
75 _Bit_reference(_Bit_type * __x, _Bit_type __y)
76 : _M_p(__x), _M_mask(__y) { }
78 _Bit_reference() _GLIBCXX_NOEXCEPT : _M_p(0), _M_mask(0) { }
80 operator bool() const _GLIBCXX_NOEXCEPT
81 {
return !!(*_M_p & _M_mask); }
84 operator=(
bool __x) _GLIBCXX_NOEXCEPT
94 operator=(
const _Bit_reference& __x) _GLIBCXX_NOEXCEPT
95 {
return *
this = bool(__x); }
98 operator==(
const _Bit_reference& __x)
const
99 {
return bool(*
this) == bool(__x); }
102 operator<(
const _Bit_reference& __x)
const
103 {
return !bool(*
this) && bool(__x); }
106 flip() _GLIBCXX_NOEXCEPT
107 { *_M_p ^= _M_mask; }
110#if __cplusplus >= 201103L
112 swap(_Bit_reference __x, _Bit_reference __y)
noexcept
120 swap(_Bit_reference __x,
bool& __y)
noexcept
128 swap(
bool& __x, _Bit_reference __y)
noexcept
136 struct _Bit_iterator_base
137 :
public std::iterator<std::random_access_iterator_tag, bool>
140 unsigned int _M_offset;
142 _Bit_iterator_base(_Bit_type * __x,
unsigned int __y)
143 : _M_p(__x), _M_offset(__y) { }
148 if (_M_offset++ ==
int(_S_word_bit) - 1)
158 if (_M_offset-- == 0)
160 _M_offset = int(_S_word_bit) - 1;
166 _M_incr(ptrdiff_t __i)
169 _M_p += __n / int(_S_word_bit);
170 __n = __n % int(_S_word_bit);
173 __n += int(_S_word_bit);
176 _M_offset =
static_cast<unsigned int>(__n);
180 operator==(
const _Bit_iterator_base& __i)
const
181 {
return _M_p == __i._M_p && _M_offset == __i._M_offset; }
184 operator<(
const _Bit_iterator_base& __i)
const
186 return _M_p < __i._M_p
187 || (_M_p == __i._M_p && _M_offset < __i._M_offset);
191 operator!=(
const _Bit_iterator_base& __i)
const
192 {
return !(*
this == __i); }
195 operator>(
const _Bit_iterator_base& __i)
const
196 {
return __i < *
this; }
199 operator<=(
const _Bit_iterator_base& __i)
const
200 {
return !(__i < *
this); }
203 operator>=(
const _Bit_iterator_base& __i)
const
204 {
return !(*
this < __i); }
208 operator-(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
210 return (
int(_S_word_bit) * (__x._M_p - __y._M_p)
211 + __x._M_offset - __y._M_offset);
214 struct _Bit_iterator :
public _Bit_iterator_base
216 typedef _Bit_reference reference;
217 typedef _Bit_reference* pointer;
218 typedef _Bit_iterator iterator;
220 _Bit_iterator() : _Bit_iterator_base(0, 0) { }
222 _Bit_iterator(_Bit_type * __x,
unsigned int __y)
223 : _Bit_iterator_base(__x, __y) { }
226 _M_const_cast()
const
231 {
return reference(_M_p, 1UL << _M_offset); }
243 iterator __tmp = *
this;
258 iterator __tmp = *
this;
280 iterator __tmp = *
this;
287 iterator __tmp = *
this;
293 {
return *(*
this + __i); }
297 operator+(ptrdiff_t __n,
const _Bit_iterator& __x)
298 {
return __x + __n; }
300 struct _Bit_const_iterator :
public _Bit_iterator_base
302 typedef bool reference;
303 typedef bool const_reference;
304 typedef const bool* pointer;
305 typedef _Bit_const_iterator const_iterator;
307 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
309 _Bit_const_iterator(_Bit_type * __x,
unsigned int __y)
310 : _Bit_iterator_base(__x, __y) { }
312 _Bit_const_iterator(
const _Bit_iterator& __x)
313 : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
316 _M_const_cast()
const
317 {
return _Bit_iterator(_M_p, _M_offset); }
321 {
return _Bit_reference(_M_p, 1UL << _M_offset); }
333 const_iterator __tmp = *
this;
348 const_iterator __tmp = *
this;
370 const_iterator __tmp = *
this;
377 const_iterator __tmp = *
this;
383 {
return *(*
this + __i); }
386 inline _Bit_const_iterator
387 operator+(ptrdiff_t __n,
const _Bit_const_iterator& __x)
388 {
return __x + __n; }
391 __fill_bvector(_Bit_iterator __first, _Bit_iterator __last,
bool __x)
393 for (; __first != __last; ++__first)
398 fill(_Bit_iterator __first, _Bit_iterator __last,
const bool& __x)
400 if (__first._M_p != __last._M_p)
402 std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0);
403 __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x);
404 __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x);
407 __fill_bvector(__first, __last, __x);
410 template<
typename _Alloc>
414 rebind<_Bit_type>::other _Bit_alloc_type;
417 typedef typename _Bit_alloc_traits::pointer _Bit_pointer;
420 :
public _Bit_alloc_type
422 _Bit_iterator _M_start;
423 _Bit_iterator _M_finish;
424 _Bit_pointer _M_end_of_storage;
427 : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage()
430 _Bvector_impl(
const _Bit_alloc_type& __a)
431 : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage()
434#if __cplusplus >= 201103L
435 _Bvector_impl(_Bit_alloc_type&& __a)
436 : _Bit_alloc_type(
std::move(__a)), _M_start(), _M_finish(),
442 _M_end_addr() const _GLIBCXX_NOEXCEPT
444 if (_M_end_of_storage)
451 typedef _Alloc allocator_type;
454 _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT
455 {
return *
static_cast<_Bit_alloc_type*
>(&this->_M_impl); }
457 const _Bit_alloc_type&
458 _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT
459 {
return *
static_cast<const _Bit_alloc_type*
>(&this->_M_impl); }
462 get_allocator() const _GLIBCXX_NOEXCEPT
463 {
return allocator_type(_M_get_Bit_allocator()); }
468 _Bvector_base(
const allocator_type& __a)
471#if __cplusplus >= 201103L
472 _Bvector_base(_Bvector_base&& __x) noexcept
473 : _M_impl(std::move(__x._M_get_Bit_allocator()))
475 this->_M_impl._M_start = __x._M_impl._M_start;
476 this->_M_impl._M_finish = __x._M_impl._M_finish;
477 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
478 __x._M_impl._M_start = _Bit_iterator();
479 __x._M_impl._M_finish = _Bit_iterator();
480 __x._M_impl._M_end_of_storage =
nullptr;
485 { this->_M_deallocate(); }
488 _Bvector_impl _M_impl;
491 _M_allocate(
size_t __n)
497 if (_M_impl._M_start._M_p)
499 const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p;
501 _M_impl._M_end_of_storage - __n,
508 {
return (__n +
int(_S_word_bit) - 1) / int(_S_word_bit); }
511_GLIBCXX_END_NAMESPACE_CONTAINER
517namespace std _GLIBCXX_VISIBILITY(default)
519_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
540template<
typename _Alloc>
541 class vector<bool, _Alloc> :
protected _Bvector_base<_Alloc>
547#if __cplusplus >= 201103L
548 template<
typename>
friend struct hash;
552 typedef bool value_type;
553 typedef size_t size_type;
555 typedef _Bit_reference reference;
556 typedef bool const_reference;
557 typedef _Bit_reference* pointer;
558 typedef const bool* const_pointer;
559 typedef _Bit_iterator iterator;
560 typedef _Bit_const_iterator const_iterator;
563 typedef _Alloc allocator_type;
566 {
return _Base::get_allocator(); }
569 using _Base::_M_allocate;
570 using _Base::_M_deallocate;
571 using _Base::_S_nword;
572 using _Base::_M_get_Bit_allocator;
576#if __cplusplus >= 201103L
582 vector(
const allocator_type& __a)
585#if __cplusplus >= 201103L
587 vector(size_type __n,
const allocator_type& __a = allocator_type())
591 vector(size_type __n,
const bool& __value,
592 const allocator_type& __a = allocator_type())
596 std::fill(this->_M_impl._M_start._M_p,
this->_M_impl._M_end_addr(),
601 vector(size_type __n,
const bool& __value =
bool(),
602 const allocator_type& __a = allocator_type())
606 std::fill(this->_M_impl._M_start._M_p,
this->_M_impl._M_end_addr(),
612 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
614 _M_initialize(__x.
size());
615 _M_copy_aligned(__x.
begin(), __x.
end(),
this->_M_impl._M_start);
618#if __cplusplus >= 201103L
620 : _Base(std::move(__x)) { }
623 noexcept(_Bit_alloc_traits::_S_always_equal())
628 this->_M_impl._M_start = __x._M_impl._M_start;
629 this->_M_impl._M_finish = __x._M_impl._M_finish;
630 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
631 __x._M_impl._M_start = _Bit_iterator();
632 __x._M_impl._M_finish = _Bit_iterator();
633 __x._M_impl._M_end_of_storage =
nullptr;
637 _M_initialize(__x.
size());
646 _M_initialize(__x.
size());
647 _M_copy_aligned(__x.
begin(), __x.
end(),
this->_M_impl._M_start);
651 const allocator_type& __a = allocator_type())
654 _M_initialize_range(
__l.begin(),
__l.end(),
659#if __cplusplus >= 201103L
663 const allocator_type& __a = allocator_type())
665 { _M_initialize_dispatch(__first, __last, __false_type()); }
667 template<
typename _InputIterator>
669 const allocator_type& __a = allocator_type())
672 typedef typename std::__is_integer<_InputIterator>::__type
_Integral;
673 _M_initialize_dispatch(__first, __last,
_Integral());
684#if __cplusplus >= 201103L
685 if (_Bit_alloc_traits::_S_propagate_on_copy_assign())
687 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator())
689 this->_M_deallocate();
690 std::__alloc_on_copy(_M_get_Bit_allocator(),
691 __x._M_get_Bit_allocator());
692 _M_initialize(__x.
size());
695 std::__alloc_on_copy(_M_get_Bit_allocator(),
696 __x._M_get_Bit_allocator());
701 this->_M_deallocate();
702 _M_initialize(__x.
size());
704 this->_M_impl._M_finish = _M_copy_aligned(__x.
begin(), __x.
end(),
709#if __cplusplus >= 201103L
713 if (_Bit_alloc_traits::_S_propagate_on_move_assign()
714 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator())
716 this->_M_deallocate();
717 this->_M_impl._M_start = __x._M_impl._M_start;
718 this->_M_impl._M_finish = __x._M_impl._M_finish;
719 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
720 __x._M_impl._M_start = _Bit_iterator();
721 __x._M_impl._M_finish = _Bit_iterator();
722 __x._M_impl._M_end_of_storage =
nullptr;
723 std::__alloc_on_move(_M_get_Bit_allocator(),
724 __x._M_get_Bit_allocator());
730 this->_M_deallocate();
731 _M_initialize(__x.
size());
733 this->_M_impl._M_finish = _M_copy_aligned(__x.
begin(), __x.
end(),
753 assign(size_type __n,
const bool& __x)
754 { _M_fill_assign(__n, __x); }
756#if __cplusplus >= 201103L
761 { _M_assign_dispatch(__first, __last, __false_type()); }
763 template<
typename _InputIterator>
767 typedef typename std::__is_integer<_InputIterator>::__type
_Integral;
768 _M_assign_dispatch(__first, __last,
_Integral());
772#if __cplusplus >= 201103L
775 { this->
assign(__l.begin(),
__l.end()); }
780 {
return this->_M_impl._M_start; }
784 {
return this->_M_impl._M_start; }
788 {
return this->_M_impl._M_finish; }
792 {
return this->_M_impl._M_finish; }
810#if __cplusplus >= 201103L
813 {
return this->_M_impl._M_start; }
816 cend()
const noexcept
817 {
return this->_M_impl._M_finish; }
824 crend()
const noexcept
830 {
return size_type(
end() -
begin()); }
836 __gnu_cxx::__numeric_traits<difference_type>::__max
837 - int(_S_word_bit) + 1;
839 = _Bit_alloc_traits::max_size(_M_get_Bit_allocator());
846 {
return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
856 return *iterator(this->_M_impl._M_start._M_p
857 + __n /
int(_S_word_bit), __n %
int(_S_word_bit));
863 return *const_iterator(this->_M_impl._M_start._M_p
864 + __n /
int(_S_word_bit), __n %
int(_S_word_bit));
871 if (__n >= this->
size())
872 __throw_out_of_range_fmt(__N(
"vector<bool>::_M_range_check: __n "
873 "(which is %zu) >= this->size() "
884 at(size_type __n)
const
891 __throw_length_error(__N(
"vector::reserve"));
906 {
return *(
end() - 1); }
910 {
return *(
end() - 1); }
923 if (this->_M_impl._M_finish._M_p !=
this->_M_impl._M_end_addr())
924 *this->_M_impl._M_finish++ = __x;
926 _M_insert_aux(
end(), __x);
932 std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
933 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
934 std::swap(this->_M_impl._M_end_of_storage,
935 __x._M_impl._M_end_of_storage);
936 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(),
937 __x._M_get_Bit_allocator());
950#if __cplusplus >= 201103L
957 if (this->_M_impl._M_finish._M_p !=
this->_M_impl._M_end_addr()
959 *this->_M_impl._M_finish++ = __x;
961 _M_insert_aux(
__position._M_const_cast(), __x);
962 return begin() + __n;
965#if __cplusplus >= 201103L
973 _M_insert_dispatch(
__position._M_const_cast(),
974 __first, __last, __false_type());
975 return begin() + __offset;
978 template<
typename _InputIterator>
983 typedef typename std::__is_integer<_InputIterator>::__type
_Integral;
988#if __cplusplus >= 201103L
993 _M_fill_insert(
__position._M_const_cast(), __n, __x);
994 return begin() + __offset;
1002#if __cplusplus >= 201103L
1010 { --this->_M_impl._M_finish; }
1013#if __cplusplus >= 201103L
1018 {
return _M_erase(
__position._M_const_cast()); }
1021#if __cplusplus >= 201103L
1022 erase(const_iterator __first, const_iterator __last)
1024 erase(iterator __first, iterator __last)
1026 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1037#if __cplusplus >= 201103L
1040 { _M_shrink_to_fit(); }
1046 _Bit_type *
const __end = this->_M_impl._M_end_addr();
1047 for (
_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p)
1053 { _M_erase_at_end(
begin()); }
1055#if __cplusplus >= 201103L
1056 template<
typename...
_Args>
1061 template<
typename...
_Args>
1070 _M_copy_aligned(const_iterator __first, const_iterator __last,
1074 return std::copy(const_iterator(__last._M_p, 0), __last,
1079 _M_initialize(size_type __n)
1084 this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1090 this->_M_impl._M_start = iterator(0, 0);
1092 this->_M_impl._M_finish = this->_M_impl._M_start +
difference_type(__n);
1096 _M_reallocate(size_type __n);
1098#if __cplusplus >= 201103L
1107 template<
typename _Integer>
1111 _M_initialize(
static_cast<size_type
>(__n));
1112 std::fill(this->_M_impl._M_start._M_p,
1113 this->_M_impl._M_end_addr(), __x ? ~0 : 0);
1116 template<
typename _InputIterator>
1120 { _M_initialize_range(__first, __last,
1123 template<
typename _InputIterator>
1128 for (; __first != __last; ++__first)
1132 template<
typename _ForwardIterator>
1139 std::copy(__first, __last, this->_M_impl._M_start);
1144 template<
typename _Integer>
1147 { _M_fill_assign(__n, __val); }
1149 template<
class _InputIterator>
1156 _M_fill_assign(
size_t __n,
bool __x)
1160 std::fill(this->_M_impl._M_start._M_p,
1161 this->_M_impl._M_end_addr(), __x ? ~0 : 0);
1166 _M_erase_at_end(
begin() + __n);
1167 std::fill(this->_M_impl._M_start._M_p,
1168 this->_M_impl._M_end_addr(), __x ? ~0 : 0);
1172 template<
typename _InputIterator>
1178 for (; __first != __last &&
__cur !=
end(); ++
__cur, ++__first)
1180 if (__first == __last)
1181 _M_erase_at_end(
__cur);
1186 template<
typename _ForwardIterator>
1193 _M_erase_at_end(std::copy(__first, __last,
begin()));
1207 template<
typename _Integer>
1211 { _M_fill_insert(
__pos, __n, __x); }
1213 template<
typename _InputIterator>
1215 _M_insert_dispatch(iterator
__pos,
1218 { _M_insert_range(
__pos, __first, __last,
1222 _M_fill_insert(iterator
__position, size_type __n,
bool __x);
1224 template<
typename _InputIterator>
1229 for (; __first != __last; ++__first)
1236 template<
typename _ForwardIterator>
1242 _M_insert_aux(iterator
__position,
bool __x);
1245 _M_check_len(size_type __n,
const char*
__s)
const
1248 __throw_length_error(__N(
__s));
1255 _M_erase_at_end(iterator
__pos)
1256 { this->_M_impl._M_finish =
__pos; }
1259 _M_erase(iterator
__pos);
1262 _M_erase(iterator __first, iterator __last);
1268#if __cplusplus >= 201103L
1272namespace std _GLIBCXX_VISIBILITY(default)
1274_GLIBCXX_BEGIN_NAMESPACE_VERSION
1278 template<
typename _Alloc>
1280 :
public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1283 operator()(
const _GLIBCXX_STD_C::vector<bool, _Alloc>&)
const noexcept;
1286_GLIBCXX_END_NAMESPACE_VERSION
complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
ISO C++ entities toplevel namespace is std.
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
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.
void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
reference at(size_type __n)
Provides access to the data contained in the vector.
iterator erase(const_iterator __position)
Remove element at given position.
reverse_iterator rbegin() noexcept
bool empty() const noexcept
const_reverse_iterator crbegin() const noexcept
iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in vector before specified iterator.
reference front() noexcept
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
reverse_iterator rend() noexcept
vector() noexcept(is_nothrow_default_constructible< _Alloc >::value)
Creates a vector with no elements.
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 swap(vector &__x) noexcept
Swaps data with another vector.
void pop_back() noexcept
Removes last element.
vector & operator=(const vector &__x)
Vector assignment operator.
const_iterator cbegin() const noexcept
const_iterator cend() const noexcept
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 pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
static void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.