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