]> git.ipfire.org Git - thirdparty/gcc.git/blob - libstdc++-v3/include/bits/stl_bvector.h
projects / thirdparty / gcc.git / blob
? search:


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