stl_bvector.h

Go to the documentation of this file.
00001 // bit_vector and vector<bool> specialization -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002 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 __GLIBCPP_INTERNAL_BVECTOR_H
00062 #define __GLIBCPP_INTERNAL_BVECTOR_H
00063 
00064 namespace std
00065 { 
00066   typedef unsigned long _Bit_type;
00067   enum { _M_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   _Bit_reference(_Bit_type * __x, _Bit_type __y) 
00074     : _M_p(__x), _M_mask(__y) {}
00075 
00076 public:
00077   _Bit_reference() : _M_p(0), _M_mask(0) {}
00078   operator bool() const { return !!(*_M_p & _M_mask); }
00079   _Bit_reference& operator=(bool __x)
00080   {
00081     if (__x)  *_M_p |= _M_mask;
00082     else      *_M_p &= ~_M_mask;
00083     return *this;
00084   }
00085   _Bit_reference& operator=(const _Bit_reference& __x) 
00086     { return *this = bool(__x); }
00087   bool operator==(const _Bit_reference& __x) const
00088     { return bool(*this) == bool(__x); }
00089   bool operator<(const _Bit_reference& __x) const
00090     { return !bool(*this) && bool(__x); }
00091   void flip() { *_M_p ^= _M_mask; }
00092 };
00093 
00094 struct _Bit_iterator_base : public iterator<random_access_iterator_tag, bool>
00095 {
00096   _Bit_type * _M_p;
00097   unsigned int _M_offset;
00098 
00099   _Bit_iterator_base(_Bit_type * __x, unsigned int __y)
00100     : _M_p(__x), _M_offset(__y) {}
00101 
00102   void _M_bump_up() {
00103     if (_M_offset++ == _M_word_bit - 1) {
00104       _M_offset = 0;
00105       ++_M_p;
00106     }
00107   }
00108   void _M_bump_down() {
00109     if (_M_offset-- == 0) {
00110       _M_offset = _M_word_bit - 1;
00111       --_M_p;
00112     }
00113   }
00114 
00115   void _M_incr(ptrdiff_t __i) {
00116     difference_type __n = __i + _M_offset;
00117     _M_p += __n / _M_word_bit;
00118     __n = __n % _M_word_bit;
00119     if (__n < 0) {
00120       _M_offset = (unsigned int) __n + _M_word_bit;
00121       --_M_p;
00122     } else
00123       _M_offset = (unsigned int) __n;
00124   }
00125 
00126   bool operator==(const _Bit_iterator_base& __i) const {
00127     return _M_p == __i._M_p && _M_offset == __i._M_offset;
00128   }
00129   bool operator<(const _Bit_iterator_base& __i) const {
00130     return _M_p < __i._M_p || (_M_p == __i._M_p && _M_offset < __i._M_offset);
00131   }
00132   bool operator!=(const _Bit_iterator_base& __i) const {
00133     return !(*this == __i);
00134   }
00135   bool operator>(const _Bit_iterator_base& __i) const {
00136     return __i < *this;
00137   }
00138   bool operator<=(const _Bit_iterator_base& __i) const {
00139     return !(__i < *this); 
00140   }
00141   bool operator>=(const _Bit_iterator_base& __i) const {
00142     return !(*this < __i);
00143   }
00144 };
00145 
00146 inline ptrdiff_t
00147 operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
00148   return _M_word_bit * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset;
00149 }
00150 
00151 
00152 struct _Bit_iterator : public _Bit_iterator_base
00153 {
00154   typedef _Bit_reference  reference;
00155   typedef _Bit_reference* pointer;
00156   typedef _Bit_iterator   iterator;
00157 
00158   _Bit_iterator() : _Bit_iterator_base(0, 0) {}
00159   _Bit_iterator(_Bit_type * __x, unsigned int __y) 
00160     : _Bit_iterator_base(__x, __y) {}
00161 
00162   reference operator*() const { return reference(_M_p, 1UL << _M_offset); }
00163   iterator& operator++() {
00164     _M_bump_up();
00165     return *this;
00166   }
00167   iterator operator++(int) {
00168     iterator __tmp = *this;
00169     _M_bump_up();
00170     return __tmp;
00171   }
00172   iterator& operator--() {
00173     _M_bump_down();
00174     return *this;
00175   }
00176   iterator operator--(int) {
00177     iterator __tmp = *this;
00178     _M_bump_down();
00179     return __tmp;
00180   }
00181   iterator& operator+=(difference_type __i) {
00182     _M_incr(__i);
00183     return *this;
00184   }
00185   iterator& operator-=(difference_type __i) {
00186     *this += -__i;
00187     return *this;
00188   }
00189   iterator operator+(difference_type __i) const {
00190     iterator __tmp = *this;
00191     return __tmp += __i;
00192   }
00193   iterator operator-(difference_type __i) const {
00194     iterator __tmp = *this;
00195     return __tmp -= __i;
00196   }
00197 
00198   reference operator[](difference_type __i) { return *(*this + __i); }
00199 };
00200 
00201 inline _Bit_iterator 
00202 operator+(ptrdiff_t __n, const _Bit_iterator& __x) { return __x + __n; }
00203 
00204 
00205 struct _Bit_const_iterator : public _Bit_iterator_base
00206 {
00207   typedef bool                 reference;
00208   typedef bool                 const_reference;
00209   typedef const bool*          pointer;
00210   typedef _Bit_const_iterator  const_iterator;
00211 
00212   _Bit_const_iterator() : _Bit_iterator_base(0, 0) {}
00213   _Bit_const_iterator(_Bit_type * __x, unsigned int __y) 
00214     : _Bit_iterator_base(__x, __y) {}
00215   _Bit_const_iterator(const _Bit_iterator& __x) 
00216     : _Bit_iterator_base(__x._M_p, __x._M_offset) {}
00217 
00218   const_reference operator*() const {
00219     return _Bit_reference(_M_p, 1UL << _M_offset);
00220   }
00221   const_iterator& operator++() {
00222     _M_bump_up();
00223     return *this;
00224   }
00225   const_iterator operator++(int) {
00226     const_iterator __tmp = *this;
00227     _M_bump_up();
00228     return __tmp;
00229   }
00230   const_iterator& operator--() {
00231     _M_bump_down();
00232     return *this;
00233   }
00234   const_iterator operator--(int) {
00235     const_iterator __tmp = *this;
00236     _M_bump_down();
00237     return __tmp;
00238   }
00239   const_iterator& operator+=(difference_type __i) {
00240     _M_incr(__i);
00241     return *this;
00242   }
00243   const_iterator& operator-=(difference_type __i) {
00244     *this += -__i;
00245     return *this;
00246   }
00247   const_iterator operator+(difference_type __i) const {
00248     const_iterator __tmp = *this;
00249     return __tmp += __i;
00250   }
00251   const_iterator operator-(difference_type __i) const {
00252     const_iterator __tmp = *this;
00253     return __tmp -= __i;
00254   }
00255   const_reference operator[](difference_type __i) { 
00256     return *(*this + __i); 
00257   }
00258 };
00259 
00260 inline _Bit_const_iterator 
00261 operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) { return __x + __n; }
00262 
00263 
00264 // Bit-vector base class, which encapsulates the difference between
00265 // old SGI-style allocators and standard-conforming allocators.
00266 
00267 // Base class for ordinary allocators.
00268 template <class _Allocator, bool __is_static>
00269 class _Bvector_alloc_base {
00270 public:
00271   typedef typename _Alloc_traits<bool, _Allocator>::allocator_type
00272           allocator_type;
00273   allocator_type get_allocator() const { return _M_data_allocator; }
00274 
00275   _Bvector_alloc_base(const allocator_type& __a)
00276     : _M_data_allocator(__a), _M_start(), _M_finish(), _M_end_of_storage(0) {}
00277 
00278 protected:
00279   _Bit_type * _M_bit_alloc(size_t __n) 
00280     { return _M_data_allocator.allocate((__n + _M_word_bit - 1)/_M_word_bit); }
00281   void _M_deallocate() {
00282     if (_M_start._M_p)
00283       _M_data_allocator.deallocate(_M_start._M_p, 
00284                                    _M_end_of_storage - _M_start._M_p);
00285   }  
00286 
00287   typename _Alloc_traits<_Bit_type, _Allocator>::allocator_type 
00288           _M_data_allocator;
00289   _Bit_iterator _M_start;
00290   _Bit_iterator _M_finish;
00291   _Bit_type * _M_end_of_storage;
00292 };
00293 
00294 // Specialization for instanceless allocators.
00295 template <class _Allocator>
00296 class _Bvector_alloc_base<_Allocator, true> {
00297 public:
00298   typedef typename _Alloc_traits<bool, _Allocator>::allocator_type
00299           allocator_type;
00300   allocator_type get_allocator() const { return allocator_type(); }
00301 
00302   _Bvector_alloc_base(const allocator_type&)
00303     : _M_start(), _M_finish(), _M_end_of_storage(0) {}
00304 
00305 protected:
00306   typedef typename _Alloc_traits<_Bit_type, _Allocator>::_Alloc_type
00307           _Alloc_type;
00308           
00309   _Bit_type * _M_bit_alloc(size_t __n) 
00310     { return _Alloc_type::allocate((__n + _M_word_bit - 1)/_M_word_bit); }
00311   void _M_deallocate() {
00312     if (_M_start._M_p)
00313       _Alloc_type::deallocate(_M_start._M_p,
00314                               _M_end_of_storage - _M_start._M_p);
00315   }  
00316 
00317   _Bit_iterator _M_start;
00318   _Bit_iterator _M_finish;
00319   _Bit_type * _M_end_of_storage;
00320 };  
00321 
00322 template <class _Alloc>
00323 class _Bvector_base
00324   : public _Bvector_alloc_base<_Alloc,
00325                                _Alloc_traits<bool, _Alloc>::_S_instanceless>
00326 {
00327   typedef _Bvector_alloc_base<_Alloc,
00328                               _Alloc_traits<bool, _Alloc>::_S_instanceless>
00329           _Base;
00330 public:
00331   typedef typename _Base::allocator_type allocator_type;
00332 
00333   _Bvector_base(const allocator_type& __a) : _Base(__a) {}
00334   ~_Bvector_base() { _Base::_M_deallocate(); }
00335 };
00336 
00337 } // namespace std
00338 
00339 // Declare a partial specialization of vector<T, Alloc>.
00340 #include <bits/stl_vector.h>
00341 namespace std
00342 {
00343 
00344 template <typename _Alloc> 
00345   class vector<bool, _Alloc> : public _Bvector_base<_Alloc> 
00346   {
00347   public:
00348     typedef bool value_type;
00349     typedef size_t size_type;
00350     typedef ptrdiff_t difference_type; 
00351     typedef _Bit_reference reference;
00352     typedef bool const_reference;
00353     typedef _Bit_reference* pointer;
00354     typedef const bool* const_pointer;
00355   
00356     typedef _Bit_iterator                iterator;
00357     typedef _Bit_const_iterator          const_iterator;
00358   
00359     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00360     typedef std::reverse_iterator<iterator> reverse_iterator;
00361   
00362     typedef typename _Bvector_base<_Alloc>::allocator_type allocator_type;
00363     allocator_type get_allocator() const {
00364       return _Bvector_base<_Alloc>::get_allocator();
00365     }
00366   
00367   protected:
00368     using _Bvector_base<_Alloc>::_M_bit_alloc;
00369     using _Bvector_base<_Alloc>::_M_deallocate;
00370     using _Bvector_base<_Alloc>::_M_start;
00371     using _Bvector_base<_Alloc>::_M_finish;
00372     using _Bvector_base<_Alloc>::_M_end_of_storage;
00373   
00374   protected:
00375     void _M_initialize(size_type __n) {
00376       _Bit_type * __q = _M_bit_alloc(__n);
00377       _M_end_of_storage = __q + (__n + _M_word_bit - 1)/_M_word_bit;
00378       _M_start = iterator(__q, 0);
00379       _M_finish = _M_start + difference_type(__n);
00380     }
00381     void _M_insert_aux(iterator __position, bool __x) {
00382       if (_M_finish._M_p != _M_end_of_storage) {
00383         copy_backward(__position, _M_finish, _M_finish + 1);
00384         *__position = __x;
00385         ++_M_finish;
00386       }
00387       else {
00388         size_type __len = size() 
00389                       ? 2 * size() : static_cast<size_type>(_M_word_bit);
00390         _Bit_type * __q = _M_bit_alloc(__len);
00391         iterator __i = copy(begin(), __position, iterator(__q, 0));
00392         *__i++ = __x;
00393         _M_finish = copy(__position, end(), __i);
00394         _M_deallocate();
00395         _M_end_of_storage = __q + (__len + _M_word_bit - 1)/_M_word_bit;
00396         _M_start = iterator(__q, 0);
00397       }
00398     }
00399   
00400     template <class _InputIterator>
00401     void _M_initialize_range(_InputIterator __first, _InputIterator __last,
00402                              input_iterator_tag) {
00403       _M_start = iterator();
00404       _M_finish = iterator();
00405       _M_end_of_storage = 0;
00406       for ( ; __first != __last; ++__first) 
00407         push_back(*__first);
00408     }
00409   
00410     template <class _ForwardIterator>
00411     void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
00412                              forward_iterator_tag) {
00413       size_type __n = distance(__first, __last);
00414       _M_initialize(__n);
00415       copy(__first, __last, _M_start);
00416     }
00417   
00418     template <class _InputIterator>
00419     void _M_insert_range(iterator __pos,
00420                          _InputIterator __first, _InputIterator __last,
00421                          input_iterator_tag) {
00422       for ( ; __first != __last; ++__first) {
00423         __pos = insert(__pos, *__first);
00424         ++__pos;
00425       }
00426     }
00427   
00428     template <class _ForwardIterator>
00429     void _M_insert_range(iterator __position,
00430                          _ForwardIterator __first, _ForwardIterator __last,
00431                          forward_iterator_tag) {
00432       if (__first != __last) {
00433         size_type __n = distance(__first, __last);
00434         if (capacity() - size() >= __n) {
00435           copy_backward(__position, end(), _M_finish + difference_type(__n));
00436           copy(__first, __last, __position);
00437           _M_finish += difference_type(__n);
00438         }
00439         else {
00440           size_type __len = size() + max(size(), __n);
00441           _Bit_type * __q = _M_bit_alloc(__len);
00442           iterator __i = copy(begin(), __position, iterator(__q, 0));
00443           __i = copy(__first, __last, __i);
00444           _M_finish = copy(__position, end(), __i);
00445           _M_deallocate();
00446           _M_end_of_storage = __q + (__len + _M_word_bit - 1)/_M_word_bit;
00447           _M_start = iterator(__q, 0);
00448         }
00449       }
00450     }      
00451   
00452   public:
00453     iterator begin() { return _M_start; }
00454     const_iterator begin() const { return _M_start; }
00455     iterator end() { return _M_finish; }
00456     const_iterator end() const { return _M_finish; }
00457   
00458     reverse_iterator rbegin() { return reverse_iterator(end()); }
00459     const_reverse_iterator rbegin() const { 
00460       return const_reverse_iterator(end()); 
00461     }
00462     reverse_iterator rend() { return reverse_iterator(begin()); }
00463     const_reverse_iterator rend() const { 
00464       return const_reverse_iterator(begin()); 
00465     }
00466   
00467     size_type size() const { return size_type(end() - begin()); }
00468     size_type max_size() const { return size_type(-1); }
00469     size_type capacity() const {
00470       return size_type(const_iterator(_M_end_of_storage, 0) - begin());
00471     }
00472     bool empty() const { return begin() == end(); }
00473   
00474     reference operator[](size_type __n)
00475       { return *(begin() + difference_type(__n)); }
00476     const_reference operator[](size_type __n) const
00477       { return *(begin() + difference_type(__n)); }
00478   
00479     void _M_range_check(size_type __n) const {
00480       if (__n >= this->size())
00481         __throw_out_of_range("vector<bool>");
00482     }
00483   
00484     reference at(size_type __n)
00485       { _M_range_check(__n); return (*this)[__n]; }
00486     const_reference at(size_type __n) const
00487       { _M_range_check(__n); return (*this)[__n]; }
00488   
00489     explicit vector(const allocator_type& __a = allocator_type())
00490       : _Bvector_base<_Alloc>(__a) {}
00491   
00492     vector(size_type __n, bool __value,
00493               const allocator_type& __a = allocator_type())
00494       : _Bvector_base<_Alloc>(__a)
00495     {
00496       _M_initialize(__n);
00497       fill(_M_start._M_p, _M_end_of_storage, __value ? ~0 : 0);
00498     }
00499   
00500     explicit vector(size_type __n)
00501       : _Bvector_base<_Alloc>(allocator_type())
00502     {
00503       _M_initialize(__n);
00504       fill(_M_start._M_p, _M_end_of_storage, 0);
00505     }
00506   
00507     vector(const vector& __x) : _Bvector_base<_Alloc>(__x.get_allocator()) {
00508       _M_initialize(__x.size());
00509       copy(__x.begin(), __x.end(), _M_start);
00510     }
00511   
00512     // Check whether it's an integral type.  If so, it's not an iterator.
00513   
00514     template <class _Integer>
00515     void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
00516       _M_initialize(__n);
00517       fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
00518     }
00519   
00520     template <class _InputIterator>
00521     void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
00522                                 __false_type) {
00523       _M_initialize_range(__first, __last, __iterator_category(__first));
00524     }
00525   
00526     template <class _InputIterator>
00527     vector(_InputIterator __first, _InputIterator __last,
00528              const allocator_type& __a = allocator_type())
00529       : _Bvector_base<_Alloc>(__a)
00530     {
00531       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00532       _M_initialize_dispatch(__first, __last, _Integral());
00533     }
00534       
00535     ~vector() { }
00536   
00537     vector& operator=(const vector& __x) {
00538       if (&__x == this) return *this;
00539       if (__x.size() > capacity()) {
00540         _M_deallocate();
00541         _M_initialize(__x.size());
00542       }
00543       copy(__x.begin(), __x.end(), begin());
00544       _M_finish = begin() + difference_type(__x.size());
00545       return *this;
00546     }
00547   
00548     // assign(), a generalized assignment member function.  Two
00549     // versions: one that takes a count, and one that takes a range.
00550     // The range version is a member template, so we dispatch on whether
00551     // or not the type is an integer.
00552   
00553     void _M_fill_assign(size_t __n, bool __x) {
00554       if (__n > size()) {
00555         fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
00556         insert(end(), __n - size(), __x);
00557       }
00558       else {
00559         erase(begin() + __n, end());
00560         fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
00561       }
00562     }
00563   
00564     void assign(size_t __n, bool __x) { _M_fill_assign(__n, __x); }
00565   
00566     template <class _InputIterator>
00567     void assign(_InputIterator __first, _InputIterator __last) {
00568       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00569       _M_assign_dispatch(__first, __last, _Integral());
00570     }
00571   
00572     template <class _Integer>
00573     void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00574       { _M_fill_assign((size_t) __n, (bool) __val); }
00575   
00576     template <class _InputIter>
00577     void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
00578       { _M_assign_aux(__first, __last, __iterator_category(__first)); }
00579   
00580     template <class _InputIterator>
00581     void _M_assign_aux(_InputIterator __first, _InputIterator __last,
00582                        input_iterator_tag) {
00583       iterator __cur = begin();
00584       for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
00585         *__cur = *__first;
00586       if (__first == __last)
00587         erase(__cur, end());
00588       else
00589         insert(end(), __first, __last);
00590     }
00591   
00592     template <class _ForwardIterator>
00593     void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00594                        forward_iterator_tag) {
00595       size_type __len = distance(__first, __last);
00596       if (__len < size())
00597         erase(copy(__first, __last, begin()), end());
00598       else {
00599         _ForwardIterator __mid = __first;
00600         advance(__mid, size());
00601         copy(__first, __mid, begin());
00602         insert(end(), __mid, __last);
00603       }
00604     }    
00605   
00606     void reserve(size_type __n) {
00607       if (__n > this->max_size())
00608     __throw_length_error("vector::reserve");
00609       if (this->capacity() < __n) {
00610         _Bit_type * __q = _M_bit_alloc(__n);
00611         _M_finish = copy(begin(), end(), iterator(__q, 0));
00612         _M_deallocate();
00613         _M_start = iterator(__q, 0);
00614         _M_end_of_storage = __q + (__n + _M_word_bit - 1)/_M_word_bit;
00615       }
00616     }
00617   
00618     reference front() { return *begin(); }
00619     const_reference front() const { return *begin(); }
00620     reference back() { return *(end() - 1); }
00621     const_reference back() const { return *(end() - 1); }
00622     void push_back(bool __x) {
00623       if (_M_finish._M_p != _M_end_of_storage)
00624         *_M_finish++ = __x;
00625       else
00626         _M_insert_aux(end(), __x);
00627     }
00628     void swap(vector<bool, _Alloc>& __x) {
00629       std::swap(_M_start, __x._M_start);
00630       std::swap(_M_finish, __x._M_finish);
00631       std::swap(_M_end_of_storage, __x._M_end_of_storage);
00632     }
00633 
00634     // [23.2.5]/1, third-to-last entry in synopsis listing
00635     static void swap(reference __x, reference __y) {
00636       bool __tmp = __x;
00637       __x = __y;
00638       __y = __tmp;
00639     }
00640 
00641     iterator insert(iterator __position, bool __x = bool()) {
00642       difference_type __n = __position - begin();
00643       if (_M_finish._M_p != _M_end_of_storage && __position == end())
00644         *_M_finish++ = __x;
00645       else
00646         _M_insert_aux(__position, __x);
00647       return begin() + __n;
00648     }
00649   
00650     // Check whether it's an integral type.  If so, it's not an iterator.
00651   
00652     template <class _Integer>
00653     void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
00654                             __true_type) {
00655       _M_fill_insert(__pos, __n, __x);
00656     }
00657   
00658     template <class _InputIterator>
00659     void _M_insert_dispatch(iterator __pos,
00660                             _InputIterator __first, _InputIterator __last,
00661                             __false_type) {
00662       _M_insert_range(__pos, __first, __last, __iterator_category(__first));
00663     }
00664   
00665     template <class _InputIterator>
00666     void insert(iterator __position,
00667                 _InputIterator __first, _InputIterator __last) {
00668       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00669       _M_insert_dispatch(__position, __first, __last, _Integral());
00670     }
00671   
00672     void _M_fill_insert(iterator __position, size_type __n, bool __x) {
00673       if (__n == 0) return;
00674       if (capacity() - size() >= __n) {
00675         copy_backward(__position, end(), _M_finish + difference_type(__n));
00676         fill(__position, __position + difference_type(__n), __x);
00677         _M_finish += difference_type(__n);
00678       }
00679       else {
00680         size_type __len = size() + max(size(), __n);
00681         _Bit_type * __q = _M_bit_alloc(__len);
00682         iterator __i = copy(begin(), __position, iterator(__q, 0));
00683         fill_n(__i, __n, __x);
00684         _M_finish = copy(__position, end(), __i + difference_type(__n));
00685         _M_deallocate();
00686         _M_end_of_storage = __q + (__len + _M_word_bit - 1)/_M_word_bit;
00687         _M_start = iterator(__q, 0);
00688       }
00689     }
00690   
00691     void insert(iterator __position, size_type __n, bool __x) {
00692       _M_fill_insert(__position, __n, __x);
00693     }
00694   
00695     void pop_back() { --_M_finish; }
00696     iterator erase(iterator __position) {
00697       if (__position + 1 != end())
00698         copy(__position + 1, end(), __position);
00699         --_M_finish;
00700       return __position;
00701     }
00702     iterator erase(iterator __first, iterator __last) {
00703       _M_finish = copy(__last, end(), __first);
00704       return __first;
00705     }
00706     void resize(size_type __new_size, bool __x = bool()) {
00707       if (__new_size < size()) 
00708         erase(begin() + difference_type(__new_size), end());
00709       else
00710         insert(end(), __new_size - size(), __x);
00711     }
00712     void flip() {
00713       for (_Bit_type * __p = _M_start._M_p; __p != _M_end_of_storage; ++__p)
00714         *__p = ~*__p;
00715     }
00716   
00717     void clear() { erase(begin(), end()); }
00718   };
00719 
00720 // This typedef is non-standard.  It is provided for backward compatibility.
00721 typedef vector<bool, __alloc> bit_vector;
00722 
00723 } // namespace std 
00724 
00725 #endif /* __GLIBCPP_INTERNAL_BVECTOR_H */
00726 
00727 // Local Variables:
00728 // mode:C++
00729 // End:

Generated on Thu Feb 10 23:22:58 2005 for libstdc++-v3 Source by  doxygen 1.4.0