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

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