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