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