home *** CD-ROM | disk | FTP | other *** search
/ Beginning C++ Through Gam…rogramming (2nd Edition) / BCGP2E.ISO / bloodshed / devcpp-4.9.9.2_setup.exe / stl_bvector.h < prev    next >
C/C++ Source or Header  |  2005-01-29  |  24KB  |  877 lines

  1. // vector<bool> specialization -*- C++ -*-
  2.  
  3. // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the
  7. // terms of the GNU General Public License as published by the
  8. // Free Software Foundation; either version 2, or (at your option)
  9. // any later version.
  10.  
  11. // This library is distributed in the hope that it will be useful,
  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. // GNU General Public License for more details.
  15.  
  16. // You should have received a copy of the GNU General Public License along
  17. // with this library; see the file COPYING.  If not, write to the Free
  18. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19. // USA.
  20.  
  21. // As a special exception, you may use this file as part of a free software
  22. // library without restriction.  Specifically, if other files instantiate
  23. // templates or use macros or inline functions from this file, or you compile
  24. // this file and link it with other files to produce an executable, this
  25. // file does not by itself cause the resulting executable to be covered by
  26. // the GNU General Public License.  This exception does not however
  27. // invalidate any other reasons why the executable file might be covered by
  28. // the GNU General Public License.
  29.  
  30. /*
  31.  *
  32.  * Copyright (c) 1994
  33.  * Hewlett-Packard Company
  34.  *
  35.  * Permission to use, copy, modify, distribute and sell this software
  36.  * and its documentation for any purpose is hereby granted without fee,
  37.  * provided that the above copyright notice appear in all copies and
  38.  * that both that copyright notice and this permission notice appear
  39.  * in supporting documentation.  Hewlett-Packard Company makes no
  40.  * representations about the suitability of this software for any
  41.  * purpose.  It is provided "as is" without express or implied warranty.
  42.  *
  43.  *
  44.  * Copyright (c) 1996-1999
  45.  * Silicon Graphics Computer Systems, Inc.
  46.  *
  47.  * Permission to use, copy, modify, distribute and sell this software
  48.  * and its documentation for any purpose is hereby granted without fee,
  49.  * provided that the above copyright notice appear in all copies and
  50.  * that both that copyright notice and this permission notice appear
  51.  * in supporting documentation.  Silicon Graphics makes no
  52.  * representations about the suitability of this software for any
  53.  * purpose.  It is provided "as is" without express or implied warranty.
  54.  */
  55.  
  56. /** @file stl_bvector.h
  57.  *  This is an internal header file, included by other library headers.
  58.  *  You should not attempt to use it directly.
  59.  */
  60.  
  61. #ifndef _BVECTOR_H
  62. #define _BVECTOR_H 1
  63.  
  64. namespace _GLIBCXX_STD
  65. {
  66.   typedef unsigned long _Bit_type;
  67.   enum { _S_word_bit = int(CHAR_BIT * sizeof(_Bit_type)) };
  68.  
  69.   struct _Bit_reference
  70.   {
  71.     _Bit_type * _M_p;
  72.     _Bit_type _M_mask;
  73.  
  74.     _Bit_reference(_Bit_type * __x, _Bit_type __y)
  75.     : _M_p(__x), _M_mask(__y) { }
  76.  
  77.     _Bit_reference() : _M_p(0), _M_mask(0) { }
  78.  
  79.     operator bool() const { return !!(*_M_p & _M_mask); }
  80.  
  81.     _Bit_reference&
  82.     operator=(bool __x)
  83.     {
  84.       if (__x)
  85.     *_M_p |= _M_mask;
  86.       else
  87.     *_M_p &= ~_M_mask;
  88.       return *this;
  89.     }
  90.  
  91.     _Bit_reference&
  92.     operator=(const _Bit_reference& __x)
  93.     { return *this = bool(__x); }
  94.  
  95.     bool
  96.     operator==(const _Bit_reference& __x) const
  97.     { return bool(*this) == bool(__x); }
  98.  
  99.     bool
  100.     operator<(const _Bit_reference& __x) const
  101.     { return !bool(*this) && bool(__x); }
  102.  
  103.     void
  104.     flip() { *_M_p ^= _M_mask; }
  105.   };
  106.  
  107.   struct _Bit_iterator_base : public iterator<random_access_iterator_tag, bool>
  108.   {
  109.     _Bit_type * _M_p;
  110.     unsigned int _M_offset;
  111.  
  112.     _Bit_iterator_base(_Bit_type * __x, unsigned int __y)
  113.     : _M_p(__x), _M_offset(__y) { }
  114.  
  115.     void
  116.     _M_bump_up()
  117.     {
  118.       if (_M_offset++ == _S_word_bit - 1)
  119.     {
  120.       _M_offset = 0;
  121.       ++_M_p;
  122.     }
  123.     }
  124.  
  125.     void
  126.     _M_bump_down()
  127.     {
  128.       if (_M_offset-- == 0)
  129.     {
  130.       _M_offset = _S_word_bit - 1;
  131.       --_M_p;
  132.     }
  133.     }
  134.  
  135.     void
  136.     _M_incr(ptrdiff_t __i)
  137.     {
  138.       difference_type __n = __i + _M_offset;
  139.       _M_p += __n / _S_word_bit;
  140.       __n = __n % _S_word_bit;
  141.       if (__n < 0)
  142.     {
  143.       _M_offset = static_cast<unsigned int>(__n + _S_word_bit);
  144.       --_M_p;
  145.     }
  146.       else
  147.     _M_offset = static_cast<unsigned int>(__n);
  148.     }
  149.  
  150.     bool
  151.     operator==(const _Bit_iterator_base& __i) const
  152.     { return _M_p == __i._M_p && _M_offset == __i._M_offset; }
  153.  
  154.     bool
  155.     operator<(const _Bit_iterator_base& __i) const
  156.     {
  157.       return _M_p < __i._M_p
  158.          || (_M_p == __i._M_p && _M_offset < __i._M_offset);
  159.     }
  160.  
  161.     bool
  162.     operator!=(const _Bit_iterator_base& __i) const
  163.     { return !(*this == __i); }
  164.  
  165.     bool
  166.     operator>(const _Bit_iterator_base& __i) const
  167.     { return __i < *this; }
  168.  
  169.     bool
  170.     operator<=(const _Bit_iterator_base& __i) const
  171.     { return !(__i < *this); }
  172.  
  173.     bool
  174.     operator>=(const _Bit_iterator_base& __i) const
  175.     { return !(*this < __i); }
  176.   };
  177.  
  178.   inline ptrdiff_t
  179.   operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
  180.   {
  181.     return _S_word_bit * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset;
  182.   }
  183.  
  184.   struct _Bit_iterator : public _Bit_iterator_base
  185.   {
  186.     typedef _Bit_reference  reference;
  187.     typedef _Bit_reference* pointer;
  188.     typedef _Bit_iterator   iterator;
  189.  
  190.     _Bit_iterator() : _Bit_iterator_base(0, 0) { }
  191.     _Bit_iterator(_Bit_type * __x, unsigned int __y)
  192.     : _Bit_iterator_base(__x, __y) { }
  193.  
  194.     reference
  195.     operator*() const { return reference(_M_p, 1UL << _M_offset); }
  196.  
  197.     iterator&
  198.     operator++()
  199.     {
  200.       _M_bump_up();
  201.       return *this;
  202.     }
  203.  
  204.     iterator
  205.     operator++(int)
  206.     {
  207.       iterator __tmp = *this;
  208.       _M_bump_up();
  209.       return __tmp;
  210.     }
  211.  
  212.     iterator&
  213.     operator--()
  214.     {
  215.       _M_bump_down();
  216.       return *this;
  217.     }
  218.  
  219.     iterator
  220.     operator--(int)
  221.     {
  222.       iterator __tmp = *this;
  223.       _M_bump_down();
  224.       return __tmp;
  225.     }
  226.  
  227.     iterator&
  228.     operator+=(difference_type __i)
  229.     {
  230.       _M_incr(__i);
  231.       return *this;
  232.     }
  233.  
  234.     iterator&
  235.     operator-=(difference_type __i)
  236.     {
  237.       *this += -__i;
  238.       return *this;
  239.     }
  240.  
  241.     iterator
  242.     operator+(difference_type __i) const
  243.     {
  244.       iterator __tmp = *this;
  245.       return __tmp += __i;
  246.     }
  247.  
  248.     iterator
  249.     operator-(difference_type __i) const
  250.     {
  251.       iterator __tmp = *this;
  252.       return __tmp -= __i;
  253.     }
  254.  
  255.     reference
  256.     operator[](difference_type __i)
  257.     { return *(*this + __i); }
  258.   };
  259.  
  260.   inline _Bit_iterator
  261.   operator+(ptrdiff_t __n, const _Bit_iterator& __x) { return __x + __n; }
  262.  
  263.  
  264.   struct _Bit_const_iterator : public _Bit_iterator_base
  265.   {
  266.     typedef bool                 reference;
  267.     typedef bool                 const_reference;
  268.     typedef const bool*          pointer;
  269.     typedef _Bit_const_iterator  const_iterator;
  270.  
  271.     _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
  272.     _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
  273.     : _Bit_iterator_base(__x, __y) { }
  274.     _Bit_const_iterator(const _Bit_iterator& __x)
  275.     : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
  276.  
  277.     const_reference
  278.     operator*() const
  279.     { return _Bit_reference(_M_p, 1UL << _M_offset); }
  280.  
  281.     const_iterator&
  282.     operator++()
  283.     {
  284.       _M_bump_up();
  285.       return *this;
  286.     }
  287.  
  288.     const_iterator
  289.     operator++(int)
  290.     {
  291.       const_iterator __tmp = *this;
  292.       _M_bump_up();
  293.       return __tmp;
  294.     }
  295.  
  296.     const_iterator&
  297.     operator--()
  298.     {
  299.       _M_bump_down();
  300.       return *this;
  301.     }
  302.  
  303.     const_iterator
  304.     operator--(int)
  305.     {
  306.       const_iterator __tmp = *this;
  307.       _M_bump_down();
  308.       return __tmp;
  309.     }
  310.  
  311.     const_iterator&
  312.     operator+=(difference_type __i)
  313.     {
  314.       _M_incr(__i);
  315.       return *this;
  316.     }
  317.  
  318.     const_iterator&
  319.     operator-=(difference_type __i)
  320.     {
  321.       *this += -__i;
  322.       return *this;
  323.     }
  324.  
  325.     const_iterator 
  326.     operator+(difference_type __i) const {
  327.       const_iterator __tmp = *this;
  328.       return __tmp += __i;
  329.     }
  330.  
  331.     const_iterator
  332.     operator-(difference_type __i) const
  333.     {
  334.       const_iterator __tmp = *this;
  335.       return __tmp -= __i;
  336.     }
  337.  
  338.     const_reference
  339.     operator[](difference_type __i)
  340.     { return *(*this + __i); }
  341.   };
  342.  
  343.   inline _Bit_const_iterator
  344.   operator+(ptrdiff_t __n, const _Bit_const_iterator& __x)
  345.   { return __x + __n; }
  346.  
  347.   template<class _Alloc>
  348.     class _Bvector_base
  349.     {
  350.       typedef typename _Alloc::template rebind<_Bit_type>::other
  351.         _Bit_alloc_type;
  352.       
  353.       struct _Bvector_impl : public _Bit_alloc_type
  354.       {
  355.     _Bit_iterator     _M_start;
  356.     _Bit_iterator     _M_finish;
  357.     _Bit_type*     _M_end_of_storage;
  358.     _Bvector_impl(const _Bit_alloc_type& __a)
  359.     : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
  360.     { }
  361.       };
  362.  
  363.     public:
  364.       typedef _Alloc allocator_type;
  365.  
  366.       allocator_type
  367.       get_allocator() const
  368.       { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
  369.  
  370.       _Bvector_base(const allocator_type& __a) : _M_impl(__a) { }
  371.  
  372.       ~_Bvector_base() { this->_M_deallocate(); }
  373.  
  374.     protected:
  375.       _Bvector_impl _M_impl;
  376.  
  377.       _Bit_type*
  378.       _M_allocate(size_t __n)
  379.       { return _M_impl.allocate((__n + _S_word_bit - 1) / _S_word_bit); }
  380.  
  381.       void
  382.       _M_deallocate()
  383.       {
  384.     if (_M_impl._M_start._M_p)
  385.       _M_impl.deallocate(_M_impl._M_start._M_p,
  386.                 _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
  387.       }
  388.     };
  389. } // namespace std
  390.  
  391. // Declare a partial specialization of vector<T, Alloc>.
  392. #include <bits/stl_vector.h>
  393.  
  394. namespace _GLIBCXX_STD
  395. {
  396.   /**
  397.    *  @brief  A specialization of vector for booleans which offers fixed time
  398.    *  access to individual elements in any order.
  399.    *
  400.    *  Note that vector<bool> does not actually meet the requirements for being
  401.    *  a container.  This is because the reference and pointer types are not
  402.    *  really references and pointers to bool.  See DR96 for details.  @see
  403.    *  vector for function documentation.
  404.    *
  405.    *  @ingroup Containers
  406.    *  @ingroup Sequences
  407.    *
  408.    *  In some terminology a %vector can be described as a dynamic
  409.    *  C-style array, it offers fast and efficient access to individual
  410.    *  elements in any order and saves the user from worrying about
  411.    *  memory and size allocation.  Subscripting ( @c [] ) access is
  412.    *  also provided as with C-style arrays.
  413.   */
  414. template<typename _Alloc>
  415.   class vector<bool, _Alloc> : public _Bvector_base<_Alloc>
  416.   {
  417.   public:
  418.     typedef bool value_type;
  419.     typedef size_t size_type;
  420.     typedef ptrdiff_t difference_type;
  421.     typedef _Bit_reference reference;
  422.     typedef bool const_reference;
  423.     typedef _Bit_reference* pointer;
  424.     typedef const bool* const_pointer;
  425.  
  426.     typedef _Bit_iterator                iterator;
  427.     typedef _Bit_const_iterator          const_iterator;
  428.  
  429.     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  430.     typedef std::reverse_iterator<iterator> reverse_iterator;
  431.  
  432.     typedef typename _Bvector_base<_Alloc>::allocator_type allocator_type;
  433.  
  434.     allocator_type get_allocator() const
  435.     { return _Bvector_base<_Alloc>::get_allocator(); }
  436.  
  437.   protected:
  438.     using _Bvector_base<_Alloc>::_M_allocate;
  439.     using _Bvector_base<_Alloc>::_M_deallocate;
  440.  
  441.   protected:
  442.     void _M_initialize(size_type __n)
  443.     {
  444.       _Bit_type* __q = this->_M_allocate(__n);
  445.       this->_M_impl._M_end_of_storage = __q 
  446.                                    + (__n + _S_word_bit - 1) / _S_word_bit;
  447.       this->_M_impl._M_start = iterator(__q, 0);
  448.       this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
  449.     }
  450.  
  451.     void _M_insert_aux(iterator __position, bool __x)
  452.     {
  453.       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
  454.     {
  455.       std::copy_backward(__position, this->_M_impl._M_finish, 
  456.                  this->_M_impl._M_finish + 1);
  457.       *__position = __x;
  458.       ++this->_M_impl._M_finish;
  459.     }
  460.       else
  461.     {
  462.       const size_type __len = size() ? 2 * size()
  463.                                      : static_cast<size_type>(_S_word_bit);
  464.       _Bit_type * __q = this->_M_allocate(__len);
  465.       iterator __i = std::copy(begin(), __position, iterator(__q, 0));
  466.       *__i++ = __x;
  467.       this->_M_impl._M_finish = std::copy(__position, end(), __i);
  468.       this->_M_deallocate();
  469.       this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1)
  470.                     / _S_word_bit;
  471.       this->_M_impl._M_start = iterator(__q, 0);
  472.     }
  473.     }
  474.  
  475.     template<class _InputIterator>
  476.     void _M_initialize_range(_InputIterator __first, _InputIterator __last,
  477.                              input_iterator_tag)
  478.     {
  479.       this->_M_impl._M_start = iterator();
  480.       this->_M_impl._M_finish = iterator();
  481.       this->_M_impl._M_end_of_storage = 0;
  482.       for ( ; __first != __last; ++__first)
  483.         push_back(*__first);
  484.     }
  485.  
  486.     template<class _ForwardIterator>
  487.     void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
  488.                              forward_iterator_tag)
  489.     {
  490.       const size_type __n = std::distance(__first, __last);
  491.       _M_initialize(__n);
  492.       std::copy(__first, __last, this->_M_impl._M_start);
  493.     }
  494.  
  495.     template<class _InputIterator>
  496.     void _M_insert_range(iterator __pos, _InputIterator __first, 
  497.              _InputIterator __last, input_iterator_tag)
  498.     {
  499.       for ( ; __first != __last; ++__first)
  500.     {
  501.       __pos = insert(__pos, *__first);
  502.       ++__pos;
  503.     }
  504.     }
  505.  
  506.     template<class _ForwardIterator>
  507.     void _M_insert_range(iterator __position, _ForwardIterator __first, 
  508.              _ForwardIterator __last, forward_iterator_tag)
  509.     {
  510.       if (__first != __last)
  511.     {
  512.       size_type __n = std::distance(__first, __last);
  513.       if (capacity() - size() >= __n)
  514.         {
  515.           std::copy_backward(__position, end(),
  516.                    this->_M_impl._M_finish + difference_type(__n));
  517.           std::copy(__first, __last, __position);
  518.           this->_M_impl._M_finish += difference_type(__n);
  519.         }
  520.       else
  521.         {
  522.           const size_type __len = size() + std::max(size(), __n);
  523.           _Bit_type * __q = this->_M_allocate(__len);
  524.           iterator __i = std::copy(begin(), __position, iterator(__q, 0));
  525.           __i = std::copy(__first, __last, __i);
  526.           this->_M_impl._M_finish = std::copy(__position, end(), __i);
  527.           this->_M_deallocate();
  528.           this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1)
  529.                                         / _S_word_bit;
  530.           this->_M_impl._M_start = iterator(__q, 0);
  531.         }
  532.     }
  533.     }
  534.  
  535.   public:
  536.     iterator begin()
  537.     { return this->_M_impl._M_start; }
  538.  
  539.     const_iterator begin() const
  540.     { return this->_M_impl._M_start; }
  541.  
  542.     iterator end()
  543.     { return this->_M_impl._M_finish; }
  544.  
  545.     const_iterator end() const
  546.     { return this->_M_impl._M_finish; }
  547.  
  548.     reverse_iterator rbegin()
  549.     { return reverse_iterator(end()); }
  550.  
  551.     const_reverse_iterator rbegin() const
  552.     { return const_reverse_iterator(end()); }
  553.  
  554.     reverse_iterator rend()
  555.     { return reverse_iterator(begin()); }
  556.  
  557.     const_reverse_iterator rend() const
  558.     { return const_reverse_iterator(begin()); }
  559.  
  560.     size_type size() const
  561.     { return size_type(end() - begin()); }
  562.  
  563.     size_type max_size() const
  564.     { return size_type(-1); }
  565.  
  566.     size_type capacity() const
  567.     { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
  568.                - begin()); }
  569.     bool empty() const
  570.     { return begin() == end(); }
  571.  
  572.     reference operator[](size_type __n)
  573.     { return *(begin() + difference_type(__n)); }
  574.  
  575.     const_reference operator[](size_type __n) const
  576.     { return *(begin() + difference_type(__n)); }
  577.  
  578.     void _M_range_check(size_type __n) const
  579.     {
  580.       if (__n >= this->size())
  581.         __throw_out_of_range(__N("vector<bool>::_M_range_check"));
  582.     }
  583.  
  584.     reference at(size_type __n)
  585.     { _M_range_check(__n); return (*this)[__n]; }
  586.  
  587.     const_reference at(size_type __n) const
  588.     { _M_range_check(__n); return (*this)[__n]; }
  589.  
  590.     explicit vector(const allocator_type& __a = allocator_type())
  591.       : _Bvector_base<_Alloc>(__a) { }
  592.  
  593.     vector(size_type __n, bool __value, 
  594.        const allocator_type& __a = allocator_type())
  595.     : _Bvector_base<_Alloc>(__a)
  596.     {
  597.       _M_initialize(__n);
  598.       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, 
  599.         __value ? ~0 : 0);
  600.     }
  601.  
  602.     explicit vector(size_type __n)
  603.     : _Bvector_base<_Alloc>(allocator_type())
  604.     {
  605.       _M_initialize(__n);
  606.       std::fill(this->_M_impl._M_start._M_p, 
  607.         this->_M_impl._M_end_of_storage, 0);
  608.     }
  609.  
  610.     vector(const vector& __x) : _Bvector_base<_Alloc>(__x.get_allocator())
  611.     {
  612.       _M_initialize(__x.size());
  613.       std::copy(__x.begin(), __x.end(), this->_M_impl._M_start);
  614.     }
  615.  
  616.     // Check whether it's an integral type.  If so, it's not an iterator.
  617.     template<class _Integer>
  618.     void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
  619.     {
  620.       _M_initialize(__n);
  621.       std::fill(this->_M_impl._M_start._M_p, 
  622.         this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
  623.     }
  624.  
  625.     template<class _InputIterator>
  626.       void 
  627.       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
  628.                  __false_type)
  629.       { _M_initialize_range(__first, __last, 
  630.                 std::__iterator_category(__first)); }
  631.  
  632.     template<class _InputIterator>
  633.       vector(_InputIterator __first, _InputIterator __last,
  634.          const allocator_type& __a = allocator_type())
  635.     : _Bvector_base<_Alloc>(__a)
  636.     {
  637.       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  638.       _M_initialize_dispatch(__first, __last, _Integral());
  639.     }
  640.  
  641.     ~vector() { }
  642.  
  643.     vector& operator=(const vector& __x)
  644.     {
  645.       if (&__x == this)
  646.     return *this;
  647.       if (__x.size() > capacity())
  648.     {
  649.       this->_M_deallocate();
  650.       _M_initialize(__x.size());
  651.     }
  652.       std::copy(__x.begin(), __x.end(), begin());
  653.       this->_M_impl._M_finish = begin() + difference_type(__x.size());
  654.       return *this;
  655.     }
  656.  
  657.     // assign(), a generalized assignment member function.  Two
  658.     // versions: one that takes a count, and one that takes a range.
  659.     // The range version is a member template, so we dispatch on whether
  660.     // or not the type is an integer.
  661.  
  662.     void _M_fill_assign(size_t __n, bool __x)
  663.     {
  664.       if (__n > size())
  665.     {
  666.       std::fill(this->_M_impl._M_start._M_p, 
  667.             this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
  668.       insert(end(), __n - size(), __x);
  669.     }
  670.       else
  671.     {
  672.       erase(begin() + __n, end());
  673.       std::fill(this->_M_impl._M_start._M_p, 
  674.             this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
  675.     }
  676.     }
  677.  
  678.     void assign(size_t __n, bool __x)
  679.     { _M_fill_assign(__n, __x); }
  680.  
  681.     template<class _InputIterator>
  682.     void assign(_InputIterator __first, _InputIterator __last)
  683.     {
  684.       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  685.       _M_assign_dispatch(__first, __last, _Integral());
  686.     }
  687.  
  688.     template<class _Integer>
  689.     void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
  690.     { _M_fill_assign((size_t) __n, (bool) __val); }
  691.  
  692.     template<class _InputIterator>
  693.     void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
  694.                 __false_type)
  695.     { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
  696.  
  697.     template<class _InputIterator>
  698.     void _M_assign_aux(_InputIterator __first, _InputIterator __last,
  699.                        input_iterator_tag)
  700.     {
  701.       iterator __cur = begin();
  702.       for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
  703.         *__cur = *__first;
  704.       if (__first == __last)
  705.         erase(__cur, end());
  706.       else
  707.         insert(end(), __first, __last);
  708.     }
  709.  
  710.     template<class _ForwardIterator>
  711.     void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
  712.                        forward_iterator_tag)
  713.     {
  714.       const size_type __len = std::distance(__first, __last);
  715.       if (__len < size())
  716.         erase(std::copy(__first, __last, begin()), end());
  717.       else
  718.     {
  719.       _ForwardIterator __mid = __first;
  720.       std::advance(__mid, size());
  721.       std::copy(__first, __mid, begin());
  722.       insert(end(), __mid, __last);
  723.     }
  724.     }
  725.  
  726.     void reserve(size_type __n)
  727.     {
  728.       if (__n > this->max_size())
  729.     __throw_length_error(__N("vector::reserve"));
  730.       if (this->capacity() < __n)
  731.     {
  732.       _Bit_type* __q = this->_M_allocate(__n);
  733.       this->_M_impl._M_finish = std::copy(begin(), end(), 
  734.                           iterator(__q, 0));
  735.       this->_M_deallocate();
  736.       this->_M_impl._M_start = iterator(__q, 0);
  737.       this->_M_impl._M_end_of_storage = __q + (__n + _S_word_bit - 1) / _S_word_bit;
  738.     }
  739.     }
  740.  
  741.     reference front()
  742.     { return *begin(); }
  743.  
  744.     const_reference front() const
  745.     { return *begin(); }
  746.  
  747.     reference back()
  748.     { return *(end() - 1); }
  749.  
  750.     const_reference back() const
  751.     { return *(end() - 1); }
  752.  
  753.     void push_back(bool __x)
  754.     {
  755.       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
  756.         *this->_M_impl._M_finish++ = __x;
  757.       else
  758.         _M_insert_aux(end(), __x);
  759.     }
  760.  
  761.     void swap(vector<bool, _Alloc>& __x)
  762.     {
  763.       std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
  764.       std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
  765.       std::swap(this->_M_impl._M_end_of_storage, 
  766.         __x._M_impl._M_end_of_storage);
  767.     }
  768.  
  769.     // [23.2.5]/1, third-to-last entry in synopsis listing
  770.     static void swap(reference __x, reference __y)
  771.     {
  772.       bool __tmp = __x;
  773.       __x = __y;
  774.       __y = __tmp;
  775.     }
  776.  
  777.     iterator insert(iterator __position, bool __x = bool())
  778.     {
  779.       const difference_type __n = __position - begin();
  780.       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
  781.       && __position == end())
  782.         *this->_M_impl._M_finish++ = __x;
  783.       else
  784.         _M_insert_aux(__position, __x);
  785.       return begin() + __n;
  786.     }
  787.  
  788.     // Check whether it's an integral type.  If so, it's not an iterator.
  789.  
  790.     template<class _Integer>
  791.     void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
  792.                             __true_type)
  793.     { _M_fill_insert(__pos, __n, __x); }
  794.  
  795.     template<class _InputIterator>
  796.     void _M_insert_dispatch(iterator __pos,
  797.                             _InputIterator __first, _InputIterator __last,
  798.                             __false_type)
  799.     { _M_insert_range(__pos, __first, __last,
  800.               std::__iterator_category(__first)); }
  801.  
  802.     template<class _InputIterator>
  803.     void insert(iterator __position,
  804.                 _InputIterator __first, _InputIterator __last)
  805.     {
  806.       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  807.       _M_insert_dispatch(__position, __first, __last, _Integral());
  808.     }
  809.  
  810.     void _M_fill_insert(iterator __position, size_type __n, bool __x)
  811.     {
  812.       if (__n == 0)
  813.     return;
  814.       if (capacity() - size() >= __n)
  815.     {
  816.       std::copy_backward(__position, end(),
  817.                  this->_M_impl._M_finish + difference_type(__n));
  818.       std::fill(__position, __position + difference_type(__n), __x);
  819.       this->_M_impl._M_finish += difference_type(__n);
  820.     }
  821.       else
  822.     {
  823.       const size_type __len = size() + std::max(size(), __n);
  824.       _Bit_type * __q = this->_M_allocate(__len);
  825.       iterator __i = std::copy(begin(), __position, iterator(__q, 0));
  826.       std::fill_n(__i, __n, __x);
  827.       this->_M_impl._M_finish = std::copy(__position, end(),
  828.                           __i + difference_type(__n));
  829.       this->_M_deallocate();
  830.       this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1)
  831.                                         / _S_word_bit;
  832.       this->_M_impl._M_start = iterator(__q, 0);
  833.     }
  834.     }
  835.  
  836.     void insert(iterator __position, size_type __n, bool __x)
  837.     { _M_fill_insert(__position, __n, __x); }
  838.  
  839.     void pop_back()
  840.     { --this->_M_impl._M_finish; }
  841.  
  842.     iterator erase(iterator __position)
  843.     {
  844.       if (__position + 1 != end())
  845.         std::copy(__position + 1, end(), __position);
  846.       --this->_M_impl._M_finish;
  847.       return __position;
  848.     }
  849.  
  850.     iterator erase(iterator __first, iterator __last)
  851.     {
  852.       this->_M_impl._M_finish = std::copy(__last, end(), __first);
  853.       return __first;
  854.     }
  855.  
  856.     void resize(size_type __new_size, bool __x = bool())
  857.     {
  858.       if (__new_size < size())
  859.         erase(begin() + difference_type(__new_size), end());
  860.       else
  861.         insert(end(), __new_size - size(), __x);
  862.     }
  863.  
  864.     void flip()
  865.     {
  866.       for (_Bit_type * __p = this->_M_impl._M_start._M_p;
  867.        __p != this->_M_impl._M_end_of_storage; ++__p)
  868.         *__p = ~*__p;
  869.     }
  870.  
  871.     void clear()
  872.     { erase(begin(), end()); }
  873.   };
  874. } // namespace std
  875.  
  876. #endif
  877.