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

   1 // vector<bool> specialization -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  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
  80     { return !!(*_M_p & _M_mask); }
  81
  82     _Bit_reference&
  83     operator=(bool __x)
  84     {
  85       if (__x)
  86         *_M_p |= _M_mask;
  87       else
  88         *_M_p &= ~_M_mask;
  89       return *this;
  90     }
  91
  92     _Bit_reference&
  93     operator=(const _Bit_reference& __x)
  94     { return *this = bool(__x); }
  95
  96     bool
  97     operator==(const _Bit_reference& __x) const
  98     { return bool(*this) == bool(__x); }
  99
 100     bool
 101     operator<(const _Bit_reference& __x) const
 102     { return !bool(*this) && bool(__x); }
 103
 104     void
 105     flip()
 106     { *_M_p ^= _M_mask; }
 107   };
 108
 109   struct _Bit_iterator_base
 110   : public std::iterator<std::random_access_iterator_tag, bool>
 111   {
 112     _Bit_type * _M_p;
 113     unsigned int _M_offset;
 114
 115     _Bit_iterator_base(_Bit_type * __x, unsigned int __y)
 116     : _M_p(__x), _M_offset(__y) { }
 117
 118     void
 119     _M_bump_up()
 120     {
 121       if (_M_offset++ == int(_S_word_bit) - 1)
 122         {
 123           _M_offset = 0;
 124           ++_M_p;
 125         }
 126     }
 127
 128     void
 129     _M_bump_down()
 130     {
 131       if (_M_offset-- == 0)
 132         {
 133           _M_offset = int(_S_word_bit) - 1;
 134           --_M_p;
 135         }
 136     }
 137
 138     void
 139     _M_incr(ptrdiff_t __i)
 140     {
 141       difference_type __n = __i + _M_offset;
 142       _M_p += __n / int(_S_word_bit);
 143       __n = __n % int(_S_word_bit);
 144       if (__n < 0)
 145         {
 146           _M_offset = static_cast<unsigned int>(__n + int(_S_word_bit));
 147           --_M_p;
 148         }
 149       else
 150         _M_offset = static_cast<unsigned int>(__n);
 151     }
 152
 153     bool
 154     operator==(const _Bit_iterator_base& __i) const
 155     { return _M_p == __i._M_p && _M_offset == __i._M_offset; }
 156
 157     bool
 158     operator<(const _Bit_iterator_base& __i) const
 159     {
 160       return _M_p < __i._M_p
 161              || (_M_p == __i._M_p && _M_offset < __i._M_offset);
 162     }
 163
 164     bool
 165     operator!=(const _Bit_iterator_base& __i) const
 166     { return !(*this == __i); }
 167
 168     bool
 169     operator>(const _Bit_iterator_base& __i) const
 170     { return __i < *this; }
 171
 172     bool
 173     operator<=(const _Bit_iterator_base& __i) const
 174     { return !(__i < *this); }
 175
 176     bool
 177     operator>=(const _Bit_iterator_base& __i) const
 178     { return !(*this < __i); }
 179   };
 180
 181   inline ptrdiff_t
 182   operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
 183   {
 184     return (int(_S_word_bit) * (__x._M_p - __y._M_p)
 185             + __x._M_offset - __y._M_offset);
 186   }
 187
 188   struct _Bit_iterator : public _Bit_iterator_base
 189   {
 190     typedef _Bit_reference  reference;
 191     typedef _Bit_reference* pointer;
 192     typedef _Bit_iterator   iterator;
 193
 194     _Bit_iterator() : _Bit_iterator_base(0, 0) { }
 195
 196     _Bit_iterator(_Bit_type * __x, unsigned int __y)
 197     : _Bit_iterator_base(__x, __y) { }
 198
 199     reference
 200     operator*() const
 201     { return reference(_M_p, 1UL << _M_offset); }
 202
 203     iterator&
 204     operator++()
 205     {
 206       _M_bump_up();
 207       return *this;
 208     }
 209
 210     iterator
 211     operator++(int)
 212     {
 213       iterator __tmp = *this;
 214       _M_bump_up();
 215       return __tmp;
 216     }
 217
 218     iterator&
 219     operator--()
 220     {
 221       _M_bump_down();
 222       return *this;
 223     }
 224
 225     iterator
 226     operator--(int)
 227     {
 228       iterator __tmp = *this;
 229       _M_bump_down();
 230       return __tmp;
 231     }
 232
 233     iterator&
 234     operator+=(difference_type __i)
 235     {
 236       _M_incr(__i);
 237       return *this;
 238     }
 239
 240     iterator&
 241     operator-=(difference_type __i)
 242     {
 243       *this += -__i;
 244       return *this;
 245     }
 246
 247     iterator
 248     operator+(difference_type __i) const
 249     {
 250       iterator __tmp = *this;
 251       return __tmp += __i;
 252     }
 253
 254     iterator
 255     operator-(difference_type __i) const
 256     {
 257       iterator __tmp = *this;
 258       return __tmp -= __i;
 259     }
 260
 261     reference
 262     operator[](difference_type __i) const
 263     { return *(*this + __i); }
 264   };
 265
 266   inline _Bit_iterator
 267   operator+(ptrdiff_t __n, const _Bit_iterator& __x)
 268   { return __x + __n; }
 269
 270   struct _Bit_const_iterator : public _Bit_iterator_base
 271   {
 272     typedef bool                 reference;
 273     typedef bool                 const_reference;
 274     typedef const bool*          pointer;
 275     typedef _Bit_const_iterator  const_iterator;
 276
 277     _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
 278
 279     _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
 280     : _Bit_iterator_base(__x, __y) { }
 281
 282     _Bit_const_iterator(const _Bit_iterator& __x)
 283     : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
 284
 285     const_reference
 286     operator*() const
 287     { return _Bit_reference(_M_p, 1UL << _M_offset); }
 288
 289     const_iterator&
 290     operator++()
 291     {
 292       _M_bump_up();
 293       return *this;
 294     }
 295
 296     const_iterator
 297     operator++(int)
 298     {
 299       const_iterator __tmp = *this;
 300       _M_bump_up();
 301       return __tmp;
 302     }
 303
 304     const_iterator&
 305     operator--()
 306     {
 307       _M_bump_down();
 308       return *this;
 309     }
 310
 311     const_iterator
 312     operator--(int)
 313     {
 314       const_iterator __tmp = *this;
 315       _M_bump_down();
 316       return __tmp;
 317     }
 318
 319     const_iterator&
 320     operator+=(difference_type __i)
 321     {
 322       _M_incr(__i);
 323       return *this;
 324     }
 325
 326     const_iterator&
 327     operator-=(difference_type __i)
 328     {
 329       *this += -__i;
 330       return *this;
 331     }
 332
 333     const_iterator
 334     operator+(difference_type __i) const
 335     {
 336       const_iterator __tmp = *this;
 337       return __tmp += __i;
 338     }
 339
 340     const_iterator
 341     operator-(difference_type __i) const
 342     {
 343       const_iterator __tmp = *this;
 344       return __tmp -= __i;
 345     }
 346
 347     const_reference
 348     operator[](difference_type __i) const
 349     { return *(*this + __i); }
 350   };
 351
 352   inline _Bit_const_iterator
 353   operator+(ptrdiff_t __n, const _Bit_const_iterator& __x)
 354   { return __x + __n; }
 355
 356   template<class _Alloc>
 357     class _Bvector_base
 358     {
 359       typedef typename _Alloc::template rebind<_Bit_type>::other
 360         _Bit_alloc_type;
 361
 362       struct _Bvector_impl : public _Bit_alloc_type
 363       {
 364         _Bit_iterator   _M_start;
 365         _Bit_iterator   _M_finish;
 366         _Bit_type*      _M_end_of_storage;
 367         _Bvector_impl(const _Bit_alloc_type& __a)
 368         : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
 369         { }
 370       };
 371
 372     public:
 373       typedef _Alloc allocator_type;
 374
 375       allocator_type
 376       get_allocator() const
 377       { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
 378
 379       _Bvector_base(const allocator_type& __a) : _M_impl(__a) { }
 380
 381       ~_Bvector_base()
 382       { this->_M_deallocate(); }
 383
 384     protected:
 385       _Bvector_impl _M_impl;
 386
 387       _Bit_type*
 388       _M_allocate(size_t __n)
 389       { return _M_impl.allocate((__n + int(_S_word_bit) - 1)
 390                                 / int(_S_word_bit)); }
 391
 392       void
 393       _M_deallocate()
 394       {
 395         if (_M_impl._M_start._M_p)
 396           _M_impl.deallocate(_M_impl._M_start._M_p,
 397                              _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
 398       }
 399     };
 400 } // namespace std
 401
 402 // Declare a partial specialization of vector<T, Alloc>.
 403 #include <bits/stl_vector.h>
 404
 405 namespace _GLIBCXX_STD
 406 {
 407   /**
 408    *  @brief  A specialization of vector for booleans which offers fixed time
 409    *  access to individual elements in any order.
 410    *
 411    *  Note that vector<bool> does not actually meet the requirements for being
 412    *  a container.  This is because the reference and pointer types are not
 413    *  really references and pointers to bool.  See DR96 for details.  @see
 414    *  vector for function documentation.
 415    *
 416    *  @ingroup Containers
 417    *  @ingroup Sequences
 418    *
 419    *  In some terminology a %vector can be described as a dynamic
 420    *  C-style array, it offers fast and efficient access to individual
 421    *  elements in any order and saves the user from worrying about
 422    *  memory and size allocation.  Subscripting ( @c [] ) access is
 423    *  also provided as with C-style arrays.
 424   */
 425 template<typename _Alloc>
 426   class vector<bool, _Alloc> : public _Bvector_base<_Alloc>
 427   {
 428   public:
 429     typedef bool value_type;
 430     typedef size_t size_type;
 431     typedef ptrdiff_t difference_type;
 432     typedef _Bit_reference reference;
 433     typedef bool const_reference;
 434     typedef _Bit_reference* pointer;
 435     typedef const bool* const_pointer;
 436
 437     typedef _Bit_iterator                iterator;
 438     typedef _Bit_const_iterator          const_iterator;
 439
 440     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 441     typedef std::reverse_iterator<iterator> reverse_iterator;
 442
 443     typedef typename _Bvector_base<_Alloc>::allocator_type allocator_type;
 444
 445     allocator_type get_allocator() const
 446     { return _Bvector_base<_Alloc>::get_allocator(); }
 447
 448   protected:
 449     using _Bvector_base<_Alloc>::_M_allocate;
 450     using _Bvector_base<_Alloc>::_M_deallocate;
 451
 452   protected:
 453     void
 454     _M_initialize(size_type __n)
 455     {
 456       _Bit_type* __q = this->_M_allocate(__n);
 457       this->_M_impl._M_end_of_storage = (__q
 458                                          + ((__n + int(_S_word_bit) - 1)
 459                                             / int(_S_word_bit)));
 460       this->_M_impl._M_start = iterator(__q, 0);
 461       this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
 462     }
 463
 464     void
 465     _M_insert_aux(iterator __position, bool __x)
 466     {
 467       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
 468         {
 469           std::copy_backward(__position, this->_M_impl._M_finish,
 470                              this->_M_impl._M_finish + 1);
 471           *__position = __x;
 472           ++this->_M_impl._M_finish;
 473         }
 474       else
 475         {
 476           const size_type __len = size() ? 2 * size()
 477                                          : static_cast<size_type>(_S_word_bit);
 478           _Bit_type * __q = this->_M_allocate(__len);
 479           iterator __i = std::copy(begin(), __position, iterator(__q, 0));
 480           *__i++ = __x;
 481           this->_M_impl._M_finish = std::copy(__position, end(), __i);
 482           this->_M_deallocate();
 483           this->_M_impl._M_end_of_storage = (__q + ((__len
 484                                                      + int(_S_word_bit) - 1)
 485                                                     / int(_S_word_bit)));
 486           this->_M_impl._M_start = iterator(__q, 0);
 487         }
 488     }
 489
 490     template<class _InputIterator>
 491       void
 492       _M_initialize_range(_InputIterator __first, _InputIterator __last,
 493                           std::input_iterator_tag)
 494       {
 495         this->_M_impl._M_start = iterator();
 496         this->_M_impl._M_finish = iterator();
 497         this->_M_impl._M_end_of_storage = 0;
 498         for (; __first != __last; ++__first)
 499           push_back(*__first);
 500       }
 501
 502     template<class _ForwardIterator>
 503       void
 504       _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
 505                           std::forward_iterator_tag)
 506       {
 507         const size_type __n = std::distance(__first, __last);
 508         _M_initialize(__n);
 509         std::copy(__first, __last, this->_M_impl._M_start);
 510       }
 511
 512     template<class _InputIterator>
 513       void
 514       _M_insert_range(iterator __pos, _InputIterator __first,
 515                       _InputIterator __last, std::input_iterator_tag)
 516       {
 517         for (; __first != __last; ++__first)
 518           {
 519             __pos = insert(__pos, *__first);
 520             ++__pos;
 521           }
 522       }
 523
 524     template<class _ForwardIterator>
 525       void
 526       _M_insert_range(iterator __position, _ForwardIterator __first,
 527                       _ForwardIterator __last, std::forward_iterator_tag)
 528       {
 529         if (__first != __last)
 530           {
 531             size_type __n = std::distance(__first, __last);
 532             if (capacity() - size() >= __n)
 533               {
 534                 std::copy_backward(__position, end(),
 535                                    this->_M_impl._M_finish
 536                                    + difference_type(__n));
 537                 std::copy(__first, __last, __position);
 538                 this->_M_impl._M_finish += difference_type(__n);
 539               }
 540             else
 541               {
 542                 const size_type __len = size() + std::max(size(), __n);
 543                 _Bit_type * __q = this->_M_allocate(__len);
 544                 iterator __i = std::copy(begin(), __position,
 545                                          iterator(__q, 0));
 546                 __i = std::copy(__first, __last, __i);
 547                 this->_M_impl._M_finish = std::copy(__position, end(), __i);
 548                 this->_M_deallocate();
 549                 this->_M_impl._M_end_of_storage = (__q
 550                                                    + ((__len
 551                                                        + int(_S_word_bit) - 1)
 552                                                       / int(_S_word_bit)));
 553                 this->_M_impl._M_start = iterator(__q, 0);
 554               }
 555           }
 556       }
 557
 558   public:
 559     iterator
 560     begin()
 561     { return this->_M_impl._M_start; }
 562
 563     const_iterator
 564     begin() const
 565     { return this->_M_impl._M_start; }
 566
 567     iterator
 568     end()
 569     { return this->_M_impl._M_finish; }
 570
 571     const_iterator
 572     end() const
 573     { return this->_M_impl._M_finish; }
 574
 575     reverse_iterator
 576     rbegin()
 577     { return reverse_iterator(end()); }
 578
 579     const_reverse_iterator
 580     rbegin() const
 581     { return const_reverse_iterator(end()); }
 582
 583     reverse_iterator
 584     rend()
 585     { return reverse_iterator(begin()); }
 586
 587     const_reverse_iterator
 588     rend() const
 589     { return const_reverse_iterator(begin()); }
 590
 591     size_type
 592     size() const
 593     { return size_type(end() - begin()); }
 594
 595     size_type
 596     max_size() const
 597     { return size_type(-1); }
 598
 599     size_type
 600     capacity() const
 601     { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
 602                        - begin()); }
 603     bool
 604     empty() const
 605     { return begin() == end(); }
 606
 607     reference
 608     operator[](size_type __n)
 609     { return *(begin() + difference_type(__n)); }
 610
 611     const_reference
 612     operator[](size_type __n) const
 613     { return *(begin() + difference_type(__n)); }
 614
 615     void
 616     _M_range_check(size_type __n) const
 617     {
 618       if (__n >= this->size())
 619         __throw_out_of_range(__N("vector<bool>::_M_range_check"));
 620     }
 621
 622     reference
 623     at(size_type __n)
 624     { _M_range_check(__n); return (*this)[__n]; }
 625
 626     const_reference
 627     at(size_type __n) const
 628     { _M_range_check(__n); return (*this)[__n]; }
 629
 630     explicit
 631     vector(const allocator_type& __a = allocator_type())
 632     : _Bvector_base<_Alloc>(__a) { }
 633
 634     vector(size_type __n, bool __value,
 635            const allocator_type& __a = allocator_type())
 636     : _Bvector_base<_Alloc>(__a)
 637     {
 638       _M_initialize(__n);
 639       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage,
 640                 __value ? ~0 : 0);
 641     }
 642
 643     explicit
 644     vector(size_type __n)
 645     : _Bvector_base<_Alloc>(allocator_type())
 646     {
 647       _M_initialize(__n);
 648       std::fill(this->_M_impl._M_start._M_p,
 649                 this->_M_impl._M_end_of_storage, 0);
 650     }
 651
 652     vector(const vector& __x)
 653     : _Bvector_base<_Alloc>(__x.get_allocator())
 654     {
 655       _M_initialize(__x.size());
 656       std::copy(__x.begin(), __x.end(), this->_M_impl._M_start);
 657     }
 658
 659     // Check whether it's an integral type.  If so, it's not an iterator.
 660     template<class _Integer>
 661       void
 662       _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
 663       {
 664         _M_initialize(__n);
 665         std::fill(this->_M_impl._M_start._M_p,
 666                   this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
 667       }
 668
 669     template<class _InputIterator>
 670       void
 671       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
 672                              __false_type)
 673       { _M_initialize_range(__first, __last,
 674                             std::__iterator_category(__first)); }
 675
 676     template<class _InputIterator>
 677       vector(_InputIterator __first, _InputIterator __last,
 678              const allocator_type& __a = allocator_type())
 679       : _Bvector_base<_Alloc>(__a)
 680       {
 681         typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 682         _M_initialize_dispatch(__first, __last, _Integral());
 683       }
 684
 685     ~vector() { }
 686
 687     vector&
 688     operator=(const vector& __x)
 689     {
 690       if (&__x == this)
 691         return *this;
 692       if (__x.size() > capacity())
 693         {
 694           this->_M_deallocate();
 695           _M_initialize(__x.size());
 696         }
 697       std::copy(__x.begin(), __x.end(), begin());
 698       this->_M_impl._M_finish = begin() + difference_type(__x.size());
 699       return *this;
 700     }
 701
 702     // assign(), a generalized assignment member function.  Two
 703     // versions: one that takes a count, and one that takes a range.
 704     // The range version is a member template, so we dispatch on whether
 705     // or not the type is an integer.
 706
 707     void
 708     _M_fill_assign(size_t __n, bool __x)
 709     {
 710       if (__n > size())
 711         {
 712           std::fill(this->_M_impl._M_start._M_p,
 713                     this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
 714           insert(end(), __n - size(), __x);
 715         }
 716       else
 717         {
 718           erase(begin() + __n, end());
 719           std::fill(this->_M_impl._M_start._M_p,
 720                     this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
 721         }
 722     }
 723
 724     void
 725     assign(size_t __n, bool __x)
 726     { _M_fill_assign(__n, __x); }
 727
 728     template<class _InputIterator>
 729       void
 730       assign(_InputIterator __first, _InputIterator __last)
 731       {
 732         typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 733         _M_assign_dispatch(__first, __last, _Integral());
 734       }
 735
 736     template<class _Integer>
 737       void
 738       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
 739       { _M_fill_assign((size_t) __n, (bool) __val); }
 740
 741     template<class _InputIterator>
 742       void
 743       _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
 744                          __false_type)
 745       { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
 746
 747     template<class _InputIterator>
 748       void
 749       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 750                     std::input_iterator_tag)
 751       {
 752         iterator __cur = begin();
 753         for (; __first != __last && __cur != end(); ++__cur, ++__first)
 754           *__cur = *__first;
 755         if (__first == __last)
 756           erase(__cur, end());
 757         else
 758           insert(end(), __first, __last);
 759       }
 760
 761     template<class _ForwardIterator>
 762       void
 763       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 764                     std::forward_iterator_tag)
 765       {
 766         const size_type __len = std::distance(__first, __last);
 767         if (__len < size())
 768           erase(std::copy(__first, __last, begin()), end());
 769         else
 770           {
 771             _ForwardIterator __mid = __first;
 772             std::advance(__mid, size());
 773             std::copy(__first, __mid, begin());
 774             insert(end(), __mid, __last);
 775           }
 776       }
 777
 778     void
 779     reserve(size_type __n)
 780     {
 781       if (__n > this->max_size())
 782         __throw_length_error(__N("vector::reserve"));
 783       if (this->capacity() < __n)
 784         {
 785           _Bit_type* __q = this->_M_allocate(__n);
 786           this->_M_impl._M_finish = std::copy(begin(), end(),
 787                                               iterator(__q, 0));
 788           this->_M_deallocate();
 789           this->_M_impl._M_start = iterator(__q, 0);
 790           this->_M_impl._M_end_of_storage = (__q + (__n + int(_S_word_bit) - 1)
 791                                              / int(_S_word_bit));
 792         }
 793     }
 794
 795     reference
 796     front()
 797     { return *begin(); }
 798
 799     const_reference
 800     front() const
 801     { return *begin(); }
 802
 803     reference
 804     back()
 805     { return *(end() - 1); }
 806
 807     const_reference
 808     back() const
 809     { return *(end() - 1); }
 810
 811     // _GLIBCXX_RESOLVE_LIB_DEFECTS
 812     // DR 464. Suggestion for new member functions in standard containers.
 813     // N.B. DR 464 says nothing about vector<bool> but we need something
 814     // here due to the way we are implementing DR 464 in the debug-mode
 815     // vector class.
 816     void
 817     data() { }
 818
 819     void
 820     push_back(bool __x)
 821     {
 822       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
 823         *this->_M_impl._M_finish++ = __x;
 824       else
 825         _M_insert_aux(end(), __x);
 826     }
 827
 828     void
 829     swap(vector<bool, _Alloc>& __x)
 830     {
 831       std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
 832       std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
 833       std::swap(this->_M_impl._M_end_of_storage,
 834                 __x._M_impl._M_end_of_storage);
 835     }
 836
 837     // [23.2.5]/1, third-to-last entry in synopsis listing
 838     static void
 839     swap(reference __x, reference __y)
 840     {
 841       bool __tmp = __x;
 842       __x = __y;
 843       __y = __tmp;
 844     }
 845
 846     iterator
 847     insert(iterator __position, bool __x = bool())
 848     {
 849       const difference_type __n = __position - begin();
 850       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
 851           && __position == end())
 852         *this->_M_impl._M_finish++ = __x;
 853       else
 854         _M_insert_aux(__position, __x);
 855       return begin() + __n;
 856     }
 857
 858     // Check whether it's an integral type.  If so, it's not an iterator.
 859
 860     template<class _Integer>
 861       void
 862       _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
 863                          __true_type)
 864       { _M_fill_insert(__pos, __n, __x); }
 865
 866     template<class _InputIterator>
 867       void
 868       _M_insert_dispatch(iterator __pos,
 869                          _InputIterator __first, _InputIterator __last,
 870                          __false_type)
 871       { _M_insert_range(__pos, __first, __last,
 872                         std::__iterator_category(__first)); }
 873
 874     template<class _InputIterator>
 875       void
 876       insert(iterator __position,
 877              _InputIterator __first, _InputIterator __last)
 878       {
 879         typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 880         _M_insert_dispatch(__position, __first, __last, _Integral());
 881       }
 882
 883     void
 884     _M_fill_insert(iterator __position, size_type __n, bool __x)
 885     {
 886       if (__n == 0)
 887         return;
 888       if (capacity() - size() >= __n)
 889         {
 890           std::copy_backward(__position, end(),
 891                              this->_M_impl._M_finish + difference_type(__n));
 892           std::fill(__position, __position + difference_type(__n), __x);
 893           this->_M_impl._M_finish += difference_type(__n);
 894         }
 895       else
 896         {
 897           const size_type __len = size() + std::max(size(), __n);
 898           _Bit_type * __q = this->_M_allocate(__len);
 899           iterator __i = std::copy(begin(), __position, iterator(__q, 0));
 900           std::fill_n(__i, __n, __x);
 901           this->_M_impl._M_finish = std::copy(__position, end(),
 902                                               __i + difference_type(__n));
 903           this->_M_deallocate();
 904           this->_M_impl._M_end_of_storage = (__q + ((__len
 905                                                      + int(_S_word_bit) - 1)
 906                                                     / int(_S_word_bit)));
 907           this->_M_impl._M_start = iterator(__q, 0);
 908         }
 909     }
 910
 911     void
 912     insert(iterator __position, size_type __n, bool __x)
 913     { _M_fill_insert(__position, __n, __x); }
 914
 915     void
 916     pop_back()
 917     { --this->_M_impl._M_finish; }
 918
 919     iterator
 920     erase(iterator __position)
 921     {
 922       if (__position + 1 != end())
 923         std::copy(__position + 1, end(), __position);
 924       --this->_M_impl._M_finish;
 925       return __position;
 926     }
 927
 928     iterator
 929     erase(iterator __first, iterator __last)
 930     {
 931       this->_M_impl._M_finish = std::copy(__last, end(), __first);
 932       return __first;
 933     }
 934
 935     void
 936     resize(size_type __new_size, bool __x = bool())
 937     {
 938       if (__new_size < size())
 939         erase(begin() + difference_type(__new_size), end());
 940       else
 941         insert(end(), __new_size - size(), __x);
 942     }
 943
 944     void
 945     flip()
 946     {
 947       for (_Bit_type * __p = this->_M_impl._M_start._M_p;
 948            __p != this->_M_impl._M_end_of_storage; ++__p)
 949         *__p = ~*__p;
 950     }
 951
 952     void
 953     clear()
 954     { erase(begin(), end()); }
 955   };
 956 } // namespace std
 957
 958 #endif