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