libstdc++
stl_bvector.h
Go to the documentation of this file.
00001 // vector<bool> specialization -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2017 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 __gnu_cxx::__alloc_traits<_Alloc>::template
00414         rebind<_Bit_type>::other _Bit_alloc_type;
00415       typedef typename __gnu_cxx::__alloc_traits<_Bit_alloc_type>
00416         _Bit_alloc_traits;
00417       typedef typename _Bit_alloc_traits::pointer _Bit_pointer;
00418 
00419       struct _Bvector_impl
00420       : public _Bit_alloc_type
00421       {
00422         _Bit_iterator   _M_start;
00423         _Bit_iterator   _M_finish;
00424         _Bit_pointer    _M_end_of_storage;
00425 
00426         _Bvector_impl()
00427         : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage()
00428         { }
00429  
00430         _Bvector_impl(const _Bit_alloc_type& __a)
00431         : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage()
00432         { }
00433 
00434 #if __cplusplus >= 201103L
00435         _Bvector_impl(_Bit_alloc_type&& __a)
00436         : _Bit_alloc_type(std::move(__a)), _M_start(), _M_finish(),
00437           _M_end_of_storage()
00438         { }
00439 #endif
00440 
00441         _Bit_type*
00442         _M_end_addr() const _GLIBCXX_NOEXCEPT
00443         {
00444           if (_M_end_of_storage)
00445             return std::__addressof(_M_end_of_storage[-1]) + 1;
00446           return 0;
00447         }
00448       };
00449 
00450     public:
00451       typedef _Alloc allocator_type;
00452 
00453       _Bit_alloc_type&
00454       _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT
00455       { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); }
00456 
00457       const _Bit_alloc_type&
00458       _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT
00459       { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
00460 
00461       allocator_type
00462       get_allocator() const _GLIBCXX_NOEXCEPT
00463       { return allocator_type(_M_get_Bit_allocator()); }
00464 
00465       _Bvector_base()
00466       : _M_impl() { }
00467       
00468       _Bvector_base(const allocator_type& __a)
00469       : _M_impl(__a) { }
00470 
00471 #if __cplusplus >= 201103L
00472       _Bvector_base(_Bvector_base&& __x) noexcept
00473       : _M_impl(std::move(__x._M_get_Bit_allocator()))
00474       {
00475         this->_M_impl._M_start = __x._M_impl._M_start;
00476         this->_M_impl._M_finish = __x._M_impl._M_finish;
00477         this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
00478         __x._M_impl._M_start = _Bit_iterator();
00479         __x._M_impl._M_finish = _Bit_iterator();
00480         __x._M_impl._M_end_of_storage = nullptr;
00481       }
00482 #endif
00483 
00484       ~_Bvector_base()
00485       { this->_M_deallocate(); }
00486 
00487     protected:
00488       _Bvector_impl _M_impl;
00489 
00490       _Bit_pointer
00491       _M_allocate(size_t __n)
00492       { return _Bit_alloc_traits::allocate(_M_impl, _S_nword(__n)); }
00493 
00494       void
00495       _M_deallocate()
00496       {
00497         if (_M_impl._M_start._M_p)
00498           {
00499             const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p;
00500             _Bit_alloc_traits::deallocate(_M_impl,
00501                                           _M_impl._M_end_of_storage - __n,
00502                                           __n);
00503             _M_impl._M_start = _M_impl._M_finish = _Bit_iterator();
00504             _M_impl._M_end_of_storage = _Bit_pointer();
00505           }
00506       }
00507 
00508       static size_t
00509       _S_nword(size_t __n)
00510       { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); }
00511     };
00512 
00513 _GLIBCXX_END_NAMESPACE_CONTAINER
00514 } // namespace std
00515 
00516 // Declare a partial specialization of vector<T, Alloc>.
00517 #include <bits/stl_vector.h>
00518 
00519 namespace std _GLIBCXX_VISIBILITY(default)
00520 {
00521 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00522 
00523   /**
00524    *  @brief  A specialization of vector for booleans which offers fixed time
00525    *  access to individual elements in any order.
00526    *
00527    *  @ingroup sequences
00528    *
00529    *  @tparam _Alloc  Allocator type.
00530    *
00531    *  Note that vector<bool> does not actually meet the requirements for being
00532    *  a container.  This is because the reference and pointer types are not
00533    *  really references and pointers to bool.  See DR96 for details.  @see
00534    *  vector for function documentation.
00535    *
00536    *  In some terminology a %vector can be described as a dynamic
00537    *  C-style array, it offers fast and efficient access to individual
00538    *  elements in any order and saves the user from worrying about
00539    *  memory and size allocation.  Subscripting ( @c [] ) access is
00540    *  also provided as with C-style arrays.
00541   */
00542 template<typename _Alloc>
00543   class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
00544   {
00545     typedef _Bvector_base<_Alloc>                        _Base;
00546     typedef typename _Base::_Bit_pointer                 _Bit_pointer;
00547     typedef typename _Base::_Bit_alloc_traits            _Bit_alloc_traits;
00548 
00549 #if __cplusplus >= 201103L
00550     template<typename> friend struct hash;
00551 #endif
00552 
00553   public:
00554     typedef bool                                         value_type;
00555     typedef size_t                                       size_type;
00556     typedef ptrdiff_t                                    difference_type;
00557     typedef _Bit_reference                               reference;
00558     typedef bool                                         const_reference;
00559     typedef _Bit_reference*                              pointer;
00560     typedef const bool*                                  const_pointer;
00561     typedef _Bit_iterator                                iterator;
00562     typedef _Bit_const_iterator                          const_iterator;
00563     typedef std::reverse_iterator<const_iterator>        const_reverse_iterator;
00564     typedef std::reverse_iterator<iterator>              reverse_iterator;
00565     typedef _Alloc                                       allocator_type;
00566 
00567     allocator_type get_allocator() const
00568     { return _Base::get_allocator(); }
00569 
00570   protected:
00571     using _Base::_M_allocate;
00572     using _Base::_M_deallocate;
00573     using _Base::_S_nword;
00574     using _Base::_M_get_Bit_allocator;
00575 
00576   public:
00577     vector()
00578 #if __cplusplus >= 201103L
00579       noexcept(is_nothrow_default_constructible<allocator_type>::value)
00580 #endif
00581     : _Base() { }
00582 
00583     explicit
00584     vector(const allocator_type& __a)
00585     : _Base(__a) { }
00586 
00587 #if __cplusplus >= 201103L
00588     explicit
00589     vector(size_type __n, const allocator_type& __a = allocator_type())
00590     : vector(__n, false, __a)
00591     { }
00592 
00593     vector(size_type __n, const bool& __value, 
00594            const allocator_type& __a = allocator_type())
00595     : _Base(__a)
00596     {
00597       _M_initialize(__n);
00598       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(),
00599                 __value ? ~0 : 0);
00600     }
00601 #else
00602     explicit
00603     vector(size_type __n, const bool& __value = bool(), 
00604            const allocator_type& __a = allocator_type())
00605     : _Base(__a)
00606     {
00607       _M_initialize(__n);
00608       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(),
00609                 __value ? ~0 : 0);
00610     }
00611 #endif
00612 
00613     vector(const vector& __x)
00614     : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
00615     {
00616       _M_initialize(__x.size());
00617       _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start);
00618     }
00619 
00620 #if __cplusplus >= 201103L
00621     vector(vector&& __x) noexcept
00622     : _Base(std::move(__x)) { }
00623 
00624     vector(vector&& __x, const allocator_type& __a)
00625     noexcept(_Bit_alloc_traits::_S_always_equal())
00626     : _Base(__a)
00627     {
00628       if (__x.get_allocator() == __a)
00629         {
00630           this->_M_impl._M_start = __x._M_impl._M_start;
00631           this->_M_impl._M_finish = __x._M_impl._M_finish;
00632           this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
00633           __x._M_impl._M_start = _Bit_iterator();
00634           __x._M_impl._M_finish = _Bit_iterator();
00635           __x._M_impl._M_end_of_storage = nullptr;
00636         }
00637       else
00638         {
00639           _M_initialize(__x.size());
00640           _M_copy_aligned(__x.begin(), __x.end(), begin());
00641           __x.clear();
00642         }
00643     }
00644 
00645     vector(const vector& __x, const allocator_type& __a)
00646     : _Base(__a)
00647     {
00648       _M_initialize(__x.size());
00649       _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start);
00650     }
00651 
00652     vector(initializer_list<bool> __l,
00653            const allocator_type& __a = allocator_type())
00654     : _Base(__a)
00655     {
00656       _M_initialize_range(__l.begin(), __l.end(),
00657                           random_access_iterator_tag());
00658     }
00659 #endif
00660 
00661 #if __cplusplus >= 201103L
00662     template<typename _InputIterator,
00663              typename = std::_RequireInputIter<_InputIterator>>
00664       vector(_InputIterator __first, _InputIterator __last,
00665              const allocator_type& __a = allocator_type())
00666       : _Base(__a)
00667       { _M_initialize_dispatch(__first, __last, __false_type()); }
00668 #else
00669     template<typename _InputIterator>
00670       vector(_InputIterator __first, _InputIterator __last,
00671              const allocator_type& __a = allocator_type())
00672       : _Base(__a)
00673       {
00674         typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00675         _M_initialize_dispatch(__first, __last, _Integral());
00676       }
00677 #endif
00678 
00679     ~vector() _GLIBCXX_NOEXCEPT { }
00680 
00681     vector&
00682     operator=(const vector& __x)
00683     {
00684       if (&__x == this)
00685         return *this;
00686 #if __cplusplus >= 201103L
00687       if (_Bit_alloc_traits::_S_propagate_on_copy_assign())
00688         {
00689           if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator())
00690             {
00691               this->_M_deallocate();
00692               std::__alloc_on_copy(_M_get_Bit_allocator(),
00693                                    __x._M_get_Bit_allocator());
00694               _M_initialize(__x.size());
00695             }
00696           else
00697             std::__alloc_on_copy(_M_get_Bit_allocator(),
00698                                  __x._M_get_Bit_allocator());
00699         }
00700 #endif
00701       if (__x.size() > capacity())
00702         {
00703           this->_M_deallocate();
00704           _M_initialize(__x.size());
00705         }
00706       this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
00707                                                 begin());
00708       return *this;
00709     }
00710 
00711 #if __cplusplus >= 201103L
00712     vector&
00713     operator=(vector&& __x) noexcept(_Bit_alloc_traits::_S_nothrow_move())
00714     {
00715       if (_Bit_alloc_traits::_S_propagate_on_move_assign()
00716           || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator())
00717         {
00718           this->_M_deallocate();
00719           this->_M_impl._M_start = __x._M_impl._M_start;
00720           this->_M_impl._M_finish = __x._M_impl._M_finish;
00721           this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
00722           __x._M_impl._M_start = _Bit_iterator();
00723           __x._M_impl._M_finish = _Bit_iterator();
00724           __x._M_impl._M_end_of_storage = nullptr;
00725           std::__alloc_on_move(_M_get_Bit_allocator(),
00726                                __x._M_get_Bit_allocator());
00727         }
00728       else
00729         {
00730           if (__x.size() > capacity())
00731             {
00732               this->_M_deallocate();
00733               _M_initialize(__x.size());
00734             }
00735           this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
00736                                                     begin());
00737           __x.clear();
00738         }
00739       return *this;
00740     }
00741 
00742     vector&
00743     operator=(initializer_list<bool> __l)
00744     {
00745       this->assign (__l.begin(), __l.end());
00746       return *this;
00747     }
00748 #endif
00749 
00750     // assign(), a generalized assignment member function.  Two
00751     // versions: one that takes a count, and one that takes a range.
00752     // The range version is a member template, so we dispatch on whether
00753     // or not the type is an integer.
00754     void
00755     assign(size_type __n, const bool& __x)
00756     { _M_fill_assign(__n, __x); }
00757 
00758 #if __cplusplus >= 201103L
00759     template<typename _InputIterator,
00760              typename = std::_RequireInputIter<_InputIterator>>
00761       void
00762       assign(_InputIterator __first, _InputIterator __last)
00763       { _M_assign_dispatch(__first, __last, __false_type()); }
00764 #else
00765     template<typename _InputIterator>
00766       void
00767       assign(_InputIterator __first, _InputIterator __last)
00768       {
00769         typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00770         _M_assign_dispatch(__first, __last, _Integral());
00771       }
00772 #endif
00773 
00774 #if __cplusplus >= 201103L
00775     void
00776     assign(initializer_list<bool> __l)
00777     { this->assign(__l.begin(), __l.end()); }
00778 #endif
00779 
00780     iterator
00781     begin() _GLIBCXX_NOEXCEPT
00782     { return this->_M_impl._M_start; }
00783 
00784     const_iterator
00785     begin() const _GLIBCXX_NOEXCEPT
00786     { return this->_M_impl._M_start; }
00787 
00788     iterator
00789     end() _GLIBCXX_NOEXCEPT
00790     { return this->_M_impl._M_finish; }
00791 
00792     const_iterator
00793     end() const _GLIBCXX_NOEXCEPT
00794     { return this->_M_impl._M_finish; }
00795 
00796     reverse_iterator
00797     rbegin() _GLIBCXX_NOEXCEPT
00798     { return reverse_iterator(end()); }
00799 
00800     const_reverse_iterator
00801     rbegin() const _GLIBCXX_NOEXCEPT
00802     { return const_reverse_iterator(end()); }
00803 
00804     reverse_iterator
00805     rend() _GLIBCXX_NOEXCEPT
00806     { return reverse_iterator(begin()); }
00807 
00808     const_reverse_iterator
00809     rend() const _GLIBCXX_NOEXCEPT
00810     { return const_reverse_iterator(begin()); }
00811 
00812 #if __cplusplus >= 201103L
00813     const_iterator
00814     cbegin() const noexcept
00815     { return this->_M_impl._M_start; }
00816 
00817     const_iterator
00818     cend() const noexcept
00819     { return this->_M_impl._M_finish; }
00820 
00821     const_reverse_iterator
00822     crbegin() const noexcept
00823     { return const_reverse_iterator(end()); }
00824 
00825     const_reverse_iterator
00826     crend() const noexcept
00827     { return const_reverse_iterator(begin()); }
00828 #endif
00829 
00830     size_type
00831     size() const _GLIBCXX_NOEXCEPT
00832     { return size_type(end() - begin()); }
00833 
00834     size_type
00835     max_size() const _GLIBCXX_NOEXCEPT
00836     {
00837       const size_type __isize =
00838         __gnu_cxx::__numeric_traits<difference_type>::__max
00839         - int(_S_word_bit) + 1;
00840       const size_type __asize
00841         = _Bit_alloc_traits::max_size(_M_get_Bit_allocator());
00842       return (__asize <= __isize / int(_S_word_bit)
00843               ? __asize * int(_S_word_bit) : __isize);
00844     }
00845 
00846     size_type
00847     capacity() const _GLIBCXX_NOEXCEPT
00848     { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
00849                        - begin()); }
00850 
00851     bool
00852     empty() const _GLIBCXX_NOEXCEPT
00853     { return begin() == end(); }
00854 
00855     reference
00856     operator[](size_type __n)
00857     {
00858       return *iterator(this->_M_impl._M_start._M_p
00859                        + __n / int(_S_word_bit), __n % int(_S_word_bit));
00860     }
00861 
00862     const_reference
00863     operator[](size_type __n) const
00864     {
00865       return *const_iterator(this->_M_impl._M_start._M_p
00866                              + __n / int(_S_word_bit), __n % int(_S_word_bit));
00867     }
00868 
00869   protected:
00870     void
00871     _M_range_check(size_type __n) const
00872     {
00873       if (__n >= this->size())
00874         __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n "
00875                                      "(which is %zu) >= this->size() "
00876                                      "(which is %zu)"),
00877                                  __n, this->size());
00878     }
00879 
00880   public:
00881     reference
00882     at(size_type __n)
00883     { _M_range_check(__n); return (*this)[__n]; }
00884 
00885     const_reference
00886     at(size_type __n) const
00887     { _M_range_check(__n); return (*this)[__n]; }
00888 
00889     void
00890     reserve(size_type __n)
00891     {
00892       if (__n > max_size())
00893         __throw_length_error(__N("vector::reserve"));
00894       if (capacity() < __n)
00895         _M_reallocate(__n);
00896     }
00897 
00898     reference
00899     front()
00900     { return *begin(); }
00901 
00902     const_reference
00903     front() const
00904     { return *begin(); }
00905 
00906     reference
00907     back()
00908     { return *(end() - 1); }
00909 
00910     const_reference
00911     back() const
00912     { return *(end() - 1); }
00913 
00914     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00915     // DR 464. Suggestion for new member functions in standard containers.
00916     // N.B. DR 464 says nothing about vector<bool> but we need something
00917     // here due to the way we are implementing DR 464 in the debug-mode
00918     // vector class.
00919     void
00920     data() _GLIBCXX_NOEXCEPT { }
00921 
00922     void
00923     push_back(bool __x)
00924     {
00925       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
00926         *this->_M_impl._M_finish++ = __x;
00927       else
00928         _M_insert_aux(end(), __x);
00929     }
00930 
00931     void
00932     swap(vector& __x) _GLIBCXX_NOEXCEPT
00933     {
00934       std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
00935       std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
00936       std::swap(this->_M_impl._M_end_of_storage, 
00937                 __x._M_impl._M_end_of_storage);
00938       _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(),
00939                                     __x._M_get_Bit_allocator());
00940     }
00941 
00942     // [23.2.5]/1, third-to-last entry in synopsis listing
00943     static void
00944     swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
00945     {
00946       bool __tmp = __x;
00947       __x = __y;
00948       __y = __tmp;
00949     }
00950 
00951     iterator
00952 #if __cplusplus >= 201103L
00953     insert(const_iterator __position, const bool& __x = bool())
00954 #else
00955     insert(iterator __position, const bool& __x = bool())
00956 #endif
00957     {
00958       const difference_type __n = __position - begin();
00959       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()
00960           && __position == end())
00961         *this->_M_impl._M_finish++ = __x;
00962       else
00963         _M_insert_aux(__position._M_const_cast(), __x);
00964       return begin() + __n;
00965     }
00966 
00967 #if __cplusplus >= 201103L
00968     template<typename _InputIterator,
00969              typename = std::_RequireInputIter<_InputIterator>>
00970       iterator
00971       insert(const_iterator __position,
00972              _InputIterator __first, _InputIterator __last)
00973       {
00974         difference_type __offset = __position - cbegin();
00975         _M_insert_dispatch(__position._M_const_cast(),
00976                            __first, __last, __false_type());
00977         return begin() + __offset;
00978       }
00979 #else
00980     template<typename _InputIterator>
00981       void
00982       insert(iterator __position,
00983              _InputIterator __first, _InputIterator __last)
00984       {
00985         typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00986         _M_insert_dispatch(__position, __first, __last, _Integral());
00987       }
00988 #endif
00989 
00990 #if __cplusplus >= 201103L
00991     iterator
00992     insert(const_iterator __position, size_type __n, const bool& __x)
00993     {
00994       difference_type __offset = __position - cbegin();
00995       _M_fill_insert(__position._M_const_cast(), __n, __x);
00996       return begin() + __offset;
00997     }
00998 #else
00999     void
01000     insert(iterator __position, size_type __n, const bool& __x)
01001     { _M_fill_insert(__position, __n, __x); }
01002 #endif
01003 
01004 #if __cplusplus >= 201103L
01005     iterator
01006     insert(const_iterator __p, initializer_list<bool> __l)
01007     { return this->insert(__p, __l.begin(), __l.end()); }
01008 #endif
01009 
01010     void
01011     pop_back()
01012     { --this->_M_impl._M_finish; }
01013 
01014     iterator
01015 #if __cplusplus >= 201103L
01016     erase(const_iterator __position)
01017 #else
01018     erase(iterator __position)
01019 #endif
01020     { return _M_erase(__position._M_const_cast()); }
01021 
01022     iterator
01023 #if __cplusplus >= 201103L
01024     erase(const_iterator __first, const_iterator __last)
01025 #else
01026     erase(iterator __first, iterator __last)
01027 #endif
01028     { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
01029 
01030     void
01031     resize(size_type __new_size, bool __x = bool())
01032     {
01033       if (__new_size < size())
01034         _M_erase_at_end(begin() + difference_type(__new_size));
01035       else
01036         insert(end(), __new_size - size(), __x);
01037     }
01038 
01039 #if __cplusplus >= 201103L
01040     void
01041     shrink_to_fit()
01042     { _M_shrink_to_fit(); }
01043 #endif
01044 
01045     void
01046     flip() _GLIBCXX_NOEXCEPT
01047     {
01048       _Bit_type * const __end = this->_M_impl._M_end_addr();
01049       for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p)
01050         *__p = ~*__p;
01051     }
01052 
01053     void
01054     clear() _GLIBCXX_NOEXCEPT
01055     { _M_erase_at_end(begin()); }
01056 
01057 #if __cplusplus >= 201103L
01058     template<typename... _Args>
01059 #if __cplusplus > 201402L
01060       reference
01061 #else
01062       void
01063 #endif
01064       emplace_back(_Args&&... __args)
01065       {
01066         push_back(bool(__args...));
01067 #if __cplusplus > 201402L
01068         return back();
01069 #endif
01070       }
01071 
01072     template<typename... _Args>
01073       iterator
01074       emplace(const_iterator __pos, _Args&&... __args)
01075       { return insert(__pos, bool(__args...)); }
01076 #endif
01077 
01078   protected:
01079     // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
01080     iterator
01081     _M_copy_aligned(const_iterator __first, const_iterator __last,
01082                     iterator __result)
01083     {
01084       _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
01085       return std::copy(const_iterator(__last._M_p, 0), __last,
01086                        iterator(__q, 0));
01087     }
01088 
01089     void
01090     _M_initialize(size_type __n)
01091     {
01092       _Bit_pointer __q = this->_M_allocate(__n);
01093       this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
01094       this->_M_impl._M_start = iterator(std::__addressof(*__q), 0);
01095       this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
01096     }
01097 
01098     void
01099     _M_reallocate(size_type __n);
01100 
01101 #if __cplusplus >= 201103L
01102     bool
01103     _M_shrink_to_fit();
01104 #endif
01105 
01106     // Check whether it's an integral type.  If so, it's not an iterator.
01107 
01108     // _GLIBCXX_RESOLVE_LIB_DEFECTS
01109     // 438. Ambiguity in the "do the right thing" clause
01110     template<typename _Integer>
01111       void
01112       _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
01113       {
01114         _M_initialize(static_cast<size_type>(__n));
01115         std::fill(this->_M_impl._M_start._M_p, 
01116                   this->_M_impl._M_end_addr(), __x ? ~0 : 0);
01117       }
01118 
01119     template<typename _InputIterator>
01120       void 
01121       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
01122                              __false_type)
01123       { _M_initialize_range(__first, __last, 
01124                             std::__iterator_category(__first)); }
01125 
01126     template<typename _InputIterator>
01127       void
01128       _M_initialize_range(_InputIterator __first, _InputIterator __last,
01129                           std::input_iterator_tag)
01130       {
01131         for (; __first != __last; ++__first)
01132           push_back(*__first);
01133       }
01134 
01135     template<typename _ForwardIterator>
01136       void
01137       _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
01138                           std::forward_iterator_tag)
01139       {
01140         const size_type __n = std::distance(__first, __last);
01141         _M_initialize(__n);
01142         std::copy(__first, __last, this->_M_impl._M_start);
01143       }
01144 
01145     // _GLIBCXX_RESOLVE_LIB_DEFECTS
01146     // 438. Ambiguity in the "do the right thing" clause
01147     template<typename _Integer>
01148       void
01149       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01150       { _M_fill_assign(__n, __val); }
01151 
01152     template<class _InputIterator>
01153       void
01154       _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01155                          __false_type)
01156       { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
01157 
01158     void
01159     _M_fill_assign(size_t __n, bool __x)
01160     {
01161       if (__n > size())
01162         {
01163           std::fill(this->_M_impl._M_start._M_p, 
01164                     this->_M_impl._M_end_addr(), __x ? ~0 : 0);
01165           insert(end(), __n - size(), __x);
01166         }
01167       else
01168         {
01169           _M_erase_at_end(begin() + __n);
01170           std::fill(this->_M_impl._M_start._M_p, 
01171                     this->_M_impl._M_end_addr(), __x ? ~0 : 0);
01172         }
01173     }
01174 
01175     template<typename _InputIterator>
01176       void
01177       _M_assign_aux(_InputIterator __first, _InputIterator __last,
01178                     std::input_iterator_tag)
01179       {
01180         iterator __cur = begin();
01181         for (; __first != __last && __cur != end(); ++__cur, ++__first)
01182           *__cur = *__first;
01183         if (__first == __last)
01184           _M_erase_at_end(__cur);
01185         else
01186           insert(end(), __first, __last);
01187       }
01188     
01189     template<typename _ForwardIterator>
01190       void
01191       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
01192                     std::forward_iterator_tag)
01193       {
01194         const size_type __len = std::distance(__first, __last);
01195         if (__len < size())
01196           _M_erase_at_end(std::copy(__first, __last, begin()));
01197         else
01198           {
01199             _ForwardIterator __mid = __first;
01200             std::advance(__mid, size());
01201             std::copy(__first, __mid, begin());
01202             insert(end(), __mid, __last);
01203           }
01204       }
01205 
01206     // Check whether it's an integral type.  If so, it's not an iterator.
01207 
01208     // _GLIBCXX_RESOLVE_LIB_DEFECTS
01209     // 438. Ambiguity in the "do the right thing" clause
01210     template<typename _Integer>
01211       void
01212       _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
01213                          __true_type)
01214       { _M_fill_insert(__pos, __n, __x); }
01215 
01216     template<typename _InputIterator>
01217       void
01218       _M_insert_dispatch(iterator __pos,
01219                          _InputIterator __first, _InputIterator __last,
01220                          __false_type)
01221       { _M_insert_range(__pos, __first, __last,
01222                         std::__iterator_category(__first)); }
01223 
01224     void
01225     _M_fill_insert(iterator __position, size_type __n, bool __x);
01226 
01227     template<typename _InputIterator>
01228       void
01229       _M_insert_range(iterator __pos, _InputIterator __first, 
01230                       _InputIterator __last, std::input_iterator_tag)
01231       {
01232         for (; __first != __last; ++__first)
01233           {
01234             __pos = insert(__pos, *__first);
01235             ++__pos;
01236           }
01237       }
01238 
01239     template<typename _ForwardIterator>
01240       void
01241       _M_insert_range(iterator __position, _ForwardIterator __first, 
01242                       _ForwardIterator __last, std::forward_iterator_tag);
01243 
01244     void
01245     _M_insert_aux(iterator __position, bool __x);
01246 
01247     size_type
01248     _M_check_len(size_type __n, const char* __s) const
01249     {
01250       if (max_size() - size() < __n)
01251         __throw_length_error(__N(__s));
01252 
01253       const size_type __len = size() + std::max(size(), __n);
01254       return (__len < size() || __len > max_size()) ? max_size() : __len;
01255     }
01256 
01257     void
01258     _M_erase_at_end(iterator __pos)
01259     { this->_M_impl._M_finish = __pos; }
01260 
01261     iterator
01262     _M_erase(iterator __pos);
01263 
01264     iterator
01265     _M_erase(iterator __first, iterator __last);
01266   };
01267 
01268 _GLIBCXX_END_NAMESPACE_CONTAINER
01269 } // namespace std
01270 
01271 #if __cplusplus >= 201103L
01272 
01273 #include <bits/functional_hash.h>
01274 
01275 namespace std _GLIBCXX_VISIBILITY(default)
01276 {
01277 _GLIBCXX_BEGIN_NAMESPACE_VERSION
01278 
01279   // DR 1182.
01280   /// std::hash specialization for vector<bool>.
01281   template<typename _Alloc>
01282     struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
01283     : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
01284     {
01285       size_t
01286       operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
01287     };
01288 
01289 _GLIBCXX_END_NAMESPACE_VERSION
01290 }// namespace std
01291 
01292 #endif // C++11
01293 
01294 #endif