1// vector<bool> specialization -*- C++ -*-
2
3// Copyright (C) 2001-2021 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996-1999
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_bvector.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{vector}
54 */
55
56#ifndef _STL_BVECTOR_H
57#define _STL_BVECTOR_H 1
58
59#if __cplusplus >= 201103L
60#include <initializer_list>
61#include <bits/functional_hash.h>
62#endif
63
64namespace std _GLIBCXX_VISIBILITY(default)
65{
66_GLIBCXX_BEGIN_NAMESPACE_VERSION
67_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
68
69 typedef unsigned long _Bit_type;
70 enum { _S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type)) };
71
72 struct _Bit_reference
73 {
74 _Bit_type * _M_p;
75 _Bit_type _M_mask;
76
77 _Bit_reference(_Bit_type * __x, _Bit_type __y)
78 : _M_p(__x), _M_mask(__y) { }
79
80 _Bit_reference() _GLIBCXX_NOEXCEPT : _M_p(0), _M_mask(0) { }
81
82#if __cplusplus >= 201103L
83 _Bit_reference(const _Bit_reference&) = default;
84#endif
85
86 operator bool() const _GLIBCXX_NOEXCEPT
87 { return !!(*_M_p & _M_mask); }
88
89 _Bit_reference&
90 operator=(bool __x) _GLIBCXX_NOEXCEPT
91 {
92 if (__x)
93 *_M_p |= _M_mask;
94 else
95 *_M_p &= ~_M_mask;
96 return *this;
97 }
98
99 _Bit_reference&
100 operator=(const _Bit_reference& __x) _GLIBCXX_NOEXCEPT
101 { return *this = bool(__x); }
102
103 bool
104 operator==(const _Bit_reference& __x) const
105 { return bool(*this) == bool(__x); }
106
107 bool
108 operator<(const _Bit_reference& __x) const
109 { return !bool(*this) && bool(__x); }
110
111 void
112 flip() _GLIBCXX_NOEXCEPT
113 { *_M_p ^= _M_mask; }
114 };
115
116#if __cplusplus >= 201103L
117 inline void
118 swap(_Bit_reference __x, _Bit_reference __y) noexcept
119 {
120 bool __tmp = __x;
121 __x = __y;
122 __y = __tmp;
123 }
124
125 inline void
126 swap(_Bit_reference __x, bool& __y) noexcept
127 {
128 bool __tmp = __x;
129 __x = __y;
130 __y = __tmp;
131 }
132
133 inline void
134 swap(bool& __x, _Bit_reference __y) noexcept
135 {
136 bool __tmp = __x;
137 __x = __y;
138 __y = __tmp;
139 }
140#endif
141
142 struct _Bit_iterator_base
143 : public std::iterator<std::random_access_iterator_tag, bool>
144 {
145 _Bit_type * _M_p;
146 unsigned int _M_offset;
147
148 _Bit_iterator_base(_Bit_type * __x, unsigned int __y)
149 : _M_p(__x), _M_offset(__y) { }
150
151 void
152 _M_bump_up()
153 {
154 if (_M_offset++ == int(_S_word_bit) - 1)
155 {
156 _M_offset = 0;
157 ++_M_p;
158 }
159 }
160
161 void
162 _M_bump_down()
163 {
164 if (_M_offset-- == 0)
165 {
166 _M_offset = int(_S_word_bit) - 1;
167 --_M_p;
168 }
169 }
170
171 void
172 _M_incr(ptrdiff_t __i)
173 {
174 difference_type __n = __i + _M_offset;
175 _M_p += __n / int(_S_word_bit);
176 __n = __n % int(_S_word_bit);
177 if (__n < 0)
178 {
179 __n += int(_S_word_bit);
180 --_M_p;
181 }
182 _M_offset = static_cast<unsigned int>(__n);
183 }
184
185 friend _GLIBCXX20_CONSTEXPR bool
186 operator==(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
187 { return __x._M_p == __y._M_p && __x._M_offset == __y._M_offset; }
188
189#if __cpp_lib_three_way_comparison
190 friend constexpr strong_ordering
191 operator<=>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
192 noexcept
193 {
194 if (const auto __cmp = __x._M_p <=> __y._M_p; __cmp != 0)
195 return __cmp;
196 return __x._M_offset <=> __y._M_offset;
197 }
198#else
199 friend bool
200 operator<(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
201 {
202 return __x._M_p < __y._M_p
203 || (__x._M_p == __y._M_p && __x._M_offset < __y._M_offset);
204 }
205
206 friend bool
207 operator!=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
208 { return !(__x == __y); }
209
210 friend bool
211 operator>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
212 { return __y < __x; }
213
214 friend bool
215 operator<=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
216 { return !(__y < __x); }
217
218 friend bool
219 operator>=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
220 { return !(__x < __y); }
221#endif // three-way comparison
222
223 friend ptrdiff_t
224 operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
225 {
226 return (int(_S_word_bit) * (__x._M_p - __y._M_p)
227 + __x._M_offset - __y._M_offset);
228 }
229 };
230
231 struct _Bit_iterator : public _Bit_iterator_base
232 {
233 typedef _Bit_reference reference;
234#if __cplusplus > 201703L
235 typedef void pointer;
236#else
237 typedef _Bit_reference* pointer;
238#endif
239 typedef _Bit_iterator iterator;
240
241 _Bit_iterator() : _Bit_iterator_base(0, 0) { }
242
243 _Bit_iterator(_Bit_type * __x, unsigned int __y)
244 : _Bit_iterator_base(__x, __y) { }
245
246 iterator
247 _M_const_cast() const
248 { return *this; }
249
250 reference
251 operator*() const
252 { return reference(_M_p, 1UL << _M_offset); }
253
254 iterator&
255 operator++()
256 {
257 _M_bump_up();
258 return *this;
259 }
260
261 iterator
262 operator++(int)
263 {
264 iterator __tmp = *this;
265 _M_bump_up();
266 return __tmp;
267 }
268
269 iterator&
270 operator--()
271 {
272 _M_bump_down();
273 return *this;
274 }
275
276 iterator
277 operator--(int)
278 {
279 iterator __tmp = *this;
280 _M_bump_down();
281 return __tmp;
282 }
283
284 iterator&
285 operator+=(difference_type __i)
286 {
287 _M_incr(__i);
288 return *this;
289 }
290
291 iterator&
292 operator-=(difference_type __i)
293 {
294 *this += -__i;
295 return *this;
296 }
297
298 reference
299 operator[](difference_type __i) const
300 { return *(*this + __i); }
301
302 friend iterator
303 operator+(const iterator& __x, difference_type __n)
304 {
305 iterator __tmp = __x;
306 __tmp += __n;
307 return __tmp;
308 }
309
310 friend iterator
311 operator+(difference_type __n, const iterator& __x)
312 { return __x + __n; }
313
314 friend iterator
315 operator-(const iterator& __x, difference_type __n)
316 {
317 iterator __tmp = __x;
318 __tmp -= __n;
319 return __tmp;
320 }
321 };
322
323 struct _Bit_const_iterator : public _Bit_iterator_base
324 {
325 typedef bool reference;
326 typedef bool const_reference;
327#if __cplusplus > 201703L
328 typedef void pointer;
329#else
330 typedef const bool* pointer;
331#endif
332 typedef _Bit_const_iterator const_iterator;
333
334 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
335
336 _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
337 : _Bit_iterator_base(__x, __y) { }
338
339 _Bit_const_iterator(const _Bit_iterator& __x)
340 : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
341
342 _Bit_iterator
343 _M_const_cast() const
344 { return _Bit_iterator(_M_p, _M_offset); }
345
346 const_reference
347 operator*() const
348 { return _Bit_reference(_M_p, 1UL << _M_offset); }
349
350 const_iterator&
351 operator++()
352 {
353 _M_bump_up();
354 return *this;
355 }
356
357 const_iterator
358 operator++(int)
359 {
360 const_iterator __tmp = *this;
361 _M_bump_up();
362 return __tmp;
363 }
364
365 const_iterator&
366 operator--()
367 {
368 _M_bump_down();
369 return *this;
370 }
371
372 const_iterator
373 operator--(int)
374 {
375 const_iterator __tmp = *this;
376 _M_bump_down();
377 return __tmp;
378 }
379
380 const_iterator&
381 operator+=(difference_type __i)
382 {
383 _M_incr(__i);
384 return *this;
385 }
386
387 const_iterator&
388 operator-=(difference_type __i)
389 {
390 *this += -__i;
391 return *this;
392 }
393
394 const_reference
395 operator[](difference_type __i) const
396 { return *(*this + __i); }
397
398 friend const_iterator
399 operator+(const const_iterator& __x, difference_type __n)
400 {
401 const_iterator __tmp = __x;
402 __tmp += __n;
403 return __tmp;
404 }
405
406 friend const_iterator
407 operator-(const const_iterator& __x, difference_type __n)
408 {
409 const_iterator __tmp = __x;
410 __tmp -= __n;
411 return __tmp;
412 }
413
414 friend const_iterator
415 operator+(difference_type __n, const const_iterator& __x)
416 { return __x + __n; }
417 };
418
419 template<typename _Alloc>
420 struct _Bvector_base
421 {
422 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
423 rebind<_Bit_type>::other _Bit_alloc_type;
424 typedef typename __gnu_cxx::__alloc_traits<_Bit_alloc_type>
425 _Bit_alloc_traits;
426 typedef typename _Bit_alloc_traits::pointer _Bit_pointer;
427
428 struct _Bvector_impl_data
429 {
430#if !_GLIBCXX_INLINE_VERSION
431 _Bit_iterator _M_start;
432#else
433 // We don't need the offset field for the start, it's always zero.
434 struct {
435 _Bit_type* _M_p;
436 // Allow assignment from iterators (assume offset is zero):
437 void operator=(_Bit_iterator __it) { _M_p = __it._M_p; }
438 } _M_start;
439#endif
440 _Bit_iterator _M_finish;
441 _Bit_pointer _M_end_of_storage;
442
443 _Bvector_impl_data() _GLIBCXX_NOEXCEPT
444 : _M_start(), _M_finish(), _M_end_of_storage()
445 { }
446
447#if __cplusplus >= 201103L
448 _Bvector_impl_data(const _Bvector_impl_data&) = default;
449 _Bvector_impl_data&
450 operator=(const _Bvector_impl_data&) = default;
451
452 _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept
453 : _Bvector_impl_data(__x)
454 { __x._M_reset(); }
455
456 void
457 _M_move_data(_Bvector_impl_data&& __x) noexcept
458 {
459 *this = __x;
460 __x._M_reset();
461 }
462#endif
463
464 void
465 _M_reset() _GLIBCXX_NOEXCEPT
466 { *this = _Bvector_impl_data(); }
467
468 void
469 _M_swap_data(_Bvector_impl_data& __x) _GLIBCXX_NOEXCEPT
470 {
471 // Do not use std::swap(_M_start, __x._M_start), etc as it loses
472 // information used by TBAA.
473 std::swap(*this, __x);
474 }
475 };
476
477 struct _Bvector_impl
478 : public _Bit_alloc_type, public _Bvector_impl_data
479 {
480 _Bvector_impl() _GLIBCXX_NOEXCEPT_IF(
481 is_nothrow_default_constructible<_Bit_alloc_type>::value)
482 : _Bit_alloc_type()
483 { }
484
485 _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT
486 : _Bit_alloc_type(__a)
487 { }
488
489#if __cplusplus >= 201103L
490 // Not defaulted, to enforce noexcept(true) even when
491 // !is_nothrow_move_constructible<_Bit_alloc_type>.
492 _Bvector_impl(_Bvector_impl&& __x) noexcept
493 : _Bit_alloc_type(std::move(__x)), _Bvector_impl_data(std::move(__x))
494 { }
495
496 _Bvector_impl(_Bit_alloc_type&& __a, _Bvector_impl&& __x) noexcept
497 : _Bit_alloc_type(std::move(__a)), _Bvector_impl_data(std::move(__x))
498 { }
499#endif
500
501 _Bit_type*
502 _M_end_addr() const _GLIBCXX_NOEXCEPT
503 {
504 if (this->_M_end_of_storage)
505 return std::__addressof(this->_M_end_of_storage[-1]) + 1;
506 return 0;
507 }
508 };
509
510 public:
511 typedef _Alloc allocator_type;
512
513 _Bit_alloc_type&
514 _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT
515 { return this->_M_impl; }
516
517 const _Bit_alloc_type&
518 _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT
519 { return this->_M_impl; }
520
521 allocator_type
522 get_allocator() const _GLIBCXX_NOEXCEPT
523 { return allocator_type(_M_get_Bit_allocator()); }
524
525#if __cplusplus >= 201103L
526 _Bvector_base() = default;
527#else
528 _Bvector_base() { }
529#endif
530
531 _Bvector_base(const allocator_type& __a)
532 : _M_impl(__a) { }
533
534#if __cplusplus >= 201103L
535 _Bvector_base(_Bvector_base&&) = default;
536
537 _Bvector_base(_Bvector_base&& __x, const allocator_type& __a) noexcept
538 : _M_impl(_Bit_alloc_type(__a), std::move(__x._M_impl))
539 { }
540#endif
541
542 ~_Bvector_base()
543 { this->_M_deallocate(); }
544
545 protected:
546 _Bvector_impl _M_impl;
547
548 _Bit_pointer
549 _M_allocate(size_t __n)
550 { return _Bit_alloc_traits::allocate(_M_impl, _S_nword(__n)); }
551
552 void
553 _M_deallocate()
554 {
555 if (_M_impl._M_start._M_p)
556 {
557 const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p;
558 _Bit_alloc_traits::deallocate(_M_impl,
559 _M_impl._M_end_of_storage - __n,
560 __n);
561 _M_impl._M_reset();
562 }
563 }
564
565#if __cplusplus >= 201103L
566 void
567 _M_move_data(_Bvector_base&& __x) noexcept
568 { _M_impl._M_move_data(std::move(__x._M_impl)); }
569#endif
570
571 static size_t
572 _S_nword(size_t __n)
573 { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); }
574 };
575
576 /**
577 * @brief A specialization of vector for booleans which offers fixed time
578 * access to individual elements in any order.
579 *
580 * @ingroup sequences
581 *
582 * @tparam _Alloc Allocator type.
583 *
584 * Note that vector<bool> does not actually meet the requirements for being
585 * a container. This is because the reference and pointer types are not
586 * really references and pointers to bool. See DR96 for details. @see
587 * vector for function documentation.
588 *
589 * In some terminology a %vector can be described as a dynamic
590 * C-style array, it offers fast and efficient access to individual
591 * elements in any order and saves the user from worrying about
592 * memory and size allocation. Subscripting ( @c [] ) access is
593 * also provided as with C-style arrays.
594 */
595 template<typename _Alloc>
596 class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
597 {
598 typedef _Bvector_base<_Alloc> _Base;
599 typedef typename _Base::_Bit_pointer _Bit_pointer;
600 typedef typename _Base::_Bit_alloc_traits _Bit_alloc_traits;
601
602#if __cplusplus >= 201103L
603 friend struct std::hash<vector>;
604#endif
605
606 public:
607 typedef bool value_type;
608 typedef size_t size_type;
609 typedef ptrdiff_t difference_type;
610 typedef _Bit_reference reference;
611 typedef bool const_reference;
612 typedef _Bit_reference* pointer;
613 typedef const bool* const_pointer;
614 typedef _Bit_iterator iterator;
615 typedef _Bit_const_iterator const_iterator;
616 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
617 typedef std::reverse_iterator<iterator> reverse_iterator;
618 typedef _Alloc allocator_type;
619
620 allocator_type
621 get_allocator() const
622 { return _Base::get_allocator(); }
623
624 protected:
625 using _Base::_M_allocate;
626 using _Base::_M_deallocate;
627 using _Base::_S_nword;
628 using _Base::_M_get_Bit_allocator;
629
630 public:
631#if __cplusplus >= 201103L
632 vector() = default;
633#else
634 vector() { }
635#endif
636
637 explicit
638 vector(const allocator_type& __a)
639 : _Base(__a) { }
640
641#if __cplusplus >= 201103L
642 explicit
643 vector(size_type __n, const allocator_type& __a = allocator_type())
644 : vector(__n, false, __a)
645 { }
646
647 vector(size_type __n, const bool& __value,
648 const allocator_type& __a = allocator_type())
649#else
650 explicit
651 vector(size_type __n, const bool& __value = bool(),
652 const allocator_type& __a = allocator_type())
653#endif
654 : _Base(__a)
655 {
656 _M_initialize(__n);
657 _M_initialize_value(x: __value);
658 }
659
660 vector(const vector& __x)
661 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
662 {
663 _M_initialize(n: __x.size());
664 _M_copy_aligned(first: __x.begin(), last: __x.end(), result: begin());
665 }
666
667#if __cplusplus >= 201103L
668 vector(vector&&) = default;
669
670 private:
671 vector(vector&& __x, const allocator_type& __a, true_type) noexcept
672 : _Base(std::move(__x), __a)
673 { }
674
675 vector(vector&& __x, const allocator_type& __a, false_type)
676 : _Base(__a)
677 {
678 if (__x.get_allocator() == __a)
679 this->_M_move_data(std::move(__x));
680 else
681 {
682 _M_initialize(n: __x.size());
683 _M_copy_aligned(first: __x.begin(), last: __x.end(), result: begin());
684 __x.clear();
685 }
686 }
687
688 public:
689 vector(vector&& __x, const allocator_type& __a)
690 noexcept(_Bit_alloc_traits::_S_always_equal())
691 : vector(std::move(__x), __a,
692 typename _Bit_alloc_traits::is_always_equal{})
693 { }
694
695 vector(const vector& __x, const allocator_type& __a)
696 : _Base(__a)
697 {
698 _M_initialize(n: __x.size());
699 _M_copy_aligned(first: __x.begin(), last: __x.end(), result: begin());
700 }
701
702 vector(initializer_list<bool> __l,
703 const allocator_type& __a = allocator_type())
704 : _Base(__a)
705 {
706 _M_initialize_range(__l.begin(), __l.end(),
707 random_access_iterator_tag());
708 }
709#endif
710
711#if __cplusplus >= 201103L
712 template<typename _InputIterator,
713 typename = std::_RequireInputIter<_InputIterator>>
714 vector(_InputIterator __first, _InputIterator __last,
715 const allocator_type& __a = allocator_type())
716 : _Base(__a)
717 {
718 _M_initialize_range(__first, __last,
719 std::__iterator_category(__first));
720 }
721#else
722 template<typename _InputIterator>
723 vector(_InputIterator __first, _InputIterator __last,
724 const allocator_type& __a = allocator_type())
725 : _Base(__a)
726 {
727 // Check whether it's an integral type. If so, it's not an iterator.
728 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
729 _M_initialize_dispatch(__first, __last, _Integral());
730 }
731#endif
732
733 ~vector() _GLIBCXX_NOEXCEPT { }
734
735 vector&
736 operator=(const vector& __x)
737 {
738 if (&__x == this)
739 return *this;
740#if __cplusplus >= 201103L
741 if (_Bit_alloc_traits::_S_propagate_on_copy_assign())
742 {
743 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator())
744 {
745 this->_M_deallocate();
746 std::__alloc_on_copy(_M_get_Bit_allocator(),
747 __x._M_get_Bit_allocator());
748 _M_initialize(n: __x.size());
749 }
750 else
751 std::__alloc_on_copy(_M_get_Bit_allocator(),
752 __x._M_get_Bit_allocator());
753 }
754#endif
755 if (__x.size() > capacity())
756 {
757 this->_M_deallocate();
758 _M_initialize(n: __x.size());
759 }
760 this->_M_impl._M_finish = _M_copy_aligned(first: __x.begin(), last: __x.end(),
761 result: begin());
762 return *this;
763 }
764
765#if __cplusplus >= 201103L
766 vector&
767 operator=(vector&& __x) noexcept(_Bit_alloc_traits::_S_nothrow_move())
768 {
769 if (_Bit_alloc_traits::_S_propagate_on_move_assign()
770 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator())
771 {
772 this->_M_deallocate();
773 this->_M_move_data(std::move(__x));
774 std::__alloc_on_move(_M_get_Bit_allocator(),
775 __x._M_get_Bit_allocator());
776 }
777 else
778 {
779 if (__x.size() > capacity())
780 {
781 this->_M_deallocate();
782 _M_initialize(n: __x.size());
783 }
784 this->_M_impl._M_finish = _M_copy_aligned(first: __x.begin(), last: __x.end(),
785 result: begin());
786 __x.clear();
787 }
788 return *this;
789 }
790
791 vector&
792 operator=(initializer_list<bool> __l)
793 {
794 this->assign(__l.begin(), __l.end());
795 return *this;
796 }
797#endif
798
799 // assign(), a generalized assignment member function. Two
800 // versions: one that takes a count, and one that takes a range.
801 // The range version is a member template, so we dispatch on whether
802 // or not the type is an integer.
803 void
804 assign(size_type __n, const bool& __x)
805 { _M_fill_assign(__n, __x); }
806
807#if __cplusplus >= 201103L
808 template<typename _InputIterator,
809 typename = std::_RequireInputIter<_InputIterator>>
810 void
811 assign(_InputIterator __first, _InputIterator __last)
812 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
813#else
814 template<typename _InputIterator>
815 void
816 assign(_InputIterator __first, _InputIterator __last)
817 {
818 // Check whether it's an integral type. If so, it's not an iterator.
819 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
820 _M_assign_dispatch(__first, __last, _Integral());
821 }
822#endif
823
824#if __cplusplus >= 201103L
825 void
826 assign(initializer_list<bool> __l)
827 { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); }
828#endif
829
830 iterator
831 begin() _GLIBCXX_NOEXCEPT
832 { return iterator(this->_M_impl._M_start._M_p, 0); }
833
834 const_iterator
835 begin() const _GLIBCXX_NOEXCEPT
836 { return const_iterator(this->_M_impl._M_start._M_p, 0); }
837
838 iterator
839 end() _GLIBCXX_NOEXCEPT
840 { return this->_M_impl._M_finish; }
841
842 const_iterator
843 end() const _GLIBCXX_NOEXCEPT
844 { return this->_M_impl._M_finish; }
845
846 reverse_iterator
847 rbegin() _GLIBCXX_NOEXCEPT
848 { return reverse_iterator(end()); }
849
850 const_reverse_iterator
851 rbegin() const _GLIBCXX_NOEXCEPT
852 { return const_reverse_iterator(end()); }
853
854 reverse_iterator
855 rend() _GLIBCXX_NOEXCEPT
856 { return reverse_iterator(begin()); }
857
858 const_reverse_iterator
859 rend() const _GLIBCXX_NOEXCEPT
860 { return const_reverse_iterator(begin()); }
861
862#if __cplusplus >= 201103L
863 const_iterator
864 cbegin() const noexcept
865 { return const_iterator(this->_M_impl._M_start._M_p, 0); }
866
867 const_iterator
868 cend() const noexcept
869 { return this->_M_impl._M_finish; }
870
871 const_reverse_iterator
872 crbegin() const noexcept
873 { return const_reverse_iterator(end()); }
874
875 const_reverse_iterator
876 crend() const noexcept
877 { return const_reverse_iterator(begin()); }
878#endif
879
880 size_type
881 size() const _GLIBCXX_NOEXCEPT
882 { return size_type(end() - begin()); }
883
884 size_type
885 max_size() const _GLIBCXX_NOEXCEPT
886 {
887 const size_type __isize =
888 __gnu_cxx::__numeric_traits<difference_type>::__max
889 - int(_S_word_bit) + 1;
890 const size_type __asize
891 = _Bit_alloc_traits::max_size(_M_get_Bit_allocator());
892 return (__asize <= __isize / int(_S_word_bit)
893 ? __asize * int(_S_word_bit) : __isize);
894 }
895
896 size_type
897 capacity() const _GLIBCXX_NOEXCEPT
898 { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
899 - begin()); }
900
901 _GLIBCXX_NODISCARD bool
902 empty() const _GLIBCXX_NOEXCEPT
903 { return begin() == end(); }
904
905 reference
906 operator[](size_type __n)
907 { return begin()[__n]; }
908
909 const_reference
910 operator[](size_type __n) const
911 { return begin()[__n]; }
912
913 protected:
914 void
915 _M_range_check(size_type __n) const
916 {
917 if (__n >= this->size())
918 __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n "
919 "(which is %zu) >= this->size() "
920 "(which is %zu)"),
921 __n, this->size());
922 }
923
924 public:
925 reference
926 at(size_type __n)
927 { _M_range_check(__n); return (*this)[__n]; }
928
929 const_reference
930 at(size_type __n) const
931 { _M_range_check(__n); return (*this)[__n]; }
932
933 void
934 reserve(size_type __n)
935 {
936 if (__n > max_size())
937 __throw_length_error(__N("vector::reserve"));
938 if (capacity() < __n)
939 _M_reallocate(__n);
940 }
941
942 reference
943 front()
944 { return *begin(); }
945
946 const_reference
947 front() const
948 { return *begin(); }
949
950 reference
951 back()
952 { return *(end() - 1); }
953
954 const_reference
955 back() const
956 { return *(end() - 1); }
957
958 // _GLIBCXX_RESOLVE_LIB_DEFECTS
959 // DR 464. Suggestion for new member functions in standard containers.
960 // N.B. DR 464 says nothing about vector<bool> but we need something
961 // here due to the way we are implementing DR 464 in the debug-mode
962 // vector class.
963 void
964 data() _GLIBCXX_NOEXCEPT { }
965
966 void
967 push_back(bool __x)
968 {
969 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
970 *this->_M_impl._M_finish++ = __x;
971 else
972 _M_insert_aux(position: end(), __x);
973 }
974
975 void
976 swap(vector& __x) _GLIBCXX_NOEXCEPT
977 {
978#if __cplusplus >= 201103L
979 __glibcxx_assert(_Bit_alloc_traits::propagate_on_container_swap::value
980 || _M_get_Bit_allocator() == __x._M_get_Bit_allocator());
981#endif
982 this->_M_impl._M_swap_data(__x._M_impl);
983 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(),
984 __x._M_get_Bit_allocator());
985 }
986
987 // [23.2.5]/1, third-to-last entry in synopsis listing
988 static void
989 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
990 {
991 bool __tmp = __x;
992 __x = __y;
993 __y = __tmp;
994 }
995
996 iterator
997#if __cplusplus >= 201103L
998 insert(const_iterator __position, const bool& __x = bool())
999#else
1000 insert(iterator __position, const bool& __x = bool())
1001#endif
1002 {
1003 const difference_type __n = __position - begin();
1004 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()
1005 && __position == end())
1006 *this->_M_impl._M_finish++ = __x;
1007 else
1008 _M_insert_aux(position: __position._M_const_cast(), __x);
1009 return begin() + __n;
1010 }
1011
1012#if __cplusplus >= 201103L
1013 template<typename _InputIterator,
1014 typename = std::_RequireInputIter<_InputIterator>>
1015 iterator
1016 insert(const_iterator __position,
1017 _InputIterator __first, _InputIterator __last)
1018 {
1019 difference_type __offset = __position - cbegin();
1020 _M_insert_range(__position._M_const_cast(),
1021 __first, __last,
1022 std::__iterator_category(__first));
1023 return begin() + __offset;
1024 }
1025#else
1026 template<typename _InputIterator>
1027 void
1028 insert(iterator __position,
1029 _InputIterator __first, _InputIterator __last)
1030 {
1031 // Check whether it's an integral type. If so, it's not an iterator.
1032 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1033 _M_insert_dispatch(__position, __first, __last, _Integral());
1034 }
1035#endif
1036
1037#if __cplusplus >= 201103L
1038 iterator
1039 insert(const_iterator __position, size_type __n, const bool& __x)
1040 {
1041 difference_type __offset = __position - cbegin();
1042 _M_fill_insert(position: __position._M_const_cast(), __n, __x);
1043 return begin() + __offset;
1044 }
1045#else
1046 void
1047 insert(iterator __position, size_type __n, const bool& __x)
1048 { _M_fill_insert(__position, __n, __x); }
1049#endif
1050
1051#if __cplusplus >= 201103L
1052 iterator
1053 insert(const_iterator __p, initializer_list<bool> __l)
1054 { return this->insert(__p, __l.begin(), __l.end()); }
1055#endif
1056
1057 void
1058 pop_back()
1059 { --this->_M_impl._M_finish; }
1060
1061 iterator
1062#if __cplusplus >= 201103L
1063 erase(const_iterator __position)
1064#else
1065 erase(iterator __position)
1066#endif
1067 { return _M_erase(__position._M_const_cast()); }
1068
1069 iterator
1070#if __cplusplus >= 201103L
1071 erase(const_iterator __first, const_iterator __last)
1072#else
1073 erase(iterator __first, iterator __last)
1074#endif
1075 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1076
1077 void
1078 resize(size_type __new_size, bool __x = bool())
1079 {
1080 if (__new_size < size())
1081 _M_erase_at_end(pos: begin() + difference_type(__new_size));
1082 else
1083 insert(end(), __new_size - size(), __x);
1084 }
1085
1086#if __cplusplus >= 201103L
1087 void
1088 shrink_to_fit()
1089 { _M_shrink_to_fit(); }
1090#endif
1091
1092 void
1093 flip() _GLIBCXX_NOEXCEPT
1094 {
1095 _Bit_type * const __end = this->_M_impl._M_end_addr();
1096 for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p)
1097 *__p = ~*__p;
1098 }
1099
1100 void
1101 clear() _GLIBCXX_NOEXCEPT
1102 { _M_erase_at_end(pos: begin()); }
1103
1104#if __cplusplus >= 201103L
1105 template<typename... _Args>
1106#if __cplusplus > 201402L
1107 reference
1108#else
1109 void
1110#endif
1111 emplace_back(_Args&&... __args)
1112 {
1113 push_back(x: bool(__args...));
1114#if __cplusplus > 201402L
1115 return back();
1116#endif
1117 }
1118
1119 template<typename... _Args>
1120 iterator
1121 emplace(const_iterator __pos, _Args&&... __args)
1122 { return insert(__pos, bool(__args...)); }
1123#endif
1124
1125 protected:
1126 // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
1127 iterator
1128 _M_copy_aligned(const_iterator __first, const_iterator __last,
1129 iterator __result)
1130 {
1131 _Bit_type* __q = std::copy(first: __first._M_p, last: __last._M_p, result: __result._M_p);
1132 return std::copy(first: const_iterator(__last._M_p, 0), __last,
1133 result: iterator(__q, 0));
1134 }
1135
1136 void
1137 _M_initialize(size_type __n)
1138 {
1139 if (__n)
1140 {
1141 _Bit_pointer __q = this->_M_allocate(__n);
1142 this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1143 iterator __start = iterator(std::__addressof(*__q), 0);
1144 this->_M_impl._M_start = __start;
1145 this->_M_impl._M_finish = __start + difference_type(__n);
1146 }
1147 }
1148
1149 void
1150 _M_initialize_value(bool __x)
1151 {
1152 if (_Bit_type* __p = this->_M_impl._M_start._M_p)
1153 __builtin_memset(__p, __x ? ~0 : 0,
1154 (this->_M_impl._M_end_addr() - __p)
1155 * sizeof(_Bit_type));
1156 }
1157
1158 void
1159 _M_reallocate(size_type __n);
1160
1161#if __cplusplus >= 201103L
1162 bool
1163 _M_shrink_to_fit();
1164#endif
1165
1166#if __cplusplus < 201103L
1167 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1168 // 438. Ambiguity in the "do the right thing" clause
1169 template<typename _Integer>
1170 void
1171 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1172 {
1173 _M_initialize(static_cast<size_type>(__n));
1174 _M_initialize_value(__x);
1175 }
1176
1177 template<typename _InputIterator>
1178 void
1179 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1180 __false_type)
1181 { _M_initialize_range(__first, __last,
1182 std::__iterator_category(__first)); }
1183#endif
1184
1185 template<typename _InputIterator>
1186 void
1187 _M_initialize_range(_InputIterator __first, _InputIterator __last,
1188 std::input_iterator_tag)
1189 {
1190 for (; __first != __last; ++__first)
1191 push_back(x: *__first);
1192 }
1193
1194 template<typename _ForwardIterator>
1195 void
1196 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
1197 std::forward_iterator_tag)
1198 {
1199 const size_type __n = std::distance(__first, __last);
1200 _M_initialize(__n);
1201 std::copy(__first, __last, begin());
1202 }
1203
1204#if __cplusplus < 201103L
1205 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1206 // 438. Ambiguity in the "do the right thing" clause
1207 template<typename _Integer>
1208 void
1209 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1210 { _M_fill_assign(__n, __val); }
1211
1212 template<class _InputIterator>
1213 void
1214 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1215 __false_type)
1216 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1217#endif
1218
1219 void
1220 _M_fill_assign(size_t __n, bool __x)
1221 {
1222 if (__n > size())
1223 {
1224 _M_initialize_value(__x);
1225 insert(end(), __n - size(), __x);
1226 }
1227 else
1228 {
1229 _M_erase_at_end(pos: begin() + __n);
1230 _M_initialize_value(__x);
1231 }
1232 }
1233
1234 template<typename _InputIterator>
1235 void
1236 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1237 std::input_iterator_tag)
1238 {
1239 iterator __cur = begin();
1240 for (; __first != __last && __cur != end(); ++__cur, (void)++__first)
1241 *__cur = *__first;
1242 if (__first == __last)
1243 _M_erase_at_end(pos: __cur);
1244 else
1245 insert(end(), __first, __last);
1246 }
1247
1248 template<typename _ForwardIterator>
1249 void
1250 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1251 std::forward_iterator_tag)
1252 {
1253 const size_type __len = std::distance(__first, __last);
1254 if (__len < size())
1255 _M_erase_at_end(pos: std::copy(__first, __last, begin()));
1256 else
1257 {
1258 _ForwardIterator __mid = __first;
1259 std::advance(__mid, size());
1260 std::copy(__first, __mid, begin());
1261 insert(end(), __mid, __last);
1262 }
1263 }
1264
1265#if __cplusplus < 201103L
1266 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1267 // 438. Ambiguity in the "do the right thing" clause
1268 template<typename _Integer>
1269 void
1270 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1271 __true_type)
1272 { _M_fill_insert(__pos, __n, __x); }
1273
1274 template<typename _InputIterator>
1275 void
1276 _M_insert_dispatch(iterator __pos,
1277 _InputIterator __first, _InputIterator __last,
1278 __false_type)
1279 { _M_insert_range(__pos, __first, __last,
1280 std::__iterator_category(__first)); }
1281#endif
1282
1283 void
1284 _M_fill_insert(iterator __position, size_type __n, bool __x);
1285
1286 template<typename _InputIterator>
1287 void
1288 _M_insert_range(iterator __pos, _InputIterator __first,
1289 _InputIterator __last, std::input_iterator_tag)
1290 {
1291 for (; __first != __last; ++__first)
1292 {
1293 __pos = insert(__pos, *__first);
1294 ++__pos;
1295 }
1296 }
1297
1298 template<typename _ForwardIterator>
1299 void
1300 _M_insert_range(iterator __position, _ForwardIterator __first,
1301 _ForwardIterator __last, std::forward_iterator_tag);
1302
1303 void
1304 _M_insert_aux(iterator __position, bool __x);
1305
1306 size_type
1307 _M_check_len(size_type __n, const char* __s) const
1308 {
1309 if (max_size() - size() < __n)
1310 __throw_length_error(__N(__s));
1311
1312 const size_type __len = size() + std::max(size(), __n);
1313 return (__len < size() || __len > max_size()) ? max_size() : __len;
1314 }
1315
1316 void
1317 _M_erase_at_end(iterator __pos)
1318 { this->_M_impl._M_finish = __pos; }
1319
1320 iterator
1321 _M_erase(iterator __pos);
1322
1323 iterator
1324 _M_erase(iterator __first, iterator __last);
1325 };
1326
1327_GLIBCXX_END_NAMESPACE_CONTAINER
1328
1329 inline void
1330 __fill_bvector(_GLIBCXX_STD_C::_Bit_type * __v,
1331 unsigned int __first, unsigned int __last, bool __x)
1332 {
1333 using _GLIBCXX_STD_C::_Bit_type;
1334 using _GLIBCXX_STD_C::_S_word_bit;
1335 const _Bit_type __fmask = ~0ul << __first;
1336 const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last);
1337 const _Bit_type __mask = __fmask & __lmask;
1338
1339 if (__x)
1340 *__v |= __mask;
1341 else
1342 *__v &= ~__mask;
1343 }
1344
1345 inline void
1346 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator __first,
1347 _GLIBCXX_STD_C::_Bit_iterator __last, const bool& __x)
1348 {
1349 using _GLIBCXX_STD_C::_Bit_type;
1350 using _GLIBCXX_STD_C::_S_word_bit;
1351 if (__first._M_p != __last._M_p)
1352 {
1353 _Bit_type* __first_p = __first._M_p;
1354 if (__first._M_offset != 0)
1355 __fill_bvector(v: __first_p++, first: __first._M_offset, last: _S_word_bit, __x);
1356
1357 __builtin_memset(__first_p, __x ? ~0 : 0,
1358 (__last._M_p - __first_p) * sizeof(_Bit_type));
1359
1360 if (__last._M_offset != 0)
1361 __fill_bvector(v: __last._M_p, first: 0, last: __last._M_offset, __x);
1362 }
1363 else if (__first._M_offset != __last._M_offset)
1364 __fill_bvector(v: __first._M_p, first: __first._M_offset, last: __last._M_offset, __x);
1365 }
1366
1367#if __cplusplus >= 201103L
1368 // DR 1182.
1369 /// std::hash specialization for vector<bool>.
1370 template<typename _Alloc>
1371 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
1372 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1373 {
1374 size_t
1375 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
1376 };
1377#endif // C++11
1378
1379_GLIBCXX_END_NAMESPACE_VERSION
1380} // namespace std
1381
1382#endif
1383

source code of include/c++/11/bits/stl_bvector.h