1// vector<bool> specialization -*- C++ -*-
2
3// Copyright (C) 2001-2019 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 bool
186 operator==(const _Bit_iterator_base& __i) const
187 { return _M_p == __i._M_p && _M_offset == __i._M_offset; }
188
189 bool
190 operator<(const _Bit_iterator_base& __i) const
191 {
192 return _M_p < __i._M_p
193 || (_M_p == __i._M_p && _M_offset < __i._M_offset);
194 }
195
196 bool
197 operator!=(const _Bit_iterator_base& __i) const
198 { return !(*this == __i); }
199
200 bool
201 operator>(const _Bit_iterator_base& __i) const
202 { return __i < *this; }
203
204 bool
205 operator<=(const _Bit_iterator_base& __i) const
206 { return !(__i < *this); }
207
208 bool
209 operator>=(const _Bit_iterator_base& __i) const
210 { return !(*this < __i); }
211 };
212
213 inline ptrdiff_t
214 operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
215 {
216 return (int(_S_word_bit) * (__x._M_p - __y._M_p)
217 + __x._M_offset - __y._M_offset);
218 }
219
220 struct _Bit_iterator : public _Bit_iterator_base
221 {
222 typedef _Bit_reference reference;
223 typedef _Bit_reference* pointer;
224 typedef _Bit_iterator iterator;
225
226 _Bit_iterator() : _Bit_iterator_base(0, 0) { }
227
228 _Bit_iterator(_Bit_type * __x, unsigned int __y)
229 : _Bit_iterator_base(__x, __y) { }
230
231 iterator
232 _M_const_cast() const
233 { return *this; }
234
235 reference
236 operator*() const
237 { return reference(_M_p, 1UL << _M_offset); }
238
239 iterator&
240 operator++()
241 {
242 _M_bump_up();
243 return *this;
244 }
245
246 iterator
247 operator++(int)
248 {
249 iterator __tmp = *this;
250 _M_bump_up();
251 return __tmp;
252 }
253
254 iterator&
255 operator--()
256 {
257 _M_bump_down();
258 return *this;
259 }
260
261 iterator
262 operator--(int)
263 {
264 iterator __tmp = *this;
265 _M_bump_down();
266 return __tmp;
267 }
268
269 iterator&
270 operator+=(difference_type __i)
271 {
272 _M_incr(__i);
273 return *this;
274 }
275
276 iterator&
277 operator-=(difference_type __i)
278 {
279 *this += -__i;
280 return *this;
281 }
282
283 iterator
284 operator+(difference_type __i) const
285 {
286 iterator __tmp = *this;
287 return __tmp += __i;
288 }
289
290 iterator
291 operator-(difference_type __i) const
292 {
293 iterator __tmp = *this;
294 return __tmp -= __i;
295 }
296
297 reference
298 operator[](difference_type __i) const
299 { return *(*this + __i); }
300 };
301
302 inline _Bit_iterator
303 operator+(ptrdiff_t __n, const _Bit_iterator& __x)
304 { return __x + __n; }
305
306 struct _Bit_const_iterator : public _Bit_iterator_base
307 {
308 typedef bool reference;
309 typedef bool const_reference;
310 typedef const bool* pointer;
311 typedef _Bit_const_iterator const_iterator;
312
313 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
314
315 _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
316 : _Bit_iterator_base(__x, __y) { }
317
318 _Bit_const_iterator(const _Bit_iterator& __x)
319 : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
320
321 _Bit_iterator
322 _M_const_cast() const
323 { return _Bit_iterator(_M_p, _M_offset); }
324
325 const_reference
326 operator*() const
327 { return _Bit_reference(_M_p, 1UL << _M_offset); }
328
329 const_iterator&
330 operator++()
331 {
332 _M_bump_up();
333 return *this;
334 }
335
336 const_iterator
337 operator++(int)
338 {
339 const_iterator __tmp = *this;
340 _M_bump_up();
341 return __tmp;
342 }
343
344 const_iterator&
345 operator--()
346 {
347 _M_bump_down();
348 return *this;
349 }
350
351 const_iterator
352 operator--(int)
353 {
354 const_iterator __tmp = *this;
355 _M_bump_down();
356 return __tmp;
357 }
358
359 const_iterator&
360 operator+=(difference_type __i)
361 {
362 _M_incr(__i);
363 return *this;
364 }
365
366 const_iterator&
367 operator-=(difference_type __i)
368 {
369 *this += -__i;
370 return *this;
371 }
372
373 const_iterator
374 operator+(difference_type __i) const
375 {
376 const_iterator __tmp = *this;
377 return __tmp += __i;
378 }
379
380 const_iterator
381 operator-(difference_type __i) const
382 {
383 const_iterator __tmp = *this;
384 return __tmp -= __i;
385 }
386
387 const_reference
388 operator[](difference_type __i) const
389 { return *(*this + __i); }
390 };
391
392 inline _Bit_const_iterator
393 operator+(ptrdiff_t __n, const _Bit_const_iterator& __x)
394 { return __x + __n; }
395
396 inline void
397 __fill_bvector(_Bit_type * __v,
398 unsigned int __first, unsigned int __last, bool __x)
399 {
400 const _Bit_type __fmask = ~0ul << __first;
401 const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last);
402 const _Bit_type __mask = __fmask & __lmask;
403
404 if (__x)
405 *__v |= __mask;
406 else
407 *__v &= ~__mask;
408 }
409
410 inline void
411 fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x)
412 {
413 if (__first._M_p != __last._M_p)
414 {
415 _Bit_type* __first_p = __first._M_p;
416 if (__first._M_offset != 0)
417 __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x);
418
419 __builtin_memset(__first_p, __x ? ~0 : 0,
420 (__last._M_p - __first_p) * sizeof(_Bit_type));
421
422 if (__last._M_offset != 0)
423 __fill_bvector(__last._M_p, 0, __last._M_offset, __x);
424 }
425 else if (__first._M_offset != __last._M_offset)
426 __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x);
427 }
428
429 template<typename _Alloc>
430 struct _Bvector_base
431 {
432 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
433 rebind<_Bit_type>::other _Bit_alloc_type;
434 typedef typename __gnu_cxx::__alloc_traits<_Bit_alloc_type>
435 _Bit_alloc_traits;
436 typedef typename _Bit_alloc_traits::pointer _Bit_pointer;
437
438 struct _Bvector_impl_data
439 {
440 _Bit_iterator _M_start;
441 _Bit_iterator _M_finish;
442 _Bit_pointer _M_end_of_storage;
443
444 _Bvector_impl_data() _GLIBCXX_NOEXCEPT
445 : _M_start(), _M_finish(), _M_end_of_storage()
446 { }
447
448#if __cplusplus >= 201103L
449 _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept
450 : _M_start(__x._M_start), _M_finish(__x._M_finish)
451 , _M_end_of_storage(__x._M_end_of_storage)
452 { __x._M_reset(); }
453
454 void
455 _M_move_data(_Bvector_impl_data&& __x) noexcept
456 {
457 this->_M_start = __x._M_start;
458 this->_M_finish = __x._M_finish;
459 this->_M_end_of_storage = __x._M_end_of_storage;
460 __x._M_reset();
461 }
462#endif
463
464 void
465 _M_reset() _GLIBCXX_NOEXCEPT
466 {
467 _M_start = _M_finish = _Bit_iterator();
468 _M_end_of_storage = _Bit_pointer();
469 }
470 };
471
472 struct _Bvector_impl
473 : public _Bit_alloc_type, public _Bvector_impl_data
474 {
475 public:
476 _Bvector_impl() _GLIBCXX_NOEXCEPT_IF(
477 is_nothrow_default_constructible<_Bit_alloc_type>::value)
478 : _Bit_alloc_type()
479 { }
480
481 _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT
482 : _Bit_alloc_type(__a)
483 { }
484
485#if __cplusplus >= 201103L
486 _Bvector_impl(_Bvector_impl&&) = default;
487#endif
488
489 _Bit_type*
490 _M_end_addr() const _GLIBCXX_NOEXCEPT
491 {
492 if (this->_M_end_of_storage)
493 return std::__addressof(this->_M_end_of_storage[-1]) + 1;
494 return 0;
495 }
496 };
497
498 public:
499 typedef _Alloc allocator_type;
500
501 _Bit_alloc_type&
502 _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT
503 { return this->_M_impl; }
504
505 const _Bit_alloc_type&
506 _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT
507 { return this->_M_impl; }
508
509 allocator_type
510 get_allocator() const _GLIBCXX_NOEXCEPT
511 { return allocator_type(_M_get_Bit_allocator()); }
512
513#if __cplusplus >= 201103L
514 _Bvector_base() = default;
515#else
516 _Bvector_base() { }
517#endif
518
519 _Bvector_base(const allocator_type& __a)
520 : _M_impl(__a) { }
521
522#if __cplusplus >= 201103L
523 _Bvector_base(_Bvector_base&&) = default;
524#endif
525
526 ~_Bvector_base()
527 { this->_M_deallocate(); }
528
529 protected:
530 _Bvector_impl _M_impl;
531
532 _Bit_pointer
533 _M_allocate(size_t __n)
534 { return _Bit_alloc_traits::allocate(_M_impl, _S_nword(__n)); }
535
536 void
537 _M_deallocate()
538 {
539 if (_M_impl._M_start._M_p)
540 {
541 const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p;
542 _Bit_alloc_traits::deallocate(_M_impl,
543 _M_impl._M_end_of_storage - __n,
544 __n);
545 _M_impl._M_reset();
546 }
547 }
548
549#if __cplusplus >= 201103L
550 void
551 _M_move_data(_Bvector_base&& __x) noexcept
552 { _M_impl._M_move_data(std::move(__x._M_impl)); }
553#endif
554
555 static size_t
556 _S_nword(size_t __n)
557 { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); }
558 };
559
560_GLIBCXX_END_NAMESPACE_CONTAINER
561_GLIBCXX_END_NAMESPACE_VERSION
562} // namespace std
563
564// Declare a partial specialization of vector<T, Alloc>.
565#include <bits/stl_vector.h>
566
567namespace std _GLIBCXX_VISIBILITY(default)
568{
569_GLIBCXX_BEGIN_NAMESPACE_VERSION
570_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
571
572 /**
573 * @brief A specialization of vector for booleans which offers fixed time
574 * access to individual elements in any order.
575 *
576 * @ingroup sequences
577 *
578 * @tparam _Alloc Allocator type.
579 *
580 * Note that vector<bool> does not actually meet the requirements for being
581 * a container. This is because the reference and pointer types are not
582 * really references and pointers to bool. See DR96 for details. @see
583 * vector for function documentation.
584 *
585 * In some terminology a %vector can be described as a dynamic
586 * C-style array, it offers fast and efficient access to individual
587 * elements in any order and saves the user from worrying about
588 * memory and size allocation. Subscripting ( @c [] ) access is
589 * also provided as with C-style arrays.
590 */
591 template<typename _Alloc>
592 class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
593 {
594 typedef _Bvector_base<_Alloc> _Base;
595 typedef typename _Base::_Bit_pointer _Bit_pointer;
596 typedef typename _Base::_Bit_alloc_traits _Bit_alloc_traits;
597
598#if __cplusplus >= 201103L
599 friend struct std::hash<vector>;
600#endif
601
602 public:
603 typedef bool value_type;
604 typedef size_t size_type;
605 typedef ptrdiff_t difference_type;
606 typedef _Bit_reference reference;
607 typedef bool const_reference;
608 typedef _Bit_reference* pointer;
609 typedef const bool* const_pointer;
610 typedef _Bit_iterator iterator;
611 typedef _Bit_const_iterator const_iterator;
612 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
613 typedef std::reverse_iterator<iterator> reverse_iterator;
614 typedef _Alloc allocator_type;
615
616 allocator_type
617 get_allocator() const
618 { return _Base::get_allocator(); }
619
620 protected:
621 using _Base::_M_allocate;
622 using _Base::_M_deallocate;
623 using _Base::_S_nword;
624 using _Base::_M_get_Bit_allocator;
625
626 public:
627#if __cplusplus >= 201103L
628 vector() = default;
629#else
630 vector() { }
631#endif
632
633 explicit
634 vector(const allocator_type& __a)
635 : _Base(__a) { }
636
637#if __cplusplus >= 201103L
638 explicit
639 vector(size_type __n, const allocator_type& __a = allocator_type())
640 : vector(__n, false, __a)
641 { }
642
643 vector(size_type __n, const bool& __value,
644 const allocator_type& __a = allocator_type())
645#else
646 explicit
647 vector(size_type __n, const bool& __value = bool(),
648 const allocator_type& __a = allocator_type())
649#endif
650 : _Base(__a)
651 {
652 _M_initialize(__n);
653 _M_initialize_value(__value);
654 }
655
656 vector(const vector& __x)
657 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
658 {
659 _M_initialize(__x.size());
660 _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start);
661 }
662
663#if __cplusplus >= 201103L
664 vector(vector&&) = default;
665
666 vector(vector&& __x, const allocator_type& __a)
667 noexcept(_Bit_alloc_traits::_S_always_equal())
668 : _Base(__a)
669 {
670 if (__x.get_allocator() == __a)
671 this->_M_move_data(std::move(__x));
672 else
673 {
674 _M_initialize(__x.size());
675 _M_copy_aligned(__x.begin(), __x.end(), begin());
676 __x.clear();
677 }
678 }
679
680 vector(const vector& __x, const allocator_type& __a)
681 : _Base(__a)
682 {
683 _M_initialize(__x.size());
684 _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start);
685 }
686
687 vector(initializer_list<bool> __l,
688 const allocator_type& __a = allocator_type())
689 : _Base(__a)
690 {
691 _M_initialize_range(__l.begin(), __l.end(),
692 random_access_iterator_tag());
693 }
694#endif
695
696#if __cplusplus >= 201103L
697 template<typename _InputIterator,
698 typename = std::_RequireInputIter<_InputIterator>>
699 vector(_InputIterator __first, _InputIterator __last,
700 const allocator_type& __a = allocator_type())
701 : _Base(__a)
702 { _M_initialize_dispatch(__first, __last, __false_type()); }
703#else
704 template<typename _InputIterator>
705 vector(_InputIterator __first, _InputIterator __last,
706 const allocator_type& __a = allocator_type())
707 : _Base(__a)
708 {
709 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
710 _M_initialize_dispatch(__first, __last, _Integral());
711 }
712#endif
713
714 ~vector() _GLIBCXX_NOEXCEPT { }
715
716 vector&
717 operator=(const vector& __x)
718 {
719 if (&__x == this)
720 return *this;
721#if __cplusplus >= 201103L
722 if (_Bit_alloc_traits::_S_propagate_on_copy_assign())
723 {
724 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator())
725 {
726 this->_M_deallocate();
727 std::__alloc_on_copy(_M_get_Bit_allocator(),
728 __x._M_get_Bit_allocator());
729 _M_initialize(__x.size());
730 }
731 else
732 std::__alloc_on_copy(_M_get_Bit_allocator(),
733 __x._M_get_Bit_allocator());
734 }
735#endif
736 if (__x.size() > capacity())
737 {
738 this->_M_deallocate();
739 _M_initialize(__x.size());
740 }
741 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
742 begin());
743 return *this;
744 }
745
746#if __cplusplus >= 201103L
747 vector&
748 operator=(vector&& __x) noexcept(_Bit_alloc_traits::_S_nothrow_move())
749 {
750 if (_Bit_alloc_traits::_S_propagate_on_move_assign()
751 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator())
752 {
753 this->_M_deallocate();
754 this->_M_move_data(std::move(__x));
755 std::__alloc_on_move(_M_get_Bit_allocator(),
756 __x._M_get_Bit_allocator());
757 }
758 else
759 {
760 if (__x.size() > capacity())
761 {
762 this->_M_deallocate();
763 _M_initialize(__x.size());
764 }
765 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
766 begin());
767 __x.clear();
768 }
769 return *this;
770 }
771
772 vector&
773 operator=(initializer_list<bool> __l)
774 {
775 this->assign (__l.begin(), __l.end());
776 return *this;
777 }
778#endif
779
780 // assign(), a generalized assignment member function. Two
781 // versions: one that takes a count, and one that takes a range.
782 // The range version is a member template, so we dispatch on whether
783 // or not the type is an integer.
784 void
785 assign(size_type __n, const bool& __x)
786 { _M_fill_assign(__n, __x); }
787
788#if __cplusplus >= 201103L
789 template<typename _InputIterator,
790 typename = std::_RequireInputIter<_InputIterator>>
791 void
792 assign(_InputIterator __first, _InputIterator __last)
793 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
794#else
795 template<typename _InputIterator>
796 void
797 assign(_InputIterator __first, _InputIterator __last)
798 {
799 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
800 _M_assign_dispatch(__first, __last, _Integral());
801 }
802#endif
803
804#if __cplusplus >= 201103L
805 void
806 assign(initializer_list<bool> __l)
807 { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); }
808#endif
809
810 iterator
811 begin() _GLIBCXX_NOEXCEPT
812 { return iterator(this->_M_impl._M_start._M_p, 0); }
813
814 const_iterator
815 begin() const _GLIBCXX_NOEXCEPT
816 { return const_iterator(this->_M_impl._M_start._M_p, 0); }
817
818 iterator
819 end() _GLIBCXX_NOEXCEPT
820 { return this->_M_impl._M_finish; }
821
822 const_iterator
823 end() const _GLIBCXX_NOEXCEPT
824 { return this->_M_impl._M_finish; }
825
826 reverse_iterator
827 rbegin() _GLIBCXX_NOEXCEPT
828 { return reverse_iterator(end()); }
829
830 const_reverse_iterator
831 rbegin() const _GLIBCXX_NOEXCEPT
832 { return const_reverse_iterator(end()); }
833
834 reverse_iterator
835 rend() _GLIBCXX_NOEXCEPT
836 { return reverse_iterator(begin()); }
837
838 const_reverse_iterator
839 rend() const _GLIBCXX_NOEXCEPT
840 { return const_reverse_iterator(begin()); }
841
842#if __cplusplus >= 201103L
843 const_iterator
844 cbegin() const noexcept
845 { return const_iterator(this->_M_impl._M_start._M_p, 0); }
846
847 const_iterator
848 cend() const noexcept
849 { return this->_M_impl._M_finish; }
850
851 const_reverse_iterator
852 crbegin() const noexcept
853 { return const_reverse_iterator(end()); }
854
855 const_reverse_iterator
856 crend() const noexcept
857 { return const_reverse_iterator(begin()); }
858#endif
859
860 size_type
861 size() const _GLIBCXX_NOEXCEPT
862 { return size_type(end() - begin()); }
863
864 size_type
865 max_size() const _GLIBCXX_NOEXCEPT
866 {
867 const size_type __isize =
868 __gnu_cxx::__numeric_traits<difference_type>::__max
869 - int(_S_word_bit) + 1;
870 const size_type __asize
871 = _Bit_alloc_traits::max_size(_M_get_Bit_allocator());
872 return (__asize <= __isize / int(_S_word_bit)
873 ? __asize * int(_S_word_bit) : __isize);
874 }
875
876 size_type
877 capacity() const _GLIBCXX_NOEXCEPT
878 { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
879 - begin()); }
880
881 bool
882 empty() const _GLIBCXX_NOEXCEPT
883 { return begin() == end(); }
884
885 reference
886 operator[](size_type __n)
887 {
888 return *iterator(this->_M_impl._M_start._M_p
889 + __n / int(_S_word_bit), __n % int(_S_word_bit));
890 }
891
892 const_reference
893 operator[](size_type __n) const
894 {
895 return *const_iterator(this->_M_impl._M_start._M_p
896 + __n / int(_S_word_bit), __n % int(_S_word_bit));
897 }
898
899 protected:
900 void
901 _M_range_check(size_type __n) const
902 {
903 if (__n >= this->size())
904 __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n "
905 "(which is %zu) >= this->size() "
906 "(which is %zu)"),
907 __n, this->size());
908 }
909
910 public:
911 reference
912 at(size_type __n)
913 { _M_range_check(__n); return (*this)[__n]; }
914
915 const_reference
916 at(size_type __n) const
917 { _M_range_check(__n); return (*this)[__n]; }
918
919 void
920 reserve(size_type __n)
921 {
922 if (__n > max_size())
923 __throw_length_error(__N("vector::reserve"));
924 if (capacity() < __n)
925 _M_reallocate(__n);
926 }
927
928 reference
929 front()
930 { return *begin(); }
931
932 const_reference
933 front() const
934 { return *begin(); }
935
936 reference
937 back()
938 { return *(end() - 1); }
939
940 const_reference
941 back() const
942 { return *(end() - 1); }
943
944 // _GLIBCXX_RESOLVE_LIB_DEFECTS
945 // DR 464. Suggestion for new member functions in standard containers.
946 // N.B. DR 464 says nothing about vector<bool> but we need something
947 // here due to the way we are implementing DR 464 in the debug-mode
948 // vector class.
949 void
950 data() _GLIBCXX_NOEXCEPT { }
951
952 void
953 push_back(bool __x)
954 {
955 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
956 *this->_M_impl._M_finish++ = __x;
957 else
958 _M_insert_aux(end(), __x);
959 }
960
961 void
962 swap(vector& __x) _GLIBCXX_NOEXCEPT
963 {
964 std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
965 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
966 std::swap(this->_M_impl._M_end_of_storage,
967 __x._M_impl._M_end_of_storage);
968 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(),
969 __x._M_get_Bit_allocator());
970 }
971
972 // [23.2.5]/1, third-to-last entry in synopsis listing
973 static void
974 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
975 {
976 bool __tmp = __x;
977 __x = __y;
978 __y = __tmp;
979 }
980
981 iterator
982#if __cplusplus >= 201103L
983 insert(const_iterator __position, const bool& __x = bool())
984#else
985 insert(iterator __position, const bool& __x = bool())
986#endif
987 {
988 const difference_type __n = __position - begin();
989 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()
990 && __position == end())
991 *this->_M_impl._M_finish++ = __x;
992 else
993 _M_insert_aux(__position._M_const_cast(), __x);
994 return begin() + __n;
995 }
996
997#if __cplusplus >= 201103L
998 template<typename _InputIterator,
999 typename = std::_RequireInputIter<_InputIterator>>
1000 iterator
1001 insert(const_iterator __position,
1002 _InputIterator __first, _InputIterator __last)
1003 {
1004 difference_type __offset = __position - cbegin();
1005 _M_insert_dispatch(__position._M_const_cast(),
1006 __first, __last, __false_type());
1007 return begin() + __offset;
1008 }
1009#else
1010 template<typename _InputIterator>
1011 void
1012 insert(iterator __position,
1013 _InputIterator __first, _InputIterator __last)
1014 {
1015 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1016 _M_insert_dispatch(__position, __first, __last, _Integral());
1017 }
1018#endif
1019
1020#if __cplusplus >= 201103L
1021 iterator
1022 insert(const_iterator __position, size_type __n, const bool& __x)
1023 {
1024 difference_type __offset = __position - cbegin();
1025 _M_fill_insert(__position._M_const_cast(), __n, __x);
1026 return begin() + __offset;
1027 }
1028#else
1029 void
1030 insert(iterator __position, size_type __n, const bool& __x)
1031 { _M_fill_insert(__position, __n, __x); }
1032#endif
1033
1034#if __cplusplus >= 201103L
1035 iterator
1036 insert(const_iterator __p, initializer_list<bool> __l)
1037 { return this->insert(__p, __l.begin(), __l.end()); }
1038#endif
1039
1040 void
1041 pop_back()
1042 { --this->_M_impl._M_finish; }
1043
1044 iterator
1045#if __cplusplus >= 201103L
1046 erase(const_iterator __position)
1047#else
1048 erase(iterator __position)
1049#endif
1050 { return _M_erase(__position._M_const_cast()); }
1051
1052 iterator
1053#if __cplusplus >= 201103L
1054 erase(const_iterator __first, const_iterator __last)
1055#else
1056 erase(iterator __first, iterator __last)
1057#endif
1058 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1059
1060 void
1061 resize(size_type __new_size, bool __x = bool())
1062 {
1063 if (__new_size < size())
1064 _M_erase_at_end(begin() + difference_type(__new_size));
1065 else
1066 insert(end(), __new_size - size(), __x);
1067 }
1068
1069#if __cplusplus >= 201103L
1070 void
1071 shrink_to_fit()
1072 { _M_shrink_to_fit(); }
1073#endif
1074
1075 void
1076 flip() _GLIBCXX_NOEXCEPT
1077 {
1078 _Bit_type * const __end = this->_M_impl._M_end_addr();
1079 for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p)
1080 *__p = ~*__p;
1081 }
1082
1083 void
1084 clear() _GLIBCXX_NOEXCEPT
1085 { _M_erase_at_end(begin()); }
1086
1087#if __cplusplus >= 201103L
1088 template<typename... _Args>
1089#if __cplusplus > 201402L
1090 reference
1091#else
1092 void
1093#endif
1094 emplace_back(_Args&&... __args)
1095 {
1096 push_back(bool(__args...));
1097#if __cplusplus > 201402L
1098 return back();
1099#endif
1100 }
1101
1102 template<typename... _Args>
1103 iterator
1104 emplace(const_iterator __pos, _Args&&... __args)
1105 { return insert(__pos, bool(__args...)); }
1106#endif
1107
1108 protected:
1109 // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
1110 iterator
1111 _M_copy_aligned(const_iterator __first, const_iterator __last,
1112 iterator __result)
1113 {
1114 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
1115 return std::copy(const_iterator(__last._M_p, 0), __last,
1116 iterator(__q, 0));
1117 }
1118
1119 void
1120 _M_initialize(size_type __n)
1121 {
1122 if (__n)
1123 {
1124 _Bit_pointer __q = this->_M_allocate(__n);
1125 this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1126 this->_M_impl._M_start = iterator(std::__addressof(*__q), 0);
1127 }
1128 else
1129 {
1130 this->_M_impl._M_end_of_storage = _Bit_pointer();
1131 this->_M_impl._M_start = iterator(0, 0);
1132 }
1133 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
1134
1135 }
1136
1137 void
1138 _M_initialize_value(bool __x)
1139 {
1140 if (_Bit_type* __p = this->_M_impl._M_start._M_p)
1141 __builtin_memset(__p, __x ? ~0 : 0,
1142 (this->_M_impl._M_end_addr() - __p)
1143 * sizeof(_Bit_type));
1144 }
1145
1146 void
1147 _M_reallocate(size_type __n);
1148
1149#if __cplusplus >= 201103L
1150 bool
1151 _M_shrink_to_fit();
1152#endif
1153
1154 // Check whether it's an integral type. If so, it's not an iterator.
1155
1156 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1157 // 438. Ambiguity in the "do the right thing" clause
1158 template<typename _Integer>
1159 void
1160 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1161 {
1162 _M_initialize(static_cast<size_type>(__n));
1163 _M_initialize_value(__x);
1164 }
1165
1166 template<typename _InputIterator>
1167 void
1168 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1169 __false_type)
1170 { _M_initialize_range(__first, __last,
1171 std::__iterator_category(__first)); }
1172
1173 template<typename _InputIterator>
1174 void
1175 _M_initialize_range(_InputIterator __first, _InputIterator __last,
1176 std::input_iterator_tag)
1177 {
1178 for (; __first != __last; ++__first)
1179 push_back(*__first);
1180 }
1181
1182 template<typename _ForwardIterator>
1183 void
1184 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
1185 std::forward_iterator_tag)
1186 {
1187 const size_type __n = std::distance(__first, __last);
1188 _M_initialize(__n);
1189 std::copy(__first, __last, this->_M_impl._M_start);
1190 }
1191
1192#if __cplusplus < 201103L
1193 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1194 // 438. Ambiguity in the "do the right thing" clause
1195 template<typename _Integer>
1196 void
1197 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1198 { _M_fill_assign(__n, __val); }
1199
1200 template<class _InputIterator>
1201 void
1202 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1203 __false_type)
1204 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1205#endif
1206
1207 void
1208 _M_fill_assign(size_t __n, bool __x)
1209 {
1210 if (__n > size())
1211 {
1212 _M_initialize_value(__x);
1213 insert(end(), __n - size(), __x);
1214 }
1215 else
1216 {
1217 _M_erase_at_end(begin() + __n);
1218 _M_initialize_value(__x);
1219 }
1220 }
1221
1222 template<typename _InputIterator>
1223 void
1224 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1225 std::input_iterator_tag)
1226 {
1227 iterator __cur = begin();
1228 for (; __first != __last && __cur != end(); ++__cur, (void)++__first)
1229 *__cur = *__first;
1230 if (__first == __last)
1231 _M_erase_at_end(__cur);
1232 else
1233 insert(end(), __first, __last);
1234 }
1235
1236 template<typename _ForwardIterator>
1237 void
1238 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1239 std::forward_iterator_tag)
1240 {
1241 const size_type __len = std::distance(__first, __last);
1242 if (__len < size())
1243 _M_erase_at_end(std::copy(__first, __last, begin()));
1244 else
1245 {
1246 _ForwardIterator __mid = __first;
1247 std::advance(__mid, size());
1248 std::copy(__first, __mid, begin());
1249 insert(end(), __mid, __last);
1250 }
1251 }
1252
1253 // Check whether it's an integral type. If so, it's not an iterator.
1254
1255 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1256 // 438. Ambiguity in the "do the right thing" clause
1257 template<typename _Integer>
1258 void
1259 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1260 __true_type)
1261 { _M_fill_insert(__pos, __n, __x); }
1262
1263 template<typename _InputIterator>
1264 void
1265 _M_insert_dispatch(iterator __pos,
1266 _InputIterator __first, _InputIterator __last,
1267 __false_type)
1268 { _M_insert_range(__pos, __first, __last,
1269 std::__iterator_category(__first)); }
1270
1271 void
1272 _M_fill_insert(iterator __position, size_type __n, bool __x);
1273
1274 template<typename _InputIterator>
1275 void
1276 _M_insert_range(iterator __pos, _InputIterator __first,
1277 _InputIterator __last, std::input_iterator_tag)
1278 {
1279 for (; __first != __last; ++__first)
1280 {
1281 __pos = insert(__pos, *__first);
1282 ++__pos;
1283 }
1284 }
1285
1286 template<typename _ForwardIterator>
1287 void
1288 _M_insert_range(iterator __position, _ForwardIterator __first,
1289 _ForwardIterator __last, std::forward_iterator_tag);
1290
1291 void
1292 _M_insert_aux(iterator __position, bool __x);
1293
1294 size_type
1295 _M_check_len(size_type __n, const char* __s) const
1296 {
1297 if (max_size() - size() < __n)
1298 __throw_length_error(__N(__s));
1299
1300 const size_type __len = size() + std::max(size(), __n);
1301 return (__len < size() || __len > max_size()) ? max_size() : __len;
1302 }
1303
1304 void
1305 _M_erase_at_end(iterator __pos)
1306 { this->_M_impl._M_finish = __pos; }
1307
1308 iterator
1309 _M_erase(iterator __pos);
1310
1311 iterator
1312 _M_erase(iterator __first, iterator __last);
1313 };
1314
1315_GLIBCXX_END_NAMESPACE_CONTAINER
1316_GLIBCXX_END_NAMESPACE_VERSION
1317} // namespace std
1318
1319#if __cplusplus >= 201103L
1320
1321namespace std _GLIBCXX_VISIBILITY(default)
1322{
1323_GLIBCXX_BEGIN_NAMESPACE_VERSION
1324
1325 // DR 1182.
1326 /// std::hash specialization for vector<bool>.
1327 template<typename _Alloc>
1328 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
1329 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1330 {
1331 size_t
1332 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
1333 };
1334
1335_GLIBCXX_END_NAMESPACE_VERSION
1336}// namespace std
1337
1338#endif // C++11
1339
1340#endif
1341