libstdc++
stl_bvector.h
Go to the documentation of this file.
00001 // vector<bool> specialization -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2013 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     reference
00226     operator*() const
00227     { return reference(_M_p, 1UL << _M_offset); }
00228 
00229     iterator&
00230     operator++()
00231     {
00232       _M_bump_up();
00233       return *this;
00234     }
00235 
00236     iterator
00237     operator++(int)
00238     {
00239       iterator __tmp = *this;
00240       _M_bump_up();
00241       return __tmp;
00242     }
00243 
00244     iterator&
00245     operator--()
00246     {
00247       _M_bump_down();
00248       return *this;
00249     }
00250 
00251     iterator
00252     operator--(int)
00253     {
00254       iterator __tmp = *this;
00255       _M_bump_down();
00256       return __tmp;
00257     }
00258 
00259     iterator&
00260     operator+=(difference_type __i)
00261     {
00262       _M_incr(__i);
00263       return *this;
00264     }
00265 
00266     iterator&
00267     operator-=(difference_type __i)
00268     {
00269       *this += -__i;
00270       return *this;
00271     }
00272 
00273     iterator
00274     operator+(difference_type __i) const
00275     {
00276       iterator __tmp = *this;
00277       return __tmp += __i;
00278     }
00279 
00280     iterator
00281     operator-(difference_type __i) const
00282     {
00283       iterator __tmp = *this;
00284       return __tmp -= __i;
00285     }
00286 
00287     reference
00288     operator[](difference_type __i) const
00289     { return *(*this + __i); }
00290   };
00291 
00292   inline _Bit_iterator
00293   operator+(ptrdiff_t __n, const _Bit_iterator& __x)
00294   { return __x + __n; }
00295 
00296   struct _Bit_const_iterator : public _Bit_iterator_base
00297   {
00298     typedef bool                 reference;
00299     typedef bool                 const_reference;
00300     typedef const bool*          pointer;
00301     typedef _Bit_const_iterator  const_iterator;
00302 
00303     _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
00304 
00305     _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
00306     : _Bit_iterator_base(__x, __y) { }
00307 
00308     _Bit_const_iterator(const _Bit_iterator& __x)
00309     : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
00310 
00311     const_reference
00312     operator*() const
00313     { return _Bit_reference(_M_p, 1UL << _M_offset); }
00314 
00315     const_iterator&
00316     operator++()
00317     {
00318       _M_bump_up();
00319       return *this;
00320     }
00321 
00322     const_iterator
00323     operator++(int)
00324     {
00325       const_iterator __tmp = *this;
00326       _M_bump_up();
00327       return __tmp;
00328     }
00329 
00330     const_iterator&
00331     operator--()
00332     {
00333       _M_bump_down();
00334       return *this;
00335     }
00336 
00337     const_iterator
00338     operator--(int)
00339     {
00340       const_iterator __tmp = *this;
00341       _M_bump_down();
00342       return __tmp;
00343     }
00344 
00345     const_iterator&
00346     operator+=(difference_type __i)
00347     {
00348       _M_incr(__i);
00349       return *this;
00350     }
00351 
00352     const_iterator&
00353     operator-=(difference_type __i)
00354     {
00355       *this += -__i;
00356       return *this;
00357     }
00358 
00359     const_iterator 
00360     operator+(difference_type __i) const
00361     {
00362       const_iterator __tmp = *this;
00363       return __tmp += __i;
00364     }
00365 
00366     const_iterator
00367     operator-(difference_type __i) const
00368     {
00369       const_iterator __tmp = *this;
00370       return __tmp -= __i;
00371     }
00372 
00373     const_reference
00374     operator[](difference_type __i) const
00375     { return *(*this + __i); }
00376   };
00377 
00378   inline _Bit_const_iterator
00379   operator+(ptrdiff_t __n, const _Bit_const_iterator& __x)
00380   { return __x + __n; }
00381 
00382   inline void
00383   __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x)
00384   {
00385     for (; __first != __last; ++__first)
00386       *__first = __x;
00387   }
00388 
00389   inline void
00390   fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x)
00391   {
00392     if (__first._M_p != __last._M_p)
00393       {
00394     std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0);
00395     __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x);
00396     __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x);
00397       }
00398     else
00399       __fill_bvector(__first, __last, __x);
00400   }
00401 
00402   template<typename _Alloc>
00403     struct _Bvector_base
00404     {
00405       typedef typename _Alloc::template rebind<_Bit_type>::other
00406         _Bit_alloc_type;
00407       
00408       struct _Bvector_impl
00409       : public _Bit_alloc_type
00410       {
00411     _Bit_iterator   _M_start;
00412     _Bit_iterator   _M_finish;
00413     _Bit_type*  _M_end_of_storage;
00414 
00415     _Bvector_impl()
00416     : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage(0)
00417     { }
00418  
00419     _Bvector_impl(const _Bit_alloc_type& __a)
00420     : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
00421     { }
00422 
00423 #if __cplusplus >= 201103L
00424     _Bvector_impl(_Bit_alloc_type&& __a)
00425     : _Bit_alloc_type(std::move(__a)), _M_start(), _M_finish(),
00426       _M_end_of_storage(0)
00427     { }
00428 #endif
00429       };
00430 
00431     public:
00432       typedef _Alloc allocator_type;
00433 
00434       _Bit_alloc_type&
00435       _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT
00436       { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); }
00437 
00438       const _Bit_alloc_type&
00439       _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT
00440       { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
00441 
00442       allocator_type
00443       get_allocator() const _GLIBCXX_NOEXCEPT
00444       { return allocator_type(_M_get_Bit_allocator()); }
00445 
00446       _Bvector_base()
00447       : _M_impl() { }
00448       
00449       _Bvector_base(const allocator_type& __a)
00450       : _M_impl(__a) { }
00451 
00452 #if __cplusplus >= 201103L
00453       _Bvector_base(_Bvector_base&& __x) noexcept
00454       : _M_impl(std::move(__x._M_get_Bit_allocator()))
00455       {
00456     this->_M_impl._M_start = __x._M_impl._M_start;
00457     this->_M_impl._M_finish = __x._M_impl._M_finish;
00458     this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
00459     __x._M_impl._M_start = _Bit_iterator();
00460     __x._M_impl._M_finish = _Bit_iterator();
00461     __x._M_impl._M_end_of_storage = 0;
00462       }
00463 #endif
00464 
00465       ~_Bvector_base()
00466       { this->_M_deallocate(); }
00467 
00468     protected:
00469       _Bvector_impl _M_impl;
00470 
00471       _Bit_type*
00472       _M_allocate(size_t __n)
00473       { return _M_impl.allocate(_S_nword(__n)); }
00474 
00475       void
00476       _M_deallocate()
00477       {
00478     if (_M_impl._M_start._M_p)
00479       _M_impl.deallocate(_M_impl._M_start._M_p,
00480                  _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
00481       }
00482 
00483       static size_t
00484       _S_nword(size_t __n)
00485       { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); }
00486     };
00487 
00488 _GLIBCXX_END_NAMESPACE_CONTAINER
00489 } // namespace std
00490 
00491 // Declare a partial specialization of vector<T, Alloc>.
00492 #include <bits/stl_vector.h>
00493 
00494 namespace std _GLIBCXX_VISIBILITY(default)
00495 {
00496 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00497 
00498   /**
00499    *  @brief  A specialization of vector for booleans which offers fixed time
00500    *  access to individual elements in any order.
00501    *
00502    *  @ingroup sequences
00503    *
00504    *  @tparam _Alloc  Allocator type.
00505    *
00506    *  Note that vector<bool> does not actually meet the requirements for being
00507    *  a container.  This is because the reference and pointer types are not
00508    *  really references and pointers to bool.  See DR96 for details.  @see
00509    *  vector for function documentation.
00510    *
00511    *  In some terminology a %vector can be described as a dynamic
00512    *  C-style array, it offers fast and efficient access to individual
00513    *  elements in any order and saves the user from worrying about
00514    *  memory and size allocation.  Subscripting ( @c [] ) access is
00515    *  also provided as with C-style arrays.
00516   */
00517 template<typename _Alloc>
00518   class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
00519   {
00520     typedef _Bvector_base<_Alloc>            _Base;
00521 
00522 #if __cplusplus >= 201103L
00523     template<typename> friend class hash;
00524 #endif
00525 
00526   public:
00527     typedef bool                                         value_type;
00528     typedef size_t                                       size_type;
00529     typedef ptrdiff_t                                    difference_type;
00530     typedef _Bit_reference                               reference;
00531     typedef bool                                         const_reference;
00532     typedef _Bit_reference*                              pointer;
00533     typedef const bool*                                  const_pointer;
00534     typedef _Bit_iterator                                iterator;
00535     typedef _Bit_const_iterator                          const_iterator;
00536     typedef std::reverse_iterator<const_iterator>        const_reverse_iterator;
00537     typedef std::reverse_iterator<iterator>              reverse_iterator;
00538     typedef _Alloc                               allocator_type;
00539 
00540     allocator_type get_allocator() const
00541     { return _Base::get_allocator(); }
00542 
00543   protected:
00544     using _Base::_M_allocate;
00545     using _Base::_M_deallocate;
00546     using _Base::_S_nword;
00547     using _Base::_M_get_Bit_allocator;
00548 
00549   public:
00550     vector()
00551     : _Base() { }
00552 
00553     explicit
00554     vector(const allocator_type& __a)
00555     : _Base(__a) { }
00556 
00557 #if __cplusplus >= 201103L
00558     explicit
00559     vector(size_type __n, const allocator_type& __a = allocator_type())
00560     : vector(__n, false, __a)
00561     { }
00562 
00563     vector(size_type __n, const bool& __value, 
00564        const allocator_type& __a = allocator_type())
00565     : _Base(__a)
00566     {
00567       _M_initialize(__n);
00568       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, 
00569         __value ? ~0 : 0);
00570     }
00571 #else
00572     explicit
00573     vector(size_type __n, const bool& __value = bool(), 
00574        const allocator_type& __a = allocator_type())
00575     : _Base(__a)
00576     {
00577       _M_initialize(__n);
00578       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, 
00579         __value ? ~0 : 0);
00580     }
00581 #endif
00582 
00583     vector(const vector& __x)
00584     : _Base(__x._M_get_Bit_allocator())
00585     {
00586       _M_initialize(__x.size());
00587       _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start);
00588     }
00589 
00590 #if __cplusplus >= 201103L
00591     vector(vector&& __x) noexcept
00592     : _Base(std::move(__x)) { }
00593 
00594     vector(initializer_list<bool> __l,
00595        const allocator_type& __a = allocator_type())
00596     : _Base(__a)
00597     {
00598       _M_initialize_range(__l.begin(), __l.end(),
00599               random_access_iterator_tag());
00600     }
00601 #endif
00602 
00603 #if __cplusplus >= 201103L
00604     template<typename _InputIterator,
00605          typename = std::_RequireInputIter<_InputIterator>>
00606       vector(_InputIterator __first, _InputIterator __last,
00607          const allocator_type& __a = allocator_type())
00608       : _Base(__a)
00609       { _M_initialize_dispatch(__first, __last, __false_type()); }
00610 #else
00611     template<typename _InputIterator>
00612       vector(_InputIterator __first, _InputIterator __last,
00613          const allocator_type& __a = allocator_type())
00614       : _Base(__a)
00615       {
00616     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00617     _M_initialize_dispatch(__first, __last, _Integral());
00618       }
00619 #endif
00620 
00621     ~vector() _GLIBCXX_NOEXCEPT { }
00622 
00623     vector&
00624     operator=(const vector& __x)
00625     {
00626       if (&__x == this)
00627     return *this;
00628       if (__x.size() > capacity())
00629     {
00630       this->_M_deallocate();
00631       _M_initialize(__x.size());
00632     }
00633       this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
00634                         begin());
00635       return *this;
00636     }
00637 
00638 #if __cplusplus >= 201103L
00639     vector&
00640     operator=(vector&& __x)
00641     {
00642       // NB: DR 1204.
00643       // NB: DR 675.
00644       this->clear();
00645       this->swap(__x); 
00646       return *this;
00647     }
00648 
00649     vector&
00650     operator=(initializer_list<bool> __l)
00651     {
00652       this->assign (__l.begin(), __l.end());
00653       return *this;
00654     }
00655 #endif
00656 
00657     // assign(), a generalized assignment member function.  Two
00658     // versions: one that takes a count, and one that takes a range.
00659     // The range version is a member template, so we dispatch on whether
00660     // or not the type is an integer.
00661     void
00662     assign(size_type __n, const bool& __x)
00663     { _M_fill_assign(__n, __x); }
00664 
00665 #if __cplusplus >= 201103L
00666     template<typename _InputIterator,
00667          typename = std::_RequireInputIter<_InputIterator>>
00668       void
00669       assign(_InputIterator __first, _InputIterator __last)
00670       { _M_assign_dispatch(__first, __last, __false_type()); }
00671 #else
00672     template<typename _InputIterator>
00673       void
00674       assign(_InputIterator __first, _InputIterator __last)
00675       {
00676     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00677     _M_assign_dispatch(__first, __last, _Integral());
00678       }
00679 #endif
00680 
00681 #if __cplusplus >= 201103L
00682     void
00683     assign(initializer_list<bool> __l)
00684     { this->assign(__l.begin(), __l.end()); }
00685 #endif
00686 
00687     iterator
00688     begin() _GLIBCXX_NOEXCEPT
00689     { return this->_M_impl._M_start; }
00690 
00691     const_iterator
00692     begin() const _GLIBCXX_NOEXCEPT
00693     { return this->_M_impl._M_start; }
00694 
00695     iterator
00696     end() _GLIBCXX_NOEXCEPT
00697     { return this->_M_impl._M_finish; }
00698 
00699     const_iterator
00700     end() const _GLIBCXX_NOEXCEPT
00701     { return this->_M_impl._M_finish; }
00702 
00703     reverse_iterator
00704     rbegin() _GLIBCXX_NOEXCEPT
00705     { return reverse_iterator(end()); }
00706 
00707     const_reverse_iterator
00708     rbegin() const _GLIBCXX_NOEXCEPT
00709     { return const_reverse_iterator(end()); }
00710 
00711     reverse_iterator
00712     rend() _GLIBCXX_NOEXCEPT
00713     { return reverse_iterator(begin()); }
00714 
00715     const_reverse_iterator
00716     rend() const _GLIBCXX_NOEXCEPT
00717     { return const_reverse_iterator(begin()); }
00718 
00719 #if __cplusplus >= 201103L
00720     const_iterator
00721     cbegin() const noexcept
00722     { return this->_M_impl._M_start; }
00723 
00724     const_iterator
00725     cend() const noexcept
00726     { return this->_M_impl._M_finish; }
00727 
00728     const_reverse_iterator
00729     crbegin() const noexcept
00730     { return const_reverse_iterator(end()); }
00731 
00732     const_reverse_iterator
00733     crend() const noexcept
00734     { return const_reverse_iterator(begin()); }
00735 #endif
00736 
00737     size_type
00738     size() const _GLIBCXX_NOEXCEPT
00739     { return size_type(end() - begin()); }
00740 
00741     size_type
00742     max_size() const _GLIBCXX_NOEXCEPT
00743     {
00744       const size_type __isize =
00745     __gnu_cxx::__numeric_traits<difference_type>::__max
00746     - int(_S_word_bit) + 1;
00747       const size_type __asize = _M_get_Bit_allocator().max_size();
00748       return (__asize <= __isize / int(_S_word_bit)
00749           ? __asize * int(_S_word_bit) : __isize);
00750     }
00751 
00752     size_type
00753     capacity() const _GLIBCXX_NOEXCEPT
00754     { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
00755                - begin()); }
00756 
00757     bool
00758     empty() const _GLIBCXX_NOEXCEPT
00759     { return begin() == end(); }
00760 
00761     reference
00762     operator[](size_type __n)
00763     {
00764       return *iterator(this->_M_impl._M_start._M_p
00765                + __n / int(_S_word_bit), __n % int(_S_word_bit));
00766     }
00767 
00768     const_reference
00769     operator[](size_type __n) const
00770     {
00771       return *const_iterator(this->_M_impl._M_start._M_p
00772                  + __n / int(_S_word_bit), __n % int(_S_word_bit));
00773     }
00774 
00775   protected:
00776     void
00777     _M_range_check(size_type __n) const
00778     {
00779       if (__n >= this->size())
00780         __throw_out_of_range(__N("vector<bool>::_M_range_check"));
00781     }
00782 
00783   public:
00784     reference
00785     at(size_type __n)
00786     { _M_range_check(__n); return (*this)[__n]; }
00787 
00788     const_reference
00789     at(size_type __n) const
00790     { _M_range_check(__n); return (*this)[__n]; }
00791 
00792     void
00793     reserve(size_type __n)
00794     {
00795       if (__n > max_size())
00796     __throw_length_error(__N("vector::reserve"));
00797       if (capacity() < __n)
00798     _M_reallocate(__n);
00799     }
00800 
00801     reference
00802     front()
00803     { return *begin(); }
00804 
00805     const_reference
00806     front() const
00807     { return *begin(); }
00808 
00809     reference
00810     back()
00811     { return *(end() - 1); }
00812 
00813     const_reference
00814     back() const
00815     { return *(end() - 1); }
00816 
00817     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00818     // DR 464. Suggestion for new member functions in standard containers.
00819     // N.B. DR 464 says nothing about vector<bool> but we need something
00820     // here due to the way we are implementing DR 464 in the debug-mode
00821     // vector class.
00822     void
00823     data() _GLIBCXX_NOEXCEPT { }
00824 
00825     void
00826     push_back(bool __x)
00827     {
00828       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
00829         *this->_M_impl._M_finish++ = __x;
00830       else
00831         _M_insert_aux(end(), __x);
00832     }
00833 
00834     void
00835     swap(vector& __x)
00836     {
00837       std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
00838       std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
00839       std::swap(this->_M_impl._M_end_of_storage, 
00840         __x._M_impl._M_end_of_storage);
00841 
00842       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00843       // 431. Swapping containers with unequal allocators.
00844       std::__alloc_swap<typename _Base::_Bit_alloc_type>::
00845     _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator());
00846     }
00847 
00848     // [23.2.5]/1, third-to-last entry in synopsis listing
00849     static void
00850     swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
00851     {
00852       bool __tmp = __x;
00853       __x = __y;
00854       __y = __tmp;
00855     }
00856 
00857     iterator
00858     insert(iterator __position, const bool& __x = bool())
00859     {
00860       const difference_type __n = __position - begin();
00861       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
00862       && __position == end())
00863         *this->_M_impl._M_finish++ = __x;
00864       else
00865         _M_insert_aux(__position, __x);
00866       return begin() + __n;
00867     }
00868 
00869 #if __cplusplus >= 201103L
00870     template<typename _InputIterator,
00871          typename = std::_RequireInputIter<_InputIterator>>
00872       void
00873       insert(iterator __position,
00874          _InputIterator __first, _InputIterator __last)
00875       { _M_insert_dispatch(__position, __first, __last, __false_type()); }
00876 #else
00877     template<typename _InputIterator>
00878       void
00879       insert(iterator __position,
00880          _InputIterator __first, _InputIterator __last)
00881       {
00882     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00883     _M_insert_dispatch(__position, __first, __last, _Integral());
00884       }
00885 #endif
00886 
00887     void
00888     insert(iterator __position, size_type __n, const bool& __x)
00889     { _M_fill_insert(__position, __n, __x); }
00890 
00891 #if __cplusplus >= 201103L
00892     void insert(iterator __p, initializer_list<bool> __l)
00893     { this->insert(__p, __l.begin(), __l.end()); }
00894 #endif
00895 
00896     void
00897     pop_back()
00898     { --this->_M_impl._M_finish; }
00899 
00900     iterator
00901     erase(iterator __position)
00902     {
00903       if (__position + 1 != end())
00904         std::copy(__position + 1, end(), __position);
00905       --this->_M_impl._M_finish;
00906       return __position;
00907     }
00908 
00909     iterator
00910     erase(iterator __first, iterator __last)
00911     {
00912       if (__first != __last)
00913     _M_erase_at_end(std::copy(__last, end(), __first));
00914       return __first;
00915     }
00916 
00917     void
00918     resize(size_type __new_size, bool __x = bool())
00919     {
00920       if (__new_size < size())
00921         _M_erase_at_end(begin() + difference_type(__new_size));
00922       else
00923         insert(end(), __new_size - size(), __x);
00924     }
00925 
00926 #if __cplusplus >= 201103L
00927     void
00928     shrink_to_fit()
00929     { _M_shrink_to_fit(); }
00930 #endif
00931 
00932     void
00933     flip() _GLIBCXX_NOEXCEPT
00934     {
00935       for (_Bit_type * __p = this->_M_impl._M_start._M_p;
00936        __p != this->_M_impl._M_end_of_storage; ++__p)
00937         *__p = ~*__p;
00938     }
00939 
00940     void
00941     clear() _GLIBCXX_NOEXCEPT
00942     { _M_erase_at_end(begin()); }
00943 
00944    
00945   protected:
00946     // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
00947     iterator
00948     _M_copy_aligned(const_iterator __first, const_iterator __last,
00949             iterator __result)
00950     {
00951       _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
00952       return std::copy(const_iterator(__last._M_p, 0), __last,
00953                iterator(__q, 0));
00954     }
00955 
00956     void
00957     _M_initialize(size_type __n)
00958     {
00959       _Bit_type* __q = this->_M_allocate(__n);
00960       this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
00961       this->_M_impl._M_start = iterator(__q, 0);
00962       this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
00963     }
00964 
00965     void
00966     _M_reallocate(size_type __n);
00967 
00968 #if __cplusplus >= 201103L
00969     bool
00970     _M_shrink_to_fit();
00971 #endif
00972 
00973     // Check whether it's an integral type.  If so, it's not an iterator.
00974 
00975     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00976     // 438. Ambiguity in the "do the right thing" clause
00977     template<typename _Integer>
00978       void
00979       _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
00980       {
00981     _M_initialize(static_cast<size_type>(__n));
00982     std::fill(this->_M_impl._M_start._M_p, 
00983           this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00984       }
00985 
00986     template<typename _InputIterator>
00987       void 
00988       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
00989                  __false_type)
00990       { _M_initialize_range(__first, __last, 
00991                 std::__iterator_category(__first)); }
00992 
00993     template<typename _InputIterator>
00994       void
00995       _M_initialize_range(_InputIterator __first, _InputIterator __last,
00996               std::input_iterator_tag)
00997       {
00998     for (; __first != __last; ++__first)
00999       push_back(*__first);
01000       }
01001 
01002     template<typename _ForwardIterator>
01003       void
01004       _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
01005               std::forward_iterator_tag)
01006       {
01007     const size_type __n = std::distance(__first, __last);
01008     _M_initialize(__n);
01009     std::copy(__first, __last, this->_M_impl._M_start);
01010       }
01011 
01012     // _GLIBCXX_RESOLVE_LIB_DEFECTS
01013     // 438. Ambiguity in the "do the right thing" clause
01014     template<typename _Integer>
01015       void
01016       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01017       { _M_fill_assign(__n, __val); }
01018 
01019     template<class _InputIterator>
01020       void
01021       _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01022              __false_type)
01023       { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
01024 
01025     void
01026     _M_fill_assign(size_t __n, bool __x)
01027     {
01028       if (__n > size())
01029     {
01030       std::fill(this->_M_impl._M_start._M_p, 
01031             this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
01032       insert(end(), __n - size(), __x);
01033     }
01034       else
01035     {
01036       _M_erase_at_end(begin() + __n);
01037       std::fill(this->_M_impl._M_start._M_p, 
01038             this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
01039     }
01040     }
01041 
01042     template<typename _InputIterator>
01043       void
01044       _M_assign_aux(_InputIterator __first, _InputIterator __last,
01045             std::input_iterator_tag)
01046       {
01047     iterator __cur = begin();
01048     for (; __first != __last && __cur != end(); ++__cur, ++__first)
01049       *__cur = *__first;
01050     if (__first == __last)
01051       _M_erase_at_end(__cur);
01052     else
01053       insert(end(), __first, __last);
01054       }
01055     
01056     template<typename _ForwardIterator>
01057       void
01058       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
01059             std::forward_iterator_tag)
01060       {
01061     const size_type __len = std::distance(__first, __last);
01062     if (__len < size())
01063       _M_erase_at_end(std::copy(__first, __last, begin()));
01064     else
01065       {
01066         _ForwardIterator __mid = __first;
01067         std::advance(__mid, size());
01068         std::copy(__first, __mid, begin());
01069         insert(end(), __mid, __last);
01070       }
01071       }
01072 
01073     // Check whether it's an integral type.  If so, it's not an iterator.
01074 
01075     // _GLIBCXX_RESOLVE_LIB_DEFECTS
01076     // 438. Ambiguity in the "do the right thing" clause
01077     template<typename _Integer>
01078       void
01079       _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
01080              __true_type)
01081       { _M_fill_insert(__pos, __n, __x); }
01082 
01083     template<typename _InputIterator>
01084       void
01085       _M_insert_dispatch(iterator __pos,
01086              _InputIterator __first, _InputIterator __last,
01087              __false_type)
01088       { _M_insert_range(__pos, __first, __last,
01089             std::__iterator_category(__first)); }
01090 
01091     void
01092     _M_fill_insert(iterator __position, size_type __n, bool __x);
01093 
01094     template<typename _InputIterator>
01095       void
01096       _M_insert_range(iterator __pos, _InputIterator __first, 
01097               _InputIterator __last, std::input_iterator_tag)
01098       {
01099     for (; __first != __last; ++__first)
01100       {
01101         __pos = insert(__pos, *__first);
01102         ++__pos;
01103       }
01104       }
01105 
01106     template<typename _ForwardIterator>
01107       void
01108       _M_insert_range(iterator __position, _ForwardIterator __first, 
01109               _ForwardIterator __last, std::forward_iterator_tag);
01110 
01111     void
01112     _M_insert_aux(iterator __position, bool __x);
01113 
01114     size_type
01115     _M_check_len(size_type __n, const char* __s) const
01116     {
01117       if (max_size() - size() < __n)
01118     __throw_length_error(__N(__s));
01119 
01120       const size_type __len = size() + std::max(size(), __n);
01121       return (__len < size() || __len > max_size()) ? max_size() : __len;
01122     }
01123 
01124     void
01125     _M_erase_at_end(iterator __pos)
01126     { this->_M_impl._M_finish = __pos; }
01127   };
01128 
01129 _GLIBCXX_END_NAMESPACE_CONTAINER
01130 } // namespace std
01131 
01132 #if __cplusplus >= 201103L
01133 
01134 #include <bits/functional_hash.h>
01135 
01136 namespace std _GLIBCXX_VISIBILITY(default)
01137 {
01138 _GLIBCXX_BEGIN_NAMESPACE_VERSION
01139 
01140   // DR 1182.
01141   /// std::hash specialization for vector<bool>.
01142   template<typename _Alloc>
01143     struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
01144     : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
01145     {
01146       size_t
01147       operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
01148     };
01149 
01150 _GLIBCXX_END_NAMESPACE_VERSION
01151 }// namespace std
01152 
01153 #endif // C++11
01154 
01155 #endif