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

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