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, 2007
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 _STL_BVECTOR_H
00063 #define _STL_BVECTOR_H 1
00064 
00065 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
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<typename _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 
00389     _Bvector_impl()
00390     : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage(0)
00391     { }
00392  
00393     _Bvector_impl(const _Bit_alloc_type& __a)
00394     : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
00395     { }
00396       };
00397 
00398     public:
00399       typedef _Alloc allocator_type;
00400 
00401       _Bit_alloc_type&
00402       _M_get_Bit_allocator()
00403       { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); }
00404 
00405       const _Bit_alloc_type&
00406       _M_get_Bit_allocator() const
00407       { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
00408 
00409       allocator_type
00410       get_allocator() const
00411       { return allocator_type(_M_get_Bit_allocator()); }
00412 
00413       _Bvector_base()
00414       : _M_impl() { }
00415       
00416       _Bvector_base(const allocator_type& __a)
00417       : _M_impl(__a) { }
00418 
00419 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00420       _Bvector_base(_Bvector_base&& __x)
00421       : _M_impl(__x._M_get_Bit_allocator())
00422       {
00423     this->_M_impl._M_start = __x._M_impl._M_start;
00424     this->_M_impl._M_finish = __x._M_impl._M_finish;
00425     this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
00426     __x._M_impl._M_start = _Bit_iterator();
00427     __x._M_impl._M_finish = _Bit_iterator();
00428     __x._M_impl._M_end_of_storage = 0;
00429       }
00430 #endif
00431 
00432       ~_Bvector_base()
00433       { this->_M_deallocate(); }
00434 
00435     protected:
00436       _Bvector_impl _M_impl;
00437 
00438       _Bit_type*
00439       _M_allocate(size_t __n)
00440       { return _M_impl.allocate((__n + int(_S_word_bit) - 1)
00441                 / int(_S_word_bit)); }
00442 
00443       void
00444       _M_deallocate()
00445       {
00446     if (_M_impl._M_start._M_p)
00447       _M_impl.deallocate(_M_impl._M_start._M_p,
00448                  _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
00449       }
00450     };
00451 
00452 _GLIBCXX_END_NESTED_NAMESPACE
00453 
00454 // Declare a partial specialization of vector<T, Alloc>.
00455 #include <bits/stl_vector.h>
00456 
00457 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
00458 
00459   /**
00460    *  @brief  A specialization of vector for booleans which offers fixed time
00461    *  access to individual elements in any order.
00462    *
00463    *  Note that vector<bool> does not actually meet the requirements for being
00464    *  a container.  This is because the reference and pointer types are not
00465    *  really references and pointers to bool.  See DR96 for details.  @see
00466    *  vector for function documentation.
00467    *
00468    *  @ingroup Containers
00469    *  @ingroup Sequences
00470    *
00471    *  In some terminology a %vector can be described as a dynamic
00472    *  C-style array, it offers fast and efficient access to individual
00473    *  elements in any order and saves the user from worrying about
00474    *  memory and size allocation.  Subscripting ( @c [] ) access is
00475    *  also provided as with C-style arrays.
00476   */
00477 template<typename _Alloc>
00478   class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
00479   {
00480     typedef _Bvector_base<_Alloc>            _Base;
00481 
00482   public:
00483     typedef bool                                         value_type;
00484     typedef size_t                                       size_type;
00485     typedef ptrdiff_t                                    difference_type;
00486     typedef _Bit_reference                               reference;
00487     typedef bool                                         const_reference;
00488     typedef _Bit_reference*                              pointer;
00489     typedef const bool*                                  const_pointer;
00490     typedef _Bit_iterator                                iterator;
00491     typedef _Bit_const_iterator                          const_iterator;
00492     typedef std::reverse_iterator<const_iterator>        const_reverse_iterator;
00493     typedef std::reverse_iterator<iterator>              reverse_iterator;
00494     typedef _Alloc                               allocator_type;
00495 
00496     allocator_type get_allocator() const
00497     { return _Base::get_allocator(); }
00498 
00499   protected:
00500     using _Base::_M_allocate;
00501     using _Base::_M_deallocate;
00502     using _Base::_M_get_Bit_allocator;
00503 
00504   public:
00505     vector()
00506     : _Base() { }
00507 
00508     explicit
00509     vector(const allocator_type& __a)
00510     : _Base(__a) { }
00511 
00512     explicit
00513     vector(size_type __n, const bool& __value = bool(), 
00514        const allocator_type& __a = allocator_type())
00515     : _Base(__a)
00516     {
00517       _M_initialize(__n);
00518       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, 
00519         __value ? ~0 : 0);
00520     }
00521 
00522     vector(const vector& __x)
00523     : _Base(__x._M_get_Bit_allocator())
00524     {
00525       _M_initialize(__x.size());
00526       _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start);
00527     }
00528 
00529 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00530     vector(vector&& __x)
00531     : _Base(std::forward<_Base>(__x)) { }
00532 #endif
00533 
00534     template<typename _InputIterator>
00535       vector(_InputIterator __first, _InputIterator __last,
00536          const allocator_type& __a = allocator_type())
00537       : _Base(__a)
00538       {
00539     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00540     _M_initialize_dispatch(__first, __last, _Integral());
00541       }
00542 
00543     ~vector() { }
00544 
00545     vector&
00546     operator=(const vector& __x)
00547     {
00548       if (&__x == this)
00549     return *this;
00550       if (__x.size() > capacity())
00551     {
00552       this->_M_deallocate();
00553       _M_initialize(__x.size());
00554     }
00555       this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
00556                         begin());
00557       return *this;
00558     }
00559 
00560 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00561     vector&
00562     operator=(vector&& __x)
00563     {
00564       // NB: DR 675.
00565       this->clear();
00566       this->swap(__x); 
00567       return *this;
00568     }
00569 #endif
00570 
00571     // assign(), a generalized assignment member function.  Two
00572     // versions: one that takes a count, and one that takes a range.
00573     // The range version is a member template, so we dispatch on whether
00574     // or not the type is an integer.
00575     void
00576     assign(size_type __n, const bool& __x)
00577     { _M_fill_assign(__n, __x); }
00578 
00579     template<typename _InputIterator>
00580       void
00581       assign(_InputIterator __first, _InputIterator __last)
00582       {
00583     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00584     _M_assign_dispatch(__first, __last, _Integral());
00585       }
00586 
00587     iterator
00588     begin()
00589     { return this->_M_impl._M_start; }
00590 
00591     const_iterator
00592     begin() const
00593     { return this->_M_impl._M_start; }
00594 
00595     iterator
00596     end()
00597     { return this->_M_impl._M_finish; }
00598 
00599     const_iterator
00600     end() const
00601     { return this->_M_impl._M_finish; }
00602 
00603     reverse_iterator
00604     rbegin()
00605     { return reverse_iterator(end()); }
00606 
00607     const_reverse_iterator
00608     rbegin() const
00609     { return const_reverse_iterator(end()); }
00610 
00611     reverse_iterator
00612     rend()
00613     { return reverse_iterator(begin()); }
00614 
00615     const_reverse_iterator
00616     rend() const
00617     { return const_reverse_iterator(begin()); }
00618 
00619 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00620     const_iterator
00621     cbegin() const
00622     { return this->_M_impl._M_start; }
00623 
00624     const_iterator
00625     cend() const
00626     { return this->_M_impl._M_finish; }
00627 
00628     const_reverse_iterator
00629     crbegin() const
00630     { return const_reverse_iterator(end()); }
00631 
00632     const_reverse_iterator
00633     crend() const
00634     { return const_reverse_iterator(begin()); }
00635 #endif
00636 
00637     size_type
00638     size() const
00639     { return size_type(end() - begin()); }
00640 
00641     size_type
00642     max_size() const
00643     {
00644       const size_type __isize =
00645     __gnu_cxx::__numeric_traits<difference_type>::__max
00646     - int(_S_word_bit) + 1;
00647       const size_type __asize = _M_get_Bit_allocator().max_size();
00648       return (__asize <= __isize / int(_S_word_bit)
00649           ? __asize * int(_S_word_bit) : __isize);
00650     }
00651 
00652     size_type
00653     capacity() const
00654     { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
00655                - begin()); }
00656 
00657     bool
00658     empty() const
00659     { return begin() == end(); }
00660 
00661     reference
00662     operator[](size_type __n)
00663     {
00664       return *iterator(this->_M_impl._M_start._M_p
00665                + __n / int(_S_word_bit), __n % int(_S_word_bit));
00666     }
00667 
00668     const_reference
00669     operator[](size_type __n) const
00670     {
00671       return *const_iterator(this->_M_impl._M_start._M_p
00672                  + __n / int(_S_word_bit), __n % int(_S_word_bit));
00673     }
00674 
00675   protected:
00676     void
00677     _M_range_check(size_type __n) const
00678     {
00679       if (__n >= this->size())
00680         __throw_out_of_range(__N("vector<bool>::_M_range_check"));
00681     }
00682 
00683   public:
00684     reference
00685     at(size_type __n)
00686     { _M_range_check(__n); return (*this)[__n]; }
00687 
00688     const_reference
00689     at(size_type __n) const
00690     { _M_range_check(__n); return (*this)[__n]; }
00691 
00692     void
00693     reserve(size_type __n);
00694 
00695     reference
00696     front()
00697     { return *begin(); }
00698 
00699     const_reference
00700     front() const
00701     { return *begin(); }
00702 
00703     reference
00704     back()
00705     { return *(end() - 1); }
00706 
00707     const_reference
00708     back() const
00709     { return *(end() - 1); }
00710 
00711     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00712     // DR 464. Suggestion for new member functions in standard containers.
00713     // N.B. DR 464 says nothing about vector<bool> but we need something
00714     // here due to the way we are implementing DR 464 in the debug-mode
00715     // vector class.
00716     void
00717     data() { }
00718 
00719     void
00720     push_back(bool __x)
00721     {
00722       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
00723         *this->_M_impl._M_finish++ = __x;
00724       else
00725         _M_insert_aux(end(), __x);
00726     }
00727 
00728     void
00729 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00730     swap(vector&& __x)
00731 #else
00732     swap(vector& __x)
00733 #endif
00734     {
00735       std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
00736       std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
00737       std::swap(this->_M_impl._M_end_of_storage, 
00738         __x._M_impl._M_end_of_storage);
00739 
00740       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00741       // 431. Swapping containers with unequal allocators.
00742       std::__alloc_swap<typename _Base::_Bit_alloc_type>::
00743     _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator());
00744     }
00745 
00746     // [23.2.5]/1, third-to-last entry in synopsis listing
00747     static void
00748     swap(reference __x, reference __y)
00749     {
00750       bool __tmp = __x;
00751       __x = __y;
00752       __y = __tmp;
00753     }
00754 
00755     iterator
00756     insert(iterator __position, const bool& __x = bool())
00757     {
00758       const difference_type __n = __position - begin();
00759       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
00760       && __position == end())
00761         *this->_M_impl._M_finish++ = __x;
00762       else
00763         _M_insert_aux(__position, __x);
00764       return begin() + __n;
00765     }
00766 
00767     template<typename _InputIterator>
00768       void
00769       insert(iterator __position,
00770          _InputIterator __first, _InputIterator __last)
00771       {
00772     typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00773     _M_insert_dispatch(__position, __first, __last, _Integral());
00774       }
00775 
00776     void
00777     insert(iterator __position, size_type __n, const bool& __x)
00778     { _M_fill_insert(__position, __n, __x); }
00779 
00780     void
00781     pop_back()
00782     { --this->_M_impl._M_finish; }
00783 
00784     iterator
00785     erase(iterator __position)
00786     {
00787       if (__position + 1 != end())
00788         std::copy(__position + 1, end(), __position);
00789       --this->_M_impl._M_finish;
00790       return __position;
00791     }
00792 
00793     iterator
00794     erase(iterator __first, iterator __last)
00795     {
00796       _M_erase_at_end(std::copy(__last, end(), __first));
00797       return __first;
00798     }
00799 
00800     void
00801     resize(size_type __new_size, bool __x = bool())
00802     {
00803       if (__new_size < size())
00804         _M_erase_at_end(begin() + difference_type(__new_size));
00805       else
00806         insert(end(), __new_size - size(), __x);
00807     }
00808 
00809     void
00810     flip()
00811     {
00812       for (_Bit_type * __p = this->_M_impl._M_start._M_p;
00813        __p != this->_M_impl._M_end_of_storage; ++__p)
00814         *__p = ~*__p;
00815     }
00816 
00817     void
00818     clear()
00819     { _M_erase_at_end(begin()); }
00820 
00821    
00822   protected:
00823     // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
00824     iterator
00825     _M_copy_aligned(const_iterator __first, const_iterator __last,
00826             iterator __result)
00827     {
00828       _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
00829       return std::copy(const_iterator(__last._M_p, 0), __last,
00830                iterator(__q, 0));
00831     }
00832 
00833     void
00834     _M_initialize(size_type __n)
00835     {
00836       _Bit_type* __q = this->_M_allocate(__n);
00837       this->_M_impl._M_end_of_storage = (__q
00838                      + ((__n + int(_S_word_bit) - 1)
00839                         / int(_S_word_bit)));
00840       this->_M_impl._M_start = iterator(__q, 0);
00841       this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
00842     }
00843 
00844     // Check whether it's an integral type.  If so, it's not an iterator.
00845 
00846     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00847     // 438. Ambiguity in the "do the right thing" clause
00848     template<typename _Integer>
00849       void
00850       _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
00851       {
00852     _M_initialize(static_cast<size_type>(__n));
00853     std::fill(this->_M_impl._M_start._M_p, 
00854           this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00855       }
00856 
00857     template<typename _InputIterator>
00858       void 
00859       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
00860                  __false_type)
00861       { _M_initialize_range(__first, __last, 
00862                 std::__iterator_category(__first)); }
00863 
00864     template<typename _InputIterator>
00865       void
00866       _M_initialize_range(_InputIterator __first, _InputIterator __last,
00867               std::input_iterator_tag)
00868       {
00869     for (; __first != __last; ++__first)
00870       push_back(*__first);
00871       }
00872 
00873     template<typename _ForwardIterator>
00874       void
00875       _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
00876               std::forward_iterator_tag)
00877       {
00878     const size_type __n = std::distance(__first, __last);
00879     _M_initialize(__n);
00880     std::copy(__first, __last, this->_M_impl._M_start);
00881       }
00882 
00883     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00884     // 438. Ambiguity in the "do the right thing" clause
00885     template<typename _Integer>
00886       void
00887       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00888       { _M_fill_assign(__n, __val); }
00889 
00890     template<class _InputIterator>
00891       void
00892       _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
00893              __false_type)
00894       { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
00895 
00896     void
00897     _M_fill_assign(size_t __n, bool __x)
00898     {
00899       if (__n > size())
00900     {
00901       std::fill(this->_M_impl._M_start._M_p, 
00902             this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00903       insert(end(), __n - size(), __x);
00904     }
00905       else
00906     {
00907       _M_erase_at_end(begin() + __n);
00908       std::fill(this->_M_impl._M_start._M_p, 
00909             this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00910     }
00911     }
00912 
00913     template<typename _InputIterator>
00914       void
00915       _M_assign_aux(_InputIterator __first, _InputIterator __last,
00916             std::input_iterator_tag)
00917       {
00918     iterator __cur = begin();
00919     for (; __first != __last && __cur != end(); ++__cur, ++__first)
00920       *__cur = *__first;
00921     if (__first == __last)
00922       _M_erase_at_end(__cur);
00923     else
00924       insert(end(), __first, __last);
00925       }
00926     
00927     template<typename _ForwardIterator>
00928       void
00929       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00930             std::forward_iterator_tag)
00931       {
00932     const size_type __len = std::distance(__first, __last);
00933     if (__len < size())
00934       _M_erase_at_end(std::copy(__first, __last, begin()));
00935     else
00936       {
00937         _ForwardIterator __mid = __first;
00938         std::advance(__mid, size());
00939         std::copy(__first, __mid, begin());
00940         insert(end(), __mid, __last);
00941       }
00942       }
00943 
00944     // Check whether it's an integral type.  If so, it's not an iterator.
00945 
00946     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00947     // 438. Ambiguity in the "do the right thing" clause
00948     template<typename _Integer>
00949       void
00950       _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
00951              __true_type)
00952       { _M_fill_insert(__pos, __n, __x); }
00953 
00954     template<typename _InputIterator>
00955       void
00956       _M_insert_dispatch(iterator __pos,
00957              _InputIterator __first, _InputIterator __last,
00958              __false_type)
00959       { _M_insert_range(__pos, __first, __last,
00960             std::__iterator_category(__first)); }
00961 
00962     void
00963     _M_fill_insert(iterator __position, size_type __n, bool __x);
00964 
00965     template<typename _InputIterator>
00966       void
00967       _M_insert_range(iterator __pos, _InputIterator __first, 
00968               _InputIterator __last, std::input_iterator_tag)
00969       {
00970     for (; __first != __last; ++__first)
00971       {
00972         __pos = insert(__pos, *__first);
00973         ++__pos;
00974       }
00975       }
00976 
00977     template<typename _ForwardIterator>
00978       void
00979       _M_insert_range(iterator __position, _ForwardIterator __first, 
00980               _ForwardIterator __last, std::forward_iterator_tag);
00981 
00982     void
00983     _M_insert_aux(iterator __position, bool __x);
00984 
00985     size_type
00986     _M_check_len(size_type __n, const char* __s) const
00987     {
00988       if (max_size() - size() < __n)
00989     __throw_length_error(__N(__s));
00990 
00991       const size_type __len = size() + std::max(size(), __n);
00992       return (__len < size() || __len > max_size()) ? max_size() : __len;
00993     }
00994 
00995     void
00996     _M_erase_at_end(iterator __pos)
00997     { this->_M_impl._M_finish = __pos; }
00998   };
00999 
01000 _GLIBCXX_END_NESTED_NAMESPACE
01001 
01002 #endif

Generated on Wed Dec 31 12:49:00 2008 for libstdc++ by  doxygen 1.5.6