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