contrib/libstdc++/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           __n += int(_S_word_bit);
 148           --_M_p;
 149         }
 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   inline void
 357   __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x)
 358   {
 359     for (; __first != __last; ++__first)
 360       *__first = __x;
 361   }
 362
 363   inline void
 364   fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x)
 365   {
 366     if (__first._M_p != __last._M_p)
 367       {
 368         std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0);
 369         __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x);
 370         __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x);
 371       }
 372     else
 373       __fill_bvector(__first, __last, __x);
 374   }
 375
 376   template<class _Alloc>
 377     struct _Bvector_base
 378     {
 379       typedef typename _Alloc::template rebind<_Bit_type>::other
 380         _Bit_alloc_type;
 381
 382       struct _Bvector_impl
 383       : public _Bit_alloc_type
 384       {
 385         _Bit_iterator   _M_start;
 386         _Bit_iterator   _M_finish;
 387         _Bit_type*      _M_end_of_storage;
 388
 389         _Bvector_impl()
 390         : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage(0)
 391         { }
 392
 393         _Bvector_impl(const _Bit_alloc_type& __a)
 394         : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
 395         { }
 396       };
 397
 398     public:
 399       typedef _Alloc allocator_type;
 400
 401       _Bit_alloc_type&
 402       _M_get_Bit_allocator()
 403       { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); }
 404
 405       const _Bit_alloc_type&
 406       _M_get_Bit_allocator() const
 407       { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
 408
 409       allocator_type
 410       get_allocator() const
 411       { return allocator_type(_M_get_Bit_allocator()); }
 412
 413       _Bvector_base()
 414       : _M_impl() { }
 415
 416       _Bvector_base(const allocator_type& __a)
 417       : _M_impl(__a) { }
 418
 419       ~_Bvector_base()
 420       { this->_M_deallocate(); }
 421
 422     protected:
 423       _Bvector_impl _M_impl;
 424
 425       _Bit_type*
 426       _M_allocate(size_t __n)
 427       { return _M_impl.allocate((__n + int(_S_word_bit) - 1)
 428                                 / int(_S_word_bit)); }
 429
 430       void
 431       _M_deallocate()
 432       {
 433         if (_M_impl._M_start._M_p)
 434           _M_impl.deallocate(_M_impl._M_start._M_p,
 435                              _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
 436       }
 437     };
 438
 439 _GLIBCXX_END_NESTED_NAMESPACE
 440
 441 // Declare a partial specialization of vector<T, Alloc>.
 442 #include <bits/stl_vector.h>
 443
 444 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
 445
 446   /**
 447    *  @brief  A specialization of vector for booleans which offers fixed time
 448    *  access to individual elements in any order.
 449    *
 450    *  Note that vector<bool> does not actually meet the requirements for being
 451    *  a container.  This is because the reference and pointer types are not
 452    *  really references and pointers to bool.  See DR96 for details.  @see
 453    *  vector for function documentation.
 454    *
 455    *  @ingroup Containers
 456    *  @ingroup Sequences
 457    *
 458    *  In some terminology a %vector can be described as a dynamic
 459    *  C-style array, it offers fast and efficient access to individual
 460    *  elements in any order and saves the user from worrying about
 461    *  memory and size allocation.  Subscripting ( @c [] ) access is
 462    *  also provided as with C-style arrays.
 463   */
 464 template<typename _Alloc>
 465   class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
 466   {
 467     typedef _Bvector_base<_Alloc>                        _Base;
 468
 469   public:
 470     typedef bool                                         value_type;
 471     typedef size_t                                       size_type;
 472     typedef ptrdiff_t                                    difference_type;
 473     typedef _Bit_reference                               reference;
 474     typedef bool                                         const_reference;
 475     typedef _Bit_reference*                              pointer;
 476     typedef const bool*                                  const_pointer;
 477     typedef _Bit_iterator                                iterator;
 478     typedef _Bit_const_iterator                          const_iterator;
 479     typedef std::reverse_iterator<const_iterator>        const_reverse_iterator;
 480     typedef std::reverse_iterator<iterator>              reverse_iterator;
 481     typedef _Alloc                                       allocator_type;
 482
 483     allocator_type get_allocator() const
 484     { return _Base::get_allocator(); }
 485
 486   protected:
 487     using _Base::_M_allocate;
 488     using _Base::_M_deallocate;
 489     using _Base::_M_get_Bit_allocator;
 490
 491   public:
 492     vector()
 493     : _Base() { }
 494
 495     explicit
 496     vector(const allocator_type& __a)
 497     : _Base(__a) { }
 498
 499     explicit
 500     vector(size_type __n, const bool& __value = bool(),
 501            const allocator_type& __a = allocator_type())
 502     : _Base(__a)
 503     {
 504       _M_initialize(__n);
 505       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage,
 506                 __value ? ~0 : 0);
 507     }
 508
 509     vector(const vector& __x)
 510     : _Base(__x._M_get_Bit_allocator())
 511     {
 512       _M_initialize(__x.size());
 513       _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start);
 514     }
 515
 516     template<class _InputIterator>
 517       vector(_InputIterator __first, _InputIterator __last,
 518              const allocator_type& __a = allocator_type())
 519       : _Base(__a)
 520       {
 521         typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 522         _M_initialize_dispatch(__first, __last, _Integral());
 523       }
 524
 525     ~vector() { }
 526
 527     vector&
 528     operator=(const vector& __x)
 529     {
 530       if (&__x == this)
 531         return *this;
 532       if (__x.size() > capacity())
 533         {
 534           this->_M_deallocate();
 535           _M_initialize(__x.size());
 536         }
 537       this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
 538                                                 begin());
 539       return *this;
 540     }
 541
 542     // assign(), a generalized assignment member function.  Two
 543     // versions: one that takes a count, and one that takes a range.
 544     // The range version is a member template, so we dispatch on whether
 545     // or not the type is an integer.
 546     void
 547     assign(size_type __n, const bool& __x)
 548     { _M_fill_assign(__n, __x); }
 549
 550     template<class _InputIterator>
 551       void
 552       assign(_InputIterator __first, _InputIterator __last)
 553       {
 554         typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 555         _M_assign_dispatch(__first, __last, _Integral());
 556       }
 557
 558     iterator
 559     begin()
 560     { return this->_M_impl._M_start; }
 561
 562     const_iterator
 563     begin() const
 564     { return this->_M_impl._M_start; }
 565
 566     iterator
 567     end()
 568     { return this->_M_impl._M_finish; }
 569
 570     const_iterator
 571     end() const
 572     { return this->_M_impl._M_finish; }
 573
 574     reverse_iterator
 575     rbegin()
 576     { return reverse_iterator(end()); }
 577
 578     const_reverse_iterator
 579     rbegin() const
 580     { return const_reverse_iterator(end()); }
 581
 582     reverse_iterator
 583     rend()
 584     { return reverse_iterator(begin()); }
 585
 586     const_reverse_iterator
 587     rend() const
 588     { return const_reverse_iterator(begin()); }
 589
 590     size_type
 591     size() const
 592     { return size_type(end() - begin()); }
 593
 594     size_type
 595     max_size() const
 596     {
 597       const size_type __asize = _M_get_Bit_allocator().max_size();
 598       return (__asize <= size_type(-1) / int(_S_word_bit) ?
 599               __asize * int(_S_word_bit) : size_type(-1));
 600     }
 601
 602     size_type
 603     capacity() const
 604     { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
 605                        - begin()); }
 606
 607     bool
 608     empty() const
 609     { return begin() == end(); }
 610
 611     reference
 612     operator[](size_type __n)
 613     {
 614       return *iterator(this->_M_impl._M_start._M_p
 615                        + __n / int(_S_word_bit), __n % int(_S_word_bit));
 616     }
 617
 618     const_reference
 619     operator[](size_type __n) const
 620     {
 621       return *const_iterator(this->_M_impl._M_start._M_p
 622                              + __n / int(_S_word_bit), __n % int(_S_word_bit));
 623     }
 624
 625   protected:
 626     void
 627     _M_range_check(size_type __n) const
 628     {
 629       if (__n >= this->size())
 630         __throw_out_of_range(__N("vector<bool>::_M_range_check"));
 631     }
 632
 633   public:
 634     reference
 635     at(size_type __n)
 636     { _M_range_check(__n); return (*this)[__n]; }
 637
 638     const_reference
 639     at(size_type __n) const
 640     { _M_range_check(__n); return (*this)[__n]; }
 641
 642     void
 643     reserve(size_type __n)
 644     {
 645       if (__n > this->max_size())
 646         __throw_length_error(__N("vector::reserve"));
 647       if (this->capacity() < __n)
 648         {
 649           _Bit_type* __q = this->_M_allocate(__n);
 650           this->_M_impl._M_finish = _M_copy_aligned(begin(), end(),
 651                                                     iterator(__q, 0));
 652           this->_M_deallocate();
 653           this->_M_impl._M_start = iterator(__q, 0);
 654           this->_M_impl._M_end_of_storage = (__q + (__n + int(_S_word_bit) - 1)
 655                                              / int(_S_word_bit));
 656         }
 657     }
 658
 659     reference
 660     front()
 661     { return *begin(); }
 662
 663     const_reference
 664     front() const
 665     { return *begin(); }
 666
 667     reference
 668     back()
 669     { return *(end() - 1); }
 670
 671     const_reference
 672     back() const
 673     { return *(end() - 1); }
 674
 675     // _GLIBCXX_RESOLVE_LIB_DEFECTS
 676     // DR 464. Suggestion for new member functions in standard containers.
 677     // N.B. DR 464 says nothing about vector<bool> but we need something
 678     // here due to the way we are implementing DR 464 in the debug-mode
 679     // vector class.
 680     void
 681     data() { }
 682
 683     void
 684     push_back(bool __x)
 685     {
 686       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
 687         *this->_M_impl._M_finish++ = __x;
 688       else
 689         _M_insert_aux(end(), __x);
 690     }
 691
 692     void
 693     swap(vector& __x)
 694     {
 695       std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
 696       std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
 697       std::swap(this->_M_impl._M_end_of_storage,
 698                 __x._M_impl._M_end_of_storage);
 699
 700       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 701       // 431. Swapping containers with unequal allocators.
 702       std::__alloc_swap<typename _Base::_Bit_alloc_type>::
 703         _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator());
 704     }
 705
 706     // [23.2.5]/1, third-to-last entry in synopsis listing
 707     static void
 708     swap(reference __x, reference __y)
 709     {
 710       bool __tmp = __x;
 711       __x = __y;
 712       __y = __tmp;
 713     }
 714
 715     iterator
 716     insert(iterator __position, const bool& __x = bool())
 717     {
 718       const difference_type __n = __position - begin();
 719       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
 720           && __position == end())
 721         *this->_M_impl._M_finish++ = __x;
 722       else
 723         _M_insert_aux(__position, __x);
 724       return begin() + __n;
 725     }
 726
 727     template<class _InputIterator>
 728       void
 729       insert(iterator __position,
 730              _InputIterator __first, _InputIterator __last)
 731       {
 732         typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 733         _M_insert_dispatch(__position, __first, __last, _Integral());
 734       }
 735
 736     void
 737     insert(iterator __position, size_type __n, const bool& __x)
 738     { _M_fill_insert(__position, __n, __x); }
 739
 740     void
 741     pop_back()
 742     { --this->_M_impl._M_finish; }
 743
 744     iterator
 745     erase(iterator __position)
 746     {
 747       if (__position + 1 != end())
 748         std::copy(__position + 1, end(), __position);
 749       --this->_M_impl._M_finish;
 750       return __position;
 751     }
 752
 753     iterator
 754     erase(iterator __first, iterator __last)
 755     {
 756       _M_erase_at_end(std::copy(__last, end(), __first));
 757       return __first;
 758     }
 759
 760     void
 761     resize(size_type __new_size, bool __x = bool())
 762     {
 763       if (__new_size < size())
 764         _M_erase_at_end(begin() + difference_type(__new_size));
 765       else
 766         insert(end(), __new_size - size(), __x);
 767     }
 768
 769     void
 770     flip()
 771     {
 772       for (_Bit_type * __p = this->_M_impl._M_start._M_p;
 773            __p != this->_M_impl._M_end_of_storage; ++__p)
 774         *__p = ~*__p;
 775     }
 776
 777     void
 778     clear()
 779     { _M_erase_at_end(begin()); }
 780
 781
 782   protected:
 783     // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
 784     iterator
 785     _M_copy_aligned(const_iterator __first, const_iterator __last,
 786                     iterator __result)
 787     {
 788       _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
 789       return std::copy(const_iterator(__last._M_p, 0), __last,
 790                        iterator(__q, 0));
 791     }
 792
 793     void
 794     _M_initialize(size_type __n)
 795     {
 796       _Bit_type* __q = this->_M_allocate(__n);
 797       this->_M_impl._M_end_of_storage = (__q
 798                                          + ((__n + int(_S_word_bit) - 1)
 799                                             / int(_S_word_bit)));
 800       this->_M_impl._M_start = iterator(__q, 0);
 801       this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
 802     }
 803
 804     // Check whether it's an integral type.  If so, it's not an iterator.
 805     template<class _Integer>
 806       void
 807       _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
 808       {
 809         _M_initialize(__n);
 810         std::fill(this->_M_impl._M_start._M_p,
 811                   this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
 812       }
 813
 814     template<class _InputIterator>
 815       void
 816       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
 817                              __false_type)
 818       { _M_initialize_range(__first, __last,
 819                             std::__iterator_category(__first)); }
 820
 821     template<class _InputIterator>
 822       void
 823       _M_initialize_range(_InputIterator __first, _InputIterator __last,
 824                           std::input_iterator_tag)
 825       {
 826         for (; __first != __last; ++__first)
 827           push_back(*__first);
 828       }
 829
 830     template<class _ForwardIterator>
 831       void
 832       _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
 833                           std::forward_iterator_tag)
 834       {
 835         const size_type __n = std::distance(__first, __last);
 836         _M_initialize(__n);
 837         std::copy(__first, __last, this->_M_impl._M_start);
 838       }
 839
 840     template<class _Integer>
 841       void
 842       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
 843       { _M_fill_assign((size_t) __n, (bool) __val); }
 844
 845     template<class _InputIterator>
 846       void
 847       _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
 848                          __false_type)
 849       { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
 850
 851     void
 852     _M_fill_assign(size_t __n, bool __x)
 853     {
 854       if (__n > size())
 855         {
 856           std::fill(this->_M_impl._M_start._M_p,
 857                     this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
 858           insert(end(), __n - size(), __x);
 859         }
 860       else
 861         {
 862           _M_erase_at_end(begin() + __n);
 863           std::fill(this->_M_impl._M_start._M_p,
 864                     this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
 865         }
 866     }
 867
 868     template<class _InputIterator>
 869       void
 870       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 871                     std::input_iterator_tag)
 872       {
 873         iterator __cur = begin();
 874         for (; __first != __last && __cur != end(); ++__cur, ++__first)
 875           *__cur = *__first;
 876         if (__first == __last)
 877           _M_erase_at_end(__cur);
 878         else
 879           insert(end(), __first, __last);
 880       }
 881
 882     template<class _ForwardIterator>
 883       void
 884       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 885                     std::forward_iterator_tag)
 886       {
 887         const size_type __len = std::distance(__first, __last);
 888         if (__len < size())
 889           _M_erase_at_end(std::copy(__first, __last, begin()));
 890         else
 891           {
 892             _ForwardIterator __mid = __first;
 893             std::advance(__mid, size());
 894             std::copy(__first, __mid, begin());
 895             insert(end(), __mid, __last);
 896           }
 897       }
 898
 899     // Check whether it's an integral type.  If so, it's not an iterator.
 900     template<class _Integer>
 901       void
 902       _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
 903                          __true_type)
 904       { _M_fill_insert(__pos, __n, __x); }
 905
 906     template<class _InputIterator>
 907       void
 908       _M_insert_dispatch(iterator __pos,
 909                          _InputIterator __first, _InputIterator __last,
 910                          __false_type)
 911       { _M_insert_range(__pos, __first, __last,
 912                         std::__iterator_category(__first)); }
 913
 914     void
 915     _M_fill_insert(iterator __position, size_type __n, bool __x)
 916     {
 917       if (__n == 0)
 918         return;
 919       if (capacity() - size() >= __n)
 920         {
 921           std::copy_backward(__position, end(),
 922                              this->_M_impl._M_finish + difference_type(__n));
 923           std::fill(__position, __position + difference_type(__n), __x);
 924           this->_M_impl._M_finish += difference_type(__n);
 925         }
 926       else
 927         {
 928           const size_type __len = size() + std::max(size(), __n);
 929           _Bit_type * __q = this->_M_allocate(__len);
 930           iterator __i = _M_copy_aligned(begin(), __position,
 931                                          iterator(__q, 0));
 932           std::fill(__i, __i + difference_type(__n), __x);
 933           this->_M_impl._M_finish = std::copy(__position, end(),
 934                                               __i + difference_type(__n));
 935           this->_M_deallocate();
 936           this->_M_impl._M_end_of_storage = (__q + ((__len
 937                                                      + int(_S_word_bit) - 1)
 938                                                     / int(_S_word_bit)));
 939           this->_M_impl._M_start = iterator(__q, 0);
 940         }
 941     }
 942
 943     template<class _InputIterator>
 944       void
 945       _M_insert_range(iterator __pos, _InputIterator __first,
 946                       _InputIterator __last, std::input_iterator_tag)
 947       {
 948         for (; __first != __last; ++__first)
 949           {
 950             __pos = insert(__pos, *__first);
 951             ++__pos;
 952           }
 953       }
 954
 955     template<class _ForwardIterator>
 956       void
 957       _M_insert_range(iterator __position, _ForwardIterator __first,
 958                       _ForwardIterator __last, std::forward_iterator_tag)
 959       {
 960         if (__first != __last)
 961           {
 962             size_type __n = std::distance(__first, __last);
 963             if (capacity() - size() >= __n)
 964               {
 965                 std::copy_backward(__position, end(),
 966                                    this->_M_impl._M_finish
 967                                    + difference_type(__n));
 968                 std::copy(__first, __last, __position);
 969                 this->_M_impl._M_finish += difference_type(__n);
 970               }
 971             else
 972               {
 973                 const size_type __len = size() + std::max(size(), __n);
 974                 _Bit_type * __q = this->_M_allocate(__len);
 975                 iterator __i = _M_copy_aligned(begin(), __position,
 976                                                iterator(__q, 0));
 977                 __i = std::copy(__first, __last, __i);
 978                 this->_M_impl._M_finish = std::copy(__position, end(), __i);
 979                 this->_M_deallocate();
 980                 this->_M_impl._M_end_of_storage = (__q
 981                                                    + ((__len
 982                                                        + int(_S_word_bit) - 1)
 983                                                       / int(_S_word_bit)));
 984                 this->_M_impl._M_start = iterator(__q, 0);
 985               }
 986           }
 987       }
 988
 989     void
 990     _M_insert_aux(iterator __position, bool __x)
 991     {
 992       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
 993         {
 994           std::copy_backward(__position, this->_M_impl._M_finish,
 995                              this->_M_impl._M_finish + 1);
 996           *__position = __x;
 997           ++this->_M_impl._M_finish;
 998         }
 999       else
1000         {
1001           const size_type __len = size() ? 2 * size()
1002                                          : static_cast<size_type>(_S_word_bit);
1003           _Bit_type * __q = this->_M_allocate(__len);
1004           iterator __i = _M_copy_aligned(begin(), __position,
1005                                          iterator(__q, 0));
1006           *__i++ = __x;
1007           this->_M_impl._M_finish = std::copy(__position, end(), __i);
1008           this->_M_deallocate();
1009           this->_M_impl._M_end_of_storage = (__q + ((__len
1010                                                      + int(_S_word_bit) - 1)
1011                                                     / int(_S_word_bit)));
1012           this->_M_impl._M_start = iterator(__q, 0);
1013         }
1014     }
1015
1016     void
1017     _M_erase_at_end(iterator __pos)
1018     { this->_M_impl._M_finish = __pos; }
1019   };
1020
1021 _GLIBCXX_END_NESTED_NAMESPACE
1022
1023 #endif