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

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