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