libstdc++
stl_bvector.h
Go to the documentation of this file.
00001 // vector<bool> specialization -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2014 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1996-1999
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file bits/stl_bvector.h
00052  *  This is an internal header file, included by other library headers.
00053  *  Do not attempt to use it directly. @headername{vector}
00054  */
00055 
00056 #ifndef _STL_BVECTOR_H
00057 #define _STL_BVECTOR_H 1
00058 
00059 #if __cplusplus >= 201103L
00060 #include <initializer_list>
00061 #endif
00062 
00063 namespace std _GLIBCXX_VISIBILITY(default)
00064 {
00065 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00066 
00067   typedef unsigned long _Bit_type;
00068   enum { _S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type)) };
00069 
00070   struct _Bit_reference
00071   {
00072     _Bit_type * _M_p;
00073     _Bit_type _M_mask;
00074 
00075     _Bit_reference(_Bit_type * __x, _Bit_type __y)
00076     : _M_p(__x), _M_mask(__y) { }
00077 
00078     _Bit_reference() _GLIBCXX_NOEXCEPT : _M_p(0), _M_mask(0) { }
00079 
00080     operator bool() const _GLIBCXX_NOEXCEPT
00081     { return !!(*_M_p & _M_mask); }
00082 
00083     _Bit_reference&
00084     operator=(bool __x) _GLIBCXX_NOEXCEPT
00085     {
00086       if (__x)
00087     *_M_p |= _M_mask;
00088       else
00089     *_M_p &= ~_M_mask;
00090       return *this;
00091     }
00092 
00093     _Bit_reference&
00094     operator=(const _Bit_reference& __x) _GLIBCXX_NOEXCEPT
00095     { return *this = bool(__x); }
00096 
00097     bool
00098     operator==(const _Bit_reference& __x) const
00099     { return bool(*this) == bool(__x); }
00100 
00101     bool
00102     operator<(const _Bit_reference& __x) const
00103     { return !bool(*this) && bool(__x); }
00104 
00105     void
00106     flip() _GLIBCXX_NOEXCEPT
00107     { *_M_p ^= _M_mask; }
00108   };
00109 
00110 #if __cplusplus >= 201103L
00111   inline void
00112   swap(_Bit_reference __x, _Bit_reference __y) noexcept
00113   {
00114     bool __tmp = __x;
00115     __x = __y;
00116     __y = __tmp;
00117   }
00118 
00119   inline void
00120   swap(_Bit_reference __x, bool& __y) noexcept
00121   {
00122     bool __tmp = __x;
00123     __x = __y;
00124     __y = __tmp;
00125   }
00126 
00127   inline void
00128   swap(bool& __x, _Bit_reference __y) noexcept
00129   {
00130     bool __tmp = __x;
00131     __x = __y;
00132     __y = __tmp;
00133   }
00134 #endif
00135 
00136   struct _Bit_iterator_base
00137   : public std::iterator<std::random_access_iterator_tag, bool>
00138   {
00139     _Bit_type * _M_p;
00140     unsigned int _M_offset;
00141 
00142     _Bit_iterator_base(_Bit_type * __x, unsigned int __y)
00143     : _M_p(__x), _M_offset(__y) { }
00144 
00145     void
00146     _M_bump_up()
00147     {
00148       if (_M_offset++ == int(_S_word_bit) - 1)
00149     {
00150       _M_offset = 0;
00151       ++_M_p;
00152     }
00153     }
00154 
00155     void
00156     _M_bump_down()
00157     {
00158       if (_M_offset-- == 0)
00159     {
00160       _M_offset = int(_S_word_bit) - 1;
00161       --_M_p;
00162     }
00163     }
00164 
00165     void
00166     _M_incr(ptrdiff_t __i)
00167     {
00168       difference_type __n = __i + _M_offset;
00169       _M_p += __n / int(_S_word_bit);
00170       __n = __n % int(_S_word_bit);
00171       if (__n < 0)
00172     {
00173       __n += int(_S_word_bit);
00174       --_M_p;
00175     }
00176       _M_offset = static_cast<unsigned int>(__n);
00177     }
00178 
00179     bool
00180     operator==(const _Bit_iterator_base& __i) const
00181     { return _M_p == __i._M_p && _M_offset == __i._M_offset; }
00182 
00183     bool
00184     operator<(const _Bit_iterator_base& __i) const
00185     {
00186       return _M_p < __i._M_p
00187          || (_M_p == __i._M_p && _M_offset < __i._M_offset);
00188     }
00189 
00190     bool
00191     operator!=(const _Bit_iterator_base& __i) const
00192     { return !(*this == __i); }
00193 
00194     bool
00195     operator>(const _Bit_iterator_base& __i) const
00196     { return __i < *this; }
00197 
00198     bool
00199     operator<=(const _Bit_iterator_base& __i) const
00200     { return !(__i < *this); }
00201 
00202     bool
00203     operator>=(const _Bit_iterator_base& __i) const
00204     { return !(*this < __i); }
00205   };
00206 
00207   inline ptrdiff_t
00208   operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
00209   {
00210     return (int(_S_word_bit) * (__x._M_p - __y._M_p)
00211         + __x._M_offset - __y._M_offset);
00212   }
00213 
00214   struct _Bit_iterator : public _Bit_iterator_base
00215   {
00216     typedef _Bit_reference  reference;
00217     typedef _Bit_reference* pointer;
00218     typedef _Bit_iterator   iterator;
00219 
00220     _Bit_iterator() : _Bit_iterator_base(0, 0) { }
00221 
00222     _Bit_iterator(_Bit_type * __x, unsigned int __y)
00223     : _Bit_iterator_base(__x, __y) { }
00224 
00225     iterator
00226     _M_const_cast() const
00227     { return *this; }
00228 
00229     reference
00230     operator*() const
00231     { return reference(_M_p, 1UL << _M_offset); }
00232 
00233     iterator&
00234     operator++()
00235     {
00236       _M_bump_up();
00237       return *this;
00238     }
00239 
00240     iterator
00241     operator++(int)
00242     {
00243       iterator __tmp = *this;
00244       _M_bump_up();
00245       return __tmp;
00246     }
00247 
00248     iterator&
00249     operator--()
00250     {
00251       _M_bump_down();
00252       return *this;
00253     }
00254 
00255     iterator
00256     operator--(int)
00257     {
00258       iterator __tmp = *this;
00259       _M_bump_down();
00260       return __tmp;
00261     }
00262 
00263     iterator&
00264     operator+=(difference_type __i)
00265     {
00266       _M_incr(__i);
00267       return *this;
00268     }
00269 
00270     iterator&
00271     operator-=(difference_type __i)
00272     {
00273       *this += -__i;
00274       return *this;
00275     }
00276 
00277     iterator
00278     operator+(difference_type __i) const
00279     {
00280       iterator __tmp = *this;
00281       return __tmp += __i;
00282     }
00283 
00284     iterator
00285     operator-(difference_type __i) const
00286     {
00287       iterator __tmp = *this;
00288       return __tmp -= __i;
00289     }
00290 
00291     reference
00292     operator[](difference_type __i) const
00293     { return *(*this + __i); }
00294   };
00295 
00296   inline _Bit_iterator
00297   operator+(ptrdiff_t __n, const _Bit_iterator& __x)
00298   { return __x + __n; }
00299 
00300   struct _Bit_const_iterator : public _Bit_iterator_base
00301   {
00302     typedef bool                 reference;
00303     typedef bool                 const_reference;
00304     typedef const bool*          pointer;
00305     typedef _Bit_const_iterator  const_iterator;
00306 
00307     _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
00308 
00309     _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
00310     : _Bit_iterator_base(__x, __y) { }
00311 
00312     _Bit_const_iterator(const _Bit_iterator& __x)
00313     : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
00314 
00315     _Bit_iterator
00316     _M_const_cast() const
00317     { return _Bit_iterator(_M_p, _M_offset); }
00318 
00319     const_reference
00320     operator*() const
00321     { return _Bit_reference(_M_p, 1UL << _M_offset); }
00322 
00323     const_iterator&
00324     operator++()
00325     {
00326       _M_bump_up();
00327       return *this;
00328     }
00329 
00330     const_iterator
00331     operator++(int)
00332     {
00333       const_iterator __tmp = *this;
00334       _M_bump_up();
00335       return __tmp;
00336     }
00337 
00338     const_iterator&
00339     operator--()
00340     {
00341       _M_bump_down();
00342       return *this;
00343     }
00344 
00345     const_iterator
00346     operator--(int)
00347     {
00348       const_iterator __tmp = *this;
00349       _M_bump_down();
00350       return __tmp;
00351     }
00352 
00353     const_iterator&
00354     operator+=(difference_type __i)
00355     {
00356       _M_incr(__i);
00357       return *this;
00358     }
00359 
00360     const_iterator&
00361     operator-=(difference_type __i)
00362     {
00363       *this += -__i;
00364       return *this;
00365     }
00366 
00367     const_iterator 
00368     operator+(difference_type __i) const
00369     {
00370       const_iterator __tmp = *this;
00371       return __tmp += __i;
00372     }
00373 
00374     const_iterator
00375     operator-(difference_type __i) const
00376     {
00377       const_iterator __tmp = *this;
00378       return __tmp -= __i;
00379     }
00380 
00381     const_reference
00382     operator[](difference_type __i) const
00383     { return *(*this + __i); }
00384   };
00385 
00386   inline _Bit_const_iterator
00387   operator+(ptrdiff_t __n, const _Bit_const_iterator& __x)
00388   { return __x + __n; }
00389 
00390   inline void
00391   __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x)
00392   {
00393     for (; __first != __last; ++__first)
00394       *__first = __x;
00395   }
00396 
00397   inline void
00398   fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x)
00399   {
00400     if (__first._M_p != __last._M_p)
00401       {
00402     std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0);
00403     __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x);
00404     __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x);
00405       }
00406     else
00407       __fill_bvector(__first, __last, __x);
00408   }
00409 
00410   template<typename _Alloc>
00411     struct _Bvector_base
00412     {
00413       typedef typename _Alloc::template rebind<_Bit_type>::other
00414         _Bit_alloc_type;
00415       
00416       struct _Bvector_impl
00417       : public _Bit_alloc_type
00418       {
00419     _Bit_iterator   _M_start;
00420     _Bit_iterator   _M_finish;
00421     _Bit_type*  _M_end_of_storage;
00422 
00423     _Bvector_impl()
00424     : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage(0)
00425     { }
00426  
00427     _Bvector_impl(const _Bit_alloc_type& __a)
00428     : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
00429     { }
00430 
00431 #if __cplusplus >= 201103L
00432     _Bvector_impl(_Bit_alloc_type&& __a)
00433     : _Bit_alloc_type(std::move(__a)), _M_start(), _M_finish(),
00434       _M_end_of_storage(0)
00435     { }
00436 #endif
00437       };
00438 
00439     public:
00440       typedef _Alloc allocator_type;
00441 
00442       _Bit_alloc_type&
00443       _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT
00444       { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); }
00445 
00446       const _Bit_alloc_type&
00447       _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT
00448       { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
00449 
00450       allocator_type
00451       get_allocator() const _GLIBCXX_NOEXCEPT
00452       { return allocator_type(_M_get_Bit_allocator()); }
00453 
00454       _Bvector_base()
00455       : _M_impl() { }
00456       
00457       _Bvector_base(const allocator_type& __a)
00458       : _M_impl(__a) { }
00459 
00460 #if __cplusplus >= 201103L
00461       _Bvector_base(_Bvector_base&& __x) noexcept
00462       : _M_impl(std::move(__x._M_get_Bit_allocator()))
00463       {
00464     this->_M_impl._M_start = __x._M_impl._M_start;
00465     this->_M_impl._M_finish = __x._M_impl._M_finish;
00466     this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
00467     __x._M_impl._M_start = _Bit_iterator();
00468     __x._M_impl._M_finish = _Bit_iterator();
00469     __x._M_impl._M_end_of_storage = 0;
00470       }
00471 #endif
00472 
00473       ~_Bvector_base()
00474       { this->_M_deallocate(); }
00475 
00476     protected:
00477       _Bvector_impl _M_impl;
00478 
00479       _Bit_type*
00480       _M_allocate(size_t __n)
00481       { return _M_impl.allocate(_S_nword(__n)); }
00482 
00483       void
00484       _M_deallocate()
00485       {
00486     if (_M_impl._M_start._M_p)
00487       _M_impl.deallocate(_M_impl._M_start._M_p,
00488                  _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
00489       }
00490 
00491       static size_t
00492       _S_nword(size_t __n)
00493       { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); }
00494     };
00495 
00496 _GLIBCXX_END_NAMESPACE_CONTAINER
00497 } // namespace std
00498 
00499 // Declare a partial specialization of vector<T, Alloc>.
00500 #include <bits/stl_vector.h>
00501 
00502 namespace std _GLIBCXX_VISIBILITY(default)
00503 {
00504 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00505 
00506   /**
00507    *  @brief  A specialization of vector for booleans which offers fixed time
00508    *  access to individual elements in any order.
00509    *
00510    *  @ingroup sequences
00511    *
00512    *  @tparam _Alloc  Allocator type.
00513    *
00514    *  Note that vector<bool> does not actually meet the requirements for being
00515    *  a container.  This is because the reference and pointer types are not
00516    *  really references and pointers to bool.  See DR96 for details.  @see
00517    *  vector for function documentation.
00518    *
00519    *  In some terminology a %vector can be described as a dynamic
00520    *  C-style array, it offers fast and efficient access to individual
00521    *  elements in any order and saves the user from worrying about
00522    *  memory and size allocation.  Subscripting ( @c [] ) access is
00523    *  also provided as with C-style arrays.
00524   */
00525 template<typename _Alloc>
00526   class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
00527   {
00528     typedef _Bvector_base<_Alloc>            _Base;
00529 
00530 #if __cplusplus >= 201103L
00531     template<typename> friend struct hash;
00532 #endif
00533 
00534   public:
00535     typedef bool                                         value_type;
00536     typedef size_t                                       size_type;
00537     typedef ptrdiff_t                                    difference_type;
00538     typedef _Bit_reference                               reference;
00539     typedef bool                                         const_reference;
00540     typedef _Bit_reference*                              pointer;
00541     typedef const bool*                                  const_pointer;
00542     typedef _Bit_iterator                                iterator;
00543     typedef _Bit_const_iterator                          const_iterator;
00544     typedef std::reverse_iterator<const_iterator>        const_reverse_iterator;
00545     typedef std::reverse_iterator<iterator>              reverse_iterator;
00546     typedef _Alloc                               allocator_type;
00547 
00548     allocator_type get_allocator() const
00549     { return _Base::get_allocator(); }
00550 
00551   protected:
00552     using _Base::_M_allocate;
00553     using _Base::_M_deallocate;
00554     using _Base::_S_nword;
00555     using _Base::_M_get_Bit_allocator;
00556 
00557   public:
00558     vector()
00559     : _Base() { }
00560 
00561     explicit
00562     vector(const allocator_type& __a)
00563     : _Base(__a) { }
00564 
00565 #if __cplusplus >= 201103L
00566     explicit
00567     vector(size_type __n, const allocator_type& __a = allocator_type())
00568     : vector(__n, false, __a)
00569     { }
00570 
00571     vector(size_type __n, const bool& __value, 
00572        const allocator_type& __a = allocator_type())
00573     : _Base(__a)
00574     {
00575       _M_initialize(__n);
00576       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, 
00577         __value ? ~0 : 0);
00578     }
00579 #else
00580     explicit
00581     vector(size_type __n, const bool& __value = bool(), 
00582        const allocator_type& __a = allocator_type())
00583     : _Base(__a)
00584     {
00585       _M_initialize(__n);
00586       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, 
00587         __value ? ~0 : 0);
00588     }
00589 #endif
00590 
00591     vector(const vector& __x)
00592     : _Base(__x._M_get_Bit_allocator())
00593     {
00594       _M_initialize(__x.size());
00595       _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start);
00596     }
00597 
00598 #if __cplusplus >= 201103L
00599     vector(vector&& __x) noexcept
00600     : _Base(std::move(__x)) { }
00601 
00602     vector(initializer_list<bool> __l,
00603        const allocator_type& __a = allocator_type())
00604     : _Base(__a)
00605     {
00606       _M_initialize_range(__l.begin(), __l.end(),
00607               random_access_iterator_tag());
00608     }
00609 #endif
00610 
00611 #if __cplusplus >= 201103L
00612     template<typename _InputIterator,
00613          typename = std::_RequireInputIter<_InputIterator>>
00614       vector(_InputIterator __first, _InputIterator __last,
00615          const allocator_type& __a = allocator_type())
00616       : _Base(__a)
00617       { _M_initialize_dispatch(__first, __last, __false_type()); }
00618 #else
00619     template<typename _InputIterator>
00620       vector(_InputIterator __first, _InputIterator __last,
00621          const allocator_type& __a = allocator_type())
00622       : _Base(__a)
00623       {
00624     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00625     _M_initialize_dispatch(__first, __last, _Integral());
00626       }
00627 #endif
00628 
00629     ~vector() _GLIBCXX_NOEXCEPT { }
00630 
00631     vector&
00632     operator=(const vector& __x)
00633     {
00634       if (&__x == this)
00635     return *this;
00636       if (__x.size() > capacity())
00637     {
00638       this->_M_deallocate();
00639       _M_initialize(__x.size());
00640     }
00641       this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
00642                         begin());
00643       return *this;
00644     }
00645 
00646 #if __cplusplus >= 201103L
00647     vector&
00648     operator=(vector&& __x)
00649     {
00650       // NB: DR 1204.
00651       // NB: DR 675.
00652       this->clear();
00653       this->swap(__x); 
00654       return *this;
00655     }
00656 
00657     vector&
00658     operator=(initializer_list<bool> __l)
00659     {
00660       this->assign (__l.begin(), __l.end());
00661       return *this;
00662     }
00663 #endif
00664 
00665     // assign(), a generalized assignment member function.  Two
00666     // versions: one that takes a count, and one that takes a range.
00667     // The range version is a member template, so we dispatch on whether
00668     // or not the type is an integer.
00669     void
00670     assign(size_type __n, const bool& __x)
00671     { _M_fill_assign(__n, __x); }
00672 
00673 #if __cplusplus >= 201103L
00674     template<typename _InputIterator,
00675          typename = std::_RequireInputIter<_InputIterator>>
00676       void
00677       assign(_InputIterator __first, _InputIterator __last)
00678       { _M_assign_dispatch(__first, __last, __false_type()); }
00679 #else
00680     template<typename _InputIterator>
00681       void
00682       assign(_InputIterator __first, _InputIterator __last)
00683       {
00684     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00685     _M_assign_dispatch(__first, __last, _Integral());
00686       }
00687 #endif
00688 
00689 #if __cplusplus >= 201103L
00690     void
00691     assign(initializer_list<bool> __l)
00692     { this->assign(__l.begin(), __l.end()); }
00693 #endif
00694 
00695     iterator
00696     begin() _GLIBCXX_NOEXCEPT
00697     { return this->_M_impl._M_start; }
00698 
00699     const_iterator
00700     begin() const _GLIBCXX_NOEXCEPT
00701     { return this->_M_impl._M_start; }
00702 
00703     iterator
00704     end() _GLIBCXX_NOEXCEPT
00705     { return this->_M_impl._M_finish; }
00706 
00707     const_iterator
00708     end() const _GLIBCXX_NOEXCEPT
00709     { return this->_M_impl._M_finish; }
00710 
00711     reverse_iterator
00712     rbegin() _GLIBCXX_NOEXCEPT
00713     { return reverse_iterator(end()); }
00714 
00715     const_reverse_iterator
00716     rbegin() const _GLIBCXX_NOEXCEPT
00717     { return const_reverse_iterator(end()); }
00718 
00719     reverse_iterator
00720     rend() _GLIBCXX_NOEXCEPT
00721     { return reverse_iterator(begin()); }
00722 
00723     const_reverse_iterator
00724     rend() const _GLIBCXX_NOEXCEPT
00725     { return const_reverse_iterator(begin()); }
00726 
00727 #if __cplusplus >= 201103L
00728     const_iterator
00729     cbegin() const noexcept
00730     { return this->_M_impl._M_start; }
00731 
00732     const_iterator
00733     cend() const noexcept
00734     { return this->_M_impl._M_finish; }
00735 
00736     const_reverse_iterator
00737     crbegin() const noexcept
00738     { return const_reverse_iterator(end()); }
00739 
00740     const_reverse_iterator
00741     crend() const noexcept
00742     { return const_reverse_iterator(begin()); }
00743 #endif
00744 
00745     size_type
00746     size() const _GLIBCXX_NOEXCEPT
00747     { return size_type(end() - begin()); }
00748 
00749     size_type
00750     max_size() const _GLIBCXX_NOEXCEPT
00751     {
00752       const size_type __isize =
00753     __gnu_cxx::__numeric_traits<difference_type>::__max
00754     - int(_S_word_bit) + 1;
00755       const size_type __asize = _M_get_Bit_allocator().max_size();
00756       return (__asize <= __isize / int(_S_word_bit)
00757           ? __asize * int(_S_word_bit) : __isize);
00758     }
00759 
00760     size_type
00761     capacity() const _GLIBCXX_NOEXCEPT
00762     { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
00763                - begin()); }
00764 
00765     bool
00766     empty() const _GLIBCXX_NOEXCEPT
00767     { return begin() == end(); }
00768 
00769     reference
00770     operator[](size_type __n)
00771     {
00772       return *iterator(this->_M_impl._M_start._M_p
00773                + __n / int(_S_word_bit), __n % int(_S_word_bit));
00774     }
00775 
00776     const_reference
00777     operator[](size_type __n) const
00778     {
00779       return *const_iterator(this->_M_impl._M_start._M_p
00780                  + __n / int(_S_word_bit), __n % int(_S_word_bit));
00781     }
00782 
00783   protected:
00784     void
00785     _M_range_check(size_type __n) const
00786     {
00787       if (__n >= this->size())
00788     __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n "
00789                      "(which is %zu) >= this->size() "
00790                      "(which is %zu)"),
00791                  __n, this->size());
00792     }
00793 
00794   public:
00795     reference
00796     at(size_type __n)
00797     { _M_range_check(__n); return (*this)[__n]; }
00798 
00799     const_reference
00800     at(size_type __n) const
00801     { _M_range_check(__n); return (*this)[__n]; }
00802 
00803     void
00804     reserve(size_type __n)
00805     {
00806       if (__n > max_size())
00807     __throw_length_error(__N("vector::reserve"));
00808       if (capacity() < __n)
00809     _M_reallocate(__n);
00810     }
00811 
00812     reference
00813     front()
00814     { return *begin(); }
00815 
00816     const_reference
00817     front() const
00818     { return *begin(); }
00819 
00820     reference
00821     back()
00822     { return *(end() - 1); }
00823 
00824     const_reference
00825     back() const
00826     { return *(end() - 1); }
00827 
00828     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00829     // DR 464. Suggestion for new member functions in standard containers.
00830     // N.B. DR 464 says nothing about vector<bool> but we need something
00831     // here due to the way we are implementing DR 464 in the debug-mode
00832     // vector class.
00833     void
00834     data() _GLIBCXX_NOEXCEPT { }
00835 
00836     void
00837     push_back(bool __x)
00838     {
00839       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
00840         *this->_M_impl._M_finish++ = __x;
00841       else
00842         _M_insert_aux(end(), __x);
00843     }
00844 
00845     void
00846     swap(vector& __x)
00847     {
00848       std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
00849       std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
00850       std::swap(this->_M_impl._M_end_of_storage, 
00851         __x._M_impl._M_end_of_storage);
00852 
00853       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00854       // 431. Swapping containers with unequal allocators.
00855       std::__alloc_swap<typename _Base::_Bit_alloc_type>::
00856     _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator());
00857     }
00858 
00859     // [23.2.5]/1, third-to-last entry in synopsis listing
00860     static void
00861     swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
00862     {
00863       bool __tmp = __x;
00864       __x = __y;
00865       __y = __tmp;
00866     }
00867 
00868     iterator
00869 #if __cplusplus >= 201103L
00870     insert(const_iterator __position, const bool& __x = bool())
00871 #else
00872     insert(iterator __position, const bool& __x = bool())
00873 #endif
00874     {
00875       const difference_type __n = __position - begin();
00876       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
00877       && __position == end())
00878         *this->_M_impl._M_finish++ = __x;
00879       else
00880         _M_insert_aux(__position._M_const_cast(), __x);
00881       return begin() + __n;
00882     }
00883 
00884 #if __cplusplus >= 201103L
00885     template<typename _InputIterator,
00886          typename = std::_RequireInputIter<_InputIterator>>
00887       iterator
00888       insert(const_iterator __position,
00889          _InputIterator __first, _InputIterator __last)
00890       {
00891     difference_type __offset = __position - cbegin();
00892     _M_insert_dispatch(__position._M_const_cast(),
00893                __first, __last, __false_type());
00894     return begin() + __offset;
00895       }
00896 #else
00897     template<typename _InputIterator>
00898       void
00899       insert(iterator __position,
00900          _InputIterator __first, _InputIterator __last)
00901       {
00902     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00903     _M_insert_dispatch(__position, __first, __last, _Integral());
00904       }
00905 #endif
00906 
00907 #if __cplusplus >= 201103L
00908     iterator
00909     insert(const_iterator __position, size_type __n, const bool& __x)
00910     {
00911       difference_type __offset = __position - cbegin();
00912       _M_fill_insert(__position._M_const_cast(), __n, __x);
00913       return begin() + __offset;
00914     }
00915 #else
00916     void
00917     insert(iterator __position, size_type __n, const bool& __x)
00918     { _M_fill_insert(__position, __n, __x); }
00919 #endif
00920 
00921 #if __cplusplus >= 201103L
00922     iterator
00923     insert(const_iterator __p, initializer_list<bool> __l)
00924     { return this->insert(__p, __l.begin(), __l.end()); }
00925 #endif
00926 
00927     void
00928     pop_back()
00929     { --this->_M_impl._M_finish; }
00930 
00931     iterator
00932 #if __cplusplus >= 201103L
00933     erase(const_iterator __position)
00934 #else
00935     erase(iterator __position)
00936 #endif
00937     { return _M_erase(__position._M_const_cast()); }
00938 
00939     iterator
00940 #if __cplusplus >= 201103L
00941     erase(const_iterator __first, const_iterator __last)
00942 #else
00943     erase(iterator __first, iterator __last)
00944 #endif
00945     { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
00946 
00947     void
00948     resize(size_type __new_size, bool __x = bool())
00949     {
00950       if (__new_size < size())
00951         _M_erase_at_end(begin() + difference_type(__new_size));
00952       else
00953         insert(end(), __new_size - size(), __x);
00954     }
00955 
00956 #if __cplusplus >= 201103L
00957     void
00958     shrink_to_fit()
00959     { _M_shrink_to_fit(); }
00960 #endif
00961 
00962     void
00963     flip() _GLIBCXX_NOEXCEPT
00964     {
00965       for (_Bit_type * __p = this->_M_impl._M_start._M_p;
00966        __p != this->_M_impl._M_end_of_storage; ++__p)
00967         *__p = ~*__p;
00968     }
00969 
00970     void
00971     clear() _GLIBCXX_NOEXCEPT
00972     { _M_erase_at_end(begin()); }
00973 
00974 #if __cplusplus >= 201103L
00975     template<typename... _Args>
00976       void
00977       emplace_back(_Args&&... __args)
00978       { push_back(bool(__args...)); }
00979 
00980     template<typename... _Args>
00981       iterator
00982       emplace(const_iterator __pos, _Args&&... __args)
00983       { return insert(__pos, bool(__args...)); }
00984 #endif
00985 
00986   protected:
00987     // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
00988     iterator
00989     _M_copy_aligned(const_iterator __first, const_iterator __last,
00990             iterator __result)
00991     {
00992       _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
00993       return std::copy(const_iterator(__last._M_p, 0), __last,
00994                iterator(__q, 0));
00995     }
00996 
00997     void
00998     _M_initialize(size_type __n)
00999     {
01000       _Bit_type* __q = this->_M_allocate(__n);
01001       this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
01002       this->_M_impl._M_start = iterator(__q, 0);
01003       this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
01004     }
01005 
01006     void
01007     _M_reallocate(size_type __n);
01008 
01009 #if __cplusplus >= 201103L
01010     bool
01011     _M_shrink_to_fit();
01012 #endif
01013 
01014     // Check whether it's an integral type.  If so, it's not an iterator.
01015 
01016     // _GLIBCXX_RESOLVE_LIB_DEFECTS
01017     // 438. Ambiguity in the "do the right thing" clause
01018     template<typename _Integer>
01019       void
01020       _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
01021       {
01022     _M_initialize(static_cast<size_type>(__n));
01023     std::fill(this->_M_impl._M_start._M_p, 
01024           this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
01025       }
01026 
01027     template<typename _InputIterator>
01028       void 
01029       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
01030                  __false_type)
01031       { _M_initialize_range(__first, __last, 
01032                 std::__iterator_category(__first)); }
01033 
01034     template<typename _InputIterator>
01035       void
01036       _M_initialize_range(_InputIterator __first, _InputIterator __last,
01037               std::input_iterator_tag)
01038       {
01039     for (; __first != __last; ++__first)
01040       push_back(*__first);
01041       }
01042 
01043     template<typename _ForwardIterator>
01044       void
01045       _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
01046               std::forward_iterator_tag)
01047       {
01048     const size_type __n = std::distance(__first, __last);
01049     _M_initialize(__n);
01050     std::copy(__first, __last, this->_M_impl._M_start);
01051       }
01052 
01053     // _GLIBCXX_RESOLVE_LIB_DEFECTS
01054     // 438. Ambiguity in the "do the right thing" clause
01055     template<typename _Integer>
01056       void
01057       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01058       { _M_fill_assign(__n, __val); }
01059 
01060     template<class _InputIterator>
01061       void
01062       _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01063              __false_type)
01064       { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
01065 
01066     void
01067     _M_fill_assign(size_t __n, bool __x)
01068     {
01069       if (__n > size())
01070     {
01071       std::fill(this->_M_impl._M_start._M_p, 
01072             this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
01073       insert(end(), __n - size(), __x);
01074     }
01075       else
01076     {
01077       _M_erase_at_end(begin() + __n);
01078       std::fill(this->_M_impl._M_start._M_p, 
01079             this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
01080     }
01081     }
01082 
01083     template<typename _InputIterator>
01084       void
01085       _M_assign_aux(_InputIterator __first, _InputIterator __last,
01086             std::input_iterator_tag)
01087       {
01088     iterator __cur = begin();
01089     for (; __first != __last && __cur != end(); ++__cur, ++__first)
01090       *__cur = *__first;
01091     if (__first == __last)
01092       _M_erase_at_end(__cur);
01093     else
01094       insert(end(), __first, __last);
01095       }
01096     
01097     template<typename _ForwardIterator>
01098       void
01099       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
01100             std::forward_iterator_tag)
01101       {
01102     const size_type __len = std::distance(__first, __last);
01103     if (__len < size())
01104       _M_erase_at_end(std::copy(__first, __last, begin()));
01105     else
01106       {
01107         _ForwardIterator __mid = __first;
01108         std::advance(__mid, size());
01109         std::copy(__first, __mid, begin());
01110         insert(end(), __mid, __last);
01111       }
01112       }
01113 
01114     // Check whether it's an integral type.  If so, it's not an iterator.
01115 
01116     // _GLIBCXX_RESOLVE_LIB_DEFECTS
01117     // 438. Ambiguity in the "do the right thing" clause
01118     template<typename _Integer>
01119       void
01120       _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
01121              __true_type)
01122       { _M_fill_insert(__pos, __n, __x); }
01123 
01124     template<typename _InputIterator>
01125       void
01126       _M_insert_dispatch(iterator __pos,
01127              _InputIterator __first, _InputIterator __last,
01128              __false_type)
01129       { _M_insert_range(__pos, __first, __last,
01130             std::__iterator_category(__first)); }
01131 
01132     void
01133     _M_fill_insert(iterator __position, size_type __n, bool __x);
01134 
01135     template<typename _InputIterator>
01136       void
01137       _M_insert_range(iterator __pos, _InputIterator __first, 
01138               _InputIterator __last, std::input_iterator_tag)
01139       {
01140     for (; __first != __last; ++__first)
01141       {
01142         __pos = insert(__pos, *__first);
01143         ++__pos;
01144       }
01145       }
01146 
01147     template<typename _ForwardIterator>
01148       void
01149       _M_insert_range(iterator __position, _ForwardIterator __first, 
01150               _ForwardIterator __last, std::forward_iterator_tag);
01151 
01152     void
01153     _M_insert_aux(iterator __position, bool __x);
01154 
01155     size_type
01156     _M_check_len(size_type __n, const char* __s) const
01157     {
01158       if (max_size() - size() < __n)
01159     __throw_length_error(__N(__s));
01160 
01161       const size_type __len = size() + std::max(size(), __n);
01162       return (__len < size() || __len > max_size()) ? max_size() : __len;
01163     }
01164 
01165     void
01166     _M_erase_at_end(iterator __pos)
01167     { this->_M_impl._M_finish = __pos; }
01168 
01169     iterator
01170     _M_erase(iterator __pos);
01171 
01172     iterator
01173     _M_erase(iterator __first, iterator __last);
01174   };
01175 
01176 _GLIBCXX_END_NAMESPACE_CONTAINER
01177 } // namespace std
01178 
01179 #if __cplusplus >= 201103L
01180 
01181 #include <bits/functional_hash.h>
01182 
01183 namespace std _GLIBCXX_VISIBILITY(default)
01184 {
01185 _GLIBCXX_BEGIN_NAMESPACE_VERSION
01186 
01187   // DR 1182.
01188   /// std::hash specialization for vector<bool>.
01189   template<typename _Alloc>
01190     struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
01191     : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
01192     {
01193       size_t
01194       operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
01195     };
01196 
01197 _GLIBCXX_END_NAMESPACE_VERSION
01198 }// namespace std
01199 
01200 #endif // C++11
01201 
01202 #endif