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

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