# stl_bvector.h

Go to the documentation of this file.

    00001 // vector<bool> specialization -*- C++ -*-
    00002
    00003 // Copyright (C) 2001, 2002, 2003, 2004 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 2, 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 // You should have received a copy of the GNU General Public License along
    00017 // with this library; see the file COPYING.  If not, write to the Free
    00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
    00019 // USA.
    00020
    00021 // As a special exception, you may use this file as part of a free software
    00022 // library without restriction.  Specifically, if other files instantiate
    00023 // templates or use macros or inline functions from this file, or you compile
    00024 // this file and link it with other files to produce an executable, this
    00025 // file does not by itself cause the resulting executable to be covered by
    00026 // the GNU General Public License.  This exception does not however
    00027 // invalidate any other reasons why the executable file might be covered by
    00028 // the GNU General Public License.
    00029
    00030 /*
    00031  *
    00032  * Copyright (c) 1994
    00033  * Hewlett-Packard Company
    00034  *
    00035  * Permission to use, copy, modify, distribute and sell this software
    00036  * and its documentation for any purpose is hereby granted without fee,
    00037  * provided that the above copyright notice appear in all copies and
    00038  * that both that copyright notice and this permission notice appear
    00039  * in supporting documentation.  Hewlett-Packard Company makes no
    00040  * representations about the suitability of this software for any
    00041  * purpose.  It is provided "as is" without express or implied warranty.
    00042  *
    00043  *
    00044  * Copyright (c) 1996-1999
    00045  * Silicon Graphics Computer Systems, Inc.
    00046  *
    00047  * Permission to use, copy, modify, distribute and sell this software
    00048  * and its documentation for any purpose is hereby granted without fee,
    00049  * provided that the above copyright notice appear in all copies and
    00050  * that both that copyright notice and this permission notice appear
    00051  * in supporting documentation.  Silicon Graphics makes no
    00052  * representations about the suitability of this software for any
    00053  * purpose.  It is provided "as is" without express or implied warranty.
    00054  */
    00055
    00056 /** @file stl_bvector.h
    00057  *  This is an internal header file, included by other library headers.
    00058  *  You should not attempt to use it directly.
    00059  */
    00060
    00061 #ifndef _BVECTOR_H
    00062 #define _BVECTOR_H 1
    00063
    00064 namespace _GLIBCXX_STD
    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 { return !!(*_M_p & _M_mask); }
    00080
    00081     _Bit_reference&
    00082     operator=(bool __x)
    00083     {
    00084       if (__x)
    00085     *_M_p |= _M_mask;
    00086       else
    00087     *_M_p &= ~_M_mask;
    00088       return *this;
    00089     }
    00090
    00091     _Bit_reference&
    00092     operator=(const _Bit_reference& __x)
    00093     { return *this = bool(__x); }
    00094
    00095     bool
    00096     operator==(const _Bit_reference& __x) const
    00097     { return bool(*this) == bool(__x); }
    00098
    00099     bool
    00100     operator<(const _Bit_reference& __x) const
    00101     { return !bool(*this) && bool(__x); }
    00102
    00103     void
    00104     flip() { *_M_p ^= _M_mask; }
    00105   };
    00106
    00107   struct _Bit_iterator_base : public iterator<random_access_iterator_tag, bool>
    00108   {
    00109     _Bit_type * _M_p;
    00110     unsigned int _M_offset;
    00111
    00112     _Bit_iterator_base(_Bit_type * __x, unsigned int __y)
    00113     : _M_p(__x), _M_offset(__y) { }
    00114
    00115     void
    00116     _M_bump_up()
    00117     {
    00118       if (_M_offset++ == _S_word_bit - 1)
    00119     {
    00120       _M_offset = 0;
    00121       ++_M_p;
    00122     }
    00123     }
    00124
    00125     void
    00126     _M_bump_down()
    00127     {
    00128       if (_M_offset-- == 0)
    00129     {
    00130       _M_offset = _S_word_bit - 1;
    00131       --_M_p;
    00132     }
    00133     }
    00134
    00135     void
    00136     _M_incr(ptrdiff_t __i)
    00137     {
    00138       difference_type __n = __i + _M_offset;
    00139       _M_p += __n / _S_word_bit;
    00140       __n = __n % _S_word_bit;
    00141       if (__n < 0)
    00142     {
    00143       _M_offset = static_cast<unsigned int>(__n + _S_word_bit);
    00144       --_M_p;
    00145     }
    00146       else
    00147     _M_offset = static_cast<unsigned int>(__n);
    00148     }
    00149
    00150     bool
    00151     operator==(const _Bit_iterator_base& __i) const
    00152     { return _M_p == __i._M_p && _M_offset == __i._M_offset; }
    00153
    00154     bool
    00155     operator<(const _Bit_iterator_base& __i) const
    00156     {
    00157       return _M_p < __i._M_p
    00158          || (_M_p == __i._M_p && _M_offset < __i._M_offset);
    00159     }
    00160
    00161     bool
    00162     operator!=(const _Bit_iterator_base& __i) const
    00163     { return !(*this == __i); }
    00164
    00165     bool
    00166     operator>(const _Bit_iterator_base& __i) const
    00167     { return __i < *this; }
    00168
    00169     bool
    00170     operator<=(const _Bit_iterator_base& __i) const
    00171     { return !(__i < *this); }
    00172
    00173     bool
    00174     operator>=(const _Bit_iterator_base& __i) const
    00175     { return !(*this < __i); }
    00176   };
    00177
    00178   inline ptrdiff_t
    00179   operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
    00180   {
    00181     return _S_word_bit * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset;
    00182   }
    00183
    00184   struct _Bit_iterator : public _Bit_iterator_base
    00185   {
    00186     typedef _Bit_reference  reference;
    00187     typedef _Bit_reference* pointer;
    00188     typedef _Bit_iterator   iterator;
    00189
    00190     _Bit_iterator() : _Bit_iterator_base(0, 0) { }
    00191     _Bit_iterator(_Bit_type * __x, unsigned int __y)
    00192     : _Bit_iterator_base(__x, __y) { }
    00193
    00194     reference
    00195     operator*() const { return reference(_M_p, 1UL << _M_offset); }
    00196
    00197     iterator&
    00198     operator++()
    00199     {
    00200       _M_bump_up();
    00201       return *this;
    00202     }
    00203
    00204     iterator
    00205     operator++(int)
    00206     {
    00207       iterator __tmp = *this;
    00208       _M_bump_up();
    00209       return __tmp;
    00210     }
    00211
    00212     iterator&
    00213     operator--()
    00214     {
    00215       _M_bump_down();
    00216       return *this;
    00217     }
    00218
    00219     iterator
    00220     operator--(int)
    00221     {
    00222       iterator __tmp = *this;
    00223       _M_bump_down();
    00224       return __tmp;
    00225     }
    00226
    00227     iterator&
    00228     operator+=(difference_type __i)
    00229     {
    00230       _M_incr(__i);
    00231       return *this;
    00232     }
    00233
    00234     iterator&
    00235     operator-=(difference_type __i)
    00236     {
    00237       *this += -__i;
    00238       return *this;
    00239     }
    00240
    00241     iterator
    00242     operator+(difference_type __i) const
    00243     {
    00244       iterator __tmp = *this;
    00245       return __tmp += __i;
    00246     }
    00247
    00248     iterator
    00249     operator-(difference_type __i) const
    00250     {
    00251       iterator __tmp = *this;
    00252       return __tmp -= __i;
    00253     }
    00254
    00255     reference
    00256     operator[](difference_type __i)
    00257     { return *(*this + __i); }
    00258   };
    00259
    00260   inline _Bit_iterator
    00261   operator+(ptrdiff_t __n, const _Bit_iterator& __x) { return __x + __n; }
    00262
    00263
    00264   struct _Bit_const_iterator : public _Bit_iterator_base
    00265   {
    00266     typedef bool                 reference;
    00267     typedef bool                 const_reference;
    00268     typedef const bool*          pointer;
    00269     typedef _Bit_const_iterator  const_iterator;
    00270
    00271     _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
    00272     _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
    00273     : _Bit_iterator_base(__x, __y) { }
    00274     _Bit_const_iterator(const _Bit_iterator& __x)
    00275     : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
    00276
    00277     const_reference
    00278     operator*() const
    00279     { return _Bit_reference(_M_p, 1UL << _M_offset); }
    00280
    00281     const_iterator&
    00282     operator++()
    00283     {
    00284       _M_bump_up();
    00285       return *this;
    00286     }
    00287
    00288     const_iterator
    00289     operator++(int)
    00290     {
    00291       const_iterator __tmp = *this;
    00292       _M_bump_up();
    00293       return __tmp;
    00294     }
    00295
    00296     const_iterator&
    00297     operator--()
    00298     {
    00299       _M_bump_down();
    00300       return *this;
    00301     }
    00302
    00303     const_iterator
    00304     operator--(int)
    00305     {
    00306       const_iterator __tmp = *this;
    00307       _M_bump_down();
    00308       return __tmp;
    00309     }
    00310
    00311     const_iterator&
    00312     operator+=(difference_type __i)
    00313     {
    00314       _M_incr(__i);
    00315       return *this;
    00316     }
    00317
    00318     const_iterator&
    00319     operator-=(difference_type __i)
    00320     {
    00321       *this += -__i;
    00322       return *this;
    00323     }
    00324
    00325     const_iterator
    00326     operator+(difference_type __i) const {
    00327       const_iterator __tmp = *this;
    00328       return __tmp += __i;
    00329     }
    00330
    00331     const_iterator
    00332     operator-(difference_type __i) const
    00333     {
    00334       const_iterator __tmp = *this;
    00335       return __tmp -= __i;
    00336     }
    00337
    00338     const_reference
    00339     operator[](difference_type __i)
    00340     { return *(*this + __i); }
    00341   };
    00342
    00343   inline _Bit_const_iterator
    00344   operator+(ptrdiff_t __n, const _Bit_const_iterator& __x)
    00345   { return __x + __n; }
    00346
    00347   template<class _Alloc>
    00348     class _Bvector_base
    00349     {
    00350       typedef typename _Alloc::template rebind<_Bit_type>::other
    00351         _Bit_alloc_type;
    00352
    00353       struct _Bvector_impl : public _Bit_alloc_type
    00354       {
    00355     _Bit_iterator   _M_start;
    00356     _Bit_iterator   _M_finish;
    00357     _Bit_type*  _M_end_of_storage;
    00358     _Bvector_impl(const _Bit_alloc_type& __a)
    00359     : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
    00360     { }
    00361       };
    00362
    00363     public:
    00364       typedef _Alloc allocator_type;
    00365
    00366       allocator_type
    00367       get_allocator() const
    00368       { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
    00369
    00370       _Bvector_base(const allocator_type& __a) : _M_impl(__a) { }
    00371
    00372       ~_Bvector_base() { this->_M_deallocate(); }
    00373
    00374     protected:
    00375       _Bvector_impl _M_impl;
    00376
    00377       _Bit_type*
    00378       _M_allocate(size_t __n)
    00379       { return _M_impl.allocate((__n + _S_word_bit - 1) / _S_word_bit); }
    00380
    00381       void
    00382       _M_deallocate()
    00383       {
    00384     if (_M_impl._M_start._M_p)
    00385       _M_impl.deallocate(_M_impl._M_start._M_p,
    00386                 _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
    00387       }
    00388     };
    00389 } // namespace std
    00390
    00391 // Declare a partial specialization of vector<T, Alloc>.
    00392 #include <bits/stl_vector.h>
    00393
    00394 namespace _GLIBCXX_STD
    00395 {
    00396   /**
    00397    *  @brief  A specialization of vector for booleans which offers fixed time
    00398    *  access to individual elements in any order.
    00399    *
    00400    *  Note that vector<bool> does not actually meet the requirements for being
    00401    *  a container.  This is because the reference and pointer types are not
    00402    *  really references and pointers to bool.  See DR96 for details.  @see
    00403    *  vector for function documentation.
    00404    *
    00405    *  @ingroup Containers
    00406    *  @ingroup Sequences
    00407    *
    00408    *  In some terminology a %vector can be described as a dynamic
    00409    *  C-style array, it offers fast and efficient access to individual
    00410    *  elements in any order and saves the user from worrying about
    00411    *  memory and size allocation.  Subscripting ( @c [] ) access is
    00412    *  also provided as with C-style arrays.
    00413   */
    00414 template<typename _Alloc>
    00415   class vector<bool, _Alloc> : public _Bvector_base<_Alloc>
    00416   {
    00417   public:
    00418     typedef bool value_type;
    00419     typedef size_t size_type;
    00420     typedef ptrdiff_t difference_type;
    00421     typedef _Bit_reference reference;
    00422     typedef bool const_reference;
    00423     typedef _Bit_reference* pointer;
    00424     typedef const bool* const_pointer;
    00425
    00426     typedef _Bit_iterator                iterator;
    00427     typedef _Bit_const_iterator          const_iterator;
    00428
    00429     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    00430     typedef std::reverse_iterator<iterator> reverse_iterator;
    00431
    00432     typedef typename _Bvector_base<_Alloc>::allocator_type allocator_type;
    00433
    00434     allocator_type get_allocator() const
    00435     { return _Bvector_base<_Alloc>::get_allocator(); }
    00436
    00437   protected:
    00438     using _Bvector_base<_Alloc>::_M_allocate;
    00439     using _Bvector_base<_Alloc>::_M_deallocate;
    00440
    00441   protected:
    00442     void _M_initialize(size_type __n)
    00443     {
    00444       _Bit_type* __q = this->_M_allocate(__n);
    00445       this->_M_impl._M_end_of_storage = __q
    00446                                    + (__n + _S_word_bit - 1) / _S_word_bit;
    00447       this->_M_impl._M_start = iterator(__q, 0);
    00448       this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
    00449     }
    00450
    00451     void _M_insert_aux(iterator __position, bool __x)
    00452     {
    00453       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
    00454     {
    00455       std::copy_backward(__position, this->_M_impl._M_finish,
    00456                  this->_M_impl._M_finish + 1);
    00457       *__position = __x;
    00458       ++this->_M_impl._M_finish;
    00459     }
    00460       else
    00461     {
    00462       const size_type __len = size() ? 2 * size()
    00463                                      : static_cast<size_type>(_S_word_bit);
    00464       _Bit_type * __q = this->_M_allocate(__len);
    00465       iterator __i = std::copy(begin(), __position, iterator(__q, 0));
    00466       *__i++ = __x;
    00467       this->_M_impl._M_finish = std::copy(__position, end(), __i);
    00468       this->_M_deallocate();
    00469       this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1)
    00470                     / _S_word_bit;
    00471       this->_M_impl._M_start = iterator(__q, 0);
    00472     }
    00473     }
    00474
    00475     template<class _InputIterator>
    00476     void _M_initialize_range(_InputIterator __first, _InputIterator __last,
    00477                              input_iterator_tag)
    00478     {
    00479       this->_M_impl._M_start = iterator();
    00480       this->_M_impl._M_finish = iterator();
    00481       this->_M_impl._M_end_of_storage = 0;
    00482       for ( ; __first != __last; ++__first)
    00483         push_back(*__first);
    00484     }
    00485
    00486     template<class _ForwardIterator>
    00487     void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
    00488                              forward_iterator_tag)
    00489     {
    00490       const size_type __n = std::distance(__first, __last);
    00491       _M_initialize(__n);
    00492       std::copy(__first, __last, this->_M_impl._M_start);
    00493     }
    00494
    00495     template<class _InputIterator>
    00496     void _M_insert_range(iterator __pos, _InputIterator __first,
    00497              _InputIterator __last, input_iterator_tag)
    00498     {
    00499       for ( ; __first != __last; ++__first)
    00500     {
    00501       __pos = insert(__pos, *__first);
    00502       ++__pos;
    00503     }
    00504     }
    00505
    00506     template<class _ForwardIterator>
    00507     void _M_insert_range(iterator __position, _ForwardIterator __first,
    00508              _ForwardIterator __last, forward_iterator_tag)
    00509     {
    00510       if (__first != __last)
    00511     {
    00512       size_type __n = std::distance(__first, __last);
    00513       if (capacity() - size() >= __n)
    00514         {
    00515           std::copy_backward(__position, end(),
    00516                    this->_M_impl._M_finish + difference_type(__n));
    00517           std::copy(__first, __last, __position);
    00518           this->_M_impl._M_finish += difference_type(__n);
    00519         }
    00520       else
    00521         {
    00522           const size_type __len = size() + std::max(size(), __n);
    00523           _Bit_type * __q = this->_M_allocate(__len);
    00524           iterator __i = std::copy(begin(), __position, iterator(__q, 0));
    00525           __i = std::copy(__first, __last, __i);
    00526           this->_M_impl._M_finish = std::copy(__position, end(), __i);
    00527           this->_M_deallocate();
    00528           this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1)
    00529                                         / _S_word_bit;
    00530           this->_M_impl._M_start = iterator(__q, 0);
    00531         }
    00532     }
    00533     }
    00534
    00535   public:
    00536     iterator begin()
    00537     { return this->_M_impl._M_start; }
    00538
    00539     const_iterator begin() const
    00540     { return this->_M_impl._M_start; }
    00541
    00542     iterator end()
    00543     { return this->_M_impl._M_finish; }
    00544
    00545     const_iterator end() const
    00546     { return this->_M_impl._M_finish; }
    00547
    00548     reverse_iterator rbegin()
    00549     { return reverse_iterator(end()); }
    00550
    00551     const_reverse_iterator rbegin() const
    00552     { return const_reverse_iterator(end()); }
    00553
    00554     reverse_iterator rend()
    00555     { return reverse_iterator(begin()); }
    00556
    00557     const_reverse_iterator rend() const
    00558     { return const_reverse_iterator(begin()); }
    00559
    00560     size_type size() const
    00561     { return size_type(end() - begin()); }
    00562
    00563     size_type max_size() const
    00564     { return size_type(-1); }
    00565
    00566     size_type capacity() const
    00567     { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
    00568                - begin()); }
    00569     bool empty() const
    00570     { return begin() == end(); }
    00571
    00572     reference operator[](size_type __n)
    00573     { return *(begin() + difference_type(__n)); }
    00574
    00575     const_reference operator[](size_type __n) const
    00576     { return *(begin() + difference_type(__n)); }
    00577
    00578     void _M_range_check(size_type __n) const
    00579     {
    00580       if (__n >= this->size())
    00581         __throw_out_of_range(__N("vector<bool>::_M_range_check"));
    00582     }
    00583
    00584     reference at(size_type __n)
    00585     { _M_range_check(__n); return (*this)[__n]; }
    00586
    00587     const_reference at(size_type __n) const
    00588     { _M_range_check(__n); return (*this)[__n]; }
    00589
    00590     explicit vector(const allocator_type& __a = allocator_type())
    00591       : _Bvector_base<_Alloc>(__a) { }
    00592
    00593     vector(size_type __n, bool __value,
    00594        const allocator_type& __a = allocator_type())
    00595     : _Bvector_base<_Alloc>(__a)
    00596     {
    00597       _M_initialize(__n);
    00598       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage,
    00599         __value ? ~0 : 0);
    00600     }
    00601
    00602     explicit vector(size_type __n)
    00603     : _Bvector_base<_Alloc>(allocator_type())
    00604     {
    00605       _M_initialize(__n);
    00606       std::fill(this->_M_impl._M_start._M_p,
    00607         this->_M_impl._M_end_of_storage, 0);
    00608     }
    00609
    00610     vector(const vector& __x) : _Bvector_base<_Alloc>(__x.get_allocator())
    00611     {
    00612       _M_initialize(__x.size());
    00613       std::copy(__x.begin(), __x.end(), this->_M_impl._M_start);
    00614     }
    00615
    00616     // Check whether it's an integral type.  If so, it's not an iterator.
    00617     template<class _Integer>
    00618     void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
    00619     {
    00620       _M_initialize(__n);
    00621       std::fill(this->_M_impl._M_start._M_p,
    00622         this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
    00623     }
    00624
    00625     template<class _InputIterator>
    00626       void
    00627       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
    00628                  __false_type)
    00629       { _M_initialize_range(__first, __last,
    00630                 std::__iterator_category(__first)); }
    00631
    00632     template<class _InputIterator>
    00633       vector(_InputIterator __first, _InputIterator __last,
    00634          const allocator_type& __a = allocator_type())
    00635     : _Bvector_base<_Alloc>(__a)
    00636     {
    00637       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00638       _M_initialize_dispatch(__first, __last, _Integral());
    00639     }
    00640
    00641     ~vector() { }
    00642
    00643     vector& operator=(const vector& __x)
    00644     {
    00645       if (&__x == this)
    00646     return *this;
    00647       if (__x.size() > capacity())
    00648     {
    00649       this->_M_deallocate();
    00650       _M_initialize(__x.size());
    00651     }
    00652       std::copy(__x.begin(), __x.end(), begin());
    00653       this->_M_impl._M_finish = begin() + difference_type(__x.size());
    00654       return *this;
    00655     }
    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
    00662     void _M_fill_assign(size_t __n, bool __x)
    00663     {
    00664       if (__n > size())
    00665     {
    00666       std::fill(this->_M_impl._M_start._M_p,
    00667             this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
    00668       insert(end(), __n - size(), __x);
    00669     }
    00670       else
    00671     {
    00672       erase(begin() + __n, end());
    00673       std::fill(this->_M_impl._M_start._M_p,
    00674             this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
    00675     }
    00676     }
    00677
    00678     void assign(size_t __n, bool __x)
    00679     { _M_fill_assign(__n, __x); }
    00680
    00681     template<class _InputIterator>
    00682     void assign(_InputIterator __first, _InputIterator __last)
    00683     {
    00684       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00685       _M_assign_dispatch(__first, __last, _Integral());
    00686     }
    00687
    00688     template<class _Integer>
    00689     void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
    00690     { _M_fill_assign((size_t) __n, (bool) __val); }
    00691
    00692     template<class _InputIterator>
    00693     void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
    00694                 __false_type)
    00695     { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
    00696
    00697     template<class _InputIterator>
    00698     void _M_assign_aux(_InputIterator __first, _InputIterator __last,
    00699                        input_iterator_tag)
    00700     {
    00701       iterator __cur = begin();
    00702       for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
    00703         *__cur = *__first;
    00704       if (__first == __last)
    00705         erase(__cur, end());
    00706       else
    00707         insert(end(), __first, __last);
    00708     }
    00709
    00710     template<class _ForwardIterator>
    00711     void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
    00712                        forward_iterator_tag)
    00713     {
    00714       const size_type __len = std::distance(__first, __last);
    00715       if (__len < size())
    00716         erase(std::copy(__first, __last, begin()), end());
    00717       else
    00718     {
    00719       _ForwardIterator __mid = __first;
    00720       std::advance(__mid, size());
    00721       std::copy(__first, __mid, begin());
    00722       insert(end(), __mid, __last);
    00723     }
    00724     }
    00725
    00726     void reserve(size_type __n)
    00727     {
    00728       if (__n > this->max_size())
    00729     __throw_length_error(__N("vector::reserve"));
    00730       if (this->capacity() < __n)
    00731     {
    00732       _Bit_type* __q = this->_M_allocate(__n);
    00733       this->_M_impl._M_finish = std::copy(begin(), end(),
    00734                           iterator(__q, 0));
    00735       this->_M_deallocate();
    00736       this->_M_impl._M_start = iterator(__q, 0);
    00737       this->_M_impl._M_end_of_storage = __q + (__n + _S_word_bit - 1) / _S_word_bit;
    00738     }
    00739     }
    00740
    00741     reference front()
    00742     { return *begin(); }
    00743
    00744     const_reference front() const
    00745     { return *begin(); }
    00746
    00747     reference back()
    00748     { return *(end() - 1); }
    00749
    00750     const_reference back() const
    00751     { return *(end() - 1); }
    00752
    00753     void push_back(bool __x)
    00754     {
    00755       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
    00756         *this->_M_impl._M_finish++ = __x;
    00757       else
    00758         _M_insert_aux(end(), __x);
    00759     }
    00760
    00761     void swap(vector<bool, _Alloc>& __x)
    00762     {
    00763       std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
    00764       std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
    00765       std::swap(this->_M_impl._M_end_of_storage,
    00766         __x._M_impl._M_end_of_storage);
    00767     }
    00768
    00769     // [23.2.5]/1, third-to-last entry in synopsis listing
    00770     static void swap(reference __x, reference __y)
    00771     {
    00772       bool __tmp = __x;
    00773       __x = __y;
    00774       __y = __tmp;
    00775     }
    00776
    00777     iterator insert(iterator __position, bool __x = bool())
    00778     {
    00779       const difference_type __n = __position - begin();
    00780       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
    00781       && __position == end())
    00782         *this->_M_impl._M_finish++ = __x;
    00783       else
    00784         _M_insert_aux(__position, __x);
    00785       return begin() + __n;
    00786     }
    00787
    00788     // Check whether it's an integral type.  If so, it's not an iterator.
    00789
    00790     template<class _Integer>
    00791     void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
    00792                             __true_type)
    00793     { _M_fill_insert(__pos, __n, __x); }
    00794
    00795     template<class _InputIterator>
    00796     void _M_insert_dispatch(iterator __pos,
    00797                             _InputIterator __first, _InputIterator __last,
    00798                             __false_type)
    00799     { _M_insert_range(__pos, __first, __last,
    00800               std::__iterator_category(__first)); }
    00801
    00802     template<class _InputIterator>
    00803     void insert(iterator __position,
    00804                 _InputIterator __first, _InputIterator __last)
    00805     {
    00806       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00807       _M_insert_dispatch(__position, __first, __last, _Integral());
    00808     }
    00809
    00810     void _M_fill_insert(iterator __position, size_type __n, bool __x)
    00811     {
    00812       if (__n == 0)
    00813     return;
    00814       if (capacity() - size() >= __n)
    00815     {
    00816       std::copy_backward(__position, end(),
    00817                  this->_M_impl._M_finish + difference_type(__n));
    00818       std::fill(__position, __position + difference_type(__n), __x);
    00819       this->_M_impl._M_finish += difference_type(__n);
    00820     }
    00821       else
    00822     {
    00823       const size_type __len = size() + std::max(size(), __n);
    00824       _Bit_type * __q = this->_M_allocate(__len);
    00825       iterator __i = std::copy(begin(), __position, iterator(__q, 0));
    00826       std::fill_n(__i, __n, __x);
    00827       this->_M_impl._M_finish = std::copy(__position, end(),
    00828                           __i + difference_type(__n));
    00829       this->_M_deallocate();
    00830       this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1)
    00831                                         / _S_word_bit;
    00832       this->_M_impl._M_start = iterator(__q, 0);
    00833     }
    00834     }
    00835
    00836     void insert(iterator __position, size_type __n, bool __x)
    00837     { _M_fill_insert(__position, __n, __x); }
    00838
    00839     void pop_back()
    00840     { --this->_M_impl._M_finish; }
    00841
    00842     iterator erase(iterator __position)
    00843     {
    00844       if (__position + 1 != end())
    00845         std::copy(__position + 1, end(), __position);
    00846       --this->_M_impl._M_finish;
    00847       return __position;
    00848     }
    00849
    00850     iterator erase(iterator __first, iterator __last)
    00851     {
    00852       this->_M_impl._M_finish = std::copy(__last, end(), __first);
    00853       return __first;
    00854     }
    00855
    00856     void resize(size_type __new_size, bool __x = bool())
    00857     {
    00858       if (__new_size < size())
    00859         erase(begin() + difference_type(__new_size), end());
    00860       else
    00861         insert(end(), __new_size - size(), __x);
    00862     }
    00863
    00864     void flip()
    00865     {
    00866       for (_Bit_type * __p = this->_M_impl._M_start._M_p;
    00867        __p != this->_M_impl._M_end_of_storage; ++__p)
    00868         *__p = ~*__p;
    00869     }
    00870
    00871     void clear()
    00872     { erase(begin(), end()); }
    00873   };
    00874 } // namespace std
    00875
    00876 #endif