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

   1 // vector<bool> specialization -*- C++ -*-
   2
   3 // Copyright (C) 2001-2023 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 #ifndef _GLIBCXX_ALWAYS_INLINE
  60 #define _GLIBCXX_ALWAYS_INLINE inline __attribute__((__always_inline__))
  61 #endif
  62
  63 #if __cplusplus >= 201103L
  64 #include <initializer_list>
  65 #include <bits/functional_hash.h>
  66 #endif
  67
  68 namespace std _GLIBCXX_VISIBILITY(default)
  69 {
  70 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  71
  72   typedef unsigned long _Bit_type;
  73   enum { _S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type)) };
  74
  75   __attribute__((__nonnull__))
  76   _GLIBCXX20_CONSTEXPR
  77   void
  78   __fill_bvector_n(_Bit_type*, size_t, bool) _GLIBCXX_NOEXCEPT;
  79
  80 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  81
  82   struct _Bit_reference
  83   {
  84     _Bit_type * _M_p;
  85     _Bit_type _M_mask;
  86
  87     _GLIBCXX20_CONSTEXPR
  88     _Bit_reference(_Bit_type * __x, _Bit_type __y)
  89     : _M_p(__x), _M_mask(__y) { }
  90
  91     _GLIBCXX20_CONSTEXPR
  92     _Bit_reference() _GLIBCXX_NOEXCEPT : _M_p(0), _M_mask(0) { }
  93
  94 #if __cplusplus >= 201103L
  95     _Bit_reference(const _Bit_reference&) = default;
  96 #endif
  97
  98     _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
  99     operator bool() const _GLIBCXX_NOEXCEPT
 100     { return !!(*_M_p & _M_mask); }
 101
 102     _GLIBCXX20_CONSTEXPR
 103     _Bit_reference&
 104     operator=(bool __x) _GLIBCXX_NOEXCEPT
 105     {
 106       if (__x)
 107         *_M_p |= _M_mask;
 108       else
 109         *_M_p &= ~_M_mask;
 110       return *this;
 111     }
 112
 113 #if __cplusplus > 202002L
 114     constexpr const _Bit_reference&
 115     operator=(bool __x) const noexcept
 116     {
 117       if (__x)
 118         *_M_p |= _M_mask;
 119       else
 120         *_M_p &= ~_M_mask;
 121       return *this;
 122     }
 123 #endif // C++23
 124
 125     _GLIBCXX20_CONSTEXPR
 126     _Bit_reference&
 127     operator=(const _Bit_reference& __x) _GLIBCXX_NOEXCEPT
 128     { return *this = bool(__x); }
 129
 130     _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 131     bool
 132     operator==(const _Bit_reference& __x) const
 133     { return bool(*this) == bool(__x); }
 134
 135     _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 136     bool
 137     operator<(const _Bit_reference& __x) const
 138     { return !bool(*this) && bool(__x); }
 139
 140     _GLIBCXX20_CONSTEXPR
 141     void
 142     flip() _GLIBCXX_NOEXCEPT
 143     { *_M_p ^= _M_mask; }
 144
 145 #if __cplusplus >= 201103L
 146     _GLIBCXX20_CONSTEXPR
 147     friend void
 148     swap(_Bit_reference __x, _Bit_reference __y) noexcept
 149     {
 150       bool __tmp = __x;
 151       __x = __y;
 152       __y = __tmp;
 153     }
 154
 155     _GLIBCXX20_CONSTEXPR
 156     friend void
 157     swap(_Bit_reference __x, bool& __y) noexcept
 158     {
 159       bool __tmp = __x;
 160       __x = __y;
 161       __y = __tmp;
 162     }
 163
 164     _GLIBCXX20_CONSTEXPR
 165     friend void
 166     swap(bool& __x, _Bit_reference __y) noexcept
 167     {
 168       bool __tmp = __x;
 169       __x = __y;
 170       __y = __tmp;
 171     }
 172 #endif
 173   };
 174
 175 // Ignore warnings about std::iterator.
 176 #pragma GCC diagnostic push
 177 #pragma GCC diagnostic ignored "-Wdeprecated-declarations"
 178   struct _Bit_iterator_base
 179   : public std::iterator<std::random_access_iterator_tag, bool>
 180   {
 181     _Bit_type * _M_p;
 182     unsigned int _M_offset;
 183
 184     _GLIBCXX20_CONSTEXPR _GLIBCXX_ALWAYS_INLINE
 185     void
 186     _M_assume_normalized() const
 187     {
 188 #if __has_attribute(__assume__) && !defined(__clang__)
 189       unsigned int __ofst = _M_offset;
 190       __attribute__ ((__assume__ (__ofst < unsigned(_S_word_bit))));
 191 #endif
 192     }
 193
 194     _GLIBCXX20_CONSTEXPR
 195     _Bit_iterator_base(_Bit_type * __x, unsigned int __y)
 196     : _M_p(__x), _M_offset(__y) { }
 197
 198     _GLIBCXX20_CONSTEXPR
 199     void
 200     _M_bump_up()
 201     {
 202       _M_assume_normalized();
 203       if (_M_offset++ == int(_S_word_bit) - 1)
 204         {
 205           _M_offset = 0;
 206           ++_M_p;
 207         }
 208     }
 209
 210     _GLIBCXX20_CONSTEXPR
 211     void
 212     _M_bump_down()
 213     {
 214       _M_assume_normalized();
 215       if (_M_offset-- == 0)
 216         {
 217           _M_offset = int(_S_word_bit) - 1;
 218           --_M_p;
 219         }
 220     }
 221
 222     _GLIBCXX20_CONSTEXPR
 223     void
 224     _M_incr(ptrdiff_t __i)
 225     {
 226       _M_assume_normalized();
 227       difference_type __n = __i + _M_offset;
 228       _M_p += __n / int(_S_word_bit);
 229       __n = __n % int(_S_word_bit);
 230       if (__n < 0)
 231         {
 232           __n += int(_S_word_bit);
 233           --_M_p;
 234         }
 235       _M_offset = static_cast<unsigned int>(__n);
 236     }
 237
 238     _GLIBCXX_NODISCARD
 239     friend _GLIBCXX20_CONSTEXPR bool
 240     operator==(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
 241     {
 242       __x._M_assume_normalized();
 243       __y._M_assume_normalized();
 244       return __x._M_p == __y._M_p && __x._M_offset == __y._M_offset;
 245     }
 246
 247 #if __cpp_lib_three_way_comparison
 248     [[nodiscard]]
 249     friend constexpr strong_ordering
 250     operator<=>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
 251     noexcept
 252     {
 253       __x._M_assume_normalized();
 254       __y._M_assume_normalized();
 255       if (const auto __cmp = __x._M_p <=> __y._M_p; __cmp != 0)
 256         return __cmp;
 257       return __x._M_offset <=> __y._M_offset;
 258     }
 259 #else
 260     _GLIBCXX_NODISCARD
 261     friend bool
 262     operator<(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
 263     {
 264       __x._M_assume_normalized();
 265       __y._M_assume_normalized();
 266       return __x._M_p < __y._M_p
 267             || (__x._M_p == __y._M_p && __x._M_offset < __y._M_offset);
 268     }
 269
 270     _GLIBCXX_NODISCARD
 271     friend bool
 272     operator!=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
 273     { return !(__x == __y); }
 274
 275     _GLIBCXX_NODISCARD
 276     friend bool
 277     operator>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
 278     { return __y < __x; }
 279
 280     _GLIBCXX_NODISCARD
 281     friend bool
 282     operator<=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
 283     { return !(__y < __x); }
 284
 285     _GLIBCXX_NODISCARD
 286     friend bool
 287     operator>=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
 288     { return !(__x < __y); }
 289 #endif // three-way comparison
 290
 291     friend _GLIBCXX20_CONSTEXPR ptrdiff_t
 292     operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
 293     {
 294       __x._M_assume_normalized();
 295       __y._M_assume_normalized();
 296       return (int(_S_word_bit) * (__x._M_p - __y._M_p)
 297               + __x._M_offset - __y._M_offset);
 298     }
 299   };
 300 #pragma GCC diagnostic pop
 301
 302   struct _Bit_iterator : public _Bit_iterator_base
 303   {
 304     typedef _Bit_reference  reference;
 305 #if __cplusplus > 201703L
 306     typedef void            pointer;
 307 #else
 308     typedef _Bit_reference* pointer;
 309 #endif
 310     typedef _Bit_iterator   iterator;
 311
 312     _GLIBCXX20_CONSTEXPR
 313     _Bit_iterator() : _Bit_iterator_base(0, 0) { }
 314
 315     _GLIBCXX20_CONSTEXPR
 316     _Bit_iterator(_Bit_type * __x, unsigned int __y)
 317     : _Bit_iterator_base(__x, __y) { }
 318
 319     _GLIBCXX20_CONSTEXPR
 320     iterator
 321     _M_const_cast() const
 322     { return *this; }
 323
 324     _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 325     reference
 326     operator*() const
 327     {
 328       _M_assume_normalized();
 329       return reference(_M_p, 1UL << _M_offset);
 330     }
 331
 332     _GLIBCXX20_CONSTEXPR
 333     iterator&
 334     operator++()
 335     {
 336       _M_bump_up();
 337       return *this;
 338     }
 339
 340     _GLIBCXX20_CONSTEXPR
 341     iterator
 342     operator++(int)
 343     {
 344       iterator __tmp = *this;
 345       _M_bump_up();
 346       return __tmp;
 347     }
 348
 349     _GLIBCXX20_CONSTEXPR
 350     iterator&
 351     operator--()
 352     {
 353       _M_bump_down();
 354       return *this;
 355     }
 356
 357     _GLIBCXX20_CONSTEXPR
 358     iterator
 359     operator--(int)
 360     {
 361       iterator __tmp = *this;
 362       _M_bump_down();
 363       return __tmp;
 364     }
 365
 366     _GLIBCXX20_CONSTEXPR
 367     iterator&
 368     operator+=(difference_type __i)
 369     {
 370       _M_incr(__i);
 371       return *this;
 372     }
 373
 374     _GLIBCXX20_CONSTEXPR
 375     iterator&
 376     operator-=(difference_type __i)
 377     {
 378       *this += -__i;
 379       return *this;
 380     }
 381
 382     _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 383     reference
 384     operator[](difference_type __i) const
 385     { return *(*this + __i); }
 386
 387     _GLIBCXX_NODISCARD
 388     friend _GLIBCXX20_CONSTEXPR iterator
 389     operator+(const iterator& __x, difference_type __n)
 390     {
 391       iterator __tmp = __x;
 392       __tmp += __n;
 393       return __tmp;
 394     }
 395
 396     _GLIBCXX_NODISCARD
 397     friend _GLIBCXX20_CONSTEXPR iterator
 398     operator+(difference_type __n, const iterator& __x)
 399     { return __x + __n; }
 400
 401     _GLIBCXX_NODISCARD
 402     friend _GLIBCXX20_CONSTEXPR iterator
 403     operator-(const iterator& __x, difference_type __n)
 404     {
 405       iterator __tmp = __x;
 406       __tmp -= __n;
 407       return __tmp;
 408     }
 409   };
 410
 411   struct _Bit_const_iterator : public _Bit_iterator_base
 412   {
 413     typedef bool                 reference;
 414     typedef bool                 const_reference;
 415 #if __cplusplus > 201703L
 416     typedef void            pointer;
 417 #else
 418     typedef const bool*          pointer;
 419 #endif
 420     typedef _Bit_const_iterator  const_iterator;
 421
 422     _GLIBCXX20_CONSTEXPR
 423     _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
 424
 425     _GLIBCXX20_CONSTEXPR
 426     _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
 427     : _Bit_iterator_base(__x, __y) { }
 428
 429     _GLIBCXX20_CONSTEXPR
 430     _Bit_const_iterator(const _Bit_iterator& __x)
 431     : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
 432
 433     _GLIBCXX20_CONSTEXPR
 434     _Bit_iterator
 435     _M_const_cast() const
 436     { return _Bit_iterator(_M_p, _M_offset); }
 437
 438     _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 439     const_reference
 440     operator*() const
 441     {
 442       _M_assume_normalized();
 443       return _Bit_reference(_M_p, 1UL << _M_offset);
 444     }
 445
 446     _GLIBCXX20_CONSTEXPR
 447     const_iterator&
 448     operator++()
 449     {
 450       _M_bump_up();
 451       return *this;
 452     }
 453
 454     _GLIBCXX20_CONSTEXPR
 455     const_iterator
 456     operator++(int)
 457     {
 458       const_iterator __tmp = *this;
 459       _M_bump_up();
 460       return __tmp;
 461     }
 462
 463     _GLIBCXX20_CONSTEXPR
 464     const_iterator&
 465     operator--()
 466     {
 467       _M_bump_down();
 468       return *this;
 469     }
 470
 471     _GLIBCXX20_CONSTEXPR
 472     const_iterator
 473     operator--(int)
 474     {
 475       const_iterator __tmp = *this;
 476       _M_bump_down();
 477       return __tmp;
 478     }
 479
 480     _GLIBCXX20_CONSTEXPR
 481     const_iterator&
 482     operator+=(difference_type __i)
 483     {
 484       _M_incr(__i);
 485       return *this;
 486     }
 487
 488     _GLIBCXX20_CONSTEXPR
 489     const_iterator&
 490     operator-=(difference_type __i)
 491     {
 492       *this += -__i;
 493       return *this;
 494     }
 495
 496     _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 497     const_reference
 498     operator[](difference_type __i) const
 499     { return *(*this + __i); }
 500
 501     _GLIBCXX_NODISCARD
 502     friend _GLIBCXX20_CONSTEXPR const_iterator
 503     operator+(const const_iterator& __x, difference_type __n)
 504     {
 505       const_iterator __tmp = __x;
 506       __tmp += __n;
 507       return __tmp;
 508     }
 509
 510     _GLIBCXX_NODISCARD
 511     friend _GLIBCXX20_CONSTEXPR const_iterator
 512     operator-(const const_iterator& __x, difference_type __n)
 513     {
 514       const_iterator __tmp = __x;
 515       __tmp -= __n;
 516       return __tmp;
 517     }
 518
 519     _GLIBCXX_NODISCARD
 520     friend _GLIBCXX20_CONSTEXPR const_iterator
 521     operator+(difference_type __n, const const_iterator& __x)
 522     { return __x + __n; }
 523   };
 524
 525   template<typename _Alloc>
 526     struct _Bvector_base
 527     {
 528       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
 529         rebind<_Bit_type>::other _Bit_alloc_type;
 530       typedef typename __gnu_cxx::__alloc_traits<_Bit_alloc_type>
 531         _Bit_alloc_traits;
 532       typedef typename _Bit_alloc_traits::pointer _Bit_pointer;
 533
 534       struct _Bvector_impl_data
 535       {
 536 #if !_GLIBCXX_INLINE_VERSION
 537         _Bit_iterator   _M_start;
 538 #else
 539         // We don't need the offset field for the start, it's always zero.
 540         struct {
 541           _Bit_type* _M_p;
 542           // Allow assignment from iterators (assume offset is zero):
 543           _GLIBCXX20_CONSTEXPR
 544           void operator=(_Bit_iterator __it) { _M_p = __it._M_p; }
 545         } _M_start;
 546 #endif
 547         _Bit_iterator   _M_finish;
 548         _Bit_pointer    _M_end_of_storage;
 549
 550         _GLIBCXX20_CONSTEXPR
 551         _Bvector_impl_data() _GLIBCXX_NOEXCEPT
 552         : _M_start(), _M_finish(), _M_end_of_storage()
 553         { }
 554
 555 #if __cplusplus >= 201103L
 556         _Bvector_impl_data(const _Bvector_impl_data&) = default;
 557
 558         _Bvector_impl_data&
 559         operator=(const _Bvector_impl_data&) = default;
 560
 561         _GLIBCXX20_CONSTEXPR
 562         _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept
 563         : _Bvector_impl_data(__x)
 564         { __x._M_reset(); }
 565
 566         _GLIBCXX20_CONSTEXPR
 567         void
 568         _M_move_data(_Bvector_impl_data&& __x) noexcept
 569         {
 570           *this = __x;
 571           __x._M_reset();
 572         }
 573 #endif
 574
 575         _GLIBCXX20_CONSTEXPR
 576         void
 577         _M_reset() _GLIBCXX_NOEXCEPT
 578         { *this = _Bvector_impl_data(); }
 579
 580         _GLIBCXX20_CONSTEXPR
 581         void
 582         _M_swap_data(_Bvector_impl_data& __x) _GLIBCXX_NOEXCEPT
 583         {
 584           // Do not use std::swap(_M_start, __x._M_start), etc as it loses
 585           // information used by TBAA.
 586           std::swap(*this, __x);
 587         }
 588       };
 589
 590       struct _Bvector_impl
 591         : public _Bit_alloc_type, public _Bvector_impl_data
 592       {
 593         _GLIBCXX20_CONSTEXPR
 594         _Bvector_impl() _GLIBCXX_NOEXCEPT_IF(
 595           is_nothrow_default_constructible<_Bit_alloc_type>::value)
 596         : _Bit_alloc_type()
 597         { }
 598
 599         _GLIBCXX20_CONSTEXPR
 600         _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT
 601         : _Bit_alloc_type(__a)
 602         { }
 603
 604 #if __cplusplus >= 201103L
 605         // Not defaulted, to enforce noexcept(true) even when
 606         // !is_nothrow_move_constructible<_Bit_alloc_type>.
 607         _GLIBCXX20_CONSTEXPR
 608         _Bvector_impl(_Bvector_impl&& __x) noexcept
 609         : _Bit_alloc_type(std::move(__x)), _Bvector_impl_data(std::move(__x))
 610         { }
 611
 612         _GLIBCXX20_CONSTEXPR
 613         _Bvector_impl(_Bit_alloc_type&& __a, _Bvector_impl&& __x) noexcept
 614         : _Bit_alloc_type(std::move(__a)), _Bvector_impl_data(std::move(__x))
 615         { }
 616 #endif
 617
 618         _GLIBCXX20_CONSTEXPR
 619         _Bit_type*
 620         _M_end_addr() const _GLIBCXX_NOEXCEPT
 621         {
 622           if (this->_M_end_of_storage)
 623             return std::__addressof(this->_M_end_of_storage[-1]) + 1;
 624           return 0;
 625         }
 626       };
 627
 628     public:
 629       typedef _Alloc allocator_type;
 630
 631       _GLIBCXX20_CONSTEXPR
 632       _Bit_alloc_type&
 633       _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT
 634       { return this->_M_impl; }
 635
 636       _GLIBCXX20_CONSTEXPR
 637       const _Bit_alloc_type&
 638       _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT
 639       { return this->_M_impl; }
 640
 641       _GLIBCXX20_CONSTEXPR
 642       allocator_type
 643       get_allocator() const _GLIBCXX_NOEXCEPT
 644       { return allocator_type(_M_get_Bit_allocator()); }
 645
 646 #if __cplusplus >= 201103L
 647       _Bvector_base() = default;
 648 #else
 649       _Bvector_base() { }
 650 #endif
 651
 652       _GLIBCXX20_CONSTEXPR
 653       _Bvector_base(const allocator_type& __a)
 654       : _M_impl(__a) { }
 655
 656 #if __cplusplus >= 201103L
 657       _Bvector_base(_Bvector_base&&) = default;
 658
 659       _GLIBCXX20_CONSTEXPR
 660       _Bvector_base(_Bvector_base&& __x, const allocator_type& __a) noexcept
 661       : _M_impl(_Bit_alloc_type(__a), std::move(__x._M_impl))
 662       { }
 663 #endif
 664
 665       _GLIBCXX20_CONSTEXPR
 666       ~_Bvector_base()
 667       { this->_M_deallocate(); }
 668
 669     protected:
 670       _Bvector_impl _M_impl;
 671
 672       _GLIBCXX20_CONSTEXPR
 673       _Bit_pointer
 674       _M_allocate(size_t __n)
 675       {
 676         _Bit_pointer __p = _Bit_alloc_traits::allocate(_M_impl, _S_nword(__n));
 677 #if __cpp_lib_is_constant_evaluated
 678         if (std::is_constant_evaluated())
 679         {
 680           __n = _S_nword(__n);
 681           for (size_t __i = 0; __i < __n; ++__i)
 682             __p[__i] = 0ul;
 683         }
 684 #endif
 685         return __p;
 686       }
 687
 688       _GLIBCXX20_CONSTEXPR
 689       void
 690       _M_deallocate()
 691       {
 692         if (_M_impl._M_start._M_p)
 693           {
 694             const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p;
 695             _Bit_alloc_traits::deallocate(_M_impl,
 696                                           _M_impl._M_end_of_storage - __n,
 697                                           __n);
 698             _M_impl._M_reset();
 699           }
 700       }
 701
 702 #if __cplusplus >= 201103L
 703       _GLIBCXX20_CONSTEXPR
 704       void
 705       _M_move_data(_Bvector_base&& __x) noexcept
 706       { _M_impl._M_move_data(std::move(__x._M_impl)); }
 707 #endif
 708
 709       _GLIBCXX_CONSTEXPR
 710       static size_t
 711       _S_nword(size_t __n)
 712       { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); }
 713     };
 714
 715   /**
 716    *  @brief  A specialization of vector for booleans which offers fixed time
 717    *  access to individual elements in any order.
 718    *
 719    *  @ingroup sequences
 720    *  @headerfile vector
 721    *  @since C++98
 722    *
 723    *  @tparam _Alloc  Allocator type.
 724    *
 725    *  Note that vector<bool> does not actually meet the requirements for being
 726    *  a container.  This is because the reference and pointer types are not
 727    *  really references and pointers to bool.  See DR96 for details.  @see
 728    *  vector for function documentation.
 729    *
 730    *  In some terminology a %vector can be described as a dynamic
 731    *  C-style array, it offers fast and efficient access to individual
 732    *  elements in any order and saves the user from worrying about
 733    *  memory and size allocation.  Subscripting ( @c [] ) access is
 734    *  also provided as with C-style arrays.
 735   */
 736   template<typename _Alloc>
 737     class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
 738     {
 739       typedef _Bvector_base<_Alloc>                     _Base;
 740       typedef typename _Base::_Bit_pointer              _Bit_pointer;
 741       typedef typename _Base::_Bit_alloc_traits         _Bit_alloc_traits;
 742
 743 #if __cplusplus >= 201103L
 744       friend struct std::hash<vector>;
 745 #endif
 746
 747     public:
 748       typedef bool                                      value_type;
 749       typedef size_t                                    size_type;
 750       typedef ptrdiff_t                                 difference_type;
 751       typedef _Bit_reference                            reference;
 752       typedef bool                                      const_reference;
 753       typedef _Bit_reference*                           pointer;
 754       typedef const bool*                               const_pointer;
 755       typedef _Bit_iterator                             iterator;
 756       typedef _Bit_const_iterator                       const_iterator;
 757       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
 758       typedef std::reverse_iterator<iterator>           reverse_iterator;
 759       typedef _Alloc                                    allocator_type;
 760
 761       _GLIBCXX20_CONSTEXPR
 762       allocator_type
 763       get_allocator() const
 764       { return _Base::get_allocator(); }
 765
 766     protected:
 767       using _Base::_M_allocate;
 768       using _Base::_M_deallocate;
 769       using _Base::_S_nword;
 770       using _Base::_M_get_Bit_allocator;
 771
 772     public:
 773 #if __cplusplus >= 201103L
 774       vector() = default;
 775 #else
 776       vector() { }
 777 #endif
 778
 779       _GLIBCXX20_CONSTEXPR
 780       explicit
 781       vector(const allocator_type& __a)
 782       : _Base(__a) { }
 783
 784 #if __cplusplus >= 201103L
 785       _GLIBCXX20_CONSTEXPR
 786       explicit
 787       vector(size_type __n, const allocator_type& __a = allocator_type())
 788       : vector(__n, false, __a)
 789       { }
 790
 791       _GLIBCXX20_CONSTEXPR
 792       vector(size_type __n, const bool& __value,
 793              const allocator_type& __a = allocator_type())
 794 #else
 795       explicit
 796       vector(size_type __n, const bool& __value = bool(),
 797              const allocator_type& __a = allocator_type())
 798 #endif
 799       : _Base(__a)
 800       {
 801         _M_initialize(__n);
 802         _M_initialize_value(__value);
 803       }
 804
 805       _GLIBCXX20_CONSTEXPR
 806       vector(const vector& __x)
 807       : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator()))
 808       {
 809         const_iterator __xbegin = __x.begin(), __xend = __x.end();
 810         _M_initialize(__x.size());
 811         _M_copy_aligned(__xbegin, __xend, begin());
 812       }
 813
 814 #if __cplusplus >= 201103L
 815       vector(vector&&) = default;
 816
 817     private:
 818       _GLIBCXX20_CONSTEXPR
 819       vector(vector&& __x, const allocator_type& __a, true_type) noexcept
 820       : _Base(std::move(__x), __a)
 821       { }
 822
 823       _GLIBCXX20_CONSTEXPR
 824       vector(vector&& __x, const allocator_type& __a, false_type)
 825       : _Base(__a)
 826       {
 827         if (__x.get_allocator() == __a)
 828           this->_M_move_data(std::move(__x));
 829         else
 830           {
 831             _M_initialize(__x.size());
 832             _M_copy_aligned(__x.begin(), __x.end(), begin());
 833             __x.clear();
 834           }
 835       }
 836
 837     public:
 838       _GLIBCXX20_CONSTEXPR
 839       vector(vector&& __x, const __type_identity_t<allocator_type>& __a)
 840       noexcept(_Bit_alloc_traits::_S_always_equal())
 841       : vector(std::move(__x), __a,
 842                typename _Bit_alloc_traits::is_always_equal{})
 843       { }
 844
 845       _GLIBCXX20_CONSTEXPR
 846       vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
 847       : _Base(__a)
 848       {
 849         _M_initialize(__x.size());
 850         _M_copy_aligned(__x.begin(), __x.end(), begin());
 851       }
 852
 853       _GLIBCXX20_CONSTEXPR
 854       vector(initializer_list<bool> __l,
 855              const allocator_type& __a = allocator_type())
 856       : _Base(__a)
 857       {
 858         _M_initialize_range(__l.begin(), __l.end(),
 859                             random_access_iterator_tag());
 860       }
 861 #endif
 862
 863 #if __cplusplus >= 201103L
 864       template<typename _InputIterator,
 865                typename = std::_RequireInputIter<_InputIterator>>
 866         _GLIBCXX20_CONSTEXPR
 867         vector(_InputIterator __first, _InputIterator __last,
 868                const allocator_type& __a = allocator_type())
 869         : _Base(__a)
 870         {
 871           _M_initialize_range(__first, __last,
 872                               std::__iterator_category(__first));
 873         }
 874 #else
 875       template<typename _InputIterator>
 876         vector(_InputIterator __first, _InputIterator __last,
 877                const allocator_type& __a = allocator_type())
 878         : _Base(__a)
 879         {
 880           // Check whether it's an integral type. If so, it's not an iterator.
 881           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 882           _M_initialize_dispatch(__first, __last, _Integral());
 883         }
 884 #endif
 885
 886       _GLIBCXX20_CONSTEXPR
 887       ~vector() _GLIBCXX_NOEXCEPT { }
 888
 889       _GLIBCXX20_CONSTEXPR
 890       vector&
 891       operator=(const vector& __x)
 892       {
 893         if (&__x == this)
 894           return *this;
 895 #if __cplusplus >= 201103L
 896         if (_Bit_alloc_traits::_S_propagate_on_copy_assign())
 897           {
 898             if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator())
 899               {
 900                 this->_M_deallocate();
 901                 std::__alloc_on_copy(_M_get_Bit_allocator(),
 902                                      __x._M_get_Bit_allocator());
 903                 _M_initialize(__x.size());
 904               }
 905             else
 906               std::__alloc_on_copy(_M_get_Bit_allocator(),
 907                                    __x._M_get_Bit_allocator());
 908           }
 909 #endif
 910         if (__x.size() > capacity())
 911           {
 912             this->_M_deallocate();
 913             _M_initialize(__x.size());
 914           }
 915         this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
 916                                                   begin());
 917         return *this;
 918       }
 919
 920 #if __cplusplus >= 201103L
 921       _GLIBCXX20_CONSTEXPR
 922       vector&
 923       operator=(vector&& __x) noexcept(_Bit_alloc_traits::_S_nothrow_move())
 924       {
 925         if (_Bit_alloc_traits::_S_propagate_on_move_assign()
 926             || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator())
 927           {
 928             this->_M_deallocate();
 929             this->_M_move_data(std::move(__x));
 930             std::__alloc_on_move(_M_get_Bit_allocator(),
 931                                  __x._M_get_Bit_allocator());
 932           }
 933         else
 934           {
 935             if (__x.size() > capacity())
 936               {
 937                 this->_M_deallocate();
 938                 _M_initialize(__x.size());
 939               }
 940             this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
 941                                                       begin());
 942             __x.clear();
 943           }
 944         return *this;
 945       }
 946
 947       _GLIBCXX20_CONSTEXPR
 948       vector&
 949       operator=(initializer_list<bool> __l)
 950       {
 951         this->assign(__l.begin(), __l.end());
 952         return *this;
 953       }
 954 #endif
 955
 956       // assign(), a generalized assignment member function.  Two
 957       // versions: one that takes a count, and one that takes a range.
 958       // The range version is a member template, so we dispatch on whether
 959       // or not the type is an integer.
 960       _GLIBCXX20_CONSTEXPR
 961       void
 962       assign(size_type __n, const bool& __x)
 963       { _M_fill_assign(__n, __x); }
 964
 965 #if __cplusplus >= 201103L
 966       template<typename _InputIterator,
 967                typename = std::_RequireInputIter<_InputIterator>>
 968         _GLIBCXX20_CONSTEXPR
 969         void
 970         assign(_InputIterator __first, _InputIterator __last)
 971         { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
 972 #else
 973       template<typename _InputIterator>
 974         void
 975         assign(_InputIterator __first, _InputIterator __last)
 976         {
 977           // Check whether it's an integral type. If so, it's not an iterator.
 978           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 979           _M_assign_dispatch(__first, __last, _Integral());
 980         }
 981 #endif
 982
 983 #if __cplusplus >= 201103L
 984       _GLIBCXX20_CONSTEXPR
 985       void
 986       assign(initializer_list<bool> __l)
 987       { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); }
 988 #endif
 989
 990       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 991       iterator
 992       begin() _GLIBCXX_NOEXCEPT
 993       { return iterator(this->_M_impl._M_start._M_p, 0); }
 994
 995       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
 996       const_iterator
 997       begin() const _GLIBCXX_NOEXCEPT
 998       { return const_iterator(this->_M_impl._M_start._M_p, 0); }
 999
1000       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1001       iterator
1002       end() _GLIBCXX_NOEXCEPT
1003       { return this->_M_impl._M_finish; }
1004
1005       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1006       const_iterator
1007       end() const _GLIBCXX_NOEXCEPT
1008       { return this->_M_impl._M_finish; }
1009
1010       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1011       reverse_iterator
1012       rbegin() _GLIBCXX_NOEXCEPT
1013       { return reverse_iterator(end()); }
1014
1015       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1016       const_reverse_iterator
1017       rbegin() const _GLIBCXX_NOEXCEPT
1018       { return const_reverse_iterator(end()); }
1019
1020       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1021       reverse_iterator
1022       rend() _GLIBCXX_NOEXCEPT
1023       { return reverse_iterator(begin()); }
1024
1025       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1026       const_reverse_iterator
1027       rend() const _GLIBCXX_NOEXCEPT
1028       { return const_reverse_iterator(begin()); }
1029
1030 #if __cplusplus >= 201103L
1031       [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1032       const_iterator
1033       cbegin() const noexcept
1034       { return const_iterator(this->_M_impl._M_start._M_p, 0); }
1035
1036       [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1037       const_iterator
1038       cend() const noexcept
1039       { return this->_M_impl._M_finish; }
1040
1041       [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1042       const_reverse_iterator
1043       crbegin() const noexcept
1044       { return const_reverse_iterator(end()); }
1045
1046       [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1047       const_reverse_iterator
1048       crend() const noexcept
1049       { return const_reverse_iterator(begin()); }
1050 #endif
1051
1052       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1053       size_type
1054       size() const _GLIBCXX_NOEXCEPT
1055       { return size_type(end() - begin()); }
1056
1057       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1058       size_type
1059       max_size() const _GLIBCXX_NOEXCEPT
1060       {
1061         const size_type __isize =
1062           __gnu_cxx::__numeric_traits<difference_type>::__max
1063           - int(_S_word_bit) + 1;
1064         const size_type __asize
1065           = _Bit_alloc_traits::max_size(_M_get_Bit_allocator());
1066         return (__asize <= __isize / int(_S_word_bit)
1067                 ? __asize * int(_S_word_bit) : __isize);
1068       }
1069
1070       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1071       size_type
1072       capacity() const _GLIBCXX_NOEXCEPT
1073       { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0)
1074                          - begin()); }
1075
1076       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1077       bool
1078       empty() const _GLIBCXX_NOEXCEPT
1079       { return begin() == end(); }
1080
1081       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1082       reference
1083       operator[](size_type __n)
1084       { return begin()[__n]; }
1085
1086       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1087       const_reference
1088       operator[](size_type __n) const
1089       { return begin()[__n]; }
1090
1091     protected:
1092       _GLIBCXX20_CONSTEXPR
1093       void
1094       _M_range_check(size_type __n) const
1095       {
1096         if (__n >= this->size())
1097           __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n "
1098                                        "(which is %zu) >= this->size() "
1099                                        "(which is %zu)"),
1100                                    __n, this->size());
1101       }
1102
1103     public:
1104       _GLIBCXX20_CONSTEXPR
1105       reference
1106       at(size_type __n)
1107       {
1108         _M_range_check(__n);
1109         return (*this)[__n];
1110       }
1111
1112       _GLIBCXX20_CONSTEXPR
1113       const_reference
1114       at(size_type __n) const
1115       {
1116         _M_range_check(__n);
1117         return (*this)[__n];
1118       }
1119
1120       _GLIBCXX20_CONSTEXPR
1121       void
1122       reserve(size_type __n)
1123       {
1124         if (__n > max_size())
1125           __throw_length_error(__N("vector::reserve"));
1126         if (capacity() < __n)
1127           _M_reallocate(__n);
1128       }
1129
1130       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1131       reference
1132       front()
1133       { return *begin(); }
1134
1135       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1136       const_reference
1137       front() const
1138       { return *begin(); }
1139
1140       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1141       reference
1142       back()
1143       { return *(end() - 1); }
1144
1145       _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1146       const_reference
1147       back() const
1148       { return *(end() - 1); }
1149
1150       _GLIBCXX20_CONSTEXPR
1151       void
1152       push_back(bool __x)
1153       {
1154         if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
1155           *this->_M_impl._M_finish++ = __x;
1156         else
1157           _M_insert_aux(end(), __x);
1158       }
1159
1160       _GLIBCXX20_CONSTEXPR
1161       void
1162       swap(vector& __x) _GLIBCXX_NOEXCEPT
1163       {
1164 #if __cplusplus >= 201103L
1165         __glibcxx_assert(_Bit_alloc_traits::propagate_on_container_swap::value
1166                          || _M_get_Bit_allocator() == __x._M_get_Bit_allocator());
1167 #endif
1168         this->_M_impl._M_swap_data(__x._M_impl);
1169         _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(),
1170                                       __x._M_get_Bit_allocator());
1171       }
1172
1173       // [23.2.5]/1, third-to-last entry in synopsis listing
1174       _GLIBCXX20_CONSTEXPR
1175       static void
1176       swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
1177       {
1178         bool __tmp = __x;
1179         __x = __y;
1180         __y = __tmp;
1181       }
1182
1183       _GLIBCXX20_CONSTEXPR
1184       iterator
1185 #if __cplusplus >= 201103L
1186       insert(const_iterator __position, const bool& __x)
1187 #else
1188       insert(iterator __position, const bool& __x)
1189 #endif
1190       {
1191         const difference_type __n = __position - begin();
1192         if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()
1193             && __position == end())
1194           *this->_M_impl._M_finish++ = __x;
1195         else
1196           _M_insert_aux(__position._M_const_cast(), __x);
1197         return begin() + __n;
1198       }
1199
1200 #if _GLIBCXX_USE_DEPRECATED
1201       _GLIBCXX_DEPRECATED_SUGGEST("insert(position, false)")
1202       iterator
1203       insert(const_iterator __position)
1204       { return this->insert(__position._M_const_cast(), false); }
1205 #endif
1206
1207 #if __cplusplus >= 201103L
1208       template<typename _InputIterator,
1209                typename = std::_RequireInputIter<_InputIterator>>
1210         _GLIBCXX20_CONSTEXPR
1211         iterator
1212         insert(const_iterator __position,
1213                _InputIterator __first, _InputIterator __last)
1214         {
1215           difference_type __offset = __position - cbegin();
1216           _M_insert_range(__position._M_const_cast(),
1217                           __first, __last,
1218                           std::__iterator_category(__first));
1219           return begin() + __offset;
1220         }
1221 #else
1222       template<typename _InputIterator>
1223         void
1224         insert(iterator __position,
1225                _InputIterator __first, _InputIterator __last)
1226         {
1227           // Check whether it's an integral type. If so, it's not an iterator.
1228           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1229           _M_insert_dispatch(__position, __first, __last, _Integral());
1230         }
1231 #endif
1232
1233 #if __cplusplus >= 201103L
1234       _GLIBCXX20_CONSTEXPR
1235       iterator
1236       insert(const_iterator __position, size_type __n, const bool& __x)
1237       {
1238         difference_type __offset = __position - cbegin();
1239         _M_fill_insert(__position._M_const_cast(), __n, __x);
1240         return begin() + __offset;
1241       }
1242 #else
1243       void
1244       insert(iterator __position, size_type __n, const bool& __x)
1245       { _M_fill_insert(__position, __n, __x); }
1246 #endif
1247
1248 #if __cplusplus >= 201103L
1249       _GLIBCXX20_CONSTEXPR
1250       iterator
1251       insert(const_iterator __p, initializer_list<bool> __l)
1252       { return this->insert(__p, __l.begin(), __l.end()); }
1253 #endif
1254
1255       _GLIBCXX20_CONSTEXPR
1256       void
1257       pop_back()
1258       { --this->_M_impl._M_finish; }
1259
1260       _GLIBCXX20_CONSTEXPR
1261       iterator
1262 #if __cplusplus >= 201103L
1263       erase(const_iterator __position)
1264 #else
1265       erase(iterator __position)
1266 #endif
1267       { return _M_erase(__position._M_const_cast()); }
1268
1269       _GLIBCXX20_CONSTEXPR
1270       iterator
1271 #if __cplusplus >= 201103L
1272       erase(const_iterator __first, const_iterator __last)
1273 #else
1274       erase(iterator __first, iterator __last)
1275 #endif
1276       { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1277
1278       _GLIBCXX20_CONSTEXPR
1279       void
1280       resize(size_type __new_size, bool __x = bool())
1281       {
1282         if (__new_size < size())
1283           _M_erase_at_end(begin() + difference_type(__new_size));
1284         else
1285           insert(end(), __new_size - size(), __x);
1286       }
1287
1288 #if __cplusplus >= 201103L
1289       _GLIBCXX20_CONSTEXPR
1290       void
1291       shrink_to_fit()
1292       { _M_shrink_to_fit(); }
1293 #endif
1294
1295       _GLIBCXX20_CONSTEXPR
1296       void
1297       flip() _GLIBCXX_NOEXCEPT
1298       {
1299         _Bit_type * const __end = this->_M_impl._M_end_addr();
1300         for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p)
1301           *__p = ~*__p;
1302       }
1303
1304       _GLIBCXX20_CONSTEXPR
1305       void
1306       clear() _GLIBCXX_NOEXCEPT
1307       { _M_erase_at_end(begin()); }
1308
1309 #if __cplusplus >= 201103L
1310       template<typename... _Args>
1311 #if __cplusplus > 201402L
1312         _GLIBCXX20_CONSTEXPR
1313         reference
1314 #else
1315         void
1316 #endif
1317         emplace_back(_Args&&... __args)
1318         {
1319           push_back(bool(__args...));
1320 #if __cplusplus > 201402L
1321           return back();
1322 #endif
1323         }
1324
1325       template<typename... _Args>
1326         _GLIBCXX20_CONSTEXPR
1327         iterator
1328         emplace(const_iterator __pos, _Args&&... __args)
1329         { return insert(__pos, bool(__args...)); }
1330 #endif
1331
1332     protected:
1333       // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
1334       _GLIBCXX20_CONSTEXPR
1335       iterator
1336       _M_copy_aligned(const_iterator __first, const_iterator __last,
1337                       iterator __result)
1338       {
1339         _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
1340         return std::copy(const_iterator(__last._M_p, 0), __last,
1341                          iterator(__q, 0));
1342       }
1343
1344       _GLIBCXX20_CONSTEXPR
1345       void
1346       _M_initialize(size_type __n)
1347       {
1348         if (__n)
1349           {
1350             _Bit_pointer __q = this->_M_allocate(__n);
1351             this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1352             iterator __start = iterator(std::__addressof(*__q), 0);
1353             this->_M_impl._M_start = __start;
1354             this->_M_impl._M_finish = __start + difference_type(__n);
1355           }
1356       }
1357
1358       _GLIBCXX20_CONSTEXPR
1359       void
1360       _M_initialize_value(bool __x) _GLIBCXX_NOEXCEPT
1361       {
1362         if (_Bit_type* __p = this->_M_impl._M_start._M_p)
1363           __fill_bvector_n(__p, this->_M_impl._M_end_addr() - __p, __x);
1364       }
1365
1366       _GLIBCXX20_CONSTEXPR
1367       void
1368       _M_reallocate(size_type __n);
1369
1370 #if __cplusplus >= 201103L
1371       _GLIBCXX20_CONSTEXPR
1372       bool
1373       _M_shrink_to_fit();
1374 #endif
1375
1376 #if __cplusplus < 201103L
1377       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1378       // 438. Ambiguity in the "do the right thing" clause
1379       template<typename _Integer>
1380         void
1381         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1382         {
1383           _M_initialize(static_cast<size_type>(__n));
1384           _M_initialize_value(__x);
1385         }
1386
1387       template<typename _InputIterator>
1388         void
1389         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1390                                __false_type)
1391         { _M_initialize_range(__first, __last,
1392                               std::__iterator_category(__first)); }
1393 #endif
1394
1395       template<typename _InputIterator>
1396         _GLIBCXX20_CONSTEXPR
1397         void
1398         _M_initialize_range(_InputIterator __first, _InputIterator __last,
1399                             std::input_iterator_tag)
1400         {
1401           for (; __first != __last; ++__first)
1402             push_back(*__first);
1403         }
1404
1405       template<typename _ForwardIterator>
1406         _GLIBCXX20_CONSTEXPR
1407         void
1408         _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
1409                             std::forward_iterator_tag)
1410         {
1411           const size_type __n = std::distance(__first, __last);
1412           _M_initialize(__n);
1413           std::copy(__first, __last, begin());
1414         }
1415
1416 #if __cplusplus < 201103L
1417       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1418       // 438. Ambiguity in the "do the right thing" clause
1419       template<typename _Integer>
1420         void
1421         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1422         { _M_fill_assign(__n, __val); }
1423
1424       template<class _InputIterator>
1425         void
1426         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1427                            __false_type)
1428         { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1429 #endif
1430
1431       _GLIBCXX20_CONSTEXPR
1432       void
1433       _M_fill_assign(size_t __n, bool __x)
1434       {
1435         if (__n > size())
1436           {
1437             _M_initialize_value(__x);
1438             insert(end(), __n - size(), __x);
1439           }
1440         else
1441           {
1442             _M_erase_at_end(begin() + __n);
1443             _M_initialize_value(__x);
1444           }
1445       }
1446
1447       template<typename _InputIterator>
1448         _GLIBCXX20_CONSTEXPR
1449         void
1450         _M_assign_aux(_InputIterator __first, _InputIterator __last,
1451                       std::input_iterator_tag)
1452         {
1453           iterator __cur = begin();
1454           for (; __first != __last && __cur != end(); ++__cur, (void)++__first)
1455             *__cur = *__first;
1456           if (__first == __last)
1457             _M_erase_at_end(__cur);
1458           else
1459             insert(end(), __first, __last);
1460         }
1461
1462       template<typename _ForwardIterator>
1463         _GLIBCXX20_CONSTEXPR
1464         void
1465         _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1466                       std::forward_iterator_tag)
1467         {
1468           const size_type __len = std::distance(__first, __last);
1469           if (__len < size())
1470             _M_erase_at_end(std::copy(__first, __last, begin()));
1471           else
1472             {
1473               _ForwardIterator __mid = __first;
1474               std::advance(__mid, size());
1475               std::copy(__first, __mid, begin());
1476               insert(end(), __mid, __last);
1477             }
1478         }
1479
1480 #if __cplusplus < 201103L
1481       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1482       // 438. Ambiguity in the "do the right thing" clause
1483       template<typename _Integer>
1484         void
1485         _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1486                            __true_type)
1487         { _M_fill_insert(__pos, __n, __x); }
1488
1489       template<typename _InputIterator>
1490         void
1491         _M_insert_dispatch(iterator __pos,
1492                            _InputIterator __first, _InputIterator __last,
1493                            __false_type)
1494         { _M_insert_range(__pos, __first, __last,
1495                           std::__iterator_category(__first)); }
1496 #endif
1497
1498       _GLIBCXX20_CONSTEXPR
1499       void
1500       _M_fill_insert(iterator __position, size_type __n, bool __x);
1501
1502       template<typename _InputIterator>
1503         _GLIBCXX20_CONSTEXPR
1504         void
1505         _M_insert_range(iterator __pos, _InputIterator __first,
1506                         _InputIterator __last, std::input_iterator_tag)
1507         {
1508           for (; __first != __last; ++__first)
1509             {
1510               __pos = insert(__pos, *__first);
1511               ++__pos;
1512             }
1513         }
1514
1515       template<typename _ForwardIterator>
1516         _GLIBCXX20_CONSTEXPR
1517         void
1518         _M_insert_range(iterator __position, _ForwardIterator __first,
1519                         _ForwardIterator __last, std::forward_iterator_tag);
1520
1521       _GLIBCXX20_CONSTEXPR
1522       void
1523       _M_insert_aux(iterator __position, bool __x);
1524
1525       _GLIBCXX20_CONSTEXPR
1526       size_type
1527       _M_check_len(size_type __n, const char* __s) const
1528       {
1529         if (max_size() - size() < __n)
1530           __throw_length_error(__N(__s));
1531
1532         const size_type __len = size() + std::max(size(), __n);
1533         return (__len < size() || __len > max_size()) ? max_size() : __len;
1534       }
1535
1536       _GLIBCXX20_CONSTEXPR
1537       void
1538       _M_erase_at_end(iterator __pos)
1539       { this->_M_impl._M_finish = __pos; }
1540
1541       _GLIBCXX20_CONSTEXPR
1542       iterator
1543       _M_erase(iterator __pos);
1544
1545       _GLIBCXX20_CONSTEXPR
1546       iterator
1547       _M_erase(iterator __first, iterator __last);
1548
1549     protected:
1550       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1551       // DR 464. Suggestion for new member functions in standard containers.
1552       // N.B. DR 464 says nothing about vector<bool> but we need something
1553       // here due to the using-declaration in __gnu_debug::vector.
1554       // vector class.
1555 #if __cplusplus >= 201103L
1556       void data() = delete;
1557 #else
1558       void data() { }
1559 #endif
1560     };
1561
1562 _GLIBCXX_END_NAMESPACE_CONTAINER
1563
1564   // Fill a partial word.
1565   _GLIBCXX20_CONSTEXPR
1566   inline void
1567   __fill_bvector(_Bit_type* __v, unsigned int __first, unsigned int __last,
1568                  bool __x) _GLIBCXX_NOEXCEPT
1569   {
1570     const _Bit_type __fmask = ~0ul << __first;
1571     const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last);
1572     const _Bit_type __mask = __fmask & __lmask;
1573
1574     if (__x)
1575       *__v |= __mask;
1576     else
1577       *__v &= ~__mask;
1578   }
1579
1580   // Fill N full words, as if using memset, but usable in constant expressions.
1581   __attribute__((__nonnull__))
1582   _GLIBCXX20_CONSTEXPR
1583   inline void
1584   __fill_bvector_n(_Bit_type* __p, size_t __n, bool __x) _GLIBCXX_NOEXCEPT
1585   {
1586 #if __cpp_lib_is_constant_evaluated
1587     if (std::is_constant_evaluated())
1588     {
1589       for (size_t __i = 0; __i < __n; ++__i)
1590         __p[__i] = __x ? ~0ul : 0ul;
1591       return;
1592     }
1593 #endif
1594     __builtin_memset(__p, __x ? ~0 : 0, __n * sizeof(_Bit_type));
1595   }
1596
1597
1598   _GLIBCXX20_CONSTEXPR
1599   inline void
1600   __fill_a1(_GLIBCXX_STD_C::_Bit_iterator __first,
1601             _GLIBCXX_STD_C::_Bit_iterator __last, const bool& __x)
1602   {
1603     if (__first._M_p != __last._M_p)
1604       {
1605         _Bit_type* __first_p = __first._M_p;
1606         if (__first._M_offset != 0)
1607           __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x);
1608
1609         __fill_bvector_n(__first_p, __last._M_p - __first_p, __x);
1610
1611         if (__last._M_offset != 0)
1612           __fill_bvector(__last._M_p, 0, __last._M_offset, __x);
1613       }
1614     else if (__first._M_offset != __last._M_offset)
1615       __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x);
1616   }
1617
1618 #if __cplusplus >= 201103L
1619   // DR 1182.
1620   /// std::hash specialization for vector<bool>.
1621   template<typename _Alloc>
1622     struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
1623     : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1624     {
1625       size_t
1626       operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
1627     };
1628 #endif // C++11
1629
1630 _GLIBCXX_END_NAMESPACE_VERSION
1631 } // namespace std
1632
1633 #undef _GLIBCXX_ALWAYS_INLINE
1634
1635 #endif