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