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

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