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