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