libstdc++
stl_bvector.h
Go to the documentation of this file.
1// vector<bool> specialization -*- C++ -*-
2
3// Copyright (C) 2001-2024 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>
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 {
535 rebind<_Bit_type>::other _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;
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;
751
752#if __cplusplus >= 201103L
753 friend struct std::hash<vector>;
754#endif
755
756 public:
757 typedef bool value_type;
758 typedef size_t size_type;
759 typedef ptrdiff_t difference_type;
760 typedef _Bit_reference reference;
761 typedef bool const_reference;
762 typedef _Bit_reference* pointer;
763 typedef const bool* const_pointer;
764 typedef _Bit_iterator iterator;
765 typedef _Bit_const_iterator const_iterator;
768 typedef _Alloc allocator_type;
769
770 _GLIBCXX20_CONSTEXPR
771 allocator_type
772 get_allocator() const
773 { return _Base::get_allocator(); }
774
775 protected:
776 using _Base::_M_allocate;
777 using _Base::_M_deallocate;
778 using _Base::_S_nword;
779 using _Base::_M_get_Bit_allocator;
780
781 public:
782#if __cplusplus >= 201103L
783 vector() = default;
784#else
785 vector() { }
786#endif
787
788 _GLIBCXX20_CONSTEXPR
789 explicit
790 vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
791 : _Base(__a) { }
792
793#if __cplusplus >= 201103L
794 _GLIBCXX20_CONSTEXPR
795 explicit
796 vector(size_type __n, const allocator_type& __a = allocator_type())
797 : vector(__n, false, __a)
798 { }
799
800 _GLIBCXX20_CONSTEXPR
801 vector(size_type __n, const bool& __value,
802 const allocator_type& __a = allocator_type())
803#else
804 explicit
805 vector(size_type __n, const bool& __value = bool(),
806 const allocator_type& __a = allocator_type())
807#endif
808 : _Base(__a)
809 {
810 _M_initialize(__n);
811 _M_initialize_value(__value);
812 }
813
814 _GLIBCXX20_CONSTEXPR
815 vector(const vector& __x)
816 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
817 {
818 const_iterator __xbegin = __x.begin(), __xend = __x.end();
819 _M_initialize(__x.size());
820 _M_copy_aligned(__xbegin, __xend, begin());
821 }
822
823#if __cplusplus >= 201103L
824 vector(vector&&) = default;
825
826 private:
827 _GLIBCXX20_CONSTEXPR
828 vector(vector&& __x, const allocator_type& __a, true_type) noexcept
829 : _Base(std::move(__x), __a)
830 { }
831
832 _GLIBCXX20_CONSTEXPR
833 vector(vector&& __x, const allocator_type& __a, false_type)
834 : _Base(__a)
835 {
836 if (__x.get_allocator() == __a)
837 this->_M_move_data(std::move(__x));
838 else
839 {
840 _M_initialize(__x.size());
841 _M_copy_aligned(__x.begin(), __x.end(), begin());
842 __x.clear();
843 }
844 }
845
846 public:
847 _GLIBCXX20_CONSTEXPR
848 vector(vector&& __x, const __type_identity_t<allocator_type>& __a)
849 noexcept(_Bit_alloc_traits::_S_always_equal())
850 : vector(std::move(__x), __a,
852 { }
853
854 _GLIBCXX20_CONSTEXPR
855 vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
856 : _Base(__a)
857 {
858 _M_initialize(__x.size());
859 _M_copy_aligned(__x.begin(), __x.end(), begin());
860 }
861
862 _GLIBCXX20_CONSTEXPR
864 const allocator_type& __a = allocator_type())
865 : _Base(__a)
866 {
867 _M_initialize_range(__l.begin(), __l.end(),
869 }
870#endif
871
872#if __cplusplus >= 201103L
873 template<typename _InputIterator,
874 typename = std::_RequireInputIter<_InputIterator>>
875 _GLIBCXX20_CONSTEXPR
876 vector(_InputIterator __first, _InputIterator __last,
877 const allocator_type& __a = allocator_type())
878 : _Base(__a)
879 {
880 _M_initialize_range(__first, __last,
881 std::__iterator_category(__first));
882 }
883#else
884 template<typename _InputIterator>
885 vector(_InputIterator __first, _InputIterator __last,
886 const allocator_type& __a = allocator_type())
887 : _Base(__a)
888 {
889 // Check whether it's an integral type. If so, it's not an iterator.
890 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
891 _M_initialize_dispatch(__first, __last, _Integral());
892 }
893#endif
894
895#if __glibcxx_ranges_to_container // C++ >= 23
896 /**
897 * @brief Construct a vector from a range.
898 * @since C++23
899 */
900 template<__detail::__container_compatible_range<bool> _Rg>
901 constexpr
902 vector(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc())
903 : _Base(__a)
904 {
905 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
906 {
907 _M_initialize(size_type(ranges::distance(__rg)));
908 ranges::copy(__rg, begin());
909 }
910 else
911 {
912 auto __first = ranges::begin(__rg);
913 const auto __last = ranges::end(__rg);
914 for (; __first != __last; ++__first)
915 emplace_back(*__first);
916 }
917 }
918#endif
919
920 _GLIBCXX20_CONSTEXPR
921 ~vector() _GLIBCXX_NOEXCEPT { }
922
923 _GLIBCXX20_CONSTEXPR
924 vector&
925 operator=(const vector& __x)
926 {
927 if (&__x == this)
928 return *this;
929#if __cplusplus >= 201103L
930 if (_Bit_alloc_traits::_S_propagate_on_copy_assign())
931 {
932 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator())
933 {
934 this->_M_deallocate();
935 std::__alloc_on_copy(_M_get_Bit_allocator(),
936 __x._M_get_Bit_allocator());
937 _M_initialize(__x.size());
938 }
939 else
940 std::__alloc_on_copy(_M_get_Bit_allocator(),
941 __x._M_get_Bit_allocator());
942 }
943#endif
944 if (__x.size() > capacity())
945 {
946 this->_M_deallocate();
947 _M_initialize(__x.size());
948 }
949 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
950 begin());
951 return *this;
952 }
953
954#if __cplusplus >= 201103L
955 _GLIBCXX20_CONSTEXPR
956 vector&
957 operator=(vector&& __x) noexcept(_Bit_alloc_traits::_S_nothrow_move())
958 {
959 if (_Bit_alloc_traits::_S_propagate_on_move_assign()
960 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator())
961 {
962 this->_M_deallocate();
963 this->_M_move_data(std::move(__x));
964 std::__alloc_on_move(_M_get_Bit_allocator(),
965 __x._M_get_Bit_allocator());
966 }
967 else
968 {
969 if (__x.size() > capacity())
970 {
971 this->_M_deallocate();
972 _M_initialize(__x.size());
973 }
974 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
975 begin());
976 __x.clear();
977 }
978 return *this;
979 }
980
981 _GLIBCXX20_CONSTEXPR
982 vector&
984 {
985 this->assign(__l.begin(), __l.end());
986 return *this;
987 }
988#endif
989
990 // assign(), a generalized assignment member function. Two
991 // versions: one that takes a count, and one that takes a range.
992 // The range version is a member template, so we dispatch on whether
993 // or not the type is an integer.
994 _GLIBCXX20_CONSTEXPR
995 void
996 assign(size_type __n, const bool& __x)
997 { _M_fill_assign(__n, __x); }
998
999#if __cplusplus >= 201103L
1000 template<typename _InputIterator,
1001 typename = std::_RequireInputIter<_InputIterator>>
1002 _GLIBCXX20_CONSTEXPR
1003 void
1004 assign(_InputIterator __first, _InputIterator __last)
1005 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1006#else
1007 template<typename _InputIterator>
1008 void
1009 assign(_InputIterator __first, _InputIterator __last)
1010 {
1011 // Check whether it's an integral type. If so, it's not an iterator.
1012 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1013 _M_assign_dispatch(__first, __last, _Integral());
1014 }
1015#endif
1016
1017#if __cplusplus >= 201103L
1018 _GLIBCXX20_CONSTEXPR
1019 void
1021 { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); }
1022#endif
1023
1024#if __glibcxx_ranges_to_container // C++ >= 23
1025 /**
1026 * @brief Assign a range to the vector.
1027 * @since C++23
1028 */
1029 template<__detail::__container_compatible_range<bool> _Rg>
1030 constexpr void
1031 assign_range(_Rg&& __rg)
1032 {
1033 static_assert(assignable_from<bool&, ranges::range_reference_t<_Rg>>);
1034 clear();
1035 append_range(std::forward<_Rg>(__rg));
1036 }
1037#endif
1038
1039 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1040 iterator
1041 begin() _GLIBCXX_NOEXCEPT
1042 { return iterator(this->_M_impl._M_start._M_p, 0); }
1043
1044 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1045 const_iterator
1046 begin() const _GLIBCXX_NOEXCEPT
1047 { return const_iterator(this->_M_impl._M_start._M_p, 0); }
1048
1049 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1050 iterator
1051 end() _GLIBCXX_NOEXCEPT
1052 { return this->_M_impl._M_finish; }
1053
1054 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1055 const_iterator
1056 end() const _GLIBCXX_NOEXCEPT
1057 { return this->_M_impl._M_finish; }
1058
1059 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1061 rbegin() _GLIBCXX_NOEXCEPT
1062 { return reverse_iterator(end()); }
1063
1064 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1066 rbegin() const _GLIBCXX_NOEXCEPT
1067 { return const_reverse_iterator(end()); }
1068
1069 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1071 rend() _GLIBCXX_NOEXCEPT
1072 { return reverse_iterator(begin()); }
1073
1074 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1076 rend() const _GLIBCXX_NOEXCEPT
1077 { return const_reverse_iterator(begin()); }
1078
1079#if __cplusplus >= 201103L
1080 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1081 const_iterator
1082 cbegin() const noexcept
1083 { return const_iterator(this->_M_impl._M_start._M_p, 0); }
1084
1085 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1086 const_iterator
1087 cend() const noexcept
1088 { return this->_M_impl._M_finish; }
1089
1090 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1092 crbegin() const noexcept
1093 { return const_reverse_iterator(end()); }
1094
1095 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1097 crend() const noexcept
1098 { return const_reverse_iterator(begin()); }
1099#endif
1100
1101 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1102 size_type
1103 size() const _GLIBCXX_NOEXCEPT
1104 { return size_type(end() - begin()); }
1105
1106 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1107 size_type
1108 max_size() const _GLIBCXX_NOEXCEPT
1109 {
1110 const size_type __isize =
1111 __gnu_cxx::__numeric_traits<difference_type>::__max
1112 - int(_S_word_bit) + 1;
1113 const size_type __asize
1114 = _Bit_alloc_traits::max_size(_M_get_Bit_allocator());
1115 return (__asize <= __isize / int(_S_word_bit)
1116 ? __asize * int(_S_word_bit) : __isize);
1117 }
1118
1119 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1120 size_type
1121 capacity() const _GLIBCXX_NOEXCEPT
1122 { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
1123 - begin()); }
1124
1125 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1126 bool
1127 empty() const _GLIBCXX_NOEXCEPT
1128 { return begin() == end(); }
1129
1130 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1131 reference
1132 operator[](size_type __n)
1133 {
1134 __glibcxx_requires_subscript(__n);
1135 return begin()[__n];
1136 }
1137
1138 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1139 const_reference
1140 operator[](size_type __n) const
1141 {
1142 __glibcxx_requires_subscript(__n);
1143 return begin()[__n];
1144 }
1145
1146 protected:
1147 _GLIBCXX20_CONSTEXPR
1148 void
1149 _M_range_check(size_type __n) const
1150 {
1151 if (__n >= this->size())
1152 __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n "
1153 "(which is %zu) >= this->size() "
1154 "(which is %zu)"),
1155 __n, this->size());
1156 }
1157
1158 public:
1159 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1160 reference
1161 at(size_type __n)
1162 {
1163 _M_range_check(__n);
1164 return (*this)[__n];
1165 }
1166
1167 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1168 const_reference
1169 at(size_type __n) const
1170 {
1171 _M_range_check(__n);
1172 return (*this)[__n];
1173 }
1174
1175 _GLIBCXX20_CONSTEXPR
1176 void
1177 reserve(size_type __n)
1178 {
1179 if (__n > max_size())
1180 __throw_length_error(__N("vector::reserve"));
1181 if (capacity() < __n)
1182 _M_reallocate(__n);
1183 }
1184
1185 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1186 reference
1187 front()
1188 {
1189 __glibcxx_requires_nonempty();
1190 return *begin();
1191 }
1192
1193 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1194 const_reference
1195 front() const
1196 {
1197 __glibcxx_requires_nonempty();
1198 return *begin();
1199 }
1200
1201 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1202 reference
1203 back()
1204 {
1205 __glibcxx_requires_nonempty();
1206 return *(end() - 1);
1207 }
1208
1209 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1210 const_reference
1211 back() const
1212 {
1213 __glibcxx_requires_nonempty();
1214 return *(end() - 1);
1215 }
1216
1217 _GLIBCXX20_CONSTEXPR
1218 void
1219 push_back(bool __x)
1220 {
1221 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
1222 *this->_M_impl._M_finish++ = __x;
1223 else
1224 _M_insert_aux(end(), __x);
1225 }
1226
1227 _GLIBCXX20_CONSTEXPR
1228 void
1229 swap(vector& __x) _GLIBCXX_NOEXCEPT
1230 {
1231#if __cplusplus >= 201103L
1232 __glibcxx_assert(_Bit_alloc_traits::propagate_on_container_swap::value
1233 || _M_get_Bit_allocator() == __x._M_get_Bit_allocator());
1234#endif
1235 this->_M_impl._M_swap_data(__x._M_impl);
1236 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(),
1237 __x._M_get_Bit_allocator());
1238 }
1239
1240 // [23.2.5]/1, third-to-last entry in synopsis listing
1241 _GLIBCXX20_CONSTEXPR
1242 static void
1243 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
1244 {
1245 bool __tmp = __x;
1246 __x = __y;
1247 __y = __tmp;
1248 }
1249
1250 _GLIBCXX20_CONSTEXPR
1251 iterator
1252#if __cplusplus >= 201103L
1253 insert(const_iterator __position, const bool& __x)
1254#else
1255 insert(iterator __position, const bool& __x)
1256#endif
1257 {
1258 const difference_type __n = __position - begin();
1259 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()
1260 && __position == end())
1261 *this->_M_impl._M_finish++ = __x;
1262 else
1263 _M_insert_aux(__position._M_const_cast(), __x);
1264 return begin() + __n;
1265 }
1266
1267#if _GLIBCXX_USE_DEPRECATED
1268 _GLIBCXX_DEPRECATED_SUGGEST("insert(position, false)")
1269 iterator
1270 insert(const_iterator __position)
1271 { return this->insert(__position._M_const_cast(), false); }
1272#endif
1273
1274#if __cplusplus >= 201103L
1275 template<typename _InputIterator,
1276 typename = std::_RequireInputIter<_InputIterator>>
1277 _GLIBCXX20_CONSTEXPR
1278 iterator
1279 insert(const_iterator __position,
1280 _InputIterator __first, _InputIterator __last)
1281 {
1282 difference_type __offset = __position - cbegin();
1283 _M_insert_range(__position._M_const_cast(),
1284 __first, __last,
1285 std::__iterator_category(__first));
1286 return begin() + __offset;
1287 }
1288#else
1289 template<typename _InputIterator>
1290 void
1291 insert(iterator __position,
1292 _InputIterator __first, _InputIterator __last)
1293 {
1294 // Check whether it's an integral type. If so, it's not an iterator.
1295 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1296 _M_insert_dispatch(__position, __first, __last, _Integral());
1297 }
1298#endif
1299
1300#if __cplusplus >= 201103L
1301 _GLIBCXX20_CONSTEXPR
1302 iterator
1303 insert(const_iterator __position, size_type __n, const bool& __x)
1304 {
1305 difference_type __offset = __position - cbegin();
1306 _M_fill_insert(__position._M_const_cast(), __n, __x);
1307 return begin() + __offset;
1308 }
1309#else
1310 void
1311 insert(iterator __position, size_type __n, const bool& __x)
1312 { _M_fill_insert(__position, __n, __x); }
1313#endif
1314
1315#if __cplusplus >= 201103L
1316 _GLIBCXX20_CONSTEXPR
1317 iterator
1318 insert(const_iterator __p, initializer_list<bool> __l)
1319 { return this->insert(__p, __l.begin(), __l.end()); }
1320#endif
1321
1322#if __glibcxx_ranges_to_container // C++ >= 23
1323 /**
1324 * @brief Insert a range into the vector.
1325 * @since C++23
1326 */
1327 template<__detail::__container_compatible_range<bool> _Rg>
1328 constexpr iterator
1329 insert_range(const_iterator __pos, _Rg&& __rg)
1330 {
1331 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1332 {
1333 if (auto __n = size_type(ranges::distance(__rg)))
1334 {
1335 if (capacity() - size() >= __n)
1336 {
1337 std::copy_backward(__pos._M_const_cast(), end(),
1338 this->_M_impl._M_finish
1339 + difference_type(__n));
1340 auto __i = ranges::copy(__rg, __pos._M_const_cast()).out;
1341 this->_M_impl._M_finish += difference_type(__n);
1342 return __i;
1343 }
1344 else
1345 {
1346 const size_type __len =
1347 _M_check_len(__n, "vector<bool>::insert_range");
1348 const iterator __begin = begin(), __end = end();
1349 _Bit_pointer __q = this->_M_allocate(__len);
1350 iterator __start(std::__addressof(*__q), 0);
1351 iterator __i = _M_copy_aligned(__begin,
1352 __pos._M_const_cast(),
1353 __start);
1354 __i = ranges::copy(__rg, __i).out;
1355 iterator __finish = std::copy(__pos._M_const_cast(),
1356 __end, __i);
1357 this->_M_deallocate();
1358 this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
1359 this->_M_impl._M_start = __start;
1360 this->_M_impl._M_finish = __finish;
1361 return __i;
1362 }
1363 }
1364 else
1365 return __pos._M_const_cast();
1366 }
1367 else
1368 return insert_range(__pos,
1369 vector(from_range, __rg, get_allocator()));
1370 }
1371
1372 /**
1373 * @brief Append a range at the end of the vector.
1374 * @since C++23
1375 */
1376 template<__detail::__container_compatible_range<bool> _Rg>
1377 constexpr void
1378 append_range(_Rg&& __rg)
1379 {
1380 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1381 {
1382 reserve(size() + size_type(ranges::distance(__rg)));
1383 this->_M_impl._M_finish = ranges::copy(__rg, end()).out;
1384 }
1385 else
1386 {
1387 auto __first = ranges::begin(__rg);
1388 const auto __last = ranges::end(__rg);
1389 size_type __n = size();
1390 const size_type __cap = capacity();
1391 for (; __first != __last && __n < __cap; ++__first, (void)++__n)
1392 emplace_back(*__first);
1393 if (__first != __last)
1394 {
1395 ranges::subrange __rest(std::move(__first), __last);
1396 append_range(vector(from_range, __rest, get_allocator()));
1397 }
1398 }
1399 }
1400#endif // ranges_to_container
1401
1402 _GLIBCXX20_CONSTEXPR
1403 void
1404 pop_back()
1405 { --this->_M_impl._M_finish; }
1406
1407 _GLIBCXX20_CONSTEXPR
1408 iterator
1409#if __cplusplus >= 201103L
1410 erase(const_iterator __position)
1411#else
1412 erase(iterator __position)
1413#endif
1414 { return _M_erase(__position._M_const_cast()); }
1415
1416 _GLIBCXX20_CONSTEXPR
1417 iterator
1418#if __cplusplus >= 201103L
1419 erase(const_iterator __first, const_iterator __last)
1420#else
1421 erase(iterator __first, iterator __last)
1422#endif
1423 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1424
1425 _GLIBCXX20_CONSTEXPR
1426 void
1427 resize(size_type __new_size, bool __x = bool())
1428 {
1429 if (__new_size < size())
1430 _M_erase_at_end(begin() + difference_type(__new_size));
1431 else
1432 insert(end(), __new_size - size(), __x);
1433 }
1434
1435#if __cplusplus >= 201103L
1436 _GLIBCXX20_CONSTEXPR
1437 void
1439 { _M_shrink_to_fit(); }
1440#endif
1441
1442 _GLIBCXX20_CONSTEXPR
1443 void
1444 flip() _GLIBCXX_NOEXCEPT
1445 {
1446 _Bit_type * const __end = this->_M_impl._M_end_addr();
1447 for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p)
1448 *__p = ~*__p;
1449 }
1450
1451 _GLIBCXX20_CONSTEXPR
1452 void
1453 clear() _GLIBCXX_NOEXCEPT
1454 { _M_erase_at_end(begin()); }
1455
1456#if __cplusplus >= 201103L
1457 template<typename... _Args>
1458#if __cplusplus > 201402L
1459 _GLIBCXX20_CONSTEXPR
1460 reference
1461#else
1462 void
1463#endif
1464 emplace_back(_Args&&... __args)
1465 {
1466 push_back(bool(std::forward<_Args>(__args)...));
1467#if __cplusplus > 201402L
1468 return back();
1469#endif
1470 }
1471
1472 template<typename... _Args>
1473 _GLIBCXX20_CONSTEXPR
1474 iterator
1475 emplace(const_iterator __pos, _Args&&... __args)
1476 { return insert(__pos, bool(std::forward<_Args>(__args)...)); }
1477#endif
1478
1479 protected:
1480 // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
1481 _GLIBCXX20_CONSTEXPR
1482 iterator
1483 _M_copy_aligned(const_iterator __first, const_iterator __last,
1484 iterator __result)
1485 {
1486 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
1487 return std::copy(const_iterator(__last._M_p, 0), __last,
1488 iterator(__q, 0));
1489 }
1490
1491 _GLIBCXX20_CONSTEXPR
1492 void
1493 _M_initialize(size_type __n)
1494 {
1495 if (__n)
1496 {
1497 _Bit_pointer __q = this->_M_allocate(__n);
1498 this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1499 iterator __start = iterator(std::__addressof(*__q), 0);
1500 this->_M_impl._M_start = __start;
1501 this->_M_impl._M_finish = __start + difference_type(__n);
1502 }
1503 }
1504
1505 _GLIBCXX20_CONSTEXPR
1506 void
1507 _M_initialize_value(bool __x) _GLIBCXX_NOEXCEPT
1508 {
1509 if (_Bit_type* __p = this->_M_impl._M_start._M_p)
1510 __fill_bvector_n(__p, this->_M_impl._M_end_addr() - __p, __x);
1511 }
1512
1513 _GLIBCXX20_CONSTEXPR
1514 void
1515 _M_reallocate(size_type __n);
1516
1517#if __cplusplus >= 201103L
1518 _GLIBCXX20_CONSTEXPR
1519 bool
1520 _M_shrink_to_fit();
1521#endif
1522
1523#if __cplusplus < 201103L
1524 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1525 // 438. Ambiguity in the "do the right thing" clause
1526 template<typename _Integer>
1527 void
1528 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1529 {
1530 _M_initialize(static_cast<size_type>(__n));
1531 _M_initialize_value(__x);
1532 }
1533
1534 template<typename _InputIterator>
1535 void
1536 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1537 __false_type)
1538 { _M_initialize_range(__first, __last,
1539 std::__iterator_category(__first)); }
1540#endif
1541
1542 template<typename _InputIterator>
1543 _GLIBCXX20_CONSTEXPR
1544 void
1545 _M_initialize_range(_InputIterator __first, _InputIterator __last,
1547 {
1548 for (; __first != __last; ++__first)
1549 push_back(*__first);
1550 }
1551
1552 template<typename _ForwardIterator>
1553 _GLIBCXX20_CONSTEXPR
1554 void
1555 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
1557 {
1558 const size_type __n = std::distance(__first, __last);
1559 _M_initialize(__n);
1560 std::copy(__first, __last, begin());
1561 }
1562
1563#if __cplusplus < 201103L
1564 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1565 // 438. Ambiguity in the "do the right thing" clause
1566 template<typename _Integer>
1567 void
1568 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1569 { _M_fill_assign(__n, __val); }
1570
1571 template<class _InputIterator>
1572 void
1573 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1574 __false_type)
1575 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1576#endif
1577
1578 _GLIBCXX20_CONSTEXPR
1579 void
1580 _M_fill_assign(size_t __n, bool __x)
1581 {
1582 if (__n > size())
1583 {
1584 _M_initialize_value(__x);
1585 insert(end(), __n - size(), __x);
1586 }
1587 else
1588 {
1589 _M_erase_at_end(begin() + __n);
1590 _M_initialize_value(__x);
1591 }
1592 }
1593
1594 template<typename _InputIterator>
1595 _GLIBCXX20_CONSTEXPR
1596 void
1597 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1599 {
1600 iterator __cur = begin();
1601 for (; __first != __last && __cur != end(); ++__cur, (void)++__first)
1602 *__cur = *__first;
1603 if (__first == __last)
1604 _M_erase_at_end(__cur);
1605 else
1606 insert(end(), __first, __last);
1607 }
1608
1609 template<typename _ForwardIterator>
1610 _GLIBCXX20_CONSTEXPR
1611 void
1612 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1614 {
1615 const size_type __len = std::distance(__first, __last);
1616 if (__len < size())
1617 _M_erase_at_end(std::copy(__first, __last, begin()));
1618 else
1619 {
1620 _ForwardIterator __mid = __first;
1621 std::advance(__mid, size());
1622 std::copy(__first, __mid, begin());
1623 insert(end(), __mid, __last);
1624 }
1625 }
1626
1627#if __cplusplus < 201103L
1628 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1629 // 438. Ambiguity in the "do the right thing" clause
1630 template<typename _Integer>
1631 void
1632 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1633 __true_type)
1634 { _M_fill_insert(__pos, __n, __x); }
1635
1636 template<typename _InputIterator>
1637 void
1638 _M_insert_dispatch(iterator __pos,
1639 _InputIterator __first, _InputIterator __last,
1640 __false_type)
1641 { _M_insert_range(__pos, __first, __last,
1642 std::__iterator_category(__first)); }
1643#endif
1644
1645 _GLIBCXX20_CONSTEXPR
1646 void
1647 _M_fill_insert(iterator __position, size_type __n, bool __x);
1648
1649 template<typename _InputIterator>
1650 _GLIBCXX20_CONSTEXPR
1651 void
1652 _M_insert_range(iterator __pos, _InputIterator __first,
1653 _InputIterator __last, std::input_iterator_tag)
1654 {
1655 for (; __first != __last; ++__first)
1656 {
1657 __pos = insert(__pos, *__first);
1658 ++__pos;
1659 }
1660 }
1661
1662 template<typename _ForwardIterator>
1663 _GLIBCXX20_CONSTEXPR
1664 void
1665 _M_insert_range(iterator __position, _ForwardIterator __first,
1666 _ForwardIterator __last, std::forward_iterator_tag);
1667
1668 _GLIBCXX20_CONSTEXPR
1669 void
1670 _M_insert_aux(iterator __position, bool __x);
1671
1672 _GLIBCXX20_CONSTEXPR
1673 size_type
1674 _M_check_len(size_type __n, const char* __s) const
1675 {
1676 if (max_size() - size() < __n)
1677 __throw_length_error(__N(__s));
1678
1679 const size_type __len = size() + std::max(size(), __n);
1680 return (__len < size() || __len > max_size()) ? max_size() : __len;
1681 }
1682
1683 _GLIBCXX20_CONSTEXPR
1684 void
1685 _M_erase_at_end(iterator __pos)
1686 { this->_M_impl._M_finish = __pos; }
1687
1688 _GLIBCXX20_CONSTEXPR
1689 iterator
1690 _M_erase(iterator __pos);
1691
1692 _GLIBCXX20_CONSTEXPR
1693 iterator
1694 _M_erase(iterator __first, iterator __last);
1695
1696 protected:
1697 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1698 // DR 464. Suggestion for new member functions in standard containers.
1699 // N.B. DR 464 says nothing about vector<bool> but we need something
1700 // here due to the using-declaration in __gnu_debug::vector.
1701 // vector class.
1702#if __cplusplus >= 201103L
1703 void data() = delete;
1704#else
1705 void data() { }
1706#endif
1707 };
1708
1709_GLIBCXX_END_NAMESPACE_CONTAINER
1710
1711 // Fill a partial word.
1712 _GLIBCXX20_CONSTEXPR
1713 inline void
1714 __fill_bvector(_Bit_type* __v, unsigned int __first, unsigned int __last,
1715 bool __x) _GLIBCXX_NOEXCEPT
1716 {
1717 const _Bit_type __fmask = ~0ul << __first;
1718 const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last);
1719 const _Bit_type __mask = __fmask & __lmask;
1720
1721 if (__x)
1722 *__v |= __mask;
1723 else
1724 *__v &= ~__mask;
1725 }
1726
1727 // Fill N full words, as if using memset, but usable in constant expressions.
1728 __attribute__((__nonnull__))
1729 _GLIBCXX20_CONSTEXPR
1730 inline void
1731 __fill_bvector_n(_Bit_type* __p, size_t __n, bool __x) _GLIBCXX_NOEXCEPT
1732 {
1733#if __cpp_lib_is_constant_evaluated
1734 if (std::is_constant_evaluated())
1735 {
1736 for (size_t __i = 0; __i < __n; ++__i)
1737 __p[__i] = __x ? ~0ul : 0ul;
1738 return;
1739 }
1740#endif
1741 __builtin_memset(__p, __x ? ~0 : 0, __n * sizeof(_Bit_type));
1742 }
1743
1744
1745 _GLIBCXX20_CONSTEXPR
1746 inline void
1747 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator __first,
1748 _GLIBCXX_STD_C::_Bit_iterator __last, const bool& __x)
1749 {
1750 if (__first._M_p != __last._M_p)
1751 {
1752 _Bit_type* __first_p = __first._M_p;
1753 if (__first._M_offset != 0)
1754 __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x);
1755
1756 __fill_bvector_n(__first_p, __last._M_p - __first_p, __x);
1757
1758 if (__last._M_offset != 0)
1759 __fill_bvector(__last._M_p, 0, __last._M_offset, __x);
1760 }
1761 else if (__first._M_offset != __last._M_offset)
1762 __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x);
1763 }
1764
1765#if __cplusplus >= 201103L
1766 // DR 1182.
1767 /// std::hash specialization for vector<bool>.
1768 template<typename _Alloc>
1769 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
1770 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1771 {
1772 size_t
1773 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
1774 };
1775#endif // C++11
1776
1777_GLIBCXX_END_NAMESPACE_VERSION
1778} // namespace std
1779
1780#endif
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:859
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:873
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:826
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:866
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
Definition ptr_traits.h:232
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
Definition type_traits:116
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
Definition type_traits:119
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:127
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:51
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:70
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
initializer_list
Primary class template hash.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
static constexpr pointer allocate(_Alloc &__a, size_type __n)
typename __detected_or_t< is_empty< _Alloc >, __equal, _Alloc >::type is_always_equal
The ranges::subrange class template.
Marking input iterators.
Forward iterators support a superset of input iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.
Common iterator class.
A standard container which offers fixed time access to individual elements in any order.
Definition stl_vector.h:456
constexpr iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into vector before specified iterator.
Definition vector.tcc:135
constexpr void push_back(const value_type &__x)
Add data to the end of the vector.
constexpr reverse_iterator rbegin() noexcept
constexpr iterator end() noexcept
vector()=default
Creates a vector with no elements.
constexpr iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in vector before specified iterator.
constexpr iterator begin() noexcept
Definition stl_vector.h:997
constexpr size_type capacity() const noexcept
constexpr ~vector() noexcept
Definition stl_vector.h:801
constexpr void assign(size_type __n, const value_type &__val)
Assigns a given value to a vector.
Definition stl_vector.h:876
constexpr void swap(vector &__x) noexcept
Swaps data with another vector.
constexpr _Tp * data() noexcept
constexpr vector & operator=(const vector &__x)
Vector assignment operator.
constexpr void pop_back() noexcept
Removes last element.
constexpr void reserve(size_type __n)
Attempt to preallocate enough memory for specified number of elements.
Definition vector.tcc:68
constexpr reference at(size_type __n)
Provides access to the data contained in the vector.
constexpr void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
constexpr void _M_range_check(size_type __n) const
Safety check used only from at().
constexpr reference front() noexcept
constexpr iterator erase(const_iterator __position)
Remove element at given position.
constexpr bool empty() const noexcept
constexpr reverse_iterator rend() noexcept
constexpr const_reverse_iterator crbegin() const noexcept
constexpr const_iterator cbegin() const noexcept
constexpr void clear() noexcept
constexpr allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
Definition stl_vector.h:314
constexpr size_type size() const noexcept
constexpr reference back() noexcept
constexpr const_reverse_iterator crend() const noexcept
constexpr const_iterator cend() const noexcept
constexpr reference operator[](size_type __n) noexcept
Subscript access to the data contained in the vector.
constexpr void shrink_to_fit()
constexpr size_type max_size() const noexcept
Uniform interface to C++98 and C++11 allocators.