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