libstdc++
stl_bvector.h
Go to the documentation of this file.
00001 // vector<bool> specialization -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
00004 // 2011 Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /*
00027  *
00028  * Copyright (c) 1994
00029  * Hewlett-Packard Company
00030  *
00031  * Permission to use, copy, modify, distribute and sell this software
00032  * and its documentation for any purpose is hereby granted without fee,
00033  * provided that the above copyright notice appear in all copies and
00034  * that both that copyright notice and this permission notice appear
00035  * in supporting documentation.  Hewlett-Packard Company makes no
00036  * representations about the suitability of this software for any
00037  * purpose.  It is provided "as is" without express or implied warranty.
00038  *
00039  *
00040  * Copyright (c) 1996-1999
00041  * Silicon Graphics Computer Systems, Inc.
00042  *
00043  * Permission to use, copy, modify, distribute and sell this software
00044  * and its documentation for any purpose is hereby granted without fee,
00045  * provided that the above copyright notice appear in all copies and
00046  * that both that copyright notice and this permission notice appear
00047  * in supporting documentation.  Silicon Graphics makes no
00048  * representations about the suitability of this software for any
00049  * purpose.  It is provided "as is" without express or implied warranty.
00050  */
00051 
00052 /** @file bits/stl_bvector.h
00053  *  This is an internal header file, included by other library headers.
00054  *  Do not attempt to use it directly. @headername{vector}
00055  */
00056 
00057 #ifndef _STL_BVECTOR_H
00058 #define _STL_BVECTOR_H 1
00059 
00060 #include <initializer_list>
00061 
00062 namespace std _GLIBCXX_VISIBILITY(default)
00063 {
00064 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00065 
00066   typedef unsigned long _Bit_type;
00067   enum { _S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type)) };
00068 
00069   struct _Bit_reference
00070   {
00071     _Bit_type * _M_p;
00072     _Bit_type _M_mask;
00073 
00074     _Bit_reference(_Bit_type * __x, _Bit_type __y)
00075     : _M_p(__x), _M_mask(__y) { }
00076 
00077     _Bit_reference() : _M_p(0), _M_mask(0) { }
00078 
00079     operator bool() const
00080     { return !!(*_M_p & _M_mask); }
00081 
00082     _Bit_reference&
00083     operator=(bool __x)
00084     {
00085       if (__x)
00086     *_M_p |= _M_mask;
00087       else
00088     *_M_p &= ~_M_mask;
00089       return *this;
00090     }
00091 
00092     _Bit_reference&
00093     operator=(const _Bit_reference& __x)
00094     { return *this = bool(__x); }
00095 
00096     bool
00097     operator==(const _Bit_reference& __x) const
00098     { return bool(*this) == bool(__x); }
00099 
00100     bool
00101     operator<(const _Bit_reference& __x) const
00102     { return !bool(*this) && bool(__x); }
00103 
00104     void
00105     flip()
00106     { *_M_p ^= _M_mask; }
00107   };
00108 
00109   struct _Bit_iterator_base
00110   : public std::iterator<std::random_access_iterator_tag, bool>
00111   {
00112     _Bit_type * _M_p;
00113     unsigned int _M_offset;
00114 
00115     _Bit_iterator_base(_Bit_type * __x, unsigned int __y)
00116     : _M_p(__x), _M_offset(__y) { }
00117 
00118     void
00119     _M_bump_up()
00120     {
00121       if (_M_offset++ == int(_S_word_bit) - 1)
00122     {
00123       _M_offset = 0;
00124       ++_M_p;
00125     }
00126     }
00127 
00128     void
00129     _M_bump_down()
00130     {
00131       if (_M_offset-- == 0)
00132     {
00133       _M_offset = int(_S_word_bit) - 1;
00134       --_M_p;
00135     }
00136     }
00137 
00138     void
00139     _M_incr(ptrdiff_t __i)
00140     {
00141       difference_type __n = __i + _M_offset;
00142       _M_p += __n / int(_S_word_bit);
00143       __n = __n % int(_S_word_bit);
00144       if (__n < 0)
00145     {
00146       __n += int(_S_word_bit);
00147       --_M_p;
00148     }
00149       _M_offset = static_cast<unsigned int>(__n);
00150     }
00151 
00152     bool
00153     operator==(const _Bit_iterator_base& __i) const
00154     { return _M_p == __i._M_p && _M_offset == __i._M_offset; }
00155 
00156     bool
00157     operator<(const _Bit_iterator_base& __i) const
00158     {
00159       return _M_p < __i._M_p
00160          || (_M_p == __i._M_p && _M_offset < __i._M_offset);
00161     }
00162 
00163     bool
00164     operator!=(const _Bit_iterator_base& __i) const
00165     { return !(*this == __i); }
00166 
00167     bool
00168     operator>(const _Bit_iterator_base& __i) const
00169     { return __i < *this; }
00170 
00171     bool
00172     operator<=(const _Bit_iterator_base& __i) const
00173     { return !(__i < *this); }
00174 
00175     bool
00176     operator>=(const _Bit_iterator_base& __i) const
00177     { return !(*this < __i); }
00178   };
00179 
00180   inline ptrdiff_t
00181   operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
00182   {
00183     return (int(_S_word_bit) * (__x._M_p - __y._M_p)
00184         + __x._M_offset - __y._M_offset);
00185   }
00186 
00187   struct _Bit_iterator : public _Bit_iterator_base
00188   {
00189     typedef _Bit_reference  reference;
00190     typedef _Bit_reference* pointer;
00191     typedef _Bit_iterator   iterator;
00192 
00193     _Bit_iterator() : _Bit_iterator_base(0, 0) { }
00194 
00195     _Bit_iterator(_Bit_type * __x, unsigned int __y)
00196     : _Bit_iterator_base(__x, __y) { }
00197 
00198     reference
00199     operator*() const
00200     { return reference(_M_p, 1UL << _M_offset); }
00201 
00202     iterator&
00203     operator++()
00204     {
00205       _M_bump_up();
00206       return *this;
00207     }
00208 
00209     iterator
00210     operator++(int)
00211     {
00212       iterator __tmp = *this;
00213       _M_bump_up();
00214       return __tmp;
00215     }
00216 
00217     iterator&
00218     operator--()
00219     {
00220       _M_bump_down();
00221       return *this;
00222     }
00223 
00224     iterator
00225     operator--(int)
00226     {
00227       iterator __tmp = *this;
00228       _M_bump_down();
00229       return __tmp;
00230     }
00231 
00232     iterator&
00233     operator+=(difference_type __i)
00234     {
00235       _M_incr(__i);
00236       return *this;
00237     }
00238 
00239     iterator&
00240     operator-=(difference_type __i)
00241     {
00242       *this += -__i;
00243       return *this;
00244     }
00245 
00246     iterator
00247     operator+(difference_type __i) const
00248     {
00249       iterator __tmp = *this;
00250       return __tmp += __i;
00251     }
00252 
00253     iterator
00254     operator-(difference_type __i) const
00255     {
00256       iterator __tmp = *this;
00257       return __tmp -= __i;
00258     }
00259 
00260     reference
00261     operator[](difference_type __i) const
00262     { return *(*this + __i); }
00263   };
00264 
00265   inline _Bit_iterator
00266   operator+(ptrdiff_t __n, const _Bit_iterator& __x)
00267   { return __x + __n; }
00268 
00269   struct _Bit_const_iterator : public _Bit_iterator_base
00270   {
00271     typedef bool                 reference;
00272     typedef bool                 const_reference;
00273     typedef const bool*          pointer;
00274     typedef _Bit_const_iterator  const_iterator;
00275 
00276     _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
00277 
00278     _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
00279     : _Bit_iterator_base(__x, __y) { }
00280 
00281     _Bit_const_iterator(const _Bit_iterator& __x)
00282     : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
00283 
00284     const_reference
00285     operator*() const
00286     { return _Bit_reference(_M_p, 1UL << _M_offset); }
00287 
00288     const_iterator&
00289     operator++()
00290     {
00291       _M_bump_up();
00292       return *this;
00293     }
00294 
00295     const_iterator
00296     operator++(int)
00297     {
00298       const_iterator __tmp = *this;
00299       _M_bump_up();
00300       return __tmp;
00301     }
00302 
00303     const_iterator&
00304     operator--()
00305     {
00306       _M_bump_down();
00307       return *this;
00308     }
00309 
00310     const_iterator
00311     operator--(int)
00312     {
00313       const_iterator __tmp = *this;
00314       _M_bump_down();
00315       return __tmp;
00316     }
00317 
00318     const_iterator&
00319     operator+=(difference_type __i)
00320     {
00321       _M_incr(__i);
00322       return *this;
00323     }
00324 
00325     const_iterator&
00326     operator-=(difference_type __i)
00327     {
00328       *this += -__i;
00329       return *this;
00330     }
00331 
00332     const_iterator 
00333     operator+(difference_type __i) const
00334     {
00335       const_iterator __tmp = *this;
00336       return __tmp += __i;
00337     }
00338 
00339     const_iterator
00340     operator-(difference_type __i) const
00341     {
00342       const_iterator __tmp = *this;
00343       return __tmp -= __i;
00344     }
00345 
00346     const_reference
00347     operator[](difference_type __i) const
00348     { return *(*this + __i); }
00349   };
00350 
00351   inline _Bit_const_iterator
00352   operator+(ptrdiff_t __n, const _Bit_const_iterator& __x)
00353   { return __x + __n; }
00354 
00355   inline void
00356   __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x)
00357   {
00358     for (; __first != __last; ++__first)
00359       *__first = __x;
00360   }
00361 
00362   inline void
00363   fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x)
00364   {
00365     if (__first._M_p != __last._M_p)
00366       {
00367     std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0);
00368     __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x);
00369     __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x);
00370       }
00371     else
00372       __fill_bvector(__first, __last, __x);
00373   }
00374 
00375   template<typename _Alloc>
00376     struct _Bvector_base
00377     {
00378       typedef typename _Alloc::template rebind<_Bit_type>::other
00379         _Bit_alloc_type;
00380       
00381       struct _Bvector_impl
00382       : public _Bit_alloc_type
00383       {
00384     _Bit_iterator   _M_start;
00385     _Bit_iterator   _M_finish;
00386     _Bit_type*  _M_end_of_storage;
00387 
00388     _Bvector_impl()
00389     : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage(0)
00390     { }
00391  
00392     _Bvector_impl(const _Bit_alloc_type& __a)
00393     : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
00394     { }
00395       };
00396 
00397     public:
00398       typedef _Alloc allocator_type;
00399 
00400       _Bit_alloc_type&
00401       _M_get_Bit_allocator()
00402       { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); }
00403 
00404       const _Bit_alloc_type&
00405       _M_get_Bit_allocator() const
00406       { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
00407 
00408       allocator_type
00409       get_allocator() const
00410       { return allocator_type(_M_get_Bit_allocator()); }
00411 
00412       _Bvector_base()
00413       : _M_impl() { }
00414       
00415       _Bvector_base(const allocator_type& __a)
00416       : _M_impl(__a) { }
00417 
00418 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00419       _Bvector_base(_Bvector_base&& __x)
00420       : _M_impl(__x._M_get_Bit_allocator())
00421       {
00422     this->_M_impl._M_start = __x._M_impl._M_start;
00423     this->_M_impl._M_finish = __x._M_impl._M_finish;
00424     this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
00425     __x._M_impl._M_start = _Bit_iterator();
00426     __x._M_impl._M_finish = _Bit_iterator();
00427     __x._M_impl._M_end_of_storage = 0;
00428       }
00429 #endif
00430 
00431       ~_Bvector_base()
00432       { this->_M_deallocate(); }
00433 
00434     protected:
00435       _Bvector_impl _M_impl;
00436 
00437       _Bit_type*
00438       _M_allocate(size_t __n)
00439       { return _M_impl.allocate((__n + int(_S_word_bit) - 1)
00440                 / int(_S_word_bit)); }
00441 
00442       void
00443       _M_deallocate()
00444       {
00445     if (_M_impl._M_start._M_p)
00446       _M_impl.deallocate(_M_impl._M_start._M_p,
00447                  _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
00448       }
00449     };
00450 
00451 _GLIBCXX_END_NAMESPACE_CONTAINER
00452 } // namespace std
00453 
00454 // Declare a partial specialization of vector<T, Alloc>.
00455 #include <bits/stl_vector.h>
00456 
00457 namespace std _GLIBCXX_VISIBILITY(default)
00458 {
00459 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00460 
00461   /**
00462    *  @brief  A specialization of vector for booleans which offers fixed time
00463    *  access to individual elements in any order.
00464    *
00465    *  Note that vector<bool> does not actually meet the requirements for being
00466    *  a container.  This is because the reference and pointer types are not
00467    *  really references and pointers to bool.  See DR96 for details.  @see
00468    *  vector for function documentation.
00469    *
00470    *  @ingroup sequences
00471    *
00472    *  In some terminology a %vector can be described as a dynamic
00473    *  C-style array, it offers fast and efficient access to individual
00474    *  elements in any order and saves the user from worrying about
00475    *  memory and size allocation.  Subscripting ( @c [] ) access is
00476    *  also provided as with C-style arrays.
00477   */
00478 template<typename _Alloc>
00479   class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
00480   {
00481     typedef _Bvector_base<_Alloc>            _Base;
00482 
00483 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00484     template<typename> friend class hash;
00485 #endif
00486 
00487   public:
00488     typedef bool                                         value_type;
00489     typedef size_t                                       size_type;
00490     typedef ptrdiff_t                                    difference_type;
00491     typedef _Bit_reference                               reference;
00492     typedef bool                                         const_reference;
00493     typedef _Bit_reference*                              pointer;
00494     typedef const bool*                                  const_pointer;
00495     typedef _Bit_iterator                                iterator;
00496     typedef _Bit_const_iterator                          const_iterator;
00497     typedef std::reverse_iterator<const_iterator>        const_reverse_iterator;
00498     typedef std::reverse_iterator<iterator>              reverse_iterator;
00499     typedef _Alloc                               allocator_type;
00500 
00501     allocator_type get_allocator() const
00502     { return _Base::get_allocator(); }
00503 
00504   protected:
00505     using _Base::_M_allocate;
00506     using _Base::_M_deallocate;
00507     using _Base::_M_get_Bit_allocator;
00508 
00509   public:
00510     vector()
00511     : _Base() { }
00512 
00513     explicit
00514     vector(const allocator_type& __a)
00515     : _Base(__a) { }
00516 
00517     explicit
00518     vector(size_type __n, const bool& __value = bool(), 
00519        const allocator_type& __a = allocator_type())
00520     : _Base(__a)
00521     {
00522       _M_initialize(__n);
00523       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, 
00524         __value ? ~0 : 0);
00525     }
00526 
00527     vector(const vector& __x)
00528     : _Base(__x._M_get_Bit_allocator())
00529     {
00530       _M_initialize(__x.size());
00531       _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start);
00532     }
00533 
00534 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00535     vector(vector&& __x)
00536     : _Base(std::move(__x)) { }
00537 
00538     vector(initializer_list<bool> __l,
00539        const allocator_type& __a = allocator_type())
00540     : _Base(__a)
00541     {
00542       _M_initialize_range(__l.begin(), __l.end(),
00543               random_access_iterator_tag());
00544     }
00545 #endif
00546 
00547     template<typename _InputIterator>
00548       vector(_InputIterator __first, _InputIterator __last,
00549          const allocator_type& __a = allocator_type())
00550       : _Base(__a)
00551       {
00552     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00553     _M_initialize_dispatch(__first, __last, _Integral());
00554       }
00555 
00556     ~vector() { }
00557 
00558     vector&
00559     operator=(const vector& __x)
00560     {
00561       if (&__x == this)
00562     return *this;
00563       if (__x.size() > capacity())
00564     {
00565       this->_M_deallocate();
00566       _M_initialize(__x.size());
00567     }
00568       this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
00569                         begin());
00570       return *this;
00571     }
00572 
00573 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00574     vector&
00575     operator=(vector&& __x)
00576     {
00577       // NB: DR 1204.
00578       // NB: DR 675.
00579       this->clear();
00580       this->swap(__x); 
00581       return *this;
00582     }
00583 
00584     vector&
00585     operator=(initializer_list<bool> __l)
00586     {
00587       this->assign (__l.begin(), __l.end());
00588       return *this;
00589     }
00590 #endif
00591 
00592     // assign(), a generalized assignment member function.  Two
00593     // versions: one that takes a count, and one that takes a range.
00594     // The range version is a member template, so we dispatch on whether
00595     // or not the type is an integer.
00596     void
00597     assign(size_type __n, const bool& __x)
00598     { _M_fill_assign(__n, __x); }
00599 
00600     template<typename _InputIterator>
00601       void
00602       assign(_InputIterator __first, _InputIterator __last)
00603       {
00604     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00605     _M_assign_dispatch(__first, __last, _Integral());
00606       }
00607 
00608 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00609     void
00610     assign(initializer_list<bool> __l)
00611     { this->assign(__l.begin(), __l.end()); }
00612 #endif
00613 
00614     iterator
00615     begin()
00616     { return this->_M_impl._M_start; }
00617 
00618     const_iterator
00619     begin() const
00620     { return this->_M_impl._M_start; }
00621 
00622     iterator
00623     end()
00624     { return this->_M_impl._M_finish; }
00625 
00626     const_iterator
00627     end() const
00628     { return this->_M_impl._M_finish; }
00629 
00630     reverse_iterator
00631     rbegin()
00632     { return reverse_iterator(end()); }
00633 
00634     const_reverse_iterator
00635     rbegin() const
00636     { return const_reverse_iterator(end()); }
00637 
00638     reverse_iterator
00639     rend()
00640     { return reverse_iterator(begin()); }
00641 
00642     const_reverse_iterator
00643     rend() const
00644     { return const_reverse_iterator(begin()); }
00645 
00646 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00647     const_iterator
00648     cbegin() const
00649     { return this->_M_impl._M_start; }
00650 
00651     const_iterator
00652     cend() const
00653     { return this->_M_impl._M_finish; }
00654 
00655     const_reverse_iterator
00656     crbegin() const
00657     { return const_reverse_iterator(end()); }
00658 
00659     const_reverse_iterator
00660     crend() const
00661     { return const_reverse_iterator(begin()); }
00662 #endif
00663 
00664     size_type
00665     size() const
00666     { return size_type(end() - begin()); }
00667 
00668     size_type
00669     max_size() const
00670     {
00671       const size_type __isize =
00672     __gnu_cxx::__numeric_traits<difference_type>::__max
00673     - int(_S_word_bit) + 1;
00674       const size_type __asize = _M_get_Bit_allocator().max_size();
00675       return (__asize <= __isize / int(_S_word_bit)
00676           ? __asize * int(_S_word_bit) : __isize);
00677     }
00678 
00679     size_type
00680     capacity() const
00681     { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
00682                - begin()); }
00683 
00684     bool
00685     empty() const
00686     { return begin() == end(); }
00687 
00688     reference
00689     operator[](size_type __n)
00690     {
00691       return *iterator(this->_M_impl._M_start._M_p
00692                + __n / int(_S_word_bit), __n % int(_S_word_bit));
00693     }
00694 
00695     const_reference
00696     operator[](size_type __n) const
00697     {
00698       return *const_iterator(this->_M_impl._M_start._M_p
00699                  + __n / int(_S_word_bit), __n % int(_S_word_bit));
00700     }
00701 
00702   protected:
00703     void
00704     _M_range_check(size_type __n) const
00705     {
00706       if (__n >= this->size())
00707         __throw_out_of_range(__N("vector<bool>::_M_range_check"));
00708     }
00709 
00710   public:
00711     reference
00712     at(size_type __n)
00713     { _M_range_check(__n); return (*this)[__n]; }
00714 
00715     const_reference
00716     at(size_type __n) const
00717     { _M_range_check(__n); return (*this)[__n]; }
00718 
00719     void
00720     reserve(size_type __n);
00721 
00722     reference
00723     front()
00724     { return *begin(); }
00725 
00726     const_reference
00727     front() const
00728     { return *begin(); }
00729 
00730     reference
00731     back()
00732     { return *(end() - 1); }
00733 
00734     const_reference
00735     back() const
00736     { return *(end() - 1); }
00737 
00738     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00739     // DR 464. Suggestion for new member functions in standard containers.
00740     // N.B. DR 464 says nothing about vector<bool> but we need something
00741     // here due to the way we are implementing DR 464 in the debug-mode
00742     // vector class.
00743     void
00744     data() { }
00745 
00746     void
00747     push_back(bool __x)
00748     {
00749       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
00750         *this->_M_impl._M_finish++ = __x;
00751       else
00752         _M_insert_aux(end(), __x);
00753     }
00754 
00755     void
00756     swap(vector& __x)
00757     {
00758       std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
00759       std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
00760       std::swap(this->_M_impl._M_end_of_storage, 
00761         __x._M_impl._M_end_of_storage);
00762 
00763       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00764       // 431. Swapping containers with unequal allocators.
00765       std::__alloc_swap<typename _Base::_Bit_alloc_type>::
00766     _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator());
00767     }
00768 
00769     // [23.2.5]/1, third-to-last entry in synopsis listing
00770     static void
00771     swap(reference __x, reference __y)
00772     {
00773       bool __tmp = __x;
00774       __x = __y;
00775       __y = __tmp;
00776     }
00777 
00778     iterator
00779     insert(iterator __position, const bool& __x = bool())
00780     {
00781       const difference_type __n = __position - begin();
00782       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
00783       && __position == end())
00784         *this->_M_impl._M_finish++ = __x;
00785       else
00786         _M_insert_aux(__position, __x);
00787       return begin() + __n;
00788     }
00789 
00790     template<typename _InputIterator>
00791       void
00792       insert(iterator __position,
00793          _InputIterator __first, _InputIterator __last)
00794       {
00795     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00796     _M_insert_dispatch(__position, __first, __last, _Integral());
00797       }
00798 
00799     void
00800     insert(iterator __position, size_type __n, const bool& __x)
00801     { _M_fill_insert(__position, __n, __x); }
00802 
00803 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00804     void insert(iterator __p, initializer_list<bool> __l)
00805     { this->insert(__p, __l.begin(), __l.end()); }
00806 #endif
00807 
00808     void
00809     pop_back()
00810     { --this->_M_impl._M_finish; }
00811 
00812     iterator
00813     erase(iterator __position)
00814     {
00815       if (__position + 1 != end())
00816         std::copy(__position + 1, end(), __position);
00817       --this->_M_impl._M_finish;
00818       return __position;
00819     }
00820 
00821     iterator
00822     erase(iterator __first, iterator __last)
00823     {
00824       if (__first != __last)
00825     _M_erase_at_end(std::copy(__last, end(), __first));
00826       return __first;
00827     }
00828 
00829     void
00830     resize(size_type __new_size, bool __x = bool())
00831     {
00832       if (__new_size < size())
00833         _M_erase_at_end(begin() + difference_type(__new_size));
00834       else
00835         insert(end(), __new_size - size(), __x);
00836     }
00837 
00838 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00839     void
00840     shrink_to_fit()
00841     { std::__shrink_to_fit<vector>::_S_do_it(*this); }
00842 #endif
00843 
00844     void
00845     flip()
00846     {
00847       for (_Bit_type * __p = this->_M_impl._M_start._M_p;
00848        __p != this->_M_impl._M_end_of_storage; ++__p)
00849         *__p = ~*__p;
00850     }
00851 
00852     void
00853     clear()
00854     { _M_erase_at_end(begin()); }
00855 
00856    
00857   protected:
00858     // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
00859     iterator
00860     _M_copy_aligned(const_iterator __first, const_iterator __last,
00861             iterator __result)
00862     {
00863       _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
00864       return std::copy(const_iterator(__last._M_p, 0), __last,
00865                iterator(__q, 0));
00866     }
00867 
00868     void
00869     _M_initialize(size_type __n)
00870     {
00871       _Bit_type* __q = this->_M_allocate(__n);
00872       this->_M_impl._M_end_of_storage = (__q
00873                      + ((__n + int(_S_word_bit) - 1)
00874                         / int(_S_word_bit)));
00875       this->_M_impl._M_start = iterator(__q, 0);
00876       this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
00877     }
00878 
00879     // Check whether it's an integral type.  If so, it's not an iterator.
00880 
00881     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00882     // 438. Ambiguity in the "do the right thing" clause
00883     template<typename _Integer>
00884       void
00885       _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
00886       {
00887     _M_initialize(static_cast<size_type>(__n));
00888     std::fill(this->_M_impl._M_start._M_p, 
00889           this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00890       }
00891 
00892     template<typename _InputIterator>
00893       void 
00894       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
00895                  __false_type)
00896       { _M_initialize_range(__first, __last, 
00897                 std::__iterator_category(__first)); }
00898 
00899     template<typename _InputIterator>
00900       void
00901       _M_initialize_range(_InputIterator __first, _InputIterator __last,
00902               std::input_iterator_tag)
00903       {
00904     for (; __first != __last; ++__first)
00905       push_back(*__first);
00906       }
00907 
00908     template<typename _ForwardIterator>
00909       void
00910       _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
00911               std::forward_iterator_tag)
00912       {
00913     const size_type __n = std::distance(__first, __last);
00914     _M_initialize(__n);
00915     std::copy(__first, __last, this->_M_impl._M_start);
00916       }
00917 
00918     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00919     // 438. Ambiguity in the "do the right thing" clause
00920     template<typename _Integer>
00921       void
00922       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00923       { _M_fill_assign(__n, __val); }
00924 
00925     template<class _InputIterator>
00926       void
00927       _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
00928              __false_type)
00929       { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
00930 
00931     void
00932     _M_fill_assign(size_t __n, bool __x)
00933     {
00934       if (__n > size())
00935     {
00936       std::fill(this->_M_impl._M_start._M_p, 
00937             this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00938       insert(end(), __n - size(), __x);
00939     }
00940       else
00941     {
00942       _M_erase_at_end(begin() + __n);
00943       std::fill(this->_M_impl._M_start._M_p, 
00944             this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00945     }
00946     }
00947 
00948     template<typename _InputIterator>
00949       void
00950       _M_assign_aux(_InputIterator __first, _InputIterator __last,
00951             std::input_iterator_tag)
00952       {
00953     iterator __cur = begin();
00954     for (; __first != __last && __cur != end(); ++__cur, ++__first)
00955       *__cur = *__first;
00956     if (__first == __last)
00957       _M_erase_at_end(__cur);
00958     else
00959       insert(end(), __first, __last);
00960       }
00961     
00962     template<typename _ForwardIterator>
00963       void
00964       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00965             std::forward_iterator_tag)
00966       {
00967     const size_type __len = std::distance(__first, __last);
00968     if (__len < size())
00969       _M_erase_at_end(std::copy(__first, __last, begin()));
00970     else
00971       {
00972         _ForwardIterator __mid = __first;
00973         std::advance(__mid, size());
00974         std::copy(__first, __mid, begin());
00975         insert(end(), __mid, __last);
00976       }
00977       }
00978 
00979     // Check whether it's an integral type.  If so, it's not an iterator.
00980 
00981     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00982     // 438. Ambiguity in the "do the right thing" clause
00983     template<typename _Integer>
00984       void
00985       _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
00986              __true_type)
00987       { _M_fill_insert(__pos, __n, __x); }
00988 
00989     template<typename _InputIterator>
00990       void
00991       _M_insert_dispatch(iterator __pos,
00992              _InputIterator __first, _InputIterator __last,
00993              __false_type)
00994       { _M_insert_range(__pos, __first, __last,
00995             std::__iterator_category(__first)); }
00996 
00997     void
00998     _M_fill_insert(iterator __position, size_type __n, bool __x);
00999 
01000     template<typename _InputIterator>
01001       void
01002       _M_insert_range(iterator __pos, _InputIterator __first, 
01003               _InputIterator __last, std::input_iterator_tag)
01004       {
01005     for (; __first != __last; ++__first)
01006       {
01007         __pos = insert(__pos, *__first);
01008         ++__pos;
01009       }
01010       }
01011 
01012     template<typename _ForwardIterator>
01013       void
01014       _M_insert_range(iterator __position, _ForwardIterator __first, 
01015               _ForwardIterator __last, std::forward_iterator_tag);
01016 
01017     void
01018     _M_insert_aux(iterator __position, bool __x);
01019 
01020     size_type
01021     _M_check_len(size_type __n, const char* __s) const
01022     {
01023       if (max_size() - size() < __n)
01024     __throw_length_error(__N(__s));
01025 
01026       const size_type __len = size() + std::max(size(), __n);
01027       return (__len < size() || __len > max_size()) ? max_size() : __len;
01028     }
01029 
01030     void
01031     _M_erase_at_end(iterator __pos)
01032     { this->_M_impl._M_finish = __pos; }
01033   };
01034 
01035 _GLIBCXX_END_NAMESPACE_CONTAINER
01036 } // namespace std
01037 
01038 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01039 
01040 #include <bits/functional_hash.h>
01041 
01042 namespace std _GLIBCXX_VISIBILITY(default)
01043 {
01044 _GLIBCXX_BEGIN_NAMESPACE_VERSION
01045 
01046   // DR 1182.
01047   /// std::hash specialization for vector<bool>.
01048   template<typename _Alloc>
01049     struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
01050     : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
01051     {
01052       size_t
01053       operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const;
01054     };
01055 
01056 _GLIBCXX_END_NAMESPACE_VERSION
01057 }// namespace std
01058 
01059 #endif // __GXX_EXPERIMENTAL_CXX0X__
01060 
01061 #endif