1// vector<bool> specialization -*- C++ -*-
2
3// Copyright (C) 2001-2025 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#ifndef _GLIBCXX_ALWAYS_INLINE
60#define _GLIBCXX_ALWAYS_INLINE inline __attribute__((__always_inline__))
61#endif
62
63#if __cplusplus >= 201103L
64#include <initializer_list>
65#include <bits/functional_hash.h>
66#endif
67
68namespace std _GLIBCXX_VISIBILITY(default)
69{
70_GLIBCXX_BEGIN_NAMESPACE_VERSION
71
72 typedef unsigned long _Bit_type;
73 enum { _S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type)) };
74
75 __attribute__((__nonnull__))
76 _GLIBCXX20_CONSTEXPR
77 void
78 __fill_bvector_n(_Bit_type*, size_t, bool) _GLIBCXX_NOEXCEPT;
79
80_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
81
82 struct _Bit_reference
83 {
84 private:
85 template<typename, typename> friend class vector;
86 friend struct _Bit_iterator;
87 friend struct _Bit_const_iterator;
88
89 _GLIBCXX20_CONSTEXPR
90 _Bit_reference() _GLIBCXX_NOEXCEPT : _M_p(0), _M_mask(0) { }
91
92 _Bit_type * _M_p;
93 _Bit_type _M_mask;
94
95 _GLIBCXX20_CONSTEXPR
96 _Bit_reference(_Bit_type * __x, _Bit_type __y)
97 : _M_p(__x), _M_mask(__y) { }
98
99 public:
100#if __cplusplus >= 201103L
101 _Bit_reference(const _Bit_reference&) = default;
102#endif
103
104 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
105 operator bool() const _GLIBCXX_NOEXCEPT
106 { return !!(*_M_p & _M_mask); }
107
108 _GLIBCXX20_CONSTEXPR
109 _Bit_reference&
110 operator=(bool __x) _GLIBCXX_NOEXCEPT
111 {
112 if (__x)
113 *_M_p |= _M_mask;
114 else
115 *_M_p &= ~_M_mask;
116 return *this;
117 }
118
119#if __cplusplus > 202002L
120 constexpr const _Bit_reference&
121 operator=(bool __x) const noexcept
122 {
123 if (__x)
124 *_M_p |= _M_mask;
125 else
126 *_M_p &= ~_M_mask;
127 return *this;
128 }
129#endif // C++23
130
131 _GLIBCXX20_CONSTEXPR
132 _Bit_reference&
133 operator=(const _Bit_reference& __x) _GLIBCXX_NOEXCEPT
134 { return *this = bool(__x); }
135
136 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
137 bool
138 operator==(const _Bit_reference& __x) const
139 { return bool(*this) == bool(__x); }
140
141 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
142 bool
143 operator<(const _Bit_reference& __x) const
144 { return !bool(*this) && bool(__x); }
145
146 _GLIBCXX20_CONSTEXPR
147 void
148 flip() _GLIBCXX_NOEXCEPT
149 { *_M_p ^= _M_mask; }
150
151#if __cplusplus >= 201103L
152 _GLIBCXX20_CONSTEXPR
153 friend void
154 swap(_Bit_reference __x, _Bit_reference __y) noexcept
155 {
156 bool __tmp = __x;
157 __x = __y;
158 __y = __tmp;
159 }
160
161 _GLIBCXX20_CONSTEXPR
162 friend void
163 swap(_Bit_reference __x, bool& __y) noexcept
164 {
165 bool __tmp = __x;
166 __x = __y;
167 __y = __tmp;
168 }
169
170 _GLIBCXX20_CONSTEXPR
171 friend void
172 swap(bool& __x, _Bit_reference __y) noexcept
173 {
174 bool __tmp = __x;
175 __x = __y;
176 __y = __tmp;
177 }
178#endif
179 };
180
181// Ignore warnings about std::iterator.
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>
186 {
187 _Bit_type * _M_p;
188 unsigned int _M_offset;
189
190 _GLIBCXX20_CONSTEXPR _GLIBCXX_ALWAYS_INLINE
191 void
192 _M_assume_normalized() const
193 {
194#if __has_attribute(__assume__) && !defined(_GLIBCXX_CLANG)
195 unsigned int __ofst = _M_offset;
196 __attribute__ ((__assume__ (__ofst < unsigned(_S_word_bit))));
197#endif
198 }
199
200 _GLIBCXX20_CONSTEXPR
201 _Bit_iterator_base(_Bit_type * __x, unsigned int __y)
202 : _M_p(__x), _M_offset(__y) { }
203
204 _GLIBCXX20_CONSTEXPR
205 void
206 _M_bump_up()
207 {
208 _M_assume_normalized();
209 if (_M_offset++ == int(_S_word_bit) - 1)
210 {
211 _M_offset = 0;
212 ++_M_p;
213 }
214 }
215
216 _GLIBCXX20_CONSTEXPR
217 void
218 _M_bump_down()
219 {
220 _M_assume_normalized();
221 if (_M_offset-- == 0)
222 {
223 _M_offset = int(_S_word_bit) - 1;
224 --_M_p;
225 }
226 }
227
228 _GLIBCXX20_CONSTEXPR
229 void
230 _M_incr(ptrdiff_t __i)
231 {
232 _M_assume_normalized();
233 difference_type __n = __i + _M_offset;
234 _M_p += __n / int(_S_word_bit);
235 __n = __n % int(_S_word_bit);
236 if (__n < 0)
237 {
238 __n += int(_S_word_bit);
239 --_M_p;
240 }
241 _M_offset = static_cast<unsigned int>(__n);
242 }
243
244 _GLIBCXX_NODISCARD
245 friend _GLIBCXX20_CONSTEXPR bool
246 operator==(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
247 {
248 __x._M_assume_normalized();
249 __y._M_assume_normalized();
250 return __x._M_p == __y._M_p && __x._M_offset == __y._M_offset;
251 }
252
253#if __cpp_lib_three_way_comparison
254 [[nodiscard]]
255 friend constexpr strong_ordering
256 operator<=>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
257 noexcept
258 {
259 __x._M_assume_normalized();
260 __y._M_assume_normalized();
261 if (const auto __cmp = __x._M_p <=> __y._M_p; __cmp != 0)
262 return __cmp;
263 return __x._M_offset <=> __y._M_offset;
264 }
265#else
266 _GLIBCXX_NODISCARD
267 friend bool
268 operator<(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
269 {
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);
274 }
275
276 _GLIBCXX_NODISCARD
277 friend bool
278 operator!=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
279 { return !(__x == __y); }
280
281 _GLIBCXX_NODISCARD
282 friend bool
283 operator>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
284 { return __y < __x; }
285
286 _GLIBCXX_NODISCARD
287 friend bool
288 operator<=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
289 { return !(__y < __x); }
290
291 _GLIBCXX_NODISCARD
292 friend bool
293 operator>=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
294 { return !(__x < __y); }
295#endif // three-way comparison
296
297 friend _GLIBCXX20_CONSTEXPR ptrdiff_t
298 operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
299 {
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);
304 }
305 };
306#pragma GCC diagnostic pop
307
308 struct _Bit_iterator : public _Bit_iterator_base
309 {
310 typedef _Bit_reference reference;
311#if __cplusplus > 201703L
312 typedef void pointer;
313#else
314 typedef _Bit_reference* pointer;
315#endif
316 typedef _Bit_iterator iterator;
317
318 _GLIBCXX20_CONSTEXPR
319 _Bit_iterator() : _Bit_iterator_base(0, 0) { }
320
321 _GLIBCXX20_CONSTEXPR
322 _Bit_iterator(_Bit_type * __x, unsigned int __y)
323 : _Bit_iterator_base(__x, __y) { }
324
325 _GLIBCXX20_CONSTEXPR
326 iterator
327 _M_const_cast() const
328 { return *this; }
329
330 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
331 reference
332 operator*() const
333 {
334 _M_assume_normalized();
335 return reference(_M_p, 1UL << _M_offset);
336 }
337
338 _GLIBCXX20_CONSTEXPR
339 iterator&
340 operator++()
341 {
342 _M_bump_up();
343 return *this;
344 }
345
346 _GLIBCXX20_CONSTEXPR
347 iterator
348 operator++(int)
349 {
350 iterator __tmp = *this;
351 _M_bump_up();
352 return __tmp;
353 }
354
355 _GLIBCXX20_CONSTEXPR
356 iterator&
357 operator--()
358 {
359 _M_bump_down();
360 return *this;
361 }
362
363 _GLIBCXX20_CONSTEXPR
364 iterator
365 operator--(int)
366 {
367 iterator __tmp = *this;
368 _M_bump_down();
369 return __tmp;
370 }
371
372 _GLIBCXX20_CONSTEXPR
373 iterator&
374 operator+=(difference_type __i)
375 {
376 _M_incr(__i);
377 return *this;
378 }
379
380 _GLIBCXX20_CONSTEXPR
381 iterator&
382 operator-=(difference_type __i)
383 {
384 *this += -__i;
385 return *this;
386 }
387
388 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
389 reference
390 operator[](difference_type __i) const
391 { return *(*this + __i); }
392
393 _GLIBCXX_NODISCARD
394 friend _GLIBCXX20_CONSTEXPR iterator
395 operator+(const iterator& __x, difference_type __n)
396 {
397 iterator __tmp = __x;
398 __tmp += __n;
399 return __tmp;
400 }
401
402 _GLIBCXX_NODISCARD
403 friend _GLIBCXX20_CONSTEXPR iterator
404 operator+(difference_type __n, const iterator& __x)
405 { return __x + __n; }
406
407 _GLIBCXX_NODISCARD
408 friend _GLIBCXX20_CONSTEXPR iterator
409 operator-(const iterator& __x, difference_type __n)
410 {
411 iterator __tmp = __x;
412 __tmp -= __n;
413 return __tmp;
414 }
415 };
416
417 struct _Bit_const_iterator : public _Bit_iterator_base
418 {
419 typedef bool reference;
420 typedef bool const_reference;
421#if __cplusplus > 201703L
422 typedef void pointer;
423#else
424 typedef const bool* pointer;
425#endif
426 typedef _Bit_const_iterator const_iterator;
427
428 _GLIBCXX20_CONSTEXPR
429 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
430
431 _GLIBCXX20_CONSTEXPR
432 _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
433 : _Bit_iterator_base(__x, __y) { }
434
435 _GLIBCXX20_CONSTEXPR
436 _Bit_const_iterator(const _Bit_iterator& __x)
437 : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
438
439 _GLIBCXX20_CONSTEXPR
440 _Bit_iterator
441 _M_const_cast() const
442 { return _Bit_iterator(_M_p, _M_offset); }
443
444 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
445 const_reference
446 operator*() const
447 {
448 _M_assume_normalized();
449 return _Bit_reference(_M_p, 1UL << _M_offset);
450 }
451
452 _GLIBCXX20_CONSTEXPR
453 const_iterator&
454 operator++()
455 {
456 _M_bump_up();
457 return *this;
458 }
459
460 _GLIBCXX20_CONSTEXPR
461 const_iterator
462 operator++(int)
463 {
464 const_iterator __tmp = *this;
465 _M_bump_up();
466 return __tmp;
467 }
468
469 _GLIBCXX20_CONSTEXPR
470 const_iterator&
471 operator--()
472 {
473 _M_bump_down();
474 return *this;
475 }
476
477 _GLIBCXX20_CONSTEXPR
478 const_iterator
479 operator--(int)
480 {
481 const_iterator __tmp = *this;
482 _M_bump_down();
483 return __tmp;
484 }
485
486 _GLIBCXX20_CONSTEXPR
487 const_iterator&
488 operator+=(difference_type __i)
489 {
490 _M_incr(__i);
491 return *this;
492 }
493
494 _GLIBCXX20_CONSTEXPR
495 const_iterator&
496 operator-=(difference_type __i)
497 {
498 *this += -__i;
499 return *this;
500 }
501
502 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
503 const_reference
504 operator[](difference_type __i) const
505 { return *(*this + __i); }
506
507 _GLIBCXX_NODISCARD
508 friend _GLIBCXX20_CONSTEXPR const_iterator
509 operator+(const const_iterator& __x, difference_type __n)
510 {
511 const_iterator __tmp = __x;
512 __tmp += __n;
513 return __tmp;
514 }
515
516 _GLIBCXX_NODISCARD
517 friend _GLIBCXX20_CONSTEXPR const_iterator
518 operator-(const const_iterator& __x, difference_type __n)
519 {
520 const_iterator __tmp = __x;
521 __tmp -= __n;
522 return __tmp;
523 }
524
525 _GLIBCXX_NODISCARD
526 friend _GLIBCXX20_CONSTEXPR const_iterator
527 operator+(difference_type __n, const const_iterator& __x)
528 { return __x + __n; }
529 };
530
531 template<typename _Alloc>
532 struct _Bvector_base
533 {
534 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
535 rebind<_Bit_type>::other _Bit_alloc_type;
536 typedef typename __gnu_cxx::__alloc_traits<_Bit_alloc_type>
537 _Bit_alloc_traits;
538 typedef typename _Bit_alloc_traits::pointer _Bit_pointer;
539
540 struct _Bvector_impl_data
541 {
542#if !_GLIBCXX_INLINE_VERSION
543 _Bit_iterator _M_start;
544#else
545 // We don't need the offset field for the start, it's always zero.
546 struct {
547 _Bit_type* _M_p;
548 // Allow assignment from iterators (assume offset is zero):
549 _GLIBCXX20_CONSTEXPR
550 void operator=(_Bit_iterator __it) { _M_p = __it._M_p; }
551 } _M_start;
552#endif
553 _Bit_iterator _M_finish;
554 _Bit_pointer _M_end_of_storage;
555
556 _GLIBCXX20_CONSTEXPR
557 _Bvector_impl_data() _GLIBCXX_NOEXCEPT
558 : _M_start(), _M_finish(), _M_end_of_storage()
559 { }
560
561#if __cplusplus >= 201103L
562 _Bvector_impl_data(const _Bvector_impl_data&) = default;
563
564 _Bvector_impl_data&
565 operator=(const _Bvector_impl_data&) = default;
566
567 _GLIBCXX20_CONSTEXPR
568 _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept
569 : _Bvector_impl_data(__x)
570 { __x._M_reset(); }
571
572 _GLIBCXX20_CONSTEXPR
573 void
574 _M_move_data(_Bvector_impl_data&& __x) noexcept
575 {
576 *this = __x;
577 __x._M_reset();
578 }
579#endif
580
581 _GLIBCXX20_CONSTEXPR
582 void
583 _M_reset() _GLIBCXX_NOEXCEPT
584 { *this = _Bvector_impl_data(); }
585
586 _GLIBCXX20_CONSTEXPR
587 void
588 _M_swap_data(_Bvector_impl_data& __x) _GLIBCXX_NOEXCEPT
589 {
590 // Do not use std::swap(_M_start, __x._M_start), etc as it loses
591 // information used by TBAA.
592 std::swap(*this, __x);
593 }
594 };
595
596 struct _Bvector_impl
597 : public _Bit_alloc_type, public _Bvector_impl_data
598 {
599 _GLIBCXX20_CONSTEXPR
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>
604#endif
605 : _Bit_alloc_type()
606 { }
607
608 _GLIBCXX20_CONSTEXPR
609 _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT
610 : _Bit_alloc_type(__a)
611 { }
612
613#if __cplusplus >= 201103L
614 // Not defaulted, to enforce noexcept(true) even when
615 // !is_nothrow_move_constructible<_Bit_alloc_type>.
616 _GLIBCXX20_CONSTEXPR
617 _Bvector_impl(_Bvector_impl&& __x) noexcept
618 : _Bit_alloc_type(std::move(__x)), _Bvector_impl_data(std::move(__x))
619 { }
620
621 _GLIBCXX20_CONSTEXPR
622 _Bvector_impl(_Bit_alloc_type&& __a, _Bvector_impl&& __x) noexcept
623 : _Bit_alloc_type(std::move(__a)), _Bvector_impl_data(std::move(__x))
624 { }
625#endif
626
627 _GLIBCXX20_CONSTEXPR
628 _Bit_type*
629 _M_end_addr() const _GLIBCXX_NOEXCEPT
630 {
631 if (this->_M_end_of_storage)
632 return std::__addressof(this->_M_end_of_storage[-1]) + 1;
633 return 0;
634 }
635 };
636
637 public:
638 typedef _Alloc allocator_type;
639
640 _GLIBCXX20_CONSTEXPR
641 _Bit_alloc_type&
642 _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT
643 { return this->_M_impl; }
644
645 _GLIBCXX20_CONSTEXPR
646 const _Bit_alloc_type&
647 _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT
648 { return this->_M_impl; }
649
650 _GLIBCXX20_CONSTEXPR
651 allocator_type
652 get_allocator() const _GLIBCXX_NOEXCEPT
653 { return allocator_type(_M_get_Bit_allocator()); }
654
655#if __cplusplus >= 201103L
656 _Bvector_base() = default;
657#else
658 _Bvector_base() { }
659#endif
660
661 _GLIBCXX20_CONSTEXPR
662 _Bvector_base(const allocator_type& __a)
663 : _M_impl(_Bit_alloc_type(__a)) { }
664
665#if __cplusplus >= 201103L
666 _Bvector_base(_Bvector_base&&) = default;
667
668 _GLIBCXX20_CONSTEXPR
669 _Bvector_base(_Bvector_base&& __x, const allocator_type& __a) noexcept
670 : _M_impl(_Bit_alloc_type(__a), std::move(__x._M_impl))
671 { }
672#endif
673
674 _GLIBCXX20_CONSTEXPR
675 ~_Bvector_base()
676 { this->_M_deallocate(); }
677
678 protected:
679 _Bvector_impl _M_impl;
680
681 _GLIBCXX20_CONSTEXPR
682 _Bit_pointer
683 _M_allocate(size_t __n)
684 {
685 _Bit_pointer __p = _Bit_alloc_traits::allocate(_M_impl, _S_nword(__n));
686#if __cpp_lib_is_constant_evaluated && __cpp_constexpr_dynamic_alloc
687 if (std::is_constant_evaluated())
688 {
689 __n = _S_nword(__n);
690 for (size_t __i = 0; __i < __n; ++__i)
691 std::construct_at(std::to_address(__p) + __i);
692 }
693#endif
694 return __p;
695 }
696
697 _GLIBCXX20_CONSTEXPR
698 void
699 _M_deallocate()
700 {
701 if (_M_impl._M_start._M_p)
702 {
703 const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p;
704 _Bit_alloc_traits::deallocate(_M_impl,
705 _M_impl._M_end_of_storage - __n,
706 __n);
707 _M_impl._M_reset();
708 }
709 }
710
711#if __cplusplus >= 201103L
712 _GLIBCXX20_CONSTEXPR
713 void
714 _M_move_data(_Bvector_base&& __x) noexcept
715 { _M_impl._M_move_data(std::move(__x._M_impl)); }
716#endif
717
718 _GLIBCXX_CONSTEXPR
719 static size_t
720 _S_nword(size_t __n)
721 { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); }
722 };
723
724 /**
725 * @brief A specialization of vector for booleans which offers fixed time
726 * access to individual elements in any order.
727 *
728 * @ingroup sequences
729 * @headerfile vector
730 * @since C++98
731 *
732 * @tparam _Alloc Allocator type.
733 *
734 * Note that vector<bool> does not actually meet the requirements for being
735 * a container. This is because the reference and pointer types are not
736 * really references and pointers to bool. See DR96 for details. @see
737 * vector for function documentation.
738 *
739 * In some terminology a %vector can be described as a dynamic
740 * C-style array, it offers fast and efficient access to individual
741 * elements in any order and saves the user from worrying about
742 * memory and size allocation. Subscripting ( @c [] ) access is
743 * also provided as with C-style arrays.
744 */
745 template<typename _Alloc>
746 class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
747 {
748 typedef _Bvector_base<_Alloc> _Base;
749 typedef typename _Base::_Bit_pointer _Bit_pointer;
750 typedef typename _Base::_Bit_alloc_traits _Bit_alloc_traits;
751
752#if __cplusplus >= 201103L
753 friend struct std::hash<vector>;
754# if __cplusplus > 201703L // || defined __STRICT_ANSI__
755 static_assert(is_same<typename _Alloc::value_type, bool>::value,
756 "std::vector must have the same value_type as its allocator");
757# endif
758#endif
759
760 public:
761 typedef bool value_type;
762 typedef size_t size_type;
763 typedef ptrdiff_t difference_type;
764 typedef _Bit_reference reference;
765 typedef bool const_reference;
766 typedef _Bit_reference* pointer;
767 typedef const bool* const_pointer;
768 typedef _Bit_iterator iterator;
769 typedef _Bit_const_iterator const_iterator;
770 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
771 typedef std::reverse_iterator<iterator> reverse_iterator;
772 typedef _Alloc allocator_type;
773
774 _GLIBCXX20_CONSTEXPR
775 allocator_type
776 get_allocator() const
777 { return _Base::get_allocator(); }
778
779 protected:
780 using _Base::_M_allocate;
781 using _Base::_M_deallocate;
782 using _Base::_S_nword;
783 using _Base::_M_get_Bit_allocator;
784
785 public:
786#if __cplusplus >= 201103L
787 vector() = default;
788#else
789 vector() { }
790#endif
791
792 _GLIBCXX20_CONSTEXPR
793 explicit
794 vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
795 : _Base(__a) { }
796
797#if __cplusplus >= 201103L
798 _GLIBCXX20_CONSTEXPR
799 explicit
800 vector(size_type __n, const allocator_type& __a = allocator_type())
801 : vector(__n, false, __a)
802 { }
803
804 _GLIBCXX20_CONSTEXPR
805 vector(size_type __n, const bool& __value,
806 const allocator_type& __a = allocator_type())
807#else
808 explicit
809 vector(size_type __n, const bool& __value = bool(),
810 const allocator_type& __a = allocator_type())
811#endif
812 : _Base(__a)
813 {
814 _M_initialize(__n);
815 _M_initialize_value(x: __value);
816 }
817
818 _GLIBCXX20_CONSTEXPR
819 vector(const vector& __x)
820 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
821 {
822 const_iterator __xbegin = __x.begin(), __xend = __x.end();
823 _M_initialize(n: __x.size());
824 _M_copy_aligned(first: __xbegin, last: __xend, result: begin());
825 }
826
827#if __cplusplus >= 201103L
828 vector(vector&&) = default;
829
830 private:
831 _GLIBCXX20_CONSTEXPR
832 vector(vector&& __x, const allocator_type& __a, true_type) noexcept
833 : _Base(std::move(__x), __a)
834 { }
835
836 _GLIBCXX20_CONSTEXPR
837 vector(vector&& __x, const allocator_type& __a, false_type)
838 : _Base(__a)
839 {
840 if (__x.get_allocator() == __a)
841 this->_M_move_data(std::move(__x));
842 else
843 {
844 _M_initialize(n: __x.size());
845 _M_copy_aligned(first: __x.begin(), last: __x.end(), result: begin());
846 __x.clear();
847 }
848 }
849
850 public:
851 _GLIBCXX20_CONSTEXPR
852 vector(vector&& __x, const __type_identity_t<allocator_type>& __a)
853 noexcept(_Bit_alloc_traits::_S_always_equal())
854 : vector(std::move(__x), __a,
855 typename _Bit_alloc_traits::is_always_equal{})
856 { }
857
858 _GLIBCXX20_CONSTEXPR
859 vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
860 : _Base(__a)
861 {
862 _M_initialize(n: __x.size());
863 _M_copy_aligned(first: __x.begin(), last: __x.end(), result: begin());
864 }
865
866 _GLIBCXX20_CONSTEXPR
867 vector(initializer_list<bool> __l,
868 const allocator_type& __a = allocator_type())
869 : _Base(__a)
870 {
871 _M_initialize_range(__l.begin(), __l.end(),
872 random_access_iterator_tag());
873 }
874#endif
875
876#if __cplusplus >= 201103L
877 template<typename _InputIterator,
878 typename = std::_RequireInputIter<_InputIterator>>
879 _GLIBCXX20_CONSTEXPR
880 vector(_InputIterator __first, _InputIterator __last,
881 const allocator_type& __a = allocator_type())
882 : _Base(__a)
883 {
884 _M_initialize_range(__first, __last,
885 std::__iterator_category(__first));
886 }
887#else
888 template<typename _InputIterator>
889 vector(_InputIterator __first, _InputIterator __last,
890 const allocator_type& __a = allocator_type())
891 : _Base(__a)
892 {
893 // Check whether it's an integral type. If so, it's not an iterator.
894 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
895 _M_initialize_dispatch(__first, __last, _Integral());
896 }
897#endif
898
899#if __glibcxx_containers_ranges // C++ >= 23
900 /**
901 * @brief Construct a vector from a range.
902 * @param __rg A range of values that are convertible to `value_type`.
903 * @since C++23
904 */
905 template<__detail::__container_compatible_range<bool> _Rg>
906 constexpr
907 vector(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc())
908 : _Base(__a)
909 {
910 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
911 {
912 _M_initialize(size_type(ranges::distance(__rg)));
913 ranges::copy(__rg, begin());
914 }
915 else
916 {
917 auto __first = ranges::begin(__rg);
918 const auto __last = ranges::end(__rg);
919 for (; __first != __last; ++__first)
920 emplace_back(*__first);
921 }
922 }
923#endif
924
925 _GLIBCXX20_CONSTEXPR
926 ~vector() _GLIBCXX_NOEXCEPT { }
927
928 _GLIBCXX20_CONSTEXPR
929 vector&
930 operator=(const vector& __x)
931 {
932 if (&__x == this)
933 return *this;
934#if __cplusplus >= 201103L
935 if (_Bit_alloc_traits::_S_propagate_on_copy_assign())
936 {
937 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator())
938 {
939 this->_M_deallocate();
940 std::__alloc_on_copy(_M_get_Bit_allocator(),
941 __x._M_get_Bit_allocator());
942 _M_initialize(n: __x.size());
943 }
944 else
945 std::__alloc_on_copy(_M_get_Bit_allocator(),
946 __x._M_get_Bit_allocator());
947 }
948#endif
949 if (__x.size() > capacity())
950 {
951 this->_M_deallocate();
952 _M_initialize(n: __x.size());
953 }
954 this->_M_impl._M_finish = _M_copy_aligned(first: __x.begin(), last: __x.end(),
955 result: begin());
956 return *this;
957 }
958
959#if __cplusplus >= 201103L
960 _GLIBCXX20_CONSTEXPR
961 vector&
962 operator=(vector&& __x) noexcept(_Bit_alloc_traits::_S_nothrow_move())
963 {
964 if (_Bit_alloc_traits::_S_propagate_on_move_assign()
965 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator())
966 {
967 this->_M_deallocate();
968 this->_M_move_data(std::move(__x));
969 std::__alloc_on_move(_M_get_Bit_allocator(),
970 __x._M_get_Bit_allocator());
971 }
972 else
973 {
974 if (__x.size() > capacity())
975 {
976 this->_M_deallocate();
977 _M_initialize(n: __x.size());
978 }
979 this->_M_impl._M_finish = _M_copy_aligned(first: __x.begin(), last: __x.end(),
980 result: begin());
981 __x.clear();
982 }
983 return *this;
984 }
985
986 _GLIBCXX20_CONSTEXPR
987 vector&
988 operator=(initializer_list<bool> __l)
989 {
990 this->assign(__l.begin(), __l.end());
991 return *this;
992 }
993#endif
994
995 // assign(), a generalized assignment member function. Two
996 // versions: one that takes a count, and one that takes a range.
997 // The range version is a member template, so we dispatch on whether
998 // or not the type is an integer.
999 _GLIBCXX20_CONSTEXPR
1000 void
1001 assign(size_type __n, const bool& __x)
1002 { _M_fill_assign(__n, __x); }
1003
1004#if __cplusplus >= 201103L
1005 template<typename _InputIterator,
1006 typename = std::_RequireInputIter<_InputIterator>>
1007 _GLIBCXX20_CONSTEXPR
1008 void
1009 assign(_InputIterator __first, _InputIterator __last)
1010 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1011#else
1012 template<typename _InputIterator>
1013 void
1014 assign(_InputIterator __first, _InputIterator __last)
1015 {
1016 // Check whether it's an integral type. If so, it's not an iterator.
1017 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1018 _M_assign_dispatch(__first, __last, _Integral());
1019 }
1020#endif
1021
1022#if __cplusplus >= 201103L
1023 _GLIBCXX20_CONSTEXPR
1024 void
1025 assign(initializer_list<bool> __l)
1026 { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); }
1027#endif
1028
1029#if __glibcxx_containers_ranges // C++ >= 23
1030 /**
1031 * @brief Assign a range to the vector.
1032 * @param __rg A range of values that are convertible to `value_type`.
1033 * @pre `__rg` and `*this` do not overlap.
1034 * @since C++23
1035 */
1036 template<__detail::__container_compatible_range<bool> _Rg>
1037 constexpr void
1038 assign_range(_Rg&& __rg)
1039 {
1040 static_assert(assignable_from<bool&, ranges::range_reference_t<_Rg>>);
1041 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1042 {
1043 if (auto __n = size_type(ranges::distance(__rg)))
1044 {
1045 reserve(__n);
1046 this->_M_impl._M_finish
1047 = ranges::copy(std::forward<_Rg>(__rg), begin()).out;
1048 }
1049 else
1050 clear();
1051 }
1052 else
1053 {
1054 clear();
1055 auto __first = ranges::begin(__rg);
1056 const auto __last = ranges::end(__rg);
1057 for (; __first != __last; ++__first)
1058 emplace_back(*__first);
1059 }
1060 }
1061#endif
1062
1063 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1064 iterator
1065 begin() _GLIBCXX_NOEXCEPT
1066 { return iterator(this->_M_impl._M_start._M_p, 0); }
1067
1068 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1069 const_iterator
1070 begin() const _GLIBCXX_NOEXCEPT
1071 { return const_iterator(this->_M_impl._M_start._M_p, 0); }
1072
1073 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1074 iterator
1075 end() _GLIBCXX_NOEXCEPT
1076 { return this->_M_impl._M_finish; }
1077
1078 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1079 const_iterator
1080 end() const _GLIBCXX_NOEXCEPT
1081 { return this->_M_impl._M_finish; }
1082
1083 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1084 reverse_iterator
1085 rbegin() _GLIBCXX_NOEXCEPT
1086 { return reverse_iterator(end()); }
1087
1088 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1089 const_reverse_iterator
1090 rbegin() const _GLIBCXX_NOEXCEPT
1091 { return const_reverse_iterator(end()); }
1092
1093 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1094 reverse_iterator
1095 rend() _GLIBCXX_NOEXCEPT
1096 { return reverse_iterator(begin()); }
1097
1098 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1099 const_reverse_iterator
1100 rend() const _GLIBCXX_NOEXCEPT
1101 { return const_reverse_iterator(begin()); }
1102
1103#if __cplusplus >= 201103L
1104 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1105 const_iterator
1106 cbegin() const noexcept
1107 { return const_iterator(this->_M_impl._M_start._M_p, 0); }
1108
1109 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1110 const_iterator
1111 cend() const noexcept
1112 { return this->_M_impl._M_finish; }
1113
1114 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1115 const_reverse_iterator
1116 crbegin() const noexcept
1117 { return const_reverse_iterator(end()); }
1118
1119 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1120 const_reverse_iterator
1121 crend() const noexcept
1122 { return const_reverse_iterator(begin()); }
1123#endif
1124
1125 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1126 size_type
1127 size() const _GLIBCXX_NOEXCEPT
1128 { return size_type(end() - begin()); }
1129
1130 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1131 size_type
1132 max_size() const _GLIBCXX_NOEXCEPT
1133 {
1134 const size_type __isize =
1135 __gnu_cxx::__numeric_traits<difference_type>::__max
1136 - int(_S_word_bit) + 1;
1137 const size_type __asize
1138 = _Bit_alloc_traits::max_size(_M_get_Bit_allocator());
1139 return (__asize <= __isize / int(_S_word_bit)
1140 ? __asize * int(_S_word_bit) : __isize);
1141 }
1142
1143 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1144 size_type
1145 capacity() const _GLIBCXX_NOEXCEPT
1146 { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
1147 - begin()); }
1148
1149 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1150 bool
1151 empty() const _GLIBCXX_NOEXCEPT
1152 { return begin() == end(); }
1153
1154 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1155 reference
1156 operator[](size_type __n)
1157 {
1158 __glibcxx_requires_subscript(__n);
1159 return _Bit_reference (this->_M_impl._M_start._M_p
1160 + __n / int(_S_word_bit),
1161 1UL << __n % int(_S_word_bit));
1162 }
1163
1164 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1165 const_reference
1166 operator[](size_type __n) const
1167 {
1168 __glibcxx_requires_subscript(__n);
1169 return _Bit_reference (this->_M_impl._M_start._M_p
1170 + __n / int(_S_word_bit),
1171 1UL << __n % int(_S_word_bit));
1172 }
1173
1174 protected:
1175 _GLIBCXX20_CONSTEXPR
1176 void
1177 _M_range_check(size_type __n) const
1178 {
1179 if (__n >= this->size())
1180 __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n "
1181 "(which is %zu) >= this->size() "
1182 "(which is %zu)"),
1183 __n, this->size());
1184 }
1185
1186 public:
1187 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1188 reference
1189 at(size_type __n)
1190 {
1191 _M_range_check(__n);
1192 return (*this)[__n];
1193 }
1194
1195 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1196 const_reference
1197 at(size_type __n) const
1198 {
1199 _M_range_check(__n);
1200 return (*this)[__n];
1201 }
1202
1203 _GLIBCXX20_CONSTEXPR
1204 void
1205 reserve(size_type __n)
1206 {
1207 if (__n > max_size())
1208 __throw_length_error(__N("vector::reserve"));
1209 if (capacity() < __n)
1210 _M_reallocate(__n);
1211 }
1212
1213 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1214 reference
1215 front()
1216 {
1217 __glibcxx_requires_nonempty();
1218 return *begin();
1219 }
1220
1221 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1222 const_reference
1223 front() const
1224 {
1225 __glibcxx_requires_nonempty();
1226 return *begin();
1227 }
1228
1229 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1230 reference
1231 back()
1232 {
1233 __glibcxx_requires_nonempty();
1234 return *(end() - 1);
1235 }
1236
1237 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1238 const_reference
1239 back() const
1240 {
1241 __glibcxx_requires_nonempty();
1242 return *(end() - 1);
1243 }
1244
1245 _GLIBCXX20_CONSTEXPR
1246 void
1247 push_back(bool __x)
1248 {
1249 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
1250 *this->_M_impl._M_finish++ = __x;
1251 else
1252 _M_insert_aux(position: end(), __x);
1253 }
1254
1255 _GLIBCXX20_CONSTEXPR
1256 void
1257 swap(vector& __x) _GLIBCXX_NOEXCEPT
1258 {
1259#if __cplusplus >= 201103L
1260 __glibcxx_assert(_Bit_alloc_traits::propagate_on_container_swap::value
1261 || _M_get_Bit_allocator() == __x._M_get_Bit_allocator());
1262#endif
1263 this->_M_impl._M_swap_data(__x._M_impl);
1264 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(),
1265 __x._M_get_Bit_allocator());
1266 }
1267
1268 // [23.2.5]/1, third-to-last entry in synopsis listing
1269 _GLIBCXX20_CONSTEXPR
1270 static void
1271 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
1272 {
1273 bool __tmp = __x;
1274 __x = __y;
1275 __y = __tmp;
1276 }
1277
1278 _GLIBCXX20_CONSTEXPR
1279 iterator
1280#if __cplusplus >= 201103L
1281 insert(const_iterator __position, const bool& __x)
1282#else
1283 insert(iterator __position, const bool& __x)
1284#endif
1285 {
1286 const difference_type __n = __position - begin();
1287 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()
1288 && __position == end())
1289 *this->_M_impl._M_finish++ = __x;
1290 else
1291 _M_insert_aux(position: __position._M_const_cast(), __x);
1292 return begin() + __n;
1293 }
1294
1295#if _GLIBCXX_USE_DEPRECATED
1296 _GLIBCXX_DEPRECATED_SUGGEST("insert(position, false)")
1297 iterator
1298 insert(const_iterator __position)
1299 { return this->insert(__position._M_const_cast(), false); }
1300#endif
1301
1302#if __cplusplus >= 201103L
1303 template<typename _InputIterator,
1304 typename = std::_RequireInputIter<_InputIterator>>
1305 _GLIBCXX20_CONSTEXPR
1306 iterator
1307 insert(const_iterator __position,
1308 _InputIterator __first, _InputIterator __last)
1309 {
1310 difference_type __offset = __position - cbegin();
1311 _M_insert_range(__position._M_const_cast(),
1312 __first, __last,
1313 std::__iterator_category(__first));
1314 return begin() + __offset;
1315 }
1316#else
1317 template<typename _InputIterator>
1318 void
1319 insert(iterator __position,
1320 _InputIterator __first, _InputIterator __last)
1321 {
1322 // Check whether it's an integral type. If so, it's not an iterator.
1323 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1324 _M_insert_dispatch(__position, __first, __last, _Integral());
1325 }
1326#endif
1327
1328#if __cplusplus >= 201103L
1329 _GLIBCXX20_CONSTEXPR
1330 iterator
1331 insert(const_iterator __position, size_type __n, const bool& __x)
1332 {
1333 difference_type __offset = __position - cbegin();
1334 _M_fill_insert(position: __position._M_const_cast(), __n, __x);
1335 return begin() + __offset;
1336 }
1337#else
1338 void
1339 insert(iterator __position, size_type __n, const bool& __x)
1340 { _M_fill_insert(__position, __n, __x); }
1341#endif
1342
1343#if __cplusplus >= 201103L
1344 _GLIBCXX20_CONSTEXPR
1345 iterator
1346 insert(const_iterator __p, initializer_list<bool> __l)
1347 { return this->insert(__p, __l.begin(), __l.end()); }
1348#endif
1349
1350#if __glibcxx_containers_ranges // C++ >= 23
1351 /**
1352 * @brief Insert a range into the vector.
1353 * @param __rg A range of values that are convertible to `bool`.
1354 * @return An iterator that points to the first new element inserted,
1355 * or to `__pos` if `__rg` is an empty range.
1356 * @pre `__rg` and `*this` do not overlap.
1357 * @since C++23
1358 */
1359 template<__detail::__container_compatible_range<bool> _Rg>
1360 constexpr iterator
1361 insert_range(const_iterator __pos, _Rg&& __rg)
1362 {
1363 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1364 {
1365 if (auto __n = size_type(ranges::distance(__rg)))
1366 {
1367 if (capacity() - size() >= __n)
1368 {
1369 std::copy_backward(__pos._M_const_cast(), end(),
1370 this->_M_impl._M_finish
1371 + difference_type(__n));
1372 ranges::copy(__rg, __pos._M_const_cast());
1373 this->_M_impl._M_finish += difference_type(__n);
1374 return __pos._M_const_cast();
1375 }
1376 else
1377 {
1378 const size_type __len =
1379 _M_check_len(__n, "vector<bool>::insert_range");
1380 const iterator __begin = begin(), __end = end();
1381 _Bit_pointer __q = this->_M_allocate(__len);
1382 iterator __start(std::__addressof(*__q), 0);
1383 iterator __i = _M_copy_aligned(__begin,
1384 __pos._M_const_cast(),
1385 __start);
1386 iterator __j = ranges::copy(__rg, __i).out;
1387 iterator __finish = std::copy(__pos._M_const_cast(),
1388 __end, __j);
1389 this->_M_deallocate();
1390 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
1391 this->_M_impl._M_start = __start;
1392 this->_M_impl._M_finish = __finish;
1393 return __i;
1394 }
1395 }
1396 else
1397 return __pos._M_const_cast();
1398 }
1399 else
1400 return insert_range(__pos,
1401 vector(from_range, __rg, get_allocator()));
1402 }
1403
1404 /**
1405 * @brief Append a range at the end of the vector.
1406 * @since C++23
1407 */
1408 template<__detail::__container_compatible_range<bool> _Rg>
1409 constexpr void
1410 append_range(_Rg&& __rg)
1411 {
1412 // N.B. __rg may overlap with *this, so we must copy from __rg before
1413 // existing elements or iterators referring to *this are invalidated.
1414 // e.g. in v.append_range(views::concat(v, foo)) rg overlaps v.
1415 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1416 {
1417 const auto __n = size_type(ranges::distance(__rg));
1418
1419 // If there is no existing storage, there are no iterators that
1420 // can be referring to our storage, so it's safe to allocate now.
1421 if (capacity() == 0)
1422 reserve(__n);
1423
1424 const auto __sz = size();
1425 const auto __capacity = capacity();
1426 if ((__capacity - __sz) >= __n)
1427 {
1428 this->_M_impl._M_finish
1429 = ranges::copy(std::forward<_Rg>(__rg), end()).out;
1430 return;
1431 }
1432
1433 vector __tmp(get_allocator());
1434 __tmp.reserve(_M_check_len(__n, "vector::append_range"));
1435 __tmp._M_impl._M_finish
1436 = _M_copy_aligned(cbegin(), cend(), __tmp.begin());
1437 __tmp._M_impl._M_finish
1438 = ranges::copy(std::forward<_Rg>(__rg), __tmp.end()).out;
1439 swap(__tmp);
1440 }
1441 else
1442 {
1443 auto __first = ranges::begin(__rg);
1444 const auto __last = ranges::end(__rg);
1445
1446 // Fill up to the end of current capacity.
1447 for (auto __free = capacity() - size();
1448 __first != __last && __free > 0;
1449 ++__first, (void) --__free)
1450 emplace_back(*__first);
1451
1452 if (__first == __last)
1453 return;
1454
1455 // Copy the rest of the range to a new vector.
1456 ranges::subrange __rest(std::move(__first), __last);
1457 vector __tmp(from_range, __rest, get_allocator());
1458 insert(end(), __tmp.begin(), __tmp.end());
1459 }
1460 }
1461#endif // containers_ranges
1462
1463 _GLIBCXX20_CONSTEXPR
1464 void
1465 pop_back()
1466 { --this->_M_impl._M_finish; }
1467
1468 _GLIBCXX20_CONSTEXPR
1469 iterator
1470#if __cplusplus >= 201103L
1471 erase(const_iterator __position)
1472#else
1473 erase(iterator __position)
1474#endif
1475 { return _M_erase(__position._M_const_cast()); }
1476
1477 _GLIBCXX20_CONSTEXPR
1478 iterator
1479#if __cplusplus >= 201103L
1480 erase(const_iterator __first, const_iterator __last)
1481#else
1482 erase(iterator __first, iterator __last)
1483#endif
1484 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1485
1486 _GLIBCXX20_CONSTEXPR
1487 void
1488 resize(size_type __new_size, bool __x = bool())
1489 {
1490 if (__new_size < size())
1491 _M_erase_at_end(pos: begin() + difference_type(__new_size));
1492 else
1493 insert(end(), __new_size - size(), __x);
1494 }
1495
1496#if __cplusplus >= 201103L
1497 _GLIBCXX20_CONSTEXPR
1498 void
1499 shrink_to_fit()
1500 { _M_shrink_to_fit(); }
1501#endif
1502
1503 _GLIBCXX20_CONSTEXPR
1504 void
1505 flip() _GLIBCXX_NOEXCEPT
1506 {
1507 _Bit_type * const __end = this->_M_impl._M_end_addr();
1508 for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p)
1509 *__p = ~*__p;
1510 }
1511
1512 _GLIBCXX20_CONSTEXPR
1513 void
1514 clear() _GLIBCXX_NOEXCEPT
1515 { _M_erase_at_end(pos: begin()); }
1516
1517#if __cplusplus >= 201103L
1518 template<typename... _Args>
1519#if __cplusplus > 201402L
1520 _GLIBCXX20_CONSTEXPR
1521 reference
1522#else
1523 void
1524#endif
1525 emplace_back(_Args&&... __args)
1526 {
1527 push_back(x: bool(std::forward<_Args>(__args)...));
1528#if __cplusplus > 201402L
1529 return back();
1530#endif
1531 }
1532
1533 template<typename... _Args>
1534 _GLIBCXX20_CONSTEXPR
1535 iterator
1536 emplace(const_iterator __pos, _Args&&... __args)
1537 { return insert(__pos, bool(std::forward<_Args>(__args)...)); }
1538#endif
1539
1540 protected:
1541 // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
1542 _GLIBCXX20_CONSTEXPR
1543 iterator
1544 _M_copy_aligned(const_iterator __first, const_iterator __last,
1545 iterator __result)
1546 {
1547 _Bit_type* __q = std::copy(first: __first._M_p, last: __last._M_p, result: __result._M_p);
1548 return std::copy(first: const_iterator(__last._M_p, 0), __last,
1549 result: iterator(__q, 0));
1550 }
1551
1552 _GLIBCXX20_CONSTEXPR
1553 void
1554 _M_initialize(size_type __n)
1555 {
1556 if (__n)
1557 {
1558 _Bit_pointer __q = this->_M_allocate(__n);
1559 this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1560 iterator __start = iterator(std::__addressof(*__q), 0);
1561 this->_M_impl._M_start = __start;
1562 this->_M_impl._M_finish = __start + difference_type(__n);
1563 }
1564 }
1565
1566 _GLIBCXX20_CONSTEXPR
1567 void
1568 _M_initialize_value(bool __x) _GLIBCXX_NOEXCEPT
1569 {
1570 if (_Bit_type* __p = this->_M_impl._M_start._M_p)
1571 __fill_bvector_n(__p, this->_M_impl._M_end_addr() - __p, __x);
1572 }
1573
1574 _GLIBCXX20_CONSTEXPR
1575 void
1576 _M_reallocate(size_type __n);
1577
1578#if __cplusplus >= 201103L
1579 _GLIBCXX20_CONSTEXPR
1580 bool
1581 _M_shrink_to_fit();
1582#endif
1583
1584#if __cplusplus < 201103L
1585 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1586 // 438. Ambiguity in the "do the right thing" clause
1587 template<typename _Integer>
1588 void
1589 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1590 {
1591 _M_initialize(static_cast<size_type>(__n));
1592 _M_initialize_value(__x);
1593 }
1594
1595 template<typename _InputIterator>
1596 void
1597 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1598 __false_type)
1599 { _M_initialize_range(__first, __last,
1600 std::__iterator_category(__first)); }
1601#endif
1602
1603 template<typename _InputIterator>
1604 _GLIBCXX20_CONSTEXPR
1605 void
1606 _M_initialize_range(_InputIterator __first, _InputIterator __last,
1607 std::input_iterator_tag)
1608 {
1609 for (; __first != __last; ++__first)
1610 push_back(x: *__first);
1611 }
1612
1613 template<typename _ForwardIterator>
1614 _GLIBCXX20_CONSTEXPR
1615 void
1616 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
1617 std::forward_iterator_tag)
1618 {
1619 const size_type __n = std::distance(__first, __last);
1620 _M_initialize(__n);
1621 std::copy(__first, __last, begin());
1622 }
1623
1624#if __cplusplus < 201103L
1625 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1626 // 438. Ambiguity in the "do the right thing" clause
1627 template<typename _Integer>
1628 void
1629 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1630 { _M_fill_assign(__n, __val); }
1631
1632 template<class _InputIterator>
1633 void
1634 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1635 __false_type)
1636 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1637#endif
1638
1639 _GLIBCXX20_CONSTEXPR
1640 void
1641 _M_fill_assign(size_t __n, bool __x)
1642 {
1643 if (__n > size())
1644 {
1645 _M_initialize_value(__x);
1646 insert(end(), __n - size(), __x);
1647 }
1648 else
1649 {
1650 _M_erase_at_end(pos: begin() + __n);
1651 _M_initialize_value(__x);
1652 }
1653 }
1654
1655 template<typename _InputIterator>
1656 _GLIBCXX20_CONSTEXPR
1657 void
1658 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1659 std::input_iterator_tag)
1660 {
1661 iterator __cur = begin();
1662 for (; __first != __last && __cur != end(); ++__cur, (void)++__first)
1663 *__cur = *__first;
1664 if (__first == __last)
1665 _M_erase_at_end(pos: __cur);
1666 else
1667 insert(end(), __first, __last);
1668 }
1669
1670 template<typename _ForwardIterator>
1671 _GLIBCXX20_CONSTEXPR
1672 void
1673 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1674 std::forward_iterator_tag)
1675 {
1676 const size_type __len = std::distance(__first, __last);
1677 if (__len < size())
1678 _M_erase_at_end(pos: std::copy(__first, __last, begin()));
1679 else
1680 {
1681 _ForwardIterator __mid = __first;
1682 std::advance(__mid, size());
1683 std::copy(__first, __mid, begin());
1684 insert(end(), __mid, __last);
1685 }
1686 }
1687
1688#if __cplusplus < 201103L
1689 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1690 // 438. Ambiguity in the "do the right thing" clause
1691 template<typename _Integer>
1692 void
1693 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1694 __true_type)
1695 { _M_fill_insert(__pos, __n, __x); }
1696
1697 template<typename _InputIterator>
1698 void
1699 _M_insert_dispatch(iterator __pos,
1700 _InputIterator __first, _InputIterator __last,
1701 __false_type)
1702 { _M_insert_range(__pos, __first, __last,
1703 std::__iterator_category(__first)); }
1704#endif
1705
1706 _GLIBCXX20_CONSTEXPR
1707 void
1708 _M_fill_insert(iterator __position, size_type __n, bool __x);
1709
1710 template<typename _InputIterator>
1711 _GLIBCXX20_CONSTEXPR
1712 void
1713 _M_insert_range(iterator __pos, _InputIterator __first,
1714 _InputIterator __last, std::input_iterator_tag)
1715 {
1716 for (; __first != __last; ++__first)
1717 {
1718 __pos = insert(__pos, *__first);
1719 ++__pos;
1720 }
1721 }
1722
1723 template<typename _ForwardIterator>
1724 _GLIBCXX20_CONSTEXPR
1725 void
1726 _M_insert_range(iterator __position, _ForwardIterator __first,
1727 _ForwardIterator __last, std::forward_iterator_tag);
1728
1729 _GLIBCXX20_CONSTEXPR
1730 void
1731 _M_insert_aux(iterator __position, bool __x);
1732
1733 _GLIBCXX20_CONSTEXPR
1734 size_type
1735 _M_check_len(size_type __n, const char* __s) const
1736 {
1737 if (max_size() - size() < __n)
1738 __throw_length_error(__N(__s));
1739
1740 const size_type __len = size() + std::max(size(), __n);
1741 return (__len < size() || __len > max_size()) ? max_size() : __len;
1742 }
1743
1744 _GLIBCXX20_CONSTEXPR
1745 void
1746 _M_erase_at_end(iterator __pos)
1747 { this->_M_impl._M_finish = __pos; }
1748
1749 _GLIBCXX20_CONSTEXPR
1750 iterator
1751 _M_erase(iterator __pos);
1752
1753 _GLIBCXX20_CONSTEXPR
1754 iterator
1755 _M_erase(iterator __first, iterator __last);
1756
1757 protected:
1758 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1759 // DR 464. Suggestion for new member functions in standard containers.
1760 // N.B. DR 464 says nothing about vector<bool> but we need something
1761 // here due to the using-declaration in __gnu_debug::vector.
1762 // vector class.
1763#if __cplusplus >= 201103L
1764 void data() = delete;
1765#else
1766 void data() { }
1767#endif
1768 };
1769
1770_GLIBCXX_END_NAMESPACE_CONTAINER
1771
1772 // Fill a partial word.
1773 _GLIBCXX20_CONSTEXPR
1774 inline void
1775 __fill_bvector(_Bit_type* __v, unsigned int __first, unsigned int __last,
1776 bool __x) _GLIBCXX_NOEXCEPT
1777 {
1778 const _Bit_type __fmask = ~0ul << __first;
1779 const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last);
1780 const _Bit_type __mask = __fmask & __lmask;
1781
1782 if (__x)
1783 *__v |= __mask;
1784 else
1785 *__v &= ~__mask;
1786 }
1787
1788 // Fill N full words, as if using memset, but usable in constant expressions.
1789 __attribute__((__nonnull__))
1790 _GLIBCXX20_CONSTEXPR
1791 inline void
1792 __fill_bvector_n(_Bit_type* __p, size_t __n, bool __x) _GLIBCXX_NOEXCEPT
1793 {
1794#if __cpp_lib_is_constant_evaluated
1795 if (std::is_constant_evaluated())
1796 {
1797 for (size_t __i = 0; __i < __n; ++__i)
1798 __p[__i] = __x ? ~0ul : 0ul;
1799 return;
1800 }
1801#endif
1802 __builtin_memset(__p, __x ? ~0 : 0, __n * sizeof(_Bit_type));
1803 }
1804
1805
1806 _GLIBCXX20_CONSTEXPR
1807 inline void
1808 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator __first,
1809 _GLIBCXX_STD_C::_Bit_iterator __last, const bool& __x)
1810 {
1811 if (__first._M_p != __last._M_p)
1812 {
1813 _Bit_type* __first_p = __first._M_p;
1814 if (__first._M_offset != 0)
1815 __fill_bvector(v: __first_p++, first: __first._M_offset, last: _S_word_bit, __x);
1816
1817 __fill_bvector_n(p: __first_p, n: __last._M_p - __first_p, __x);
1818
1819 if (__last._M_offset != 0)
1820 __fill_bvector(v: __last._M_p, first: 0, last: __last._M_offset, __x);
1821 }
1822 else if (__first._M_offset != __last._M_offset)
1823 __fill_bvector(v: __first._M_p, first: __first._M_offset, last: __last._M_offset, __x);
1824 }
1825
1826#if __cplusplus >= 201103L
1827 // DR 1182.
1828 /// std::hash specialization for vector<bool>.
1829 template<typename _Alloc>
1830 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
1831 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1832 {
1833 size_t
1834 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
1835 };
1836#endif // C++11
1837
1838_GLIBCXX_END_NAMESPACE_VERSION
1839} // namespace std
1840
1841#endif
1842