libstdc++-v3/include/bits/stl_bvector.h

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