stl_bvector.h

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

Generated on Sat Apr 2 13:54:43 2005 for libstdc++ source by  doxygen 1.4.0