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

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