libstdc++
stl_bvector.h
Go to the documentation of this file.
1 // vector<bool> specialization -*- C++ -*-
2 
3 // Copyright (C) 2001-2025 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10 
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /*
26  *
27  * Copyright (c) 1994
28  * Hewlett-Packard Company
29  *
30  * Permission to use, copy, modify, distribute and sell this software
31  * and its documentation for any purpose is hereby granted without fee,
32  * provided that the above copyright notice appear in all copies and
33  * that both that copyright notice and this permission notice appear
34  * in supporting documentation. Hewlett-Packard Company makes no
35  * representations about the suitability of this software for any
36  * purpose. It is provided "as is" without express or implied warranty.
37  *
38  *
39  * Copyright (c) 1996-1999
40  * Silicon Graphics Computer Systems, Inc.
41  *
42  * Permission to use, copy, modify, distribute and sell this software
43  * and its documentation for any purpose is hereby granted without fee,
44  * provided that the above copyright notice appear in all copies and
45  * that both that copyright notice and this permission notice appear
46  * in supporting documentation. Silicon Graphics makes no
47  * representations about the suitability of this software for any
48  * purpose. It is provided "as is" without express or implied warranty.
49  */
50 
51 /** @file bits/stl_bvector.h
52  * This is an internal header file, included by other library headers.
53  * Do not attempt to use it directly. @headername{vector}
54  */
55 
56 #ifndef _STL_BVECTOR_H
57 #define _STL_BVECTOR_H 1
58 
59 #ifndef _GLIBCXX_ALWAYS_INLINE
60 #define _GLIBCXX_ALWAYS_INLINE inline __attribute__((__always_inline__))
61 #endif
62 
63 #if __cplusplus >= 201103L
64 #include <initializer_list>
65 #include <bits/functional_hash.h>
66 #endif
67 
68 namespace 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  // Caller must ensure the addition won't overflow.
719  _GLIBCXX_CONSTEXPR
720  static size_t
721  _S_nword(size_t __n)
722  { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); }
723  };
724 
725  /**
726  * @brief A specialization of vector for booleans which offers fixed time
727  * access to individual elements in any order.
728  *
729  * @ingroup sequences
730  * @headerfile vector
731  * @since C++98
732  *
733  * @tparam _Alloc Allocator type.
734  *
735  * Note that vector<bool> does not actually meet the requirements for being
736  * a container. This is because the reference and pointer types are not
737  * really references and pointers to bool. See DR96 for details. @see
738  * vector for function documentation.
739  *
740  * In some terminology a %vector can be described as a dynamic
741  * C-style array, it offers fast and efficient access to individual
742  * elements in any order and saves the user from worrying about
743  * memory and size allocation. Subscripting ( @c [] ) access is
744  * also provided as with C-style arrays.
745  */
746  template<typename _Alloc>
747  class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
748  {
749  typedef _Bvector_base<_Alloc> _Base;
750  typedef typename _Base::_Bit_pointer _Bit_pointer;
752 
753 #if __cplusplus >= 201103L
754  friend struct std::hash<vector>;
755 # if __cplusplus > 201703L // || defined __STRICT_ANSI__
757  "std::vector must have the same value_type as its allocator");
758 # endif
759 #endif
760 
761  public:
762  typedef bool value_type;
763  typedef size_t size_type;
764  typedef ptrdiff_t difference_type;
765  typedef _Bit_reference reference;
766  typedef bool const_reference;
767  typedef _Bit_reference* pointer;
768  typedef const bool* const_pointer;
769  typedef _Bit_iterator iterator;
770  typedef _Bit_const_iterator const_iterator;
773  typedef _Alloc allocator_type;
774 
775  _GLIBCXX20_CONSTEXPR
776  allocator_type
777  get_allocator() const
778  { return _Base::get_allocator(); }
779 
780  protected:
781  using _Base::_M_allocate;
782  using _Base::_M_deallocate;
783  using _Base::_S_nword;
784  using _Base::_M_get_Bit_allocator;
785 
786  public:
787 #if __cplusplus >= 201103L
788  vector() = default;
789 #else
790  vector() { }
791 #endif
792 
793  _GLIBCXX20_CONSTEXPR
794  explicit
795  vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
796  : _Base(__a) { }
797 
798 #if __cplusplus >= 201103L
799  _GLIBCXX20_CONSTEXPR
800  explicit
801  vector(size_type __n, const allocator_type& __a = allocator_type())
802  : vector(__n, false, __a)
803  { }
804 
805  _GLIBCXX20_CONSTEXPR
806  vector(size_type __n, const bool& __value,
807  const allocator_type& __a = allocator_type())
808 #else
809  explicit
810  vector(size_type __n, const bool& __value = bool(),
811  const allocator_type& __a = allocator_type())
812 #endif
813  : _Base(__a)
814  {
815  _M_check_and_initialize(__n);
816  _M_initialize_value(__value);
817  }
818 
819  _GLIBCXX20_CONSTEXPR
820  vector(const vector& __x)
821  : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
822  {
823  const_iterator __xbegin = __x.begin(), __xend = __x.end();
824  _M_initialize(__x.size());
825  _M_copy_aligned(__xbegin, __xend, begin());
826  }
827 
828 #if __cplusplus >= 201103L
829  vector(vector&&) = default;
830 
831  private:
832  _GLIBCXX20_CONSTEXPR
833  vector(vector&& __x, const allocator_type& __a, true_type) noexcept
834  : _Base(std::move(__x), __a)
835  { }
836 
837  _GLIBCXX20_CONSTEXPR
838  vector(vector&& __x, const allocator_type& __a, false_type)
839  : _Base(__a)
840  {
841  if (__x.get_allocator() == __a)
842  this->_M_move_data(std::move(__x));
843  else
844  {
845  _M_initialize(__x.size());
846  _M_copy_aligned(__x.begin(), __x.end(), begin());
847  __x.clear();
848  }
849  }
850 
851  public:
852  _GLIBCXX20_CONSTEXPR
853  vector(vector&& __x, const __type_identity_t<allocator_type>& __a)
854  noexcept(_Bit_alloc_traits::_S_always_equal())
855  : vector(std::move(__x), __a,
857  { }
858 
859  _GLIBCXX20_CONSTEXPR
860  vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
861  : _Base(__a)
862  {
863  _M_initialize(__x.size());
864  _M_copy_aligned(__x.begin(), __x.end(), begin());
865  }
866 
867  _GLIBCXX20_CONSTEXPR
869  const allocator_type& __a = allocator_type())
870  : _Base(__a)
871  {
872  _M_initialize_range(__l.begin(), __l.end(),
874  }
875 #endif
876 
877 #if __cplusplus >= 201103L
878  template<typename _InputIterator,
879  typename = std::_RequireInputIter<_InputIterator>>
880  _GLIBCXX20_CONSTEXPR
881  vector(_InputIterator __first, _InputIterator __last,
882  const allocator_type& __a = allocator_type())
883  : _Base(__a)
884  {
885  _M_initialize_range(__first, __last,
886  std::__iterator_category(__first));
887  }
888 #else
889  template<typename _InputIterator>
890  vector(_InputIterator __first, _InputIterator __last,
891  const allocator_type& __a = allocator_type())
892  : _Base(__a)
893  {
894  // Check whether it's an integral type. If so, it's not an iterator.
895  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
896  _M_initialize_dispatch(__first, __last, _Integral());
897  }
898 #endif
899 
900 #if __glibcxx_containers_ranges // C++ >= 23
901  /**
902  * @brief Construct a vector from a range.
903  * @param __rg A range of values that are convertible to `value_type`.
904  * @since C++23
905  */
906  template<__detail::__container_compatible_range<bool> _Rg>
907  constexpr
908  vector(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc())
909  : _Base(__a)
910  {
911  if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
912  {
913  _M_check_and_initialize(ranges::distance(__rg));
914  ranges::copy(__rg, begin());
915  }
916  else
917  {
918  auto __first = ranges::begin(__rg);
919  const auto __last = ranges::end(__rg);
920  for (; __first != __last; ++__first)
921  emplace_back(*__first);
922  }
923  }
924 #endif
925 
926  _GLIBCXX20_CONSTEXPR
927  ~vector() _GLIBCXX_NOEXCEPT { }
928 
929  _GLIBCXX20_CONSTEXPR
930  vector&
931  operator=(const vector& __x)
932  {
933  if (&__x == this)
934  return *this;
935 #if __cplusplus >= 201103L
936  if (_Bit_alloc_traits::_S_propagate_on_copy_assign())
937  {
938  if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator())
939  {
940  this->_M_deallocate();
941  std::__alloc_on_copy(_M_get_Bit_allocator(),
942  __x._M_get_Bit_allocator());
943  _M_initialize(__x.size());
944  }
945  else
946  std::__alloc_on_copy(_M_get_Bit_allocator(),
947  __x._M_get_Bit_allocator());
948  }
949 #endif
950  if (__x.size() > capacity())
951  {
952  this->_M_deallocate();
953  _M_initialize(__x.size());
954  }
955  this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
956  begin());
957  return *this;
958  }
959 
960 #if __cplusplus >= 201103L
961  _GLIBCXX20_CONSTEXPR
962  vector&
963  operator=(vector&& __x) noexcept(_Bit_alloc_traits::_S_nothrow_move())
964  {
965  if (_Bit_alloc_traits::_S_propagate_on_move_assign()
966  || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator())
967  {
968  this->_M_deallocate();
969  this->_M_move_data(std::move(__x));
970  std::__alloc_on_move(_M_get_Bit_allocator(),
971  __x._M_get_Bit_allocator());
972  }
973  else
974  {
975  if (__x.size() > capacity())
976  {
977  this->_M_deallocate();
978  _M_initialize(__x.size());
979  }
980  this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
981  begin());
982  __x.clear();
983  }
984  return *this;
985  }
986 
987  _GLIBCXX20_CONSTEXPR
988  vector&
990  {
991  this->assign(__l.begin(), __l.end());
992  return *this;
993  }
994 #endif
995 
996  // assign(), a generalized assignment member function. Two
997  // versions: one that takes a count, and one that takes a range.
998  // The range version is a member template, so we dispatch on whether
999  // or not the type is an integer.
1000  _GLIBCXX20_CONSTEXPR
1001  void
1002  assign(size_type __n, const bool& __x)
1003  { _M_fill_assign(__n, __x); }
1004 
1005 #if __cplusplus >= 201103L
1006  template<typename _InputIterator,
1007  typename = std::_RequireInputIter<_InputIterator>>
1008  _GLIBCXX20_CONSTEXPR
1009  void
1010  assign(_InputIterator __first, _InputIterator __last)
1011  { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1012 #else
1013  template<typename _InputIterator>
1014  void
1015  assign(_InputIterator __first, _InputIterator __last)
1016  {
1017  // Check whether it's an integral type. If so, it's not an iterator.
1018  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1019  _M_assign_dispatch(__first, __last, _Integral());
1020  }
1021 #endif
1022 
1023 #if __cplusplus >= 201103L
1024  _GLIBCXX20_CONSTEXPR
1025  void
1027  { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); }
1028 #endif
1029 
1030 #if __glibcxx_containers_ranges // C++ >= 23
1031  /**
1032  * @brief Assign a range to the vector.
1033  * @param __rg A range of values that are convertible to `value_type`.
1034  * @pre `__rg` and `*this` do not overlap.
1035  * @since C++23
1036  */
1037  template<__detail::__container_compatible_range<bool> _Rg>
1038  constexpr void
1039  assign_range(_Rg&& __rg)
1040  {
1041  static_assert(assignable_from<bool&, ranges::range_reference_t<_Rg>>);
1042  if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1043  {
1044  if (auto __n = size_type(ranges::distance(__rg)))
1045  {
1046  reserve(__n);
1047  this->_M_impl._M_finish
1048  = ranges::copy(std::forward<_Rg>(__rg), begin()).out;
1049  }
1050  else
1051  clear();
1052  }
1053  else
1054  {
1055  clear();
1056  auto __first = ranges::begin(__rg);
1057  const auto __last = ranges::end(__rg);
1058  for (; __first != __last; ++__first)
1059  emplace_back(*__first);
1060  }
1061  }
1062 #endif
1063 
1064  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1065  iterator
1066  begin() _GLIBCXX_NOEXCEPT
1067  { return iterator(this->_M_impl._M_start._M_p, 0); }
1068 
1069  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1070  const_iterator
1071  begin() const _GLIBCXX_NOEXCEPT
1072  { return const_iterator(this->_M_impl._M_start._M_p, 0); }
1073 
1074  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1075  iterator
1076  end() _GLIBCXX_NOEXCEPT
1077  { return this->_M_impl._M_finish; }
1078 
1079  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1080  const_iterator
1081  end() const _GLIBCXX_NOEXCEPT
1082  { return this->_M_impl._M_finish; }
1083 
1084  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1086  rbegin() _GLIBCXX_NOEXCEPT
1087  { return reverse_iterator(end()); }
1088 
1089  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1091  rbegin() const _GLIBCXX_NOEXCEPT
1092  { return const_reverse_iterator(end()); }
1093 
1094  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1096  rend() _GLIBCXX_NOEXCEPT
1097  { return reverse_iterator(begin()); }
1098 
1099  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1101  rend() const _GLIBCXX_NOEXCEPT
1102  { return const_reverse_iterator(begin()); }
1103 
1104 #if __cplusplus >= 201103L
1105  [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1106  const_iterator
1107  cbegin() const noexcept
1108  { return const_iterator(this->_M_impl._M_start._M_p, 0); }
1109 
1110  [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1111  const_iterator
1112  cend() const noexcept
1113  { return this->_M_impl._M_finish; }
1114 
1115  [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1117  crbegin() const noexcept
1118  { return const_reverse_iterator(end()); }
1119 
1120  [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1122  crend() const noexcept
1123  { return const_reverse_iterator(begin()); }
1124 #endif
1125 
1126  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1127  size_type
1128  size() const _GLIBCXX_NOEXCEPT
1129  { return size_type(end() - begin()); }
1130 
1131  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1132  size_type
1133  max_size() const _GLIBCXX_NOEXCEPT
1134  {
1135  const size_type __isize =
1136  __gnu_cxx::__numeric_traits<difference_type>::__max
1137  - int(_S_word_bit) + 1;
1138  const size_type __asize
1139  = _Bit_alloc_traits::max_size(_M_get_Bit_allocator());
1140  return (__asize <= __isize / int(_S_word_bit)
1141  ? __asize * int(_S_word_bit) : __isize);
1142  }
1143 
1144  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1145  size_type
1146  capacity() const _GLIBCXX_NOEXCEPT
1147  { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
1148  - begin()); }
1149 
1150  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1151  bool
1152  empty() const _GLIBCXX_NOEXCEPT
1153  { return begin() == end(); }
1154 
1155  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1156  reference
1157  operator[](size_type __n)
1158  {
1159  __glibcxx_requires_subscript(__n);
1160  return _Bit_reference (this->_M_impl._M_start._M_p
1161  + __n / int(_S_word_bit),
1162  1UL << __n % int(_S_word_bit));
1163  }
1164 
1165  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1166  const_reference
1167  operator[](size_type __n) const
1168  {
1169  __glibcxx_requires_subscript(__n);
1170  return _Bit_reference (this->_M_impl._M_start._M_p
1171  + __n / int(_S_word_bit),
1172  1UL << __n % int(_S_word_bit));
1173  }
1174 
1175  protected:
1176  _GLIBCXX20_CONSTEXPR
1177  void
1178  _M_range_check(size_type __n) const
1179  {
1180  if (__n >= this->size())
1181  __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n "
1182  "(which is %zu) >= this->size() "
1183  "(which is %zu)"),
1184  __n, this->size());
1185  }
1186 
1187  public:
1188  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1189  reference
1190  at(size_type __n)
1191  {
1192  _M_range_check(__n);
1193  return (*this)[__n];
1194  }
1195 
1196  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1197  const_reference
1198  at(size_type __n) const
1199  {
1200  _M_range_check(__n);
1201  return (*this)[__n];
1202  }
1203 
1204  _GLIBCXX20_CONSTEXPR
1205  void
1206  reserve(size_type __n)
1207  {
1208  if (__n > max_size())
1209  __throw_length_error(__N("vector::reserve"));
1210  if (capacity() < __n)
1211  _M_reallocate(__n);
1212  }
1213 
1214  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1215  reference
1216  front()
1217  {
1218  __glibcxx_requires_nonempty();
1219  return *begin();
1220  }
1221 
1222  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1223  const_reference
1224  front() const
1225  {
1226  __glibcxx_requires_nonempty();
1227  return *begin();
1228  }
1229 
1230  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1231  reference
1232  back()
1233  {
1234  __glibcxx_requires_nonempty();
1235  return *(end() - 1);
1236  }
1237 
1238  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1239  const_reference
1240  back() const
1241  {
1242  __glibcxx_requires_nonempty();
1243  return *(end() - 1);
1244  }
1245 
1246  _GLIBCXX20_CONSTEXPR
1247  void
1248  push_back(bool __x)
1249  {
1250  if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
1251  *this->_M_impl._M_finish++ = __x;
1252  else
1253  _M_insert_aux(end(), __x);
1254  }
1255 
1256  _GLIBCXX20_CONSTEXPR
1257  void
1258  swap(vector& __x) _GLIBCXX_NOEXCEPT
1259  {
1260 #if __cplusplus >= 201103L
1261  __glibcxx_assert(_Bit_alloc_traits::propagate_on_container_swap::value
1262  || _M_get_Bit_allocator() == __x._M_get_Bit_allocator());
1263 #endif
1264  this->_M_impl._M_swap_data(__x._M_impl);
1265  _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(),
1266  __x._M_get_Bit_allocator());
1267  }
1268 
1269  // [23.2.5]/1, third-to-last entry in synopsis listing
1270  _GLIBCXX20_CONSTEXPR
1271  static void
1272  swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
1273  {
1274  bool __tmp = __x;
1275  __x = __y;
1276  __y = __tmp;
1277  }
1278 
1279  _GLIBCXX20_CONSTEXPR
1280  iterator
1281 #if __cplusplus >= 201103L
1282  insert(const_iterator __position, const bool& __x)
1283 #else
1284  insert(iterator __position, const bool& __x)
1285 #endif
1286  {
1287  const difference_type __n = __position - begin();
1288  if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()
1289  && __position == end())
1290  *this->_M_impl._M_finish++ = __x;
1291  else
1292  _M_insert_aux(__position._M_const_cast(), __x);
1293  return begin() + __n;
1294  }
1295 
1296 #if _GLIBCXX_USE_DEPRECATED
1297  _GLIBCXX_DEPRECATED_SUGGEST("insert(position, false)")
1298  iterator
1299  insert(const_iterator __position)
1300  { return this->insert(__position._M_const_cast(), false); }
1301 #endif
1302 
1303 #if __cplusplus >= 201103L
1304  template<typename _InputIterator,
1305  typename = std::_RequireInputIter<_InputIterator>>
1306  _GLIBCXX20_CONSTEXPR
1307  iterator
1308  insert(const_iterator __position,
1309  _InputIterator __first, _InputIterator __last)
1310  {
1311  difference_type __offset = __position - cbegin();
1312  _M_insert_range(__position._M_const_cast(),
1313  __first, __last,
1314  std::__iterator_category(__first));
1315  return begin() + __offset;
1316  }
1317 #else
1318  template<typename _InputIterator>
1319  void
1320  insert(iterator __position,
1321  _InputIterator __first, _InputIterator __last)
1322  {
1323  // Check whether it's an integral type. If so, it's not an iterator.
1324  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1325  _M_insert_dispatch(__position, __first, __last, _Integral());
1326  }
1327 #endif
1328 
1329 #if __cplusplus >= 201103L
1330  _GLIBCXX20_CONSTEXPR
1331  iterator
1332  insert(const_iterator __position, size_type __n, const bool& __x)
1333  {
1334  difference_type __offset = __position - cbegin();
1335  _M_fill_insert(__position._M_const_cast(), __n, __x);
1336  return begin() + __offset;
1337  }
1338 #else
1339  void
1340  insert(iterator __position, size_type __n, const bool& __x)
1341  { _M_fill_insert(__position, __n, __x); }
1342 #endif
1343 
1344 #if __cplusplus >= 201103L
1345  _GLIBCXX20_CONSTEXPR
1346  iterator
1347  insert(const_iterator __p, initializer_list<bool> __l)
1348  { return this->insert(__p, __l.begin(), __l.end()); }
1349 #endif
1350 
1351 #if __glibcxx_containers_ranges // C++ >= 23
1352  /**
1353  * @brief Insert a range into the vector.
1354  * @param __rg A range of values that are convertible to `bool`.
1355  * @return An iterator that points to the first new element inserted,
1356  * or to `__pos` if `__rg` is an empty range.
1357  * @pre `__rg` and `*this` do not overlap.
1358  * @since C++23
1359  */
1360  template<__detail::__container_compatible_range<bool> _Rg>
1361  constexpr iterator
1362  insert_range(const_iterator __pos, _Rg&& __rg)
1363  {
1364  if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1365  {
1366  if (auto __n = size_type(ranges::distance(__rg)))
1367  {
1368  if (capacity() - size() >= __n)
1369  {
1370  std::copy_backward(__pos._M_const_cast(), end(),
1371  this->_M_impl._M_finish
1372  + difference_type(__n));
1373  ranges::copy(__rg, __pos._M_const_cast());
1374  this->_M_impl._M_finish += difference_type(__n);
1375  return __pos._M_const_cast();
1376  }
1377  else
1378  {
1379  const size_type __len =
1380  _M_check_len(__n, "vector<bool>::insert_range");
1381  const iterator __begin = begin(), __end = end();
1382  _Bit_pointer __q = this->_M_allocate(__len);
1383  iterator __start(std::__addressof(*__q), 0);
1384  iterator __i = _M_copy_aligned(__begin,
1385  __pos._M_const_cast(),
1386  __start);
1387  iterator __j = ranges::copy(__rg, __i).out;
1388  iterator __finish = std::copy(__pos._M_const_cast(),
1389  __end, __j);
1390  this->_M_deallocate();
1391  this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
1392  this->_M_impl._M_start = __start;
1393  this->_M_impl._M_finish = __finish;
1394  return __i;
1395  }
1396  }
1397  else
1398  return __pos._M_const_cast();
1399  }
1400  else
1401  return insert_range(__pos,
1402  vector(from_range, __rg, get_allocator()));
1403  }
1404 
1405  /**
1406  * @brief Append a range at the end of the vector.
1407  * @since C++23
1408  */
1409  template<__detail::__container_compatible_range<bool> _Rg>
1410  constexpr void
1411  append_range(_Rg&& __rg)
1412  {
1413  // N.B. __rg may overlap with *this, so we must copy from __rg before
1414  // existing elements or iterators referring to *this are invalidated.
1415  // e.g. in v.append_range(views::concat(v, foo)) rg overlaps v.
1416  if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1417  {
1418  const auto __n = size_type(ranges::distance(__rg));
1419 
1420  // If there is no existing storage, there are no iterators that
1421  // can be referring to our storage, so it's safe to allocate now.
1422  if (capacity() == 0)
1423  reserve(__n);
1424 
1425  const auto __sz = size();
1426  const auto __capacity = capacity();
1427  if ((__capacity - __sz) >= __n)
1428  {
1429  this->_M_impl._M_finish
1430  = ranges::copy(std::forward<_Rg>(__rg), end()).out;
1431  return;
1432  }
1433 
1434  vector __tmp(get_allocator());
1435  __tmp.reserve(_M_check_len(__n, "vector::append_range"));
1436  __tmp._M_impl._M_finish
1437  = _M_copy_aligned(cbegin(), cend(), __tmp.begin());
1438  __tmp._M_impl._M_finish
1439  = ranges::copy(std::forward<_Rg>(__rg), __tmp.end()).out;
1440  swap(__tmp);
1441  }
1442  else
1443  {
1444  auto __first = ranges::begin(__rg);
1445  const auto __last = ranges::end(__rg);
1446 
1447  // Fill up to the end of current capacity.
1448  for (auto __free = capacity() - size();
1449  __first != __last && __free > 0;
1450  ++__first, (void) --__free)
1451  emplace_back(*__first);
1452 
1453  if (__first == __last)
1454  return;
1455 
1456  // Copy the rest of the range to a new vector.
1457  ranges::subrange __rest(std::move(__first), __last);
1458  vector __tmp(from_range, __rest, get_allocator());
1459  insert(end(), __tmp.begin(), __tmp.end());
1460  }
1461  }
1462 #endif // containers_ranges
1463 
1464  _GLIBCXX20_CONSTEXPR
1465  void
1466  pop_back()
1467  { --this->_M_impl._M_finish; }
1468 
1469  _GLIBCXX20_CONSTEXPR
1470  iterator
1471 #if __cplusplus >= 201103L
1472  erase(const_iterator __position)
1473 #else
1474  erase(iterator __position)
1475 #endif
1476  { return _M_erase(__position._M_const_cast()); }
1477 
1478  _GLIBCXX20_CONSTEXPR
1479  iterator
1480 #if __cplusplus >= 201103L
1481  erase(const_iterator __first, const_iterator __last)
1482 #else
1483  erase(iterator __first, iterator __last)
1484 #endif
1485  { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1486 
1487  _GLIBCXX20_CONSTEXPR
1488  void
1489  resize(size_type __new_size, bool __x = bool())
1490  {
1491  if (__new_size < size())
1492  _M_erase_at_end(begin() + difference_type(__new_size));
1493  else
1494  insert(end(), __new_size - size(), __x);
1495  }
1496 
1497 #if __cplusplus >= 201103L
1498  _GLIBCXX20_CONSTEXPR
1499  void
1500  shrink_to_fit()
1501  { _M_shrink_to_fit(); }
1502 #endif
1503 
1504  _GLIBCXX20_CONSTEXPR
1505  void
1506  flip() _GLIBCXX_NOEXCEPT
1507  {
1508  _Bit_type * const __end = this->_M_impl._M_end_addr();
1509  for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p)
1510  *__p = ~*__p;
1511  }
1512 
1513  _GLIBCXX20_CONSTEXPR
1514  void
1515  clear() _GLIBCXX_NOEXCEPT
1516  { _M_erase_at_end(begin()); }
1517 
1518 #if __cplusplus >= 201103L
1519  template<typename... _Args>
1520 #if __cplusplus > 201402L
1521  _GLIBCXX20_CONSTEXPR
1522  reference
1523 #else
1524  void
1525 #endif
1526  emplace_back(_Args&&... __args)
1527  {
1528  push_back(bool(std::forward<_Args>(__args)...));
1529 #if __cplusplus > 201402L
1530  return back();
1531 #endif
1532  }
1533 
1534  template<typename... _Args>
1535  _GLIBCXX20_CONSTEXPR
1536  iterator
1537  emplace(const_iterator __pos, _Args&&... __args)
1538  { return insert(__pos, bool(std::forward<_Args>(__args)...)); }
1539 #endif
1540 
1541  protected:
1542  // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
1543  _GLIBCXX20_CONSTEXPR
1544  iterator
1545  _M_copy_aligned(const_iterator __first, const_iterator __last,
1546  iterator __result)
1547  {
1548  _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
1549  return std::copy(const_iterator(__last._M_p, 0), __last,
1550  iterator(__q, 0));
1551  }
1552 
1553  _GLIBCXX20_CONSTEXPR
1554  void
1555  _M_initialize(size_type __n)
1556  {
1557  // Caller must ensure this, to avoid overflow in _S_nword.
1558  _GLIBCXX_DEBUG_ASSERT(__n <= (size_t)-_S_word_bit);
1559 
1560  if (__n)
1561  {
1562  _Bit_pointer __q = this->_M_allocate(__n);
1563  this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1564  iterator __start = iterator(std::__addressof(*__q), 0);
1565  this->_M_impl._M_start = __start;
1566  this->_M_impl._M_finish = __start + difference_type(__n);
1567  }
1568  }
1569 
1570  template<typename _SizeT>
1571  _GLIBCXX20_CONSTEXPR
1572  void
1573  _M_check_and_initialize(_SizeT __n)
1574  {
1575  if (__n > max_size() || __n < 0)
1576  __throw_length_error(
1577  __N("Cannot create std::vector<bool> larger than max_size()"));
1578  _M_initialize(static_cast<size_type>(__n));
1579  }
1580 
1581  _GLIBCXX20_CONSTEXPR
1582  void
1583  _M_initialize_value(bool __x) _GLIBCXX_NOEXCEPT
1584  {
1585  if (_Bit_type* __p = this->_M_impl._M_start._M_p)
1586  __fill_bvector_n(__p, this->_M_impl._M_end_addr() - __p, __x);
1587  }
1588 
1589  _GLIBCXX20_CONSTEXPR
1590  void
1591  _M_reallocate(size_type __n);
1592 
1593 #if __cplusplus >= 201103L
1594  _GLIBCXX20_CONSTEXPR
1595  bool
1596  _M_shrink_to_fit();
1597 #endif
1598 
1599 #if __cplusplus < 201103L
1600  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1601  // 438. Ambiguity in the "do the right thing" clause
1602  template<typename _Integer>
1603  void
1604  _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1605  {
1606  _M_check_and_initialize(static_cast<size_type>(__n));
1607  _M_initialize_value(__x);
1608  }
1609 
1610  template<typename _InputIterator>
1611  void
1612  _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1613  __false_type)
1614  { _M_initialize_range(__first, __last,
1615  std::__iterator_category(__first)); }
1616 #endif
1617 
1618  template<typename _InputIterator>
1619  _GLIBCXX20_CONSTEXPR
1620  void
1621  _M_initialize_range(_InputIterator __first, _InputIterator __last,
1623  {
1624  for (; __first != __last; ++__first)
1625  push_back(*__first);
1626  }
1627 
1628  template<typename _ForwardIterator>
1629  _GLIBCXX20_CONSTEXPR
1630  void
1631  _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
1633  {
1634  _M_check_and_initialize(std::distance(__first, __last));
1635  std::copy(__first, __last, begin());
1636  }
1637 
1638 #if __cplusplus < 201103L
1639  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1640  // 438. Ambiguity in the "do the right thing" clause
1641  template<typename _Integer>
1642  void
1643  _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1644  { _M_fill_assign(__n, __val); }
1645 
1646  template<class _InputIterator>
1647  void
1648  _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1649  __false_type)
1650  { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1651 #endif
1652 
1653  _GLIBCXX20_CONSTEXPR
1654  void
1655  _M_fill_assign(size_t __n, bool __x)
1656  {
1657  if (__n > size())
1658  {
1659  _M_initialize_value(__x);
1660  insert(end(), __n - size(), __x);
1661  }
1662  else
1663  {
1664  _M_erase_at_end(begin() + __n);
1665  _M_initialize_value(__x);
1666  }
1667  }
1668 
1669  template<typename _InputIterator>
1670  _GLIBCXX20_CONSTEXPR
1671  void
1672  _M_assign_aux(_InputIterator __first, _InputIterator __last,
1674  {
1675  iterator __cur = begin();
1676  for (; __first != __last && __cur != end(); ++__cur, (void)++__first)
1677  *__cur = *__first;
1678  if (__first == __last)
1679  _M_erase_at_end(__cur);
1680  else
1681  insert(end(), __first, __last);
1682  }
1683 
1684  template<typename _ForwardIterator>
1685  _GLIBCXX20_CONSTEXPR
1686  void
1687  _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1689  {
1690  const size_type __len = std::distance(__first, __last);
1691  if (__len < size())
1692  _M_erase_at_end(std::copy(__first, __last, begin()));
1693  else
1694  {
1695  _ForwardIterator __mid = __first;
1696  std::advance(__mid, size());
1697  std::copy(__first, __mid, begin());
1698  insert(end(), __mid, __last);
1699  }
1700  }
1701 
1702 #if __cplusplus < 201103L
1703  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1704  // 438. Ambiguity in the "do the right thing" clause
1705  template<typename _Integer>
1706  void
1707  _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1708  __true_type)
1709  { _M_fill_insert(__pos, __n, __x); }
1710 
1711  template<typename _InputIterator>
1712  void
1713  _M_insert_dispatch(iterator __pos,
1714  _InputIterator __first, _InputIterator __last,
1715  __false_type)
1716  { _M_insert_range(__pos, __first, __last,
1717  std::__iterator_category(__first)); }
1718 #endif
1719 
1720  _GLIBCXX20_CONSTEXPR
1721  void
1722  _M_fill_insert(iterator __position, size_type __n, bool __x);
1723 
1724  template<typename _InputIterator>
1725  _GLIBCXX20_CONSTEXPR
1726  void
1727  _M_insert_range(iterator __pos, _InputIterator __first,
1728  _InputIterator __last, std::input_iterator_tag)
1729  {
1730  for (; __first != __last; ++__first)
1731  {
1732  __pos = insert(__pos, *__first);
1733  ++__pos;
1734  }
1735  }
1736 
1737  template<typename _ForwardIterator>
1738  _GLIBCXX20_CONSTEXPR
1739  void
1740  _M_insert_range(iterator __position, _ForwardIterator __first,
1741  _ForwardIterator __last, std::forward_iterator_tag);
1742 
1743  _GLIBCXX20_CONSTEXPR
1744  void
1745  _M_insert_aux(iterator __position, bool __x);
1746 
1747  _GLIBCXX20_CONSTEXPR
1748  size_type
1749  _M_check_len(size_type __n, const char* __s) const
1750  {
1751  if (max_size() - size() < __n)
1752  __throw_length_error(__N(__s));
1753 
1754  const size_type __len = size() + std::max(size(), __n);
1755  return (__len < size() || __len > max_size()) ? max_size() : __len;
1756  }
1757 
1758  _GLIBCXX20_CONSTEXPR
1759  void
1760  _M_erase_at_end(iterator __pos)
1761  { this->_M_impl._M_finish = __pos; }
1762 
1763  _GLIBCXX20_CONSTEXPR
1764  iterator
1765  _M_erase(iterator __pos);
1766 
1767  _GLIBCXX20_CONSTEXPR
1768  iterator
1769  _M_erase(iterator __first, iterator __last);
1770 
1771  protected:
1772  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1773  // DR 464. Suggestion for new member functions in standard containers.
1774  // N.B. DR 464 says nothing about vector<bool> but we need something
1775  // here due to the using-declaration in __gnu_debug::vector.
1776  // vector class.
1777 #if __cplusplus >= 201103L
1778  void data() = delete;
1779 #else
1780  void data() { }
1781 #endif
1782  };
1783 
1784 _GLIBCXX_END_NAMESPACE_CONTAINER
1785 
1786  // Fill a partial word.
1787  _GLIBCXX20_CONSTEXPR
1788  inline void
1789  __fill_bvector(_Bit_type* __v, unsigned int __first, unsigned int __last,
1790  bool __x) _GLIBCXX_NOEXCEPT
1791  {
1792  const _Bit_type __fmask = ~0ul << __first;
1793  const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last);
1794  const _Bit_type __mask = __fmask & __lmask;
1795 
1796  if (__x)
1797  *__v |= __mask;
1798  else
1799  *__v &= ~__mask;
1800  }
1801 
1802  // Fill N full words, as if using memset, but usable in constant expressions.
1803  __attribute__((__nonnull__))
1804  _GLIBCXX20_CONSTEXPR
1805  inline void
1806  __fill_bvector_n(_Bit_type* __p, size_t __n, bool __x) _GLIBCXX_NOEXCEPT
1807  {
1808 #if __cpp_lib_is_constant_evaluated
1809  if (std::is_constant_evaluated())
1810  {
1811  for (size_t __i = 0; __i < __n; ++__i)
1812  __p[__i] = __x ? ~0ul : 0ul;
1813  return;
1814  }
1815 #endif
1816  __builtin_memset(__p, __x ? ~0 : 0, __n * sizeof(_Bit_type));
1817  }
1818 
1819 
1820  _GLIBCXX20_CONSTEXPR
1821  inline void
1822  __fill_a1(_GLIBCXX_STD_C::_Bit_iterator __first,
1823  _GLIBCXX_STD_C::_Bit_iterator __last, const bool& __x)
1824  {
1825  if (__first._M_p != __last._M_p)
1826  {
1827  _Bit_type* __first_p = __first._M_p;
1828  if (__first._M_offset != 0)
1829  __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x);
1830 
1831  __fill_bvector_n(__first_p, __last._M_p - __first_p, __x);
1832 
1833  if (__last._M_offset != 0)
1834  __fill_bvector(__last._M_p, 0, __last._M_offset, __x);
1835  }
1836  else if (__first._M_offset != __last._M_offset)
1837  __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x);
1838  }
1839 
1840 #if __cplusplus >= 201103L
1841  // DR 1182.
1842  /// std::hash specialization for vector<bool>.
1843  template<typename _Alloc>
1844  struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
1845  : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1846  {
1847  size_t
1848  operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
1849  };
1850 #endif // C++11
1851 
1852 _GLIBCXX_END_NAMESPACE_VERSION
1853 } // namespace std
1854 
1855 #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 complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:434
constexpr complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
Definition: complex:404
constexpr complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
Definition: complex:374
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:117
__bool_constant< false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:120
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:52
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:138
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1251
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1229
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:258
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.
is_same
Definition: type_traits:1541
typename __detected_or_t< is_empty< _Alloc >, __equal, _Alloc >::type is_always_equal
Whether all instances of the allocator type compare equal.
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.
ptrdiff_t difference_type
Distance between iterators is represented as this type.
A standard container which offers fixed time access to individual elements in any order.
Definition: stl_vector.h:459
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.
Definition: stl_vector.h:1416
constexpr reverse_iterator rbegin() noexcept
Definition: stl_vector.h:1038
constexpr iterator end() noexcept
Definition: stl_vector.h:1018
vector()=default
Creates a vector with no elements.
constexpr iterator emplace(const_iterator __position, _Args &&... __args)
Inserts an object in vector before specified iterator.
Definition: stl_vector.h:1481
constexpr iterator begin() noexcept
Definition: stl_vector.h:998
constexpr size_type capacity() const noexcept
Definition: stl_vector.h:1208
constexpr ~vector() noexcept
Definition: stl_vector.h:800
constexpr void assign(size_type __n, const value_type &__val)
Assigns a given value to a vector.
Definition: stl_vector.h:875
constexpr void swap(vector &__x) noexcept
Swaps data with another vector.
Definition: stl_vector.h:1844
constexpr _Tp * data() noexcept
Definition: stl_vector.h:1395
constexpr void pop_back() noexcept
Removes last element.
Definition: stl_vector.h:1457
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.
Definition: stl_vector.h:1313
constexpr void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
Definition: stl_vector.h:1143
constexpr void _M_range_check(size_type __n) const
Safety check used only from at().
Definition: stl_vector.h:1290
constexpr reference front() noexcept
Definition: stl_vector.h:1344
constexpr iterator erase(const_iterator __position)
Remove element at given position.
Definition: stl_vector.h:1792
constexpr bool empty() const noexcept
Definition: stl_vector.h:1223
constexpr reverse_iterator rend() noexcept
Definition: stl_vector.h:1058
constexpr const_reverse_iterator crbegin() const noexcept
Definition: stl_vector.h:1099
constexpr const_iterator cbegin() const noexcept
Definition: stl_vector.h:1079
constexpr void clear() noexcept
Definition: stl_vector.h:1863
constexpr allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
Definition: stl_vector.h:317
constexpr size_type size() const noexcept
Definition: stl_vector.h:1117
constexpr vector & operator=(const vector &__x)
Vector assignment operator.
Definition: vector.tcc:211
constexpr reference back() noexcept
Definition: stl_vector.h:1368
constexpr const_reverse_iterator crend() const noexcept
Definition: stl_vector.h:1109
constexpr const_iterator cend() const noexcept
Definition: stl_vector.h:1089
constexpr reference operator[](size_type __n) noexcept
Subscript access to the data contained in the vector.
Definition: stl_vector.h:1261
constexpr void shrink_to_fit()
Definition: stl_vector.h:1198
constexpr size_type max_size() const noexcept
Definition: stl_vector.h:1128
Uniform interface to C++98 and C++11 allocators.
static constexpr pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
static constexpr void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.