1// vector<bool> specialization -*- C++ -*- 
2 
3// Copyright (C) 2001-2021 Free Software Foundation, Inc. 
4// 
5// This file is part of the GNU ISO C++ Library. This library is free 
6// software; you can redistribute it and/or modify it under the 
7// terms of the GNU General Public License as published by the 
8// Free Software Foundation; either version 3, or (at your option) 
9// any later version. 
10 
11// This library is distributed in the hope that it will be useful, 
12// but WITHOUT ANY WARRANTY; without even the implied warranty of 
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 
14// GNU General Public License for more details. 
15 
16// Under Section 7 of GPL version 3, you are granted additional 
17// permissions described in the GCC Runtime Library Exception, version 
18// 3.1, as published by the Free Software Foundation. 
19 
20// You should have received a copy of the GNU General Public License and 
21// a copy of the GCC Runtime Library Exception along with this program; 
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 
23// <http://www.gnu.org/licenses/>. 
24 
25/* 
26 * 
27 * Copyright (c) 1994 
28 * Hewlett-Packard Company 
29 * 
30 * Permission to use, copy, modify, distribute and sell this software 
31 * and its documentation for any purpose is hereby granted without fee, 
32 * provided that the above copyright notice appear in all copies and 
33 * that both that copyright notice and this permission notice appear 
34 * in supporting documentation. Hewlett-Packard Company makes no 
35 * representations about the suitability of this software for any 
36 * purpose. It is provided "as is" without express or implied warranty. 
37 * 
38 * 
39 * Copyright (c) 1996-1999 
40 * Silicon Graphics Computer Systems, Inc. 
41 * 
42 * Permission to use, copy, modify, distribute and sell this software 
43 * and its documentation for any purpose is hereby granted without fee, 
44 * provided that the above copyright notice appear in all copies and 
45 * that both that copyright notice and this permission notice appear 
46 * in supporting documentation. Silicon Graphics makes no 
47 * representations about the suitability of this software for any 
48 * purpose. It is provided "as is" without express or implied warranty. 
49 */ 
50 
51/** @file bits/stl_bvector.h 
52 * This is an internal header file, included by other library headers. 
53 * Do not attempt to use it directly. @headername{vector} 
54 */ 
55 
56#ifndef _STL_BVECTOR_H 
57#define _STL_BVECTOR_H 1 
58 
59#if __cplusplus >= 201103L 
60#include <initializer_list> 
61#include <bits/functional_hash.h> 
62#endif 
63 
64namespace std _GLIBCXX_VISIBILITY(default) 
65{ 
66_GLIBCXX_BEGIN_NAMESPACE_VERSION 
67_GLIBCXX_BEGIN_NAMESPACE_CONTAINER 
68 
69 typedef unsigned long _Bit_type; 
70 enum { _S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type)) }; 
71 
72 struct _Bit_reference 
73 { 
74 _Bit_type * _M_p; 
75 _Bit_type _M_mask; 
76 
77 _Bit_reference(_Bit_type * __x, _Bit_type __y) 
78 : _M_p(__x), _M_mask(__y) { } 
79 
80 _Bit_reference() _GLIBCXX_NOEXCEPT : _M_p(0), _M_mask(0) { } 
81 
82#if __cplusplus >= 201103L 
83 _Bit_reference(const _Bit_reference&) = default; 
84#endif 
85 
86 operator bool() const _GLIBCXX_NOEXCEPT 
87 { return !!(*_M_p & _M_mask); } 
88 
89 _Bit_reference& 
90 operator=(bool __x) _GLIBCXX_NOEXCEPT 
91 { 
92 if (__x) 
93 *_M_p |= _M_mask; 
94 else 
95 *_M_p &= ~_M_mask; 
96 return *this; 
97 } 
98 
99 _Bit_reference& 
100 operator=(const _Bit_reference& __x) _GLIBCXX_NOEXCEPT 
101 { return *this = bool(__x); } 
102 
103 bool 
104 operator==(const _Bit_reference& __x) const 
105 { return bool(*this) == bool(__x); } 
106 
107 bool 
108 operator<(const _Bit_reference& __x) const 
109 { return !bool(*this) && bool(__x); } 
110 
111 void 
112 flip() _GLIBCXX_NOEXCEPT 
113 { *_M_p ^= _M_mask; } 
114 }; 
115 
116#if __cplusplus >= 201103L 
117 inline void 
118 swap(_Bit_reference __x, _Bit_reference __y) noexcept 
119 { 
120 bool __tmp = __x; 
121 __x = __y; 
122 __y = __tmp; 
123 } 
124 
125 inline void 
126 swap(_Bit_reference __x, bool& __y) noexcept 
127 { 
128 bool __tmp = __x; 
129 __x = __y; 
130 __y = __tmp; 
131 } 
132 
133 inline void 
134 swap(bool& __x, _Bit_reference __y) noexcept 
135 { 
136 bool __tmp = __x; 
137 __x = __y; 
138 __y = __tmp; 
139 } 
140#endif 
141 
142 struct _Bit_iterator_base 
143 : public std::iterator<std::random_access_iterator_tag, bool> 
144 { 
145 _Bit_type * _M_p; 
146 unsigned int _M_offset; 
147 
148 _Bit_iterator_base(_Bit_type * __x, unsigned int __y) 
149 : _M_p(__x), _M_offset(__y) { } 
150 
151 void 
152 _M_bump_up() 
153 { 
154 if (_M_offset++ == int(_S_word_bit) - 1) 
155 { 
156 _M_offset = 0; 
157 ++_M_p; 
158 } 
159 } 
160 
161 void 
162 _M_bump_down() 
163 { 
164 if (_M_offset-- == 0) 
165 { 
166 _M_offset = int(_S_word_bit) - 1; 
167 --_M_p; 
168 } 
169 } 
170 
171 void 
172 _M_incr(ptrdiff_t __i) 
173 { 
174 difference_type __n = __i + _M_offset; 
175 _M_p += __n / int(_S_word_bit); 
176 __n = __n % int(_S_word_bit); 
177 if (__n < 0) 
178 { 
179 __n += int(_S_word_bit); 
180 --_M_p; 
181 } 
182 _M_offset = static_cast<unsigned int>(__n); 
183 } 
184 
185 friend _GLIBCXX20_CONSTEXPR bool 
186 operator==(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 
187 { return __x._M_p == __y._M_p && __x._M_offset == __y._M_offset; } 
188 
189#if __cpp_lib_three_way_comparison 
190 friend constexpr strong_ordering 
191 operator<=>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 
192 noexcept 
193 { 
194 if (const auto __cmp = __x._M_p <=> __y._M_p; __cmp != 0) 
195 return __cmp; 
196 return __x._M_offset <=> __y._M_offset; 
197 } 
198#else 
199 friend bool 
200 operator<(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 
201 { 
202 return __x._M_p < __y._M_p 
203 || (__x._M_p == __y._M_p && __x._M_offset < __y._M_offset); 
204 } 
205 
206 friend bool 
207 operator!=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 
208 { return !(__x == __y); } 
209 
210 friend bool 
211 operator>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 
212 { return __y < __x; } 
213 
214 friend bool 
215 operator<=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 
216 { return !(__y < __x); } 
217 
218 friend bool 
219 operator>=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 
220 { return !(__x < __y); } 
221#endif // three-way comparison 
222 
223 friend ptrdiff_t 
224 operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 
225 { 
226 return (int(_S_word_bit) * (__x._M_p - __y._M_p) 
227 + __x._M_offset - __y._M_offset); 
228 } 
229 }; 
230 
231 struct _Bit_iterator : public _Bit_iterator_base 
232 { 
233 typedef _Bit_reference reference; 
234#if __cplusplus > 201703L 
235 typedef void pointer; 
236#else 
237 typedef _Bit_reference* pointer; 
238#endif 
239 typedef _Bit_iterator iterator; 
240 
241 _Bit_iterator() : _Bit_iterator_base(0, 0) { } 
242 
243 _Bit_iterator(_Bit_type * __x, unsigned int __y) 
244 : _Bit_iterator_base(__x, __y) { } 
245 
246 iterator 
247 _M_const_cast() const 
248 { return *this; } 
249 
250 reference 
251 operator*() const 
252 { return reference(_M_p, 1UL << _M_offset); } 
253 
254 iterator& 
255 operator++() 
256 { 
257 _M_bump_up(); 
258 return *this; 
259 } 
260 
261 iterator 
262 operator++(int) 
263 { 
264 iterator __tmp = *this; 
265 _M_bump_up(); 
266 return __tmp; 
267 } 
268 
269 iterator& 
270 operator--() 
271 { 
272 _M_bump_down(); 
273 return *this; 
274 } 
275 
276 iterator 
277 operator--(int) 
278 { 
279 iterator __tmp = *this; 
280 _M_bump_down(); 
281 return __tmp; 
282 } 
283 
284 iterator& 
285 operator+=(difference_type __i) 
286 { 
287 _M_incr(__i); 
288 return *this; 
289 } 
290 
291 iterator& 
292 operator-=(difference_type __i) 
293 { 
294 *this += -__i; 
295 return *this; 
296 } 
297 
298 reference 
299 operator[](difference_type __i) const 
300 { return *(*this + __i); } 
301 
302 friend iterator 
303 operator+(const iterator& __x, difference_type __n) 
304 { 
305 iterator __tmp = __x; 
306 __tmp += __n; 
307 return __tmp; 
308 } 
309 
310 friend iterator 
311 operator+(difference_type __n, const iterator& __x) 
312 { return __x + __n; } 
313 
314 friend iterator 
315 operator-(const iterator& __x, difference_type __n) 
316 { 
317 iterator __tmp = __x; 
318 __tmp -= __n; 
319 return __tmp; 
320 } 
321 }; 
322 
323 struct _Bit_const_iterator : public _Bit_iterator_base 
324 { 
325 typedef bool reference; 
326 typedef bool const_reference; 
327#if __cplusplus > 201703L 
328 typedef void pointer; 
329#else 
330 typedef const bool* pointer; 
331#endif 
332 typedef _Bit_const_iterator const_iterator; 
333 
334 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { } 
335 
336 _Bit_const_iterator(_Bit_type * __x, unsigned int __y) 
337 : _Bit_iterator_base(__x, __y) { } 
338 
339 _Bit_const_iterator(const _Bit_iterator& __x) 
340 : _Bit_iterator_base(__x._M_p, __x._M_offset) { } 
341 
342 _Bit_iterator 
343 _M_const_cast() const 
344 { return _Bit_iterator(_M_p, _M_offset); } 
345 
346 const_reference 
347 operator*() const 
348 { return _Bit_reference(_M_p, 1UL << _M_offset); } 
349 
350 const_iterator& 
351 operator++() 
352 { 
353 _M_bump_up(); 
354 return *this; 
355 } 
356 
357 const_iterator 
358 operator++(int) 
359 { 
360 const_iterator __tmp = *this; 
361 _M_bump_up(); 
362 return __tmp; 
363 } 
364 
365 const_iterator& 
366 operator--() 
367 { 
368 _M_bump_down(); 
369 return *this; 
370 } 
371 
372 const_iterator 
373 operator--(int) 
374 { 
375 const_iterator __tmp = *this; 
376 _M_bump_down(); 
377 return __tmp; 
378 } 
379 
380 const_iterator& 
381 operator+=(difference_type __i) 
382 { 
383 _M_incr(__i); 
384 return *this; 
385 } 
386 
387 const_iterator& 
388 operator-=(difference_type __i) 
389 { 
390 *this += -__i; 
391 return *this; 
392 } 
393 
394 const_reference 
395 operator[](difference_type __i) const 
396 { return *(*this + __i); } 
397 
398 friend const_iterator 
399 operator+(const const_iterator& __x, difference_type __n) 
400 { 
401 const_iterator __tmp = __x; 
402 __tmp += __n; 
403 return __tmp; 
404 } 
405 
406 friend const_iterator 
407 operator-(const const_iterator& __x, difference_type __n) 
408 { 
409 const_iterator __tmp = __x; 
410 __tmp -= __n; 
411 return __tmp; 
412 } 
413 
414 friend const_iterator 
415 operator+(difference_type __n, const const_iterator& __x) 
416 { return __x + __n; } 
417 }; 
418 
419 template<typename _Alloc> 
420 struct _Bvector_base 
421 { 
422 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 
423 rebind<_Bit_type>::other _Bit_alloc_type; 
424 typedef typename __gnu_cxx::__alloc_traits<_Bit_alloc_type> 
425 _Bit_alloc_traits; 
426 typedef typename _Bit_alloc_traits::pointer _Bit_pointer; 
427 
428 struct _Bvector_impl_data 
429 { 
430#if !_GLIBCXX_INLINE_VERSION 
431 _Bit_iterator _M_start; 
432#else 
433 // We don't need the offset field for the start, it's always zero. 
434 struct { 
435 _Bit_type* _M_p; 
436 // Allow assignment from iterators (assume offset is zero): 
437 void operator=(_Bit_iterator __it) { _M_p = __it._M_p; } 
438 } _M_start; 
439#endif 
440 _Bit_iterator _M_finish; 
441 _Bit_pointer _M_end_of_storage; 
442 
443 _Bvector_impl_data() _GLIBCXX_NOEXCEPT 
444 : _M_start(), _M_finish(), _M_end_of_storage() 
445 { } 
446 
447#if __cplusplus >= 201103L 
448 _Bvector_impl_data(const _Bvector_impl_data&) = default; 
449 _Bvector_impl_data& 
450 operator=(const _Bvector_impl_data&) = default; 
451 
452 _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept 
453 : _Bvector_impl_data(__x) 
454 { __x._M_reset(); } 
455 
456 void 
457 _M_move_data(_Bvector_impl_data&& __x) noexcept 
458 { 
459 *this = __x; 
460 __x._M_reset(); 
461 } 
462#endif 
463 
464 void 
465 _M_reset() _GLIBCXX_NOEXCEPT 
466 { *this = _Bvector_impl_data(); } 
467 
468 void 
469 _M_swap_data(_Bvector_impl_data& __x) _GLIBCXX_NOEXCEPT 
470 { 
471 // Do not use std::swap(_M_start, __x._M_start), etc as it loses 
472 // information used by TBAA. 
473 std::swap(*this, __x); 
474 } 
475 }; 
476 
477 struct _Bvector_impl 
478 : public _Bit_alloc_type, public _Bvector_impl_data 
479 { 
480 _Bvector_impl() _GLIBCXX_NOEXCEPT_IF( 
481 is_nothrow_default_constructible<_Bit_alloc_type>::value) 
482 : _Bit_alloc_type() 
483 { } 
484 
485 _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT 
486 : _Bit_alloc_type(__a) 
487 { } 
488 
489#if __cplusplus >= 201103L 
490 // Not defaulted, to enforce noexcept(true) even when 
491 // !is_nothrow_move_constructible<_Bit_alloc_type>. 
492 _Bvector_impl(_Bvector_impl&& __x) noexcept 
493 : _Bit_alloc_type(std::move(__x)), _Bvector_impl_data(std::move(__x)) 
494 { } 
495 
496 _Bvector_impl(_Bit_alloc_type&& __a, _Bvector_impl&& __x) noexcept 
497 : _Bit_alloc_type(std::move(__a)), _Bvector_impl_data(std::move(__x)) 
498 { } 
499#endif 
500 
501 _Bit_type* 
502 _M_end_addr() const _GLIBCXX_NOEXCEPT 
503 { 
504 if (this->_M_end_of_storage) 
505 return std::__addressof(this->_M_end_of_storage[-1]) + 1; 
506 return 0; 
507 } 
508 }; 
509 
510 public: 
511 typedef _Alloc allocator_type; 
512 
513 _Bit_alloc_type& 
514 _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT 
515 { return this->_M_impl; } 
516 
517 const _Bit_alloc_type& 
518 _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT 
519 { return this->_M_impl; } 
520 
521 allocator_type 
522 get_allocator() const _GLIBCXX_NOEXCEPT 
523 { return allocator_type(_M_get_Bit_allocator()); } 
524 
525#if __cplusplus >= 201103L 
526 _Bvector_base() = default; 
527#else 
528 _Bvector_base() { } 
529#endif 
530 
531 _Bvector_base(const allocator_type& __a) 
532 : _M_impl(__a) { } 
533 
534#if __cplusplus >= 201103L 
535 _Bvector_base(_Bvector_base&&) = default; 
536 
537 _Bvector_base(_Bvector_base&& __x, const allocator_type& __a) noexcept 
538 : _M_impl(_Bit_alloc_type(__a), std::move(__x._M_impl)) 
539 { } 
540#endif 
541 
542 ~_Bvector_base() 
543 { this->_M_deallocate(); } 
544 
545 protected: 
546 _Bvector_impl _M_impl; 
547 
548 _Bit_pointer 
549 _M_allocate(size_t __n) 
550 { return _Bit_alloc_traits::allocate(_M_impl, _S_nword(__n)); } 
551 
552 void 
553 _M_deallocate() 
554 { 
555 if (_M_impl._M_start._M_p) 
556 { 
557 const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p; 
558 _Bit_alloc_traits::deallocate(_M_impl, 
559 _M_impl._M_end_of_storage - __n, 
560 __n); 
561 _M_impl._M_reset(); 
562 } 
563 } 
564 
565#if __cplusplus >= 201103L 
566 void 
567 _M_move_data(_Bvector_base&& __x) noexcept 
568 { _M_impl._M_move_data(std::move(__x._M_impl)); } 
569#endif 
570 
571 static size_t 
572 _S_nword(size_t __n) 
573 { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); } 
574 }; 
575 
576 /** 
577 * @brief A specialization of vector for booleans which offers fixed time 
578 * access to individual elements in any order. 
579 * 
580 * @ingroup sequences 
581 * 
582 * @tparam _Alloc Allocator type. 
583 * 
584 * Note that vector<bool> does not actually meet the requirements for being 
585 * a container. This is because the reference and pointer types are not 
586 * really references and pointers to bool. See DR96 for details. @see 
587 * vector for function documentation. 
588 * 
589 * In some terminology a %vector can be described as a dynamic 
590 * C-style array, it offers fast and efficient access to individual 
591 * elements in any order and saves the user from worrying about 
592 * memory and size allocation. Subscripting ( @c [] ) access is 
593 * also provided as with C-style arrays. 
594 */ 
595 template<typename _Alloc> 
596 class vector<bool, _Alloc> : protected _Bvector_base<_Alloc> 
597 { 
598 typedef _Bvector_base<_Alloc> _Base; 
599 typedef typename _Base::_Bit_pointer _Bit_pointer; 
600 typedef typename _Base::_Bit_alloc_traits _Bit_alloc_traits; 
601 
602#if __cplusplus >= 201103L 
603 friend struct std::hash<vector>; 
604#endif 
605 
606 public: 
607 typedef bool value_type; 
608 typedef size_t size_type; 
609 typedef ptrdiff_t difference_type; 
610 typedef _Bit_reference reference; 
611 typedef bool const_reference; 
612 typedef _Bit_reference* pointer; 
613 typedef const bool* const_pointer; 
614 typedef _Bit_iterator iterator; 
615 typedef _Bit_const_iterator const_iterator; 
616 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 
617 typedef std::reverse_iterator<iterator> reverse_iterator; 
618 typedef _Alloc allocator_type; 
619 
620 allocator_type 
621 get_allocator() const 
622 { return _Base::get_allocator(); } 
623 
624 protected: 
625 using _Base::_M_allocate; 
626 using _Base::_M_deallocate; 
627 using _Base::_S_nword; 
628 using _Base::_M_get_Bit_allocator; 
629 
630 public: 
631#if __cplusplus >= 201103L 
632 vector() = default; 
633#else 
634 vector() { } 
635#endif 
636 
637 explicit 
638 vector(const allocator_type& __a) 
639 : _Base(__a) { } 
640 
641#if __cplusplus >= 201103L 
642 explicit 
643 vector(size_type __n, const allocator_type& __a = allocator_type()) 
644 : vector(__n, false, __a) 
645 { } 
646 
647 vector(size_type __n, const bool& __value, 
648 const allocator_type& __a = allocator_type()) 
649#else 
650 explicit 
651 vector(size_type __n, const bool& __value = bool(), 
652 const allocator_type& __a = allocator_type()) 
653#endif 
654 : _Base(__a) 
655 { 
656 _M_initialize(__n); 
657 _M_initialize_value(x: __value); 
658 } 
659 
660 vector(const vector& __x) 
661 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) 
662 { 
663 _M_initialize(n: __x.size()); 
664 _M_copy_aligned(first: __x.begin(), last: __x.end(), result: begin()); 
665 } 
666 
667#if __cplusplus >= 201103L 
668 vector(vector&&) = default; 
669 
670 private: 
671 vector(vector&& __x, const allocator_type& __a, true_type) noexcept 
672 : _Base(std::move(__x), __a) 
673 { } 
674 
675 vector(vector&& __x, const allocator_type& __a, false_type) 
676 : _Base(__a) 
677 { 
678 if (__x.get_allocator() == __a) 
679 this->_M_move_data(std::move(__x)); 
680 else 
681 { 
682 _M_initialize(n: __x.size()); 
683 _M_copy_aligned(first: __x.begin(), last: __x.end(), result: begin()); 
684 __x.clear(); 
685 } 
686 } 
687 
688 public: 
689 vector(vector&& __x, const allocator_type& __a) 
690 noexcept(_Bit_alloc_traits::_S_always_equal()) 
691 : vector(std::move(__x), __a, 
692 typename _Bit_alloc_traits::is_always_equal{}) 
693 { } 
694 
695 vector(const vector& __x, const allocator_type& __a) 
696 : _Base(__a) 
697 { 
698 _M_initialize(n: __x.size()); 
699 _M_copy_aligned(first: __x.begin(), last: __x.end(), result: begin()); 
700 } 
701 
702 vector(initializer_list<bool> __l, 
703 const allocator_type& __a = allocator_type()) 
704 : _Base(__a) 
705 { 
706 _M_initialize_range(__l.begin(), __l.end(), 
707 random_access_iterator_tag()); 
708 } 
709#endif 
710 
711#if __cplusplus >= 201103L 
712 template<typename _InputIterator, 
713 typename = std::_RequireInputIter<_InputIterator>> 
714 vector(_InputIterator __first, _InputIterator __last, 
715 const allocator_type& __a = allocator_type()) 
716 : _Base(__a) 
717 { 
718 _M_initialize_range(__first, __last, 
719 std::__iterator_category(__first)); 
720 } 
721#else 
722 template<typename _InputIterator> 
723 vector(_InputIterator __first, _InputIterator __last, 
724 const allocator_type& __a = allocator_type()) 
725 : _Base(__a) 
726 { 
727 // Check whether it's an integral type. If so, it's not an iterator. 
728 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 
729 _M_initialize_dispatch(__first, __last, _Integral()); 
730 } 
731#endif 
732 
733 ~vector() _GLIBCXX_NOEXCEPT { } 
734 
735 vector& 
736 operator=(const vector& __x) 
737 { 
738 if (&__x == this) 
739 return *this; 
740#if __cplusplus >= 201103L 
741 if (_Bit_alloc_traits::_S_propagate_on_copy_assign()) 
742 { 
743 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator()) 
744 { 
745 this->_M_deallocate(); 
746 std::__alloc_on_copy(_M_get_Bit_allocator(), 
747 __x._M_get_Bit_allocator()); 
748 _M_initialize(n: __x.size()); 
749 } 
750 else 
751 std::__alloc_on_copy(_M_get_Bit_allocator(), 
752 __x._M_get_Bit_allocator()); 
753 } 
754#endif 
755 if (__x.size() > capacity()) 
756 { 
757 this->_M_deallocate(); 
758 _M_initialize(n: __x.size()); 
759 } 
760 this->_M_impl._M_finish = _M_copy_aligned(first: __x.begin(), last: __x.end(), 
761 result: begin()); 
762 return *this; 
763 } 
764 
765#if __cplusplus >= 201103L 
766 vector& 
767 operator=(vector&& __x) noexcept(_Bit_alloc_traits::_S_nothrow_move()) 
768 { 
769 if (_Bit_alloc_traits::_S_propagate_on_move_assign() 
770 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator()) 
771 { 
772 this->_M_deallocate(); 
773 this->_M_move_data(std::move(__x)); 
774 std::__alloc_on_move(_M_get_Bit_allocator(), 
775 __x._M_get_Bit_allocator()); 
776 } 
777 else 
778 { 
779 if (__x.size() > capacity()) 
780 { 
781 this->_M_deallocate(); 
782 _M_initialize(n: __x.size()); 
783 } 
784 this->_M_impl._M_finish = _M_copy_aligned(first: __x.begin(), last: __x.end(), 
785 result: begin()); 
786 __x.clear(); 
787 } 
788 return *this; 
789 } 
790 
791 vector& 
792 operator=(initializer_list<bool> __l) 
793 { 
794 this->assign(__l.begin(), __l.end()); 
795 return *this; 
796 } 
797#endif 
798 
799 // assign(), a generalized assignment member function. Two 
800 // versions: one that takes a count, and one that takes a range. 
801 // The range version is a member template, so we dispatch on whether 
802 // or not the type is an integer. 
803 void 
804 assign(size_type __n, const bool& __x) 
805 { _M_fill_assign(__n, __x); } 
806 
807#if __cplusplus >= 201103L 
808 template<typename _InputIterator, 
809 typename = std::_RequireInputIter<_InputIterator>> 
810 void 
811 assign(_InputIterator __first, _InputIterator __last) 
812 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 
813#else 
814 template<typename _InputIterator> 
815 void 
816 assign(_InputIterator __first, _InputIterator __last) 
817 { 
818 // Check whether it's an integral type. If so, it's not an iterator. 
819 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 
820 _M_assign_dispatch(__first, __last, _Integral()); 
821 } 
822#endif 
823 
824#if __cplusplus >= 201103L 
825 void 
826 assign(initializer_list<bool> __l) 
827 { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); } 
828#endif 
829 
830 iterator 
831 begin() _GLIBCXX_NOEXCEPT 
832 { return iterator(this->_M_impl._M_start._M_p, 0); } 
833 
834 const_iterator 
835 begin() const _GLIBCXX_NOEXCEPT 
836 { return const_iterator(this->_M_impl._M_start._M_p, 0); } 
837 
838 iterator 
839 end() _GLIBCXX_NOEXCEPT 
840 { return this->_M_impl._M_finish; } 
841 
842 const_iterator 
843 end() const _GLIBCXX_NOEXCEPT 
844 { return this->_M_impl._M_finish; } 
845 
846 reverse_iterator 
847 rbegin() _GLIBCXX_NOEXCEPT 
848 { return reverse_iterator(end()); } 
849 
850 const_reverse_iterator 
851 rbegin() const _GLIBCXX_NOEXCEPT 
852 { return const_reverse_iterator(end()); } 
853 
854 reverse_iterator 
855 rend() _GLIBCXX_NOEXCEPT 
856 { return reverse_iterator(begin()); } 
857 
858 const_reverse_iterator 
859 rend() const _GLIBCXX_NOEXCEPT 
860 { return const_reverse_iterator(begin()); } 
861 
862#if __cplusplus >= 201103L 
863 const_iterator 
864 cbegin() const noexcept 
865 { return const_iterator(this->_M_impl._M_start._M_p, 0); } 
866 
867 const_iterator 
868 cend() const noexcept 
869 { return this->_M_impl._M_finish; } 
870 
871 const_reverse_iterator 
872 crbegin() const noexcept 
873 { return const_reverse_iterator(end()); } 
874 
875 const_reverse_iterator 
876 crend() const noexcept 
877 { return const_reverse_iterator(begin()); } 
878#endif 
879 
880 size_type 
881 size() const _GLIBCXX_NOEXCEPT 
882 { return size_type(end() - begin()); } 
883 
884 size_type 
885 max_size() const _GLIBCXX_NOEXCEPT 
886 { 
887 const size_type __isize = 
888 __gnu_cxx::__numeric_traits<difference_type>::__max 
889 - int(_S_word_bit) + 1; 
890 const size_type __asize 
891 = _Bit_alloc_traits::max_size(_M_get_Bit_allocator()); 
892 return (__asize <= __isize / int(_S_word_bit) 
893 ? __asize * int(_S_word_bit) : __isize); 
894 } 
895 
896 size_type 
897 capacity() const _GLIBCXX_NOEXCEPT 
898 { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0) 
899 - begin()); } 
900 
901 _GLIBCXX_NODISCARD bool 
902 empty() const _GLIBCXX_NOEXCEPT 
903 { return begin() == end(); } 
904 
905 reference 
906 operator[](size_type __n) 
907 { return begin()[__n]; } 
908 
909 const_reference 
910 operator[](size_type __n) const 
911 { return begin()[__n]; } 
912 
913 protected: 
914 void 
915 _M_range_check(size_type __n) const 
916 { 
917 if (__n >= this->size()) 
918 __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n " 
919 "(which is %zu) >= this->size() " 
920 "(which is %zu)"), 
921 __n, this->size()); 
922 } 
923 
924 public: 
925 reference 
926 at(size_type __n) 
927 { _M_range_check(__n); return (*this)[__n]; } 
928 
929 const_reference 
930 at(size_type __n) const 
931 { _M_range_check(__n); return (*this)[__n]; } 
932 
933 void 
934 reserve(size_type __n) 
935 { 
936 if (__n > max_size()) 
937 __throw_length_error(__N("vector::reserve")); 
938 if (capacity() < __n) 
939 _M_reallocate(__n); 
940 } 
941 
942 reference 
943 front() 
944 { return *begin(); } 
945 
946 const_reference 
947 front() const 
948 { return *begin(); } 
949 
950 reference 
951 back() 
952 { return *(end() - 1); } 
953 
954 const_reference 
955 back() const 
956 { return *(end() - 1); } 
957 
958 // _GLIBCXX_RESOLVE_LIB_DEFECTS 
959 // DR 464. Suggestion for new member functions in standard containers. 
960 // N.B. DR 464 says nothing about vector<bool> but we need something 
961 // here due to the way we are implementing DR 464 in the debug-mode 
962 // vector class. 
963 void 
964 data() _GLIBCXX_NOEXCEPT { } 
965 
966 void 
967 push_back(bool __x) 
968 { 
969 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()) 
970 *this->_M_impl._M_finish++ = __x; 
971 else 
972 _M_insert_aux(position: end(), __x); 
973 } 
974 
975 void 
976 swap(vector& __x) _GLIBCXX_NOEXCEPT 
977 { 
978#if __cplusplus >= 201103L 
979 __glibcxx_assert(_Bit_alloc_traits::propagate_on_container_swap::value 
980 || _M_get_Bit_allocator() == __x._M_get_Bit_allocator()); 
981#endif 
982 this->_M_impl._M_swap_data(__x._M_impl); 
983 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(), 
984 __x._M_get_Bit_allocator()); 
985 } 
986 
987 // [23.2.5]/1, third-to-last entry in synopsis listing 
988 static void 
989 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT 
990 { 
991 bool __tmp = __x; 
992 __x = __y; 
993 __y = __tmp; 
994 } 
995 
996 iterator 
997#if __cplusplus >= 201103L 
998 insert(const_iterator __position, const bool& __x = bool()) 
999#else 
1000 insert(iterator __position, const bool& __x = bool()) 
1001#endif 
1002 { 
1003 const difference_type __n = __position - begin(); 
1004 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr() 
1005 && __position == end()) 
1006 *this->_M_impl._M_finish++ = __x; 
1007 else 
1008 _M_insert_aux(position: __position._M_const_cast(), __x); 
1009 return begin() + __n; 
1010 } 
1011 
1012#if __cplusplus >= 201103L 
1013 template<typename _InputIterator, 
1014 typename = std::_RequireInputIter<_InputIterator>> 
1015 iterator 
1016 insert(const_iterator __position, 
1017 _InputIterator __first, _InputIterator __last) 
1018 { 
1019 difference_type __offset = __position - cbegin(); 
1020 _M_insert_range(__position._M_const_cast(), 
1021 __first, __last, 
1022 std::__iterator_category(__first)); 
1023 return begin() + __offset; 
1024 } 
1025#else 
1026 template<typename _InputIterator> 
1027 void 
1028 insert(iterator __position, 
1029 _InputIterator __first, _InputIterator __last) 
1030 { 
1031 // Check whether it's an integral type. If so, it's not an iterator. 
1032 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 
1033 _M_insert_dispatch(__position, __first, __last, _Integral()); 
1034 } 
1035#endif 
1036 
1037#if __cplusplus >= 201103L 
1038 iterator 
1039 insert(const_iterator __position, size_type __n, const bool& __x) 
1040 { 
1041 difference_type __offset = __position - cbegin(); 
1042 _M_fill_insert(position: __position._M_const_cast(), __n, __x); 
1043 return begin() + __offset; 
1044 } 
1045#else 
1046 void 
1047 insert(iterator __position, size_type __n, const bool& __x) 
1048 { _M_fill_insert(__position, __n, __x); } 
1049#endif 
1050 
1051#if __cplusplus >= 201103L 
1052 iterator 
1053 insert(const_iterator __p, initializer_list<bool> __l) 
1054 { return this->insert(__p, __l.begin(), __l.end()); } 
1055#endif 
1056 
1057 void 
1058 pop_back() 
1059 { --this->_M_impl._M_finish; } 
1060 
1061 iterator 
1062#if __cplusplus >= 201103L 
1063 erase(const_iterator __position) 
1064#else 
1065 erase(iterator __position) 
1066#endif 
1067 { return _M_erase(__position._M_const_cast()); } 
1068 
1069 iterator 
1070#if __cplusplus >= 201103L 
1071 erase(const_iterator __first, const_iterator __last) 
1072#else 
1073 erase(iterator __first, iterator __last) 
1074#endif 
1075 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); } 
1076 
1077 void 
1078 resize(size_type __new_size, bool __x = bool()) 
1079 { 
1080 if (__new_size < size()) 
1081 _M_erase_at_end(pos: begin() + difference_type(__new_size)); 
1082 else 
1083 insert(end(), __new_size - size(), __x); 
1084 } 
1085 
1086#if __cplusplus >= 201103L 
1087 void 
1088 shrink_to_fit() 
1089 { _M_shrink_to_fit(); } 
1090#endif 
1091 
1092 void 
1093 flip() _GLIBCXX_NOEXCEPT 
1094 { 
1095 _Bit_type * const __end = this->_M_impl._M_end_addr(); 
1096 for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p) 
1097 *__p = ~*__p; 
1098 } 
1099 
1100 void 
1101 clear() _GLIBCXX_NOEXCEPT 
1102 { _M_erase_at_end(pos: begin()); } 
1103 
1104#if __cplusplus >= 201103L 
1105 template<typename... _Args> 
1106#if __cplusplus > 201402L 
1107 reference 
1108#else 
1109 void 
1110#endif 
1111 emplace_back(_Args&&... __args) 
1112 { 
1113 push_back(x: bool(__args...)); 
1114#if __cplusplus > 201402L 
1115 return back(); 
1116#endif 
1117 } 
1118 
1119 template<typename... _Args> 
1120 iterator 
1121 emplace(const_iterator __pos, _Args&&... __args) 
1122 { return insert(__pos, bool(__args...)); } 
1123#endif 
1124 
1125 protected: 
1126 // Precondition: __first._M_offset == 0 && __result._M_offset == 0. 
1127 iterator 
1128 _M_copy_aligned(const_iterator __first, const_iterator __last, 
1129 iterator __result) 
1130 { 
1131 _Bit_type* __q = std::copy(first: __first._M_p, last: __last._M_p, result: __result._M_p); 
1132 return std::copy(first: const_iterator(__last._M_p, 0), __last, 
1133 result: iterator(__q, 0)); 
1134 } 
1135 
1136 void 
1137 _M_initialize(size_type __n) 
1138 { 
1139 if (__n) 
1140 { 
1141 _Bit_pointer __q = this->_M_allocate(__n); 
1142 this->_M_impl._M_end_of_storage = __q + _S_nword(__n); 
1143 iterator __start = iterator(std::__addressof(*__q), 0); 
1144 this->_M_impl._M_start = __start; 
1145 this->_M_impl._M_finish = __start + difference_type(__n); 
1146 } 
1147 } 
1148 
1149 void 
1150 _M_initialize_value(bool __x) 
1151 { 
1152 if (_Bit_type* __p = this->_M_impl._M_start._M_p) 
1153 __builtin_memset(__p, __x ? ~0 : 0, 
1154 (this->_M_impl._M_end_addr() - __p) 
1155 * sizeof(_Bit_type)); 
1156 } 
1157 
1158 void 
1159 _M_reallocate(size_type __n); 
1160 
1161#if __cplusplus >= 201103L 
1162 bool 
1163 _M_shrink_to_fit(); 
1164#endif 
1165 
1166#if __cplusplus < 201103L 
1167 // _GLIBCXX_RESOLVE_LIB_DEFECTS 
1168 // 438. Ambiguity in the "do the right thing" clause 
1169 template<typename _Integer> 
1170 void 
1171 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 
1172 { 
1173 _M_initialize(static_cast<size_type>(__n)); 
1174 _M_initialize_value(__x); 
1175 } 
1176 
1177 template<typename _InputIterator> 
1178 void 
1179 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 
1180 __false_type) 
1181 { _M_initialize_range(__first, __last, 
1182 std::__iterator_category(__first)); } 
1183#endif 
1184 
1185 template<typename _InputIterator> 
1186 void 
1187 _M_initialize_range(_InputIterator __first, _InputIterator __last, 
1188 std::input_iterator_tag) 
1189 { 
1190 for (; __first != __last; ++__first) 
1191 push_back(x: *__first); 
1192 } 
1193 
1194 template<typename _ForwardIterator> 
1195 void 
1196 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 
1197 std::forward_iterator_tag) 
1198 { 
1199 const size_type __n = std::distance(__first, __last); 
1200 _M_initialize(__n); 
1201 std::copy(__first, __last, begin()); 
1202 } 
1203 
1204#if __cplusplus < 201103L 
1205 // _GLIBCXX_RESOLVE_LIB_DEFECTS 
1206 // 438. Ambiguity in the "do the right thing" clause 
1207 template<typename _Integer> 
1208 void 
1209 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 
1210 { _M_fill_assign(__n, __val); } 
1211 
1212 template<class _InputIterator> 
1213 void 
1214 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 
1215 __false_type) 
1216 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 
1217#endif 
1218 
1219 void 
1220 _M_fill_assign(size_t __n, bool __x) 
1221 { 
1222 if (__n > size()) 
1223 { 
1224 _M_initialize_value(__x); 
1225 insert(end(), __n - size(), __x); 
1226 } 
1227 else 
1228 { 
1229 _M_erase_at_end(pos: begin() + __n); 
1230 _M_initialize_value(__x); 
1231 } 
1232 } 
1233 
1234 template<typename _InputIterator> 
1235 void 
1236 _M_assign_aux(_InputIterator __first, _InputIterator __last, 
1237 std::input_iterator_tag) 
1238 { 
1239 iterator __cur = begin(); 
1240 for (; __first != __last && __cur != end(); ++__cur, (void)++__first) 
1241 *__cur = *__first; 
1242 if (__first == __last) 
1243 _M_erase_at_end(pos: __cur); 
1244 else 
1245 insert(end(), __first, __last); 
1246 } 
1247 
1248 template<typename _ForwardIterator> 
1249 void 
1250 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 
1251 std::forward_iterator_tag) 
1252 { 
1253 const size_type __len = std::distance(__first, __last); 
1254 if (__len < size()) 
1255 _M_erase_at_end(pos: std::copy(__first, __last, begin())); 
1256 else 
1257 { 
1258 _ForwardIterator __mid = __first; 
1259 std::advance(__mid, size()); 
1260 std::copy(__first, __mid, begin()); 
1261 insert(end(), __mid, __last); 
1262 } 
1263 } 
1264 
1265#if __cplusplus < 201103L 
1266 // _GLIBCXX_RESOLVE_LIB_DEFECTS 
1267 // 438. Ambiguity in the "do the right thing" clause 
1268 template<typename _Integer> 
1269 void 
1270 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 
1271 __true_type) 
1272 { _M_fill_insert(__pos, __n, __x); } 
1273 
1274 template<typename _InputIterator> 
1275 void 
1276 _M_insert_dispatch(iterator __pos, 
1277 _InputIterator __first, _InputIterator __last, 
1278 __false_type) 
1279 { _M_insert_range(__pos, __first, __last, 
1280 std::__iterator_category(__first)); } 
1281#endif 
1282 
1283 void 
1284 _M_fill_insert(iterator __position, size_type __n, bool __x); 
1285 
1286 template<typename _InputIterator> 
1287 void 
1288 _M_insert_range(iterator __pos, _InputIterator __first, 
1289 _InputIterator __last, std::input_iterator_tag) 
1290 { 
1291 for (; __first != __last; ++__first) 
1292 { 
1293 __pos = insert(__pos, *__first); 
1294 ++__pos; 
1295 } 
1296 } 
1297 
1298 template<typename _ForwardIterator> 
1299 void 
1300 _M_insert_range(iterator __position, _ForwardIterator __first, 
1301 _ForwardIterator __last, std::forward_iterator_tag); 
1302 
1303 void 
1304 _M_insert_aux(iterator __position, bool __x); 
1305 
1306 size_type 
1307 _M_check_len(size_type __n, const char* __s) const 
1308 { 
1309 if (max_size() - size() < __n) 
1310 __throw_length_error(__N(__s)); 
1311 
1312 const size_type __len = size() + std::max(size(), __n); 
1313 return (__len < size() || __len > max_size()) ? max_size() : __len; 
1314 } 
1315 
1316 void 
1317 _M_erase_at_end(iterator __pos) 
1318 { this->_M_impl._M_finish = __pos; } 
1319 
1320 iterator 
1321 _M_erase(iterator __pos); 
1322 
1323 iterator 
1324 _M_erase(iterator __first, iterator __last); 
1325 }; 
1326 
1327_GLIBCXX_END_NAMESPACE_CONTAINER 
1328 
1329 inline void 
1330 __fill_bvector(_GLIBCXX_STD_C::_Bit_type * __v, 
1331 unsigned int __first, unsigned int __last, bool __x) 
1332 { 
1333 using _GLIBCXX_STD_C::_Bit_type; 
1334 using _GLIBCXX_STD_C::_S_word_bit; 
1335 const _Bit_type __fmask = ~0ul << __first; 
1336 const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last); 
1337 const _Bit_type __mask = __fmask & __lmask; 
1338 
1339 if (__x) 
1340 *__v |= __mask; 
1341 else 
1342 *__v &= ~__mask; 
1343 } 
1344 
1345 inline void 
1346 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator __first, 
1347 _GLIBCXX_STD_C::_Bit_iterator __last, const bool& __x) 
1348 { 
1349 using _GLIBCXX_STD_C::_Bit_type; 
1350 using _GLIBCXX_STD_C::_S_word_bit; 
1351 if (__first._M_p != __last._M_p) 
1352 { 
1353 _Bit_type* __first_p = __first._M_p; 
1354 if (__first._M_offset != 0) 
1355 __fill_bvector(v: __first_p++, first: __first._M_offset, last: _S_word_bit, __x); 
1356 
1357 __builtin_memset(__first_p, __x ? ~0 : 0, 
1358 (__last._M_p - __first_p) * sizeof(_Bit_type)); 
1359 
1360 if (__last._M_offset != 0) 
1361 __fill_bvector(v: __last._M_p, first: 0, last: __last._M_offset, __x); 
1362 } 
1363 else if (__first._M_offset != __last._M_offset) 
1364 __fill_bvector(v: __first._M_p, first: __first._M_offset, last: __last._M_offset, __x); 
1365 } 
1366 
1367#if __cplusplus >= 201103L 
1368 // DR 1182. 
1369 /// std::hash specialization for vector<bool>. 
1370 template<typename _Alloc> 
1371 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>> 
1372 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>> 
1373 { 
1374 size_t 
1375 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept; 
1376 }; 
1377#endif // C++11 
1378 
1379_GLIBCXX_END_NAMESPACE_VERSION 
1380} // namespace std 
1381 
1382#endif 
1383