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

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