stl_bvec.h
上传用户:nizebo
上传日期:2022-05-14
资源大小:882k
文件大小:27k
源码类别:

STL

开发平台:

Visual C++

  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996-1999
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  */
  26. /* NOTE: This is an internal header file, included by other STL headers.
  27.  *   You should not attempt to use it directly.
  28.  */
  29. #ifndef __SGI_STL_INTERNAL_BVECTOR_H
  30. #define __SGI_STL_INTERNAL_BVECTOR_H
  31. __STL_BEGIN_NAMESPACE 
  32. static const int __WORD_BIT = int(CHAR_BIT*sizeof(unsigned int));
  33. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  34. #pragma set woff 1174
  35. #pragma set woff 1375
  36. #endif
  37. struct _Bit_reference {
  38.   unsigned int* _M_p;
  39.   unsigned int _M_mask;
  40.   _Bit_reference(unsigned int* __x, unsigned int __y) 
  41.     : _M_p(__x), _M_mask(__y) {}
  42. public:
  43.   _Bit_reference() : _M_p(0), _M_mask(0) {}
  44.   operator bool() const { return !(!(*_M_p & _M_mask)); }
  45.   _Bit_reference& operator=(bool __x)
  46.   {
  47.     if (__x)  *_M_p |= _M_mask;
  48.     else      *_M_p &= ~_M_mask;
  49.     return *this;
  50.   }
  51.   _Bit_reference& operator=(const _Bit_reference& __x) 
  52.     { return *this = bool(__x); }
  53.   bool operator==(const _Bit_reference& __x) const
  54.     { return bool(*this) == bool(__x); }
  55.   bool operator<(const _Bit_reference& __x) const {
  56.     return !bool(*this) && bool(__x);
  57.   }
  58.   void flip() { *_M_p ^= _M_mask; }
  59. };
  60. inline void swap(_Bit_reference __x, _Bit_reference __y)
  61. {
  62.   bool __tmp = __x;
  63.   __x = __y;
  64.   __y = __tmp;
  65. }
  66. struct _Bit_iterator_base : public random_access_iterator<bool, ptrdiff_t> 
  67. {
  68.   unsigned int* _M_p;
  69.   unsigned int _M_offset;
  70.   _Bit_iterator_base(unsigned int* __x, unsigned int __y)
  71.     : _M_p(__x), _M_offset(__y) {}
  72.   void _M_bump_up() {
  73.     if (_M_offset++ == __WORD_BIT - 1) {
  74.       _M_offset = 0;
  75.       ++_M_p;
  76.     }
  77.   }
  78.   void _M_bump_down() {
  79.     if (_M_offset-- == 0) {
  80.       _M_offset = __WORD_BIT - 1;
  81.       --_M_p;
  82.     }
  83.   }
  84.   void _M_incr(ptrdiff_t __i) {
  85.     difference_type __n = __i + _M_offset;
  86.     _M_p += __n / __WORD_BIT;
  87.     __n = __n % __WORD_BIT;
  88.     if (__n < 0) {
  89.       _M_offset = (unsigned int) __n + __WORD_BIT;
  90.       --_M_p;
  91.     } else
  92.       _M_offset = (unsigned int) __n;
  93.   }
  94.   bool operator==(const _Bit_iterator_base& __i) const {
  95.     return _M_p == __i._M_p && _M_offset == __i._M_offset;
  96.   }
  97.   bool operator<(const _Bit_iterator_base& __i) const {
  98.     return _M_p < __i._M_p || (_M_p == __i._M_p && _M_offset < __i._M_offset);
  99.   }
  100.   bool operator!=(const _Bit_iterator_base& __i) const {
  101.     return !(*this == __i);
  102.   }
  103.   bool operator>(const _Bit_iterator_base& __i) const {
  104.     return __i < *this;
  105.   }
  106.   bool operator<=(const _Bit_iterator_base& __i) const {
  107.     return !(__i < *this); 
  108.   }
  109.   bool operator>=(const _Bit_iterator_base& __i) const {
  110.     return !(*this < __i);
  111.   }
  112. };
  113. inline ptrdiff_t
  114. operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) {
  115.   return __WORD_BIT * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset;
  116. }
  117. struct _Bit_iterator : public _Bit_iterator_base
  118. {
  119.   typedef _Bit_reference  reference;
  120.   typedef _Bit_reference* pointer;
  121.   typedef _Bit_iterator   iterator;
  122.   _Bit_iterator() : _Bit_iterator_base(0, 0) {}
  123.   _Bit_iterator(unsigned int* __x, unsigned int __y) 
  124.     : _Bit_iterator_base(__x, __y) {}
  125.   reference operator*() const { return reference(_M_p, 1U << _M_offset); }
  126.   iterator& operator++() {
  127.     _M_bump_up();
  128.     return *this;
  129.   }
  130.   iterator operator++(int) {
  131.     iterator __tmp = *this;
  132.     _M_bump_up();
  133.     return __tmp;
  134.   }
  135.   iterator& operator--() {
  136.     _M_bump_down();
  137.     return *this;
  138.   }
  139.   iterator operator--(int) {
  140.     iterator __tmp = *this;
  141.     _M_bump_down();
  142.     return __tmp;
  143.   }
  144.   iterator& operator+=(difference_type __i) {
  145.     _M_incr(__i);
  146.     return *this;
  147.   }
  148.   iterator& operator-=(difference_type __i) {
  149.     *this += -__i;
  150.     return *this;
  151.   }
  152.   iterator operator+(difference_type __i) const {
  153.     iterator __tmp = *this;
  154.     return __tmp += __i;
  155.   }
  156.   iterator operator-(difference_type __i) const {
  157.     iterator __tmp = *this;
  158.     return __tmp -= __i;
  159.   }
  160.   reference operator[](difference_type __i) { return *(*this + __i); }
  161. };
  162. inline _Bit_iterator 
  163. operator+(ptrdiff_t __n, const _Bit_iterator& __x) { return __x + __n; }
  164. struct _Bit_const_iterator : public _Bit_iterator_base
  165. {
  166.   typedef bool                 reference;
  167.   typedef bool                 const_reference;
  168.   typedef const bool*          pointer;
  169.   typedef _Bit_const_iterator  const_iterator;
  170.   _Bit_const_iterator() : _Bit_iterator_base(0, 0) {}
  171.   _Bit_const_iterator(unsigned int* __x, unsigned int __y) 
  172.     : _Bit_iterator_base(__x, __y) {}
  173.   _Bit_const_iterator(const _Bit_iterator& __x) 
  174.     : _Bit_iterator_base(__x._M_p, __x._M_offset) {}
  175.   const_reference operator*() const {
  176.     return _Bit_reference(_M_p, 1U << _M_offset);
  177.   }
  178.   const_iterator& operator++() {
  179.     _M_bump_up();
  180.     return *this;
  181.   }
  182.   const_iterator operator++(int) {
  183.     const_iterator __tmp = *this;
  184.     _M_bump_up();
  185.     return __tmp;
  186.   }
  187.   const_iterator& operator--() {
  188.     _M_bump_down();
  189.     return *this;
  190.   }
  191.   const_iterator operator--(int) {
  192.     const_iterator __tmp = *this;
  193.     _M_bump_down();
  194.     return __tmp;
  195.   }
  196.   const_iterator& operator+=(difference_type __i) {
  197.     _M_incr(__i);
  198.     return *this;
  199.   }
  200.   const_iterator& operator-=(difference_type __i) {
  201.     *this += -__i;
  202.     return *this;
  203.   }
  204.   const_iterator operator+(difference_type __i) const {
  205.     const_iterator __tmp = *this;
  206.     return __tmp += __i;
  207.   }
  208.   const_iterator operator-(difference_type __i) const {
  209.     const_iterator __tmp = *this;
  210.     return __tmp -= __i;
  211.   }
  212.   const_reference operator[](difference_type __i) { 
  213.     return *(*this + __i); 
  214.   }
  215. };
  216. inline _Bit_const_iterator 
  217. operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) { return __x + __n; }
  218. // Bit-vector base class, which encapsulates the difference between
  219. // old SGI-style allocators and standard-conforming allocators.
  220. #ifdef __STL_USE_STD_ALLOCATORS
  221. // Base class for ordinary allocators.
  222. template <class _Allocator, bool __is_static>
  223. class _Bvector_alloc_base {
  224. public:
  225.   typedef typename _Alloc_traits<bool, _Allocator>::allocator_type
  226.           allocator_type;
  227.   allocator_type get_allocator() const { return _M_data_allocator; }
  228.   _Bvector_alloc_base(const allocator_type& __a)
  229.     : _M_data_allocator(__a), _M_start(), _M_finish(), _M_end_of_storage(0) {}
  230. protected:
  231.   unsigned int* _M_bit_alloc(size_t __n) 
  232.     { return _M_data_allocator.allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
  233.   void _M_deallocate() {
  234.     if (_M_start._M_p)
  235.       _M_data_allocator.deallocate(_M_start._M_p, 
  236.                                    _M_end_of_storage - _M_start._M_p);
  237.   }  
  238.   typename _Alloc_traits<unsigned int, _Allocator>::allocator_type 
  239.           _M_data_allocator;
  240.   _Bit_iterator _M_start;
  241.   _Bit_iterator _M_finish;
  242.   unsigned int* _M_end_of_storage;
  243. };
  244. // Specialization for instanceless allocators.
  245. template <class _Allocator>
  246. class _Bvector_alloc_base<_Allocator, true> {
  247. public:
  248.   typedef typename _Alloc_traits<bool, _Allocator>::allocator_type
  249.           allocator_type;
  250.   allocator_type get_allocator() const { return allocator_type(); }
  251.   _Bvector_alloc_base(const allocator_type&)
  252.     : _M_start(), _M_finish(), _M_end_of_storage(0) {}
  253. protected:
  254.   typedef typename _Alloc_traits<unsigned int, _Allocator>::_Alloc_type
  255.           _Alloc_type;
  256.           
  257.   unsigned int* _M_bit_alloc(size_t __n) 
  258.     { return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
  259.   void _M_deallocate() {
  260.     if (_M_start._M_p)
  261.       _Alloc_type::deallocate(_M_start._M_p,
  262.                               _M_end_of_storage - _M_start._M_p);
  263.   }  
  264.   _Bit_iterator _M_start;
  265.   _Bit_iterator _M_finish;
  266.   unsigned int* _M_end_of_storage;
  267. };  
  268. template <class _Alloc>
  269. class _Bvector_base
  270.   : public _Bvector_alloc_base<_Alloc,
  271.                                _Alloc_traits<bool, _Alloc>::_S_instanceless>
  272. {
  273.   typedef _Bvector_alloc_base<_Alloc,
  274.                               _Alloc_traits<bool, _Alloc>::_S_instanceless>
  275.           _Base;
  276. public:
  277.   typedef typename _Base::allocator_type allocator_type;
  278.   _Bvector_base(const allocator_type& __a) : _Base(__a) {}
  279.   ~_Bvector_base() { _Base::_M_deallocate(); }
  280. };
  281. #else /* __STL_USE_STD_ALLOCATORS */
  282. template <class _Alloc>
  283. class _Bvector_base
  284. {
  285. public:
  286.   typedef _Alloc allocator_type;
  287.   allocator_type get_allocator() const { return allocator_type(); }
  288.   _Bvector_base(const allocator_type&)
  289.     : _M_start(), _M_finish(), _M_end_of_storage(0) {}
  290.   ~_Bvector_base() { _M_deallocate(); }
  291. protected:
  292.   typedef simple_alloc<unsigned int, _Alloc> _Alloc_type;
  293.   
  294.   unsigned int* _M_bit_alloc(size_t __n) 
  295.     { return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); }
  296.   void _M_deallocate() {
  297.     if (_M_start._M_p)
  298.       _Alloc_type::deallocate(_M_start._M_p,
  299.                               _M_end_of_storage - _M_start._M_p);
  300.   }
  301.   _Bit_iterator _M_start;
  302.   _Bit_iterator _M_finish;
  303.   unsigned int* _M_end_of_storage;  
  304. };
  305. #endif /* __STL_USE_STD_ALLOCATORS */
  306. // The next few lines are confusing.  What we're doing is declaring a
  307. //  partial specialization of vector<T, Alloc> if we have the necessary
  308. //  compiler support.  Otherwise, we define a class bit_vector which uses
  309. //  the default allocator. 
  310. #if defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && !defined(__STL_NO_BOOL)
  311. #  define __SGI_STL_VECBOOL_TEMPLATE
  312. #  define __BVECTOR           vector<bool, _Alloc>
  313. #  define __VECTOR            vector
  314. #  define __BVECTOR_BASE      _Bvector_base<_Alloc>
  315. #  define __BVECTOR_TMPL_LIST template <class _Alloc>
  316.    __STL_END_NAMESPACE
  317. #  include <stl_vector.h>
  318.    __STL_BEGIN_NAMESPACE
  319. #else  /* __STL_CLASS_PARTIAL_SPECIALIZATION && !__STL_NO_BOOL */
  320. #  undef  __SGI_STL_VECBOOL_TEMPLATE
  321. #  define __BVECTOR           bit_vector
  322. #  define __VECTOR            bit_vector
  323. #  define __BVECTOR_BASE      _Bvector_base<__STL_DEFAULT_ALLOCATOR(bool) >
  324. #  define __BVECTOR_TMPL_LIST
  325. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION && !__STL_NO_BOOL */
  326. __BVECTOR_TMPL_LIST 
  327. class __BVECTOR : public __BVECTOR_BASE 
  328. {
  329. public:
  330.   typedef bool value_type;
  331.   typedef size_t size_type;
  332.   typedef ptrdiff_t difference_type; 
  333.   typedef _Bit_reference reference;
  334.   typedef bool const_reference;
  335.   typedef _Bit_reference* pointer;
  336.   typedef const bool* const_pointer;
  337.   typedef _Bit_iterator                iterator;
  338.   typedef _Bit_const_iterator          const_iterator;
  339. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  340.   typedef reverse_iterator<const_iterator> const_reverse_iterator;
  341.   typedef reverse_iterator<iterator> reverse_iterator;
  342. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  343.   typedef reverse_iterator<const_iterator, value_type, const_reference, 
  344.                            difference_type> const_reverse_iterator;
  345.   typedef reverse_iterator<iterator, value_type, reference, difference_type>
  346.           reverse_iterator;
  347. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  348.   typedef typename __BVECTOR_BASE::allocator_type allocator_type;
  349.   allocator_type get_allocator() const {
  350.     return __BVECTOR_BASE::get_allocator();
  351.   }
  352. protected:
  353. #ifdef __STL_USE_NAMESPACES  
  354.   using __BVECTOR_BASE::_M_bit_alloc;
  355.   using __BVECTOR_BASE::_M_deallocate;
  356.   using __BVECTOR_BASE::_M_start;
  357.   using __BVECTOR_BASE::_M_finish;
  358.   using __BVECTOR_BASE::_M_end_of_storage;
  359. #endif /* __STL_USE_NAMESPACES */
  360. protected:
  361.   void _M_initialize(size_type __n) {
  362.     unsigned int* __q = _M_bit_alloc(__n);
  363.     _M_end_of_storage = __q + (__n + __WORD_BIT - 1)/__WORD_BIT;
  364.     _M_start = iterator(__q, 0);
  365.     _M_finish = _M_start + difference_type(__n);
  366.   }
  367.   void _M_insert_aux(iterator __position, bool __x) {
  368.     if (_M_finish._M_p != _M_end_of_storage) {
  369.       copy_backward(__position, _M_finish, _M_finish + 1);
  370.       *__position = __x;
  371.       ++_M_finish;
  372.     }
  373.     else {
  374.       size_type __len = size() ? 2 * size() : __WORD_BIT;
  375.       unsigned int* __q = _M_bit_alloc(__len);
  376.       iterator __i = copy(begin(), __position, iterator(__q, 0));
  377.       *__i++ = __x;
  378.       _M_finish = copy(__position, end(), __i);
  379.       _M_deallocate();
  380.       _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
  381.       _M_start = iterator(__q, 0);
  382.     }
  383.   }
  384. #ifdef __STL_MEMBER_TEMPLATES
  385.   template <class _InputIterator>
  386.   void _M_initialize_range(_InputIterator __first, _InputIterator __last,
  387.                            input_iterator_tag) {
  388.     _M_start = iterator();
  389.     _M_finish = iterator();
  390.     _M_end_of_storage = 0;
  391.     for ( ; __first != __last; ++__first) 
  392.       push_back(*__first);
  393.   }
  394.   template <class _ForwardIterator>
  395.   void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
  396.                            forward_iterator_tag) {
  397.     size_type __n = 0;
  398.     distance(__first, __last, __n);
  399.     _M_initialize(__n);
  400.     copy(__first, __last, _M_start);
  401.   }
  402.   template <class _InputIterator>
  403.   void _M_insert_range(iterator __pos,
  404.                        _InputIterator __first, _InputIterator __last,
  405.                        input_iterator_tag) {
  406.     for ( ; __first != __last; ++__first) {
  407.       __pos = insert(__pos, *__first);
  408.       ++__pos;
  409.     }
  410.   }
  411.   template <class _ForwardIterator>
  412.   void _M_insert_range(iterator __position,
  413.                        _ForwardIterator __first, _ForwardIterator __last,
  414.                        forward_iterator_tag) {
  415.     if (__first != __last) {
  416.       size_type __n = 0;
  417.       distance(__first, __last, __n);
  418.       if (capacity() - size() >= __n) {
  419.         copy_backward(__position, end(), _M_finish + difference_type(__n));
  420.         copy(__first, __last, __position);
  421.         _M_finish += difference_type(__n);
  422.       }
  423.       else {
  424.         size_type __len = size() + max(size(), __n);
  425.         unsigned int* __q = _M_bit_alloc(__len);
  426.         iterator __i = copy(begin(), __position, iterator(__q, 0));
  427.         __i = copy(__first, __last, __i);
  428.         _M_finish = copy(__position, end(), __i);
  429.         _M_deallocate();
  430.         _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
  431.         _M_start = iterator(__q, 0);
  432.       }
  433.     }
  434.   }      
  435. #endif /* __STL_MEMBER_TEMPLATES */
  436. public:
  437.   iterator begin() { return _M_start; }
  438.   const_iterator begin() const { return _M_start; }
  439.   iterator end() { return _M_finish; }
  440.   const_iterator end() const { return _M_finish; }
  441.   reverse_iterator rbegin() { return reverse_iterator(end()); }
  442.   const_reverse_iterator rbegin() const { 
  443.     return const_reverse_iterator(end()); 
  444.   }
  445.   reverse_iterator rend() { return reverse_iterator(begin()); }
  446.   const_reverse_iterator rend() const { 
  447.     return const_reverse_iterator(begin()); 
  448.   }
  449.   size_type size() const { return size_type(end() - begin()); }
  450.   size_type max_size() const { return size_type(-1); }
  451.   size_type capacity() const {
  452.     return size_type(const_iterator(_M_end_of_storage, 0) - begin());
  453.   }
  454.   bool empty() const { return begin() == end(); }
  455.   reference operator[](size_type __n)
  456.     { return *(begin() + difference_type(__n)); }
  457.   const_reference operator[](size_type __n) const
  458.     { return *(begin() + difference_type(__n)); }
  459. #ifdef __STL_THROW_RANGE_ERRORS
  460.   void _M_range_check(size_type __n) const {
  461.     if (__n >= this->size())
  462.       __stl_throw_range_error("vector<bool>");
  463.   }
  464.   reference at(size_type __n)
  465.     { _M_range_check(__n); return (*this)[__n]; }
  466.   const_reference at(size_type __n) const
  467.     { _M_range_check(__n); return (*this)[__n]; }
  468. #endif /* __STL_THROW_RANGE_ERRORS */
  469.   explicit __VECTOR(const allocator_type& __a = allocator_type())
  470.     : __BVECTOR_BASE(__a) {}
  471.   __VECTOR(size_type __n, bool __value,
  472.             const allocator_type& __a = allocator_type())
  473.     : __BVECTOR_BASE(__a)
  474.   {
  475.     _M_initialize(__n);
  476.     fill(_M_start._M_p, _M_end_of_storage, __value ? ~0 : 0);
  477.   }
  478.   explicit __VECTOR(size_type __n)
  479.     : __BVECTOR_BASE(allocator_type())
  480.   {
  481.     _M_initialize(__n);
  482.     fill(_M_start._M_p, _M_end_of_storage, 0);
  483.   }
  484.   __VECTOR(const __VECTOR& __x) : __BVECTOR_BASE(__x.get_allocator()) {
  485.     _M_initialize(__x.size());
  486.     copy(__x.begin(), __x.end(), _M_start);
  487.   }
  488. #ifdef __STL_MEMBER_TEMPLATES
  489.   // Check whether it's an integral type.  If so, it's not an iterator.
  490.   template <class _Integer>
  491.   void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
  492.     _M_initialize(__n);
  493.     fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
  494.   }
  495.   template <class _InputIterator>
  496.   void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
  497.                               __false_type) {
  498.     _M_initialize_range(__first, __last, __ITERATOR_CATEGORY(__first));
  499.   }
  500.   template <class _InputIterator>
  501.   __VECTOR(_InputIterator __first, _InputIterator __last,
  502.            const allocator_type& __a = allocator_type())
  503.     : __BVECTOR_BASE(__a)
  504.   {
  505.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  506.     _M_initialize_dispatch(__first, __last, _Integral());
  507.   }
  508.     
  509. #else /* __STL_MEMBER_TEMPLATES */
  510.   __VECTOR(const_iterator __first, const_iterator __last,
  511.            const allocator_type& __a = allocator_type())
  512.     : __BVECTOR_BASE(__a)
  513.   {
  514.     size_type __n = 0;
  515.     distance(__first, __last, __n);
  516.     _M_initialize(__n);
  517.     copy(__first, __last, _M_start);
  518.   }
  519.   __VECTOR(const bool* __first, const bool* __last,
  520.            const allocator_type& __a = allocator_type())
  521.     : __BVECTOR_BASE(__a)
  522.   {
  523.     size_type __n = 0;
  524.     distance(__first, __last, __n);
  525.     _M_initialize(__n);
  526.     copy(__first, __last, _M_start);
  527.   }
  528. #endif /* __STL_MEMBER_TEMPLATES */
  529.   ~__VECTOR() { }
  530.   __VECTOR& operator=(const __VECTOR& __x) {
  531.     if (&__x == this) return *this;
  532.     if (__x.size() > capacity()) {
  533.       _M_deallocate();
  534.       _M_initialize(__x.size());
  535.     }
  536.     copy(__x.begin(), __x.end(), begin());
  537.     _M_finish = begin() + difference_type(__x.size());
  538.     return *this;
  539.   }
  540.   // assign(), a generalized assignment member function.  Two
  541.   // versions: one that takes a count, and one that takes a range.
  542.   // The range version is a member template, so we dispatch on whether
  543.   // or not the type is an integer.
  544.   void _M_fill_assign(size_t __n, bool __x) {
  545.     if (__n > size()) {
  546.       fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
  547.       insert(end(), __n - size(), __x);
  548.     }
  549.     else {
  550.       erase(begin() + __n, end());
  551.       fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0);
  552.     }
  553.   }
  554.   void assign(size_t __n, bool __x) { _M_fill_assign(__n, __x); }
  555. #ifdef __STL_MEMBER_TEMPLATES
  556.   template <class _InputIterator>
  557.   void assign(_InputIterator __first, _InputIterator __last) {
  558.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  559.     _M_assign_dispatch(__first, __last, _Integral());
  560.   }
  561.   template <class _Integer>
  562.   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
  563.     { _M_fill_assign((size_t) __n, (bool) __val); }
  564.   template <class _InputIter>
  565.   void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
  566.     { _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); }
  567.   template <class _InputIterator>
  568.   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
  569.                      input_iterator_tag) {
  570.     iterator __cur = begin();
  571.     for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
  572.       *__cur = *__first;
  573.     if (__first == __last)
  574.       erase(__cur, end());
  575.     else
  576.       insert(end(), __first, __last);
  577.   }
  578.   template <class _ForwardIterator>
  579.   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
  580.                      forward_iterator_tag) {
  581.     size_type __len = 0;
  582.     distance(__first, __last, __len);
  583.     if (__len < size())
  584.       erase(copy(__first, __last, begin()), end());
  585.     else {
  586.       _ForwardIterator __mid = __first;
  587.       advance(__mid, size());
  588.       copy(__first, __mid, begin());
  589.       insert(end(), __mid, __last);
  590.     }
  591.   }    
  592. #endif /* __STL_MEMBER_TEMPLATES */
  593.   void reserve(size_type __n) {
  594.     if (capacity() < __n) {
  595.       unsigned int* __q = _M_bit_alloc(__n);
  596.       _M_finish = copy(begin(), end(), iterator(__q, 0));
  597.       _M_deallocate();
  598.       _M_start = iterator(__q, 0);
  599.       _M_end_of_storage = __q + (__n + __WORD_BIT - 1)/__WORD_BIT;
  600.     }
  601.   }
  602.   reference front() { return *begin(); }
  603.   const_reference front() const { return *begin(); }
  604.   reference back() { return *(end() - 1); }
  605.   const_reference back() const { return *(end() - 1); }
  606.   void push_back(bool __x) {
  607.     if (_M_finish._M_p != _M_end_of_storage)
  608.       *_M_finish++ = __x;
  609.     else
  610.       _M_insert_aux(end(), __x);
  611.   }
  612.   void swap(__BVECTOR& __x) {
  613.     __STD::swap(_M_start, __x._M_start);
  614.     __STD::swap(_M_finish, __x._M_finish);
  615.     __STD::swap(_M_end_of_storage, __x._M_end_of_storage);
  616.   }
  617.   iterator insert(iterator __position, bool __x = bool()) {
  618.     difference_type __n = __position - begin();
  619.     if (_M_finish._M_p != _M_end_of_storage && __position == end())
  620.       *_M_finish++ = __x;
  621.     else
  622.       _M_insert_aux(__position, __x);
  623.     return begin() + __n;
  624.   }
  625. #ifdef __STL_MEMBER_TEMPLATES
  626.   // Check whether it's an integral type.  If so, it's not an iterator.
  627.   template <class _Integer>
  628.   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
  629.                           __true_type) {
  630.     _M_fill_insert(__pos, __n, __x);
  631.   }
  632.   template <class _InputIterator>
  633.   void _M_insert_dispatch(iterator __pos,
  634.                           _InputIterator __first, _InputIterator __last,
  635.                           __false_type) {
  636.     _M_insert_range(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
  637.   }
  638.   template <class _InputIterator>
  639.   void insert(iterator __position,
  640.               _InputIterator __first, _InputIterator __last) {
  641.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  642.     _M_insert_dispatch(__position, __first, __last, _Integral());
  643.   }
  644. #else /* __STL_MEMBER_TEMPLATES */
  645.   void insert(iterator __position,
  646.               const_iterator __first, const_iterator __last) {
  647.     if (__first == __last) return;
  648.     size_type __n = 0;
  649.     distance(__first, __last, __n);
  650.     if (capacity() - size() >= __n) {
  651.       copy_backward(__position, end(), _M_finish + __n);
  652.       copy(__first, __last, __position);
  653.       _M_finish += __n;
  654.     }
  655.     else {
  656.       size_type __len = size() + max(size(), __n);
  657.       unsigned int* __q = _M_bit_alloc(__len);
  658.       iterator __i = copy(begin(), __position, iterator(__q, 0));
  659.       __i = copy(__first, __last, __i);
  660.       _M_finish = copy(__position, end(), __i);
  661.       _M_deallocate();
  662.       _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
  663.       _M_start = iterator(__q, 0);
  664.     }
  665.   }
  666.   void insert(iterator __position, const bool* __first, const bool* __last) {
  667.     if (__first == __last) return;
  668.     size_type __n = 0;
  669.     distance(__first, __last, __n);
  670.     if (capacity() - size() >= __n) {
  671.       copy_backward(__position, end(), _M_finish + __n);
  672.       copy(__first, __last, __position);
  673.       _M_finish += __n;
  674.     }
  675.     else {
  676.       size_type __len = size() + max(size(), __n);
  677.       unsigned int* __q = _M_bit_alloc(__len);
  678.       iterator __i = copy(begin(), __position, iterator(__q, 0));
  679.       __i = copy(__first, __last, __i);
  680.       _M_finish = copy(__position, end(), __i);
  681.       _M_deallocate();
  682.       _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
  683.       _M_start = iterator(__q, 0);
  684.     }
  685.   }
  686. #endif /* __STL_MEMBER_TEMPLATES */
  687.   void _M_fill_insert(iterator __position, size_type __n, bool __x) {
  688.     if (__n == 0) return;
  689.     if (capacity() - size() >= __n) {
  690.       copy_backward(__position, end(), _M_finish + difference_type(__n));
  691.       fill(__position, __position + difference_type(__n), __x);
  692.       _M_finish += difference_type(__n);
  693.     }
  694.     else {
  695.       size_type __len = size() + max(size(), __n);
  696.       unsigned int* __q = _M_bit_alloc(__len);
  697.       iterator __i = copy(begin(), __position, iterator(__q, 0));
  698.       fill_n(__i, __n, __x);
  699.       _M_finish = copy(__position, end(), __i + difference_type(__n));
  700.       _M_deallocate();
  701.       _M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT;
  702.       _M_start = iterator(__q, 0);
  703.     }
  704.   }
  705.   void insert(iterator __position, size_type __n, bool __x) {
  706.     _M_fill_insert(__position, __n, __x);
  707.   }
  708.   void pop_back() { --_M_finish; }
  709.   iterator erase(iterator __position) {
  710.     if (__position + 1 != end())
  711.       copy(__position + 1, end(), __position);
  712.       --_M_finish;
  713.     return __position;
  714.   }
  715.   iterator erase(iterator __first, iterator __last) {
  716.     _M_finish = copy(__last, end(), __first);
  717.     return __first;
  718.   }
  719.   void resize(size_type __new_size, bool __x = bool()) {
  720.     if (__new_size < size()) 
  721.       erase(begin() + difference_type(__new_size), end());
  722.     else
  723.       insert(end(), __new_size - size(), __x);
  724.   }
  725.   void flip() {
  726.     for (unsigned int* __p = _M_start._M_p; __p != _M_end_of_storage; ++__p)
  727.       *__p = ~*__p;
  728.   }
  729.   void clear() { erase(begin(), end()); }
  730. };
  731. #ifdef __SGI_STL_VECBOOL_TEMPLATE
  732. // This typedef is non-standard.  It is provided for backward compatibility.
  733. typedef vector<bool, alloc> bit_vector;
  734. #else /* __SGI_STL_VECBOOL_TEMPLATE */
  735. inline void swap(bit_vector& __x, bit_vector& __y) {
  736.   __x.swap(__y);
  737. }
  738. inline bool 
  739. operator==(const bit_vector& __x, const bit_vector& __y)
  740. {
  741.   return (__x.size() == __y.size() && 
  742.           equal(__x.begin(), __x.end(), __y.begin()));
  743. }
  744. inline bool 
  745. operator!=(const bit_vector& __x, const bit_vector& __y)
  746. {
  747.   return !(__x == __y);
  748. }
  749. inline bool 
  750. operator<(const bit_vector& __x, const bit_vector& __y)
  751. {
  752.   return lexicographical_compare(__x.begin(), __x.end(), 
  753.                                  __y.begin(), __y.end());
  754. }
  755. inline bool operator>(const bit_vector& __x, const bit_vector& __y)
  756. {
  757.   return __y < __x;
  758. }
  759. inline bool operator<=(const bit_vector& __x, const bit_vector& __y)
  760. {
  761.   return !(__y < __x);
  762. }
  763. inline bool operator>=(const bit_vector& __x, const bit_vector& __y)
  764. {
  765.   return !(__x < __y);
  766. }
  767. #endif /* __SGI_STL_VECBOOL_TEMPLATE */
  768. #undef __SGI_STL_VECBOOL_TEMPLATE
  769. #undef __BVECTOR
  770. #undef __VECTOR
  771. #undef __BVECTOR_BASE
  772. #undef __BVECTOR_TMPL_LIST 
  773. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  774. #pragma reset woff 1174
  775. #pragma reset woff 1375
  776. #endif
  777. __STL_END_NAMESPACE 
  778. #endif /* __SGI_STL_INTERNAL_BVECTOR_H */
  779. // Local Variables:
  780. // mode:C++
  781. // End: