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

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