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
_GLIBCXX_VISIBILITY(default)64 namespace 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 && __cpp_constexpr_dynamic_alloc
633 if (std::is_constant_evaluated())
634 {
635 __n = _S_nword(__n);
636 for (size_t __i = 0; __i < __n; ++__i)
637 std::construct_at(std::to_address(__p) + __i);
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 * @headerfile vector
676 * @since C++98
677 *
678 * @tparam _Alloc Allocator type.
679 *
680 * Note that vector<bool> does not actually meet the requirements for being
681 * a container. This is because the reference and pointer types are not
682 * really references and pointers to bool. See DR96 for details. @see
683 * vector for function documentation.
684 *
685 * In some terminology a %vector can be described as a dynamic
686 * C-style array, it offers fast and efficient access to individual
687 * elements in any order and saves the user from worrying about
688 * memory and size allocation. Subscripting ( @c [] ) access is
689 * also provided as with C-style arrays.
690 */
691 template<typename _Alloc>
692 class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
693 {
694 typedef _Bvector_base<_Alloc> _Base;
695 typedef typename _Base::_Bit_pointer _Bit_pointer;
696 typedef typename _Base::_Bit_alloc_traits _Bit_alloc_traits;
697
698 #if __cplusplus >= 201103L
699 friend struct std::hash<vector>;
700 #endif
701
702 public:
703 typedef bool value_type;
704 typedef size_t size_type;
705 typedef ptrdiff_t difference_type;
706 typedef _Bit_reference reference;
707 typedef bool const_reference;
708 typedef _Bit_reference* pointer;
709 typedef const bool* const_pointer;
710 typedef _Bit_iterator iterator;
711 typedef _Bit_const_iterator const_iterator;
712 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
713 typedef std::reverse_iterator<iterator> reverse_iterator;
714 typedef _Alloc allocator_type;
715
716 _GLIBCXX20_CONSTEXPR
717 allocator_type
718 get_allocator() const
719 { return _Base::get_allocator(); }
720
721 protected:
722 using _Base::_M_allocate;
723 using _Base::_M_deallocate;
724 using _Base::_S_nword;
725 using _Base::_M_get_Bit_allocator;
726
727 public:
728 #if __cplusplus >= 201103L
729 vector() = default;
730 #else
731 vector() { }
732 #endif
733
734 _GLIBCXX20_CONSTEXPR
735 explicit
736 vector(const allocator_type& __a)
737 : _Base(__a) { }
738
739 #if __cplusplus >= 201103L
740 _GLIBCXX20_CONSTEXPR
741 explicit
742 vector(size_type __n, const allocator_type& __a = allocator_type())
743 : vector(__n, false, __a)
744 { }
745
746 _GLIBCXX20_CONSTEXPR
747 vector(size_type __n, const bool& __value,
748 const allocator_type& __a = allocator_type())
749 #else
750 explicit
751 vector(size_type __n, const bool& __value = bool(),
752 const allocator_type& __a = allocator_type())
753 #endif
754 : _Base(__a)
755 {
756 _M_initialize(__n);
757 _M_initialize_value(__value);
758 }
759
760 _GLIBCXX20_CONSTEXPR
761 vector(const vector& __x)
762 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
763 {
764 _M_initialize(__x.size());
765 _M_copy_aligned(__x.begin(), __x.end(), begin());
766 }
767
768 #if __cplusplus >= 201103L
769 vector(vector&&) = default;
770
771 private:
772 _GLIBCXX20_CONSTEXPR
773 vector(vector&& __x, const allocator_type& __a, true_type) noexcept
774 : _Base(std::move(__x), __a)
775 { }
776
777 _GLIBCXX20_CONSTEXPR
778 vector(vector&& __x, const allocator_type& __a, false_type)
779 : _Base(__a)
780 {
781 if (__x.get_allocator() == __a)
782 this->_M_move_data(std::move(__x));
783 else
784 {
785 _M_initialize(__x.size());
786 _M_copy_aligned(__x.begin(), __x.end(), begin());
787 __x.clear();
788 }
789 }
790
791 public:
792 _GLIBCXX20_CONSTEXPR
793 vector(vector&& __x, const __type_identity_t<allocator_type>& __a)
794 noexcept(_Bit_alloc_traits::_S_always_equal())
795 : vector(std::move(__x), __a,
796 typename _Bit_alloc_traits::is_always_equal{})
797 { }
798
799 _GLIBCXX20_CONSTEXPR
800 vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
801 : _Base(__a)
802 {
803 _M_initialize(__x.size());
804 _M_copy_aligned(__x.begin(), __x.end(), begin());
805 }
806
807 _GLIBCXX20_CONSTEXPR
808 vector(initializer_list<bool> __l,
809 const allocator_type& __a = allocator_type())
810 : _Base(__a)
811 {
812 _M_initialize_range(__l.begin(), __l.end(),
813 random_access_iterator_tag());
814 }
815 #endif
816
817 #if __cplusplus >= 201103L
818 template<typename _InputIterator,
819 typename = std::_RequireInputIter<_InputIterator>>
820 _GLIBCXX20_CONSTEXPR
821 vector(_InputIterator __first, _InputIterator __last,
822 const allocator_type& __a = allocator_type())
823 : _Base(__a)
824 {
825 _M_initialize_range(__first, __last,
826 std::__iterator_category(__first));
827 }
828 #else
829 template<typename _InputIterator>
830 vector(_InputIterator __first, _InputIterator __last,
831 const allocator_type& __a = allocator_type())
832 : _Base(__a)
833 {
834 // Check whether it's an integral type. If so, it's not an iterator.
835 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
836 _M_initialize_dispatch(__first, __last, _Integral());
837 }
838 #endif
839
840 _GLIBCXX20_CONSTEXPR
841 ~vector() _GLIBCXX_NOEXCEPT { }
842
843 _GLIBCXX20_CONSTEXPR
844 vector&
845 operator=(const vector& __x)
846 {
847 if (&__x == this)
848 return *this;
849 #if __cplusplus >= 201103L
850 if (_Bit_alloc_traits::_S_propagate_on_copy_assign())
851 {
852 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator())
853 {
854 this->_M_deallocate();
855 std::__alloc_on_copy(_M_get_Bit_allocator(),
856 __x._M_get_Bit_allocator());
857 _M_initialize(__x.size());
858 }
859 else
860 std::__alloc_on_copy(_M_get_Bit_allocator(),
861 __x._M_get_Bit_allocator());
862 }
863 #endif
864 if (__x.size() > capacity())
865 {
866 this->_M_deallocate();
867 _M_initialize(__x.size());
868 }
869 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
870 begin());
871 return *this;
872 }
873
874 #if __cplusplus >= 201103L
875 _GLIBCXX20_CONSTEXPR
876 vector&
877 operator=(vector&& __x) noexcept(_Bit_alloc_traits::_S_nothrow_move())
878 {
879 if (_Bit_alloc_traits::_S_propagate_on_move_assign()
880 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator())
881 {
882 this->_M_deallocate();
883 this->_M_move_data(std::move(__x));
884 std::__alloc_on_move(_M_get_Bit_allocator(),
885 __x._M_get_Bit_allocator());
886 }
887 else
888 {
889 if (__x.size() > capacity())
890 {
891 this->_M_deallocate();
892 _M_initialize(__x.size());
893 }
894 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
895 begin());
896 __x.clear();
897 }
898 return *this;
899 }
900
901 _GLIBCXX20_CONSTEXPR
902 vector&
903 operator=(initializer_list<bool> __l)
904 {
905 this->assign(__l.begin(), __l.end());
906 return *this;
907 }
908 #endif
909
910 // assign(), a generalized assignment member function. Two
911 // versions: one that takes a count, and one that takes a range.
912 // The range version is a member template, so we dispatch on whether
913 // or not the type is an integer.
914 _GLIBCXX20_CONSTEXPR
915 void
916 assign(size_type __n, const bool& __x)
917 { _M_fill_assign(__n, __x); }
918
919 #if __cplusplus >= 201103L
920 template<typename _InputIterator,
921 typename = std::_RequireInputIter<_InputIterator>>
922 _GLIBCXX20_CONSTEXPR
923 void
924 assign(_InputIterator __first, _InputIterator __last)
925 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
926 #else
927 template<typename _InputIterator>
928 void
929 assign(_InputIterator __first, _InputIterator __last)
930 {
931 // Check whether it's an integral type. If so, it's not an iterator.
932 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
933 _M_assign_dispatch(__first, __last, _Integral());
934 }
935 #endif
936
937 #if __cplusplus >= 201103L
938 _GLIBCXX20_CONSTEXPR
939 void
940 assign(initializer_list<bool> __l)
941 { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); }
942 #endif
943
944 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
945 iterator
946 begin() _GLIBCXX_NOEXCEPT
947 { return iterator(this->_M_impl._M_start._M_p, 0); }
948
949 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
950 const_iterator
951 begin() const _GLIBCXX_NOEXCEPT
952 { return const_iterator(this->_M_impl._M_start._M_p, 0); }
953
954 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
955 iterator
956 end() _GLIBCXX_NOEXCEPT
957 { return this->_M_impl._M_finish; }
958
959 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
960 const_iterator
961 end() const _GLIBCXX_NOEXCEPT
962 { return this->_M_impl._M_finish; }
963
964 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
965 reverse_iterator
966 rbegin() _GLIBCXX_NOEXCEPT
967 { return reverse_iterator(end()); }
968
969 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
970 const_reverse_iterator
971 rbegin() const _GLIBCXX_NOEXCEPT
972 { return const_reverse_iterator(end()); }
973
974 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
975 reverse_iterator
976 rend() _GLIBCXX_NOEXCEPT
977 { return reverse_iterator(begin()); }
978
979 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
980 const_reverse_iterator
981 rend() const _GLIBCXX_NOEXCEPT
982 { return const_reverse_iterator(begin()); }
983
984 #if __cplusplus >= 201103L
985 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
986 const_iterator
987 cbegin() const noexcept
988 { return const_iterator(this->_M_impl._M_start._M_p, 0); }
989
990 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
991 const_iterator
992 cend() const noexcept
993 { return this->_M_impl._M_finish; }
994
995 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
996 const_reverse_iterator
997 crbegin() const noexcept
998 { return const_reverse_iterator(end()); }
999
1000 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1001 const_reverse_iterator
1002 crend() const noexcept
1003 { return const_reverse_iterator(begin()); }
1004 #endif
1005
1006 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1007 size_type
1008 size() const _GLIBCXX_NOEXCEPT
1009 { return size_type(end() - begin()); }
1010
1011 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1012 size_type
1013 max_size() const _GLIBCXX_NOEXCEPT
1014 {
1015 const size_type __isize =
1016 __gnu_cxx::__numeric_traits<difference_type>::__max
1017 - int(_S_word_bit) + 1;
1018 const size_type __asize
1019 = _Bit_alloc_traits::max_size(_M_get_Bit_allocator());
1020 return (__asize <= __isize / int(_S_word_bit)
1021 ? __asize * int(_S_word_bit) : __isize);
1022 }
1023
1024 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1025 size_type
1026 capacity() const _GLIBCXX_NOEXCEPT
1027 { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
1028 - begin()); }
1029
1030 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1031 bool
1032 empty() const _GLIBCXX_NOEXCEPT
1033 { return begin() == end(); }
1034
1035 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1036 reference
1037 operator[](size_type __n)
1038 { return begin()[__n]; }
1039
1040 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1041 const_reference
1042 operator[](size_type __n) const
1043 { return begin()[__n]; }
1044
1045 protected:
1046 _GLIBCXX20_CONSTEXPR
1047 void
1048 _M_range_check(size_type __n) const
1049 {
1050 if (__n >= this->size())
1051 __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n "
1052 "(which is %zu) >= this->size() "
1053 "(which is %zu)"),
1054 __n, this->size());
1055 }
1056
1057 public:
1058 _GLIBCXX20_CONSTEXPR
1059 reference
1060 at(size_type __n)
1061 {
1062 _M_range_check(__n);
1063 return (*this)[__n];
1064 }
1065
1066 _GLIBCXX20_CONSTEXPR
1067 const_reference
1068 at(size_type __n) const
1069 {
1070 _M_range_check(__n);
1071 return (*this)[__n];
1072 }
1073
1074 _GLIBCXX20_CONSTEXPR
1075 void
1076 reserve(size_type __n)
1077 {
1078 if (__n > max_size())
1079 __throw_length_error(__N("vector::reserve"));
1080 if (capacity() < __n)
1081 _M_reallocate(__n);
1082 }
1083
1084 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1085 reference
1086 front()
1087 { return *begin(); }
1088
1089 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1090 const_reference
1091 front() const
1092 { return *begin(); }
1093
1094 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1095 reference
1096 back()
1097 { return *(end() - 1); }
1098
1099 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1100 const_reference
1101 back() const
1102 { return *(end() - 1); }
1103
1104 _GLIBCXX20_CONSTEXPR
1105 void
1106 push_back(bool __x)
1107 {
1108 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
1109 *this->_M_impl._M_finish++ = __x;
1110 else
1111 _M_insert_aux(end(), __x);
1112 }
1113
1114 _GLIBCXX20_CONSTEXPR
1115 void
1116 swap(vector& __x) _GLIBCXX_NOEXCEPT
1117 {
1118 #if __cplusplus >= 201103L
1119 __glibcxx_assert(_Bit_alloc_traits::propagate_on_container_swap::value
1120 || _M_get_Bit_allocator() == __x._M_get_Bit_allocator());
1121 #endif
1122 this->_M_impl._M_swap_data(__x._M_impl);
1123 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(),
1124 __x._M_get_Bit_allocator());
1125 }
1126
1127 // [23.2.5]/1, third-to-last entry in synopsis listing
1128 _GLIBCXX20_CONSTEXPR
1129 static void
1130 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
1131 {
1132 bool __tmp = __x;
1133 __x = __y;
1134 __y = __tmp;
1135 }
1136
1137 _GLIBCXX20_CONSTEXPR
1138 iterator
1139 #if __cplusplus >= 201103L
1140 insert(const_iterator __position, const bool& __x)
1141 #else
1142 insert(iterator __position, const bool& __x)
1143 #endif
1144 {
1145 const difference_type __n = __position - begin();
1146 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()
1147 && __position == end())
1148 *this->_M_impl._M_finish++ = __x;
1149 else
1150 _M_insert_aux(__position._M_const_cast(), __x);
1151 return begin() + __n;
1152 }
1153
1154 #if _GLIBCXX_USE_DEPRECATED
1155 _GLIBCXX_DEPRECATED_SUGGEST("insert(position, false)")
1156 iterator
1157 insert(const_iterator __position)
1158 { return this->insert(__position._M_const_cast(), false); }
1159 #endif
1160
1161 #if __cplusplus >= 201103L
1162 template<typename _InputIterator,
1163 typename = std::_RequireInputIter<_InputIterator>>
1164 _GLIBCXX20_CONSTEXPR
1165 iterator
1166 insert(const_iterator __position,
1167 _InputIterator __first, _InputIterator __last)
1168 {
1169 difference_type __offset = __position - cbegin();
1170 _M_insert_range(__position._M_const_cast(),
1171 __first, __last,
1172 std::__iterator_category(__first));
1173 return begin() + __offset;
1174 }
1175 #else
1176 template<typename _InputIterator>
1177 void
1178 insert(iterator __position,
1179 _InputIterator __first, _InputIterator __last)
1180 {
1181 // Check whether it's an integral type. If so, it's not an iterator.
1182 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1183 _M_insert_dispatch(__position, __first, __last, _Integral());
1184 }
1185 #endif
1186
1187 #if __cplusplus >= 201103L
1188 _GLIBCXX20_CONSTEXPR
1189 iterator
1190 insert(const_iterator __position, size_type __n, const bool& __x)
1191 {
1192 difference_type __offset = __position - cbegin();
1193 _M_fill_insert(__position._M_const_cast(), __n, __x);
1194 return begin() + __offset;
1195 }
1196 #else
1197 void
1198 insert(iterator __position, size_type __n, const bool& __x)
1199 { _M_fill_insert(__position, __n, __x); }
1200 #endif
1201
1202 #if __cplusplus >= 201103L
1203 _GLIBCXX20_CONSTEXPR
1204 iterator
1205 insert(const_iterator __p, initializer_list<bool> __l)
1206 { return this->insert(__p, __l.begin(), __l.end()); }
1207 #endif
1208
1209 _GLIBCXX20_CONSTEXPR
1210 void
1211 pop_back()
1212 { --this->_M_impl._M_finish; }
1213
1214 _GLIBCXX20_CONSTEXPR
1215 iterator
1216 #if __cplusplus >= 201103L
1217 erase(const_iterator __position)
1218 #else
1219 erase(iterator __position)
1220 #endif
1221 { return _M_erase(__position._M_const_cast()); }
1222
1223 _GLIBCXX20_CONSTEXPR
1224 iterator
1225 #if __cplusplus >= 201103L
1226 erase(const_iterator __first, const_iterator __last)
1227 #else
1228 erase(iterator __first, iterator __last)
1229 #endif
1230 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1231
1232 _GLIBCXX20_CONSTEXPR
1233 void
1234 resize(size_type __new_size, bool __x = bool())
1235 {
1236 if (__new_size < size())
1237 _M_erase_at_end(begin() + difference_type(__new_size));
1238 else
1239 insert(end(), __new_size - size(), __x);
1240 }
1241
1242 #if __cplusplus >= 201103L
1243 _GLIBCXX20_CONSTEXPR
1244 void
1245 shrink_to_fit()
1246 { _M_shrink_to_fit(); }
1247 #endif
1248
1249 _GLIBCXX20_CONSTEXPR
1250 void
1251 flip() _GLIBCXX_NOEXCEPT
1252 {
1253 _Bit_type * const __end = this->_M_impl._M_end_addr();
1254 for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p)
1255 *__p = ~*__p;
1256 }
1257
1258 _GLIBCXX20_CONSTEXPR
1259 void
1260 clear() _GLIBCXX_NOEXCEPT
1261 { _M_erase_at_end(begin()); }
1262
1263 #if __cplusplus >= 201103L
1264 template<typename... _Args>
1265 #if __cplusplus > 201402L
1266 _GLIBCXX20_CONSTEXPR
1267 reference
1268 #else
1269 void
1270 #endif
1271 emplace_back(_Args&&... __args)
1272 {
1273 push_back(bool(__args...));
1274 #if __cplusplus > 201402L
1275 return back();
1276 #endif
1277 }
1278
1279 template<typename... _Args>
1280 _GLIBCXX20_CONSTEXPR
1281 iterator
1282 emplace(const_iterator __pos, _Args&&... __args)
1283 { return insert(__pos, bool(__args...)); }
1284 #endif
1285
1286 protected:
1287 // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
1288 _GLIBCXX20_CONSTEXPR
1289 iterator
1290 _M_copy_aligned(const_iterator __first, const_iterator __last,
1291 iterator __result)
1292 {
1293 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
1294 return std::copy(const_iterator(__last._M_p, 0), __last,
1295 iterator(__q, 0));
1296 }
1297
1298 _GLIBCXX20_CONSTEXPR
1299 void
1300 _M_initialize(size_type __n)
1301 {
1302 if (__n)
1303 {
1304 _Bit_pointer __q = this->_M_allocate(__n);
1305 this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1306 iterator __start = iterator(std::__addressof(*__q), 0);
1307 this->_M_impl._M_start = __start;
1308 this->_M_impl._M_finish = __start + difference_type(__n);
1309 }
1310 }
1311
1312 _GLIBCXX20_CONSTEXPR
1313 void
1314 _M_initialize_value(bool __x) _GLIBCXX_NOEXCEPT
1315 {
1316 if (_Bit_type* __p = this->_M_impl._M_start._M_p)
1317 __fill_bvector_n(__p, this->_M_impl._M_end_addr() - __p, __x);
1318 }
1319
1320 _GLIBCXX20_CONSTEXPR
1321 void
1322 _M_reallocate(size_type __n);
1323
1324 #if __cplusplus >= 201103L
1325 _GLIBCXX20_CONSTEXPR
1326 bool
1327 _M_shrink_to_fit();
1328 #endif
1329
1330 #if __cplusplus < 201103L
1331 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1332 // 438. Ambiguity in the "do the right thing" clause
1333 template<typename _Integer>
1334 void
1335 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1336 {
1337 _M_initialize(static_cast<size_type>(__n));
1338 _M_initialize_value(__x);
1339 }
1340
1341 template<typename _InputIterator>
1342 void
1343 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1344 __false_type)
1345 { _M_initialize_range(__first, __last,
1346 std::__iterator_category(__first)); }
1347 #endif
1348
1349 template<typename _InputIterator>
1350 _GLIBCXX20_CONSTEXPR
1351 void
1352 _M_initialize_range(_InputIterator __first, _InputIterator __last,
1353 std::input_iterator_tag)
1354 {
1355 for (; __first != __last; ++__first)
1356 push_back(*__first);
1357 }
1358
1359 template<typename _ForwardIterator>
1360 _GLIBCXX20_CONSTEXPR
1361 void
1362 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
1363 std::forward_iterator_tag)
1364 {
1365 const size_type __n = std::distance(__first, __last);
1366 _M_initialize(__n);
1367 std::copy(__first, __last, begin());
1368 }
1369
1370 #if __cplusplus < 201103L
1371 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1372 // 438. Ambiguity in the "do the right thing" clause
1373 template<typename _Integer>
1374 void
1375 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1376 { _M_fill_assign(__n, __val); }
1377
1378 template<class _InputIterator>
1379 void
1380 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1381 __false_type)
1382 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1383 #endif
1384
1385 _GLIBCXX20_CONSTEXPR
1386 void
1387 _M_fill_assign(size_t __n, bool __x)
1388 {
1389 if (__n > size())
1390 {
1391 _M_initialize_value(__x);
1392 insert(end(), __n - size(), __x);
1393 }
1394 else
1395 {
1396 _M_erase_at_end(begin() + __n);
1397 _M_initialize_value(__x);
1398 }
1399 }
1400
1401 template<typename _InputIterator>
1402 _GLIBCXX20_CONSTEXPR
1403 void
1404 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1405 std::input_iterator_tag)
1406 {
1407 iterator __cur = begin();
1408 for (; __first != __last && __cur != end(); ++__cur, (void)++__first)
1409 *__cur = *__first;
1410 if (__first == __last)
1411 _M_erase_at_end(__cur);
1412 else
1413 insert(end(), __first, __last);
1414 }
1415
1416 template<typename _ForwardIterator>
1417 _GLIBCXX20_CONSTEXPR
1418 void
1419 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1420 std::forward_iterator_tag)
1421 {
1422 const size_type __len = std::distance(__first, __last);
1423 if (__len < size())
1424 _M_erase_at_end(std::copy(__first, __last, begin()));
1425 else
1426 {
1427 _ForwardIterator __mid = __first;
1428 std::advance(__mid, size());
1429 std::copy(__first, __mid, begin());
1430 insert(end(), __mid, __last);
1431 }
1432 }
1433
1434 #if __cplusplus < 201103L
1435 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1436 // 438. Ambiguity in the "do the right thing" clause
1437 template<typename _Integer>
1438 void
1439 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1440 __true_type)
1441 { _M_fill_insert(__pos, __n, __x); }
1442
1443 template<typename _InputIterator>
1444 void
1445 _M_insert_dispatch(iterator __pos,
1446 _InputIterator __first, _InputIterator __last,
1447 __false_type)
1448 { _M_insert_range(__pos, __first, __last,
1449 std::__iterator_category(__first)); }
1450 #endif
1451
1452 _GLIBCXX20_CONSTEXPR
1453 void
1454 _M_fill_insert(iterator __position, size_type __n, bool __x);
1455
1456 template<typename _InputIterator>
1457 _GLIBCXX20_CONSTEXPR
1458 void
1459 _M_insert_range(iterator __pos, _InputIterator __first,
1460 _InputIterator __last, std::input_iterator_tag)
1461 {
1462 for (; __first != __last; ++__first)
1463 {
1464 __pos = insert(__pos, *__first);
1465 ++__pos;
1466 }
1467 }
1468
1469 template<typename _ForwardIterator>
1470 _GLIBCXX20_CONSTEXPR
1471 void
1472 _M_insert_range(iterator __position, _ForwardIterator __first,
1473 _ForwardIterator __last, std::forward_iterator_tag);
1474
1475 _GLIBCXX20_CONSTEXPR
1476 void
1477 _M_insert_aux(iterator __position, bool __x);
1478
1479 _GLIBCXX20_CONSTEXPR
1480 size_type
1481 _M_check_len(size_type __n, const char* __s) const
1482 {
1483 if (max_size() - size() < __n)
1484 __throw_length_error(__N(__s));
1485
1486 const size_type __len = size() + std::max(size(), __n);
1487 return (__len < size() || __len > max_size()) ? max_size() : __len;
1488 }
1489
1490 _GLIBCXX20_CONSTEXPR
1491 void
1492 _M_erase_at_end(iterator __pos)
1493 { this->_M_impl._M_finish = __pos; }
1494
1495 _GLIBCXX20_CONSTEXPR
1496 iterator
1497 _M_erase(iterator __pos);
1498
1499 _GLIBCXX20_CONSTEXPR
1500 iterator
1501 _M_erase(iterator __first, iterator __last);
1502
1503 protected:
1504 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1505 // DR 464. Suggestion for new member functions in standard containers.
1506 // N.B. DR 464 says nothing about vector<bool> but we need something
1507 // here due to the using-declaration in __gnu_debug::vector.
1508 // vector class.
1509 #if __cplusplus >= 201103L
1510 void data() = delete;
1511 #else
1512 void data() { }
1513 #endif
1514 };
1515
1516 _GLIBCXX_END_NAMESPACE_CONTAINER
1517
1518 // Fill a partial word.
1519 _GLIBCXX20_CONSTEXPR
1520 inline void
1521 __fill_bvector(_Bit_type* __v, unsigned int __first, unsigned int __last,
1522 bool __x) _GLIBCXX_NOEXCEPT
1523 {
1524 const _Bit_type __fmask = ~0ul << __first;
1525 const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last);
1526 const _Bit_type __mask = __fmask & __lmask;
1527
1528 if (__x)
1529 *__v |= __mask;
1530 else
1531 *__v &= ~__mask;
1532 }
1533
1534 // Fill N full words, as if using memset, but usable in constant expressions.
1535 __attribute__((__nonnull__))
1536 _GLIBCXX20_CONSTEXPR
1537 inline void
1538 __fill_bvector_n(_Bit_type* __p, size_t __n, bool __x) _GLIBCXX_NOEXCEPT
1539 {
1540 #if __cpp_lib_is_constant_evaluated
1541 if (std::is_constant_evaluated())
1542 {
1543 for (size_t __i = 0; __i < __n; ++__i)
1544 __p[__i] = __x ? ~0ul : 0ul;
1545 return;
1546 }
1547 #endif
1548 __builtin_memset(__p, __x ? ~0 : 0, __n * sizeof(_Bit_type));
1549 }
1550
1551
1552 _GLIBCXX20_CONSTEXPR
1553 inline void
1554 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator __first,
1555 _GLIBCXX_STD_C::_Bit_iterator __last, const bool& __x)
1556 {
1557 if (__first._M_p != __last._M_p)
1558 {
1559 _Bit_type* __first_p = __first._M_p;
1560 if (__first._M_offset != 0)
1561 __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x);
1562
1563 __fill_bvector_n(__first_p, __last._M_p - __first_p, __x);
1564
1565 if (__last._M_offset != 0)
1566 __fill_bvector(__last._M_p, 0, __last._M_offset, __x);
1567 }
1568 else if (__first._M_offset != __last._M_offset)
1569 __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x);
1570 }
1571
1572 #if __cplusplus >= 201103L
1573 // DR 1182.
1574 /// std::hash specialization for vector<bool>.
1575 template<typename _Alloc>
1576 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
1577 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1578 {
1579 size_t
1580 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
1581 };
1582 #endif // C++11
1583
1584 _GLIBCXX_END_NAMESPACE_VERSION
1585 } // namespace std
1586
1587 #endif
1588