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

Generated on Tue Dec 23 12:34:06 2003 for libstdc++-v3 Source by doxygen 1.3.4