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