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