l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.8/include/bits/stl_bvector.h

   1 // vector<bool> specialization -*- C++ -*-
   2
   3 // Copyright (C) 2001-2013 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     reference
 226     operator*() const
 227     { return reference(_M_p, 1UL << _M_offset); }
 228
 229     iterator&
 230     operator++()
 231     {
 232       _M_bump_up();
 233       return *this;
 234     }
 235
 236     iterator
 237     operator++(int)
 238     {
 239       iterator __tmp = *this;
 240       _M_bump_up();
 241       return __tmp;
 242     }
 243
 244     iterator&
 245     operator--()
 246     {
 247       _M_bump_down();
 248       return *this;
 249     }
 250
 251     iterator
 252     operator--(int)
 253     {
 254       iterator __tmp = *this;
 255       _M_bump_down();
 256       return __tmp;
 257     }
 258
 259     iterator&
 260     operator+=(difference_type __i)
 261     {
 262       _M_incr(__i);
 263       return *this;
 264     }
 265
 266     iterator&
 267     operator-=(difference_type __i)
 268     {
 269       *this += -__i;
 270       return *this;
 271     }
 272
 273     iterator
 274     operator+(difference_type __i) const
 275     {
 276       iterator __tmp = *this;
 277       return __tmp += __i;
 278     }
 279
 280     iterator
 281     operator-(difference_type __i) const
 282     {
 283       iterator __tmp = *this;
 284       return __tmp -= __i;
 285     }
 286
 287     reference
 288     operator[](difference_type __i) const
 289     { return *(*this + __i); }
 290   };
 291
 292   inline _Bit_iterator
 293   operator+(ptrdiff_t __n, const _Bit_iterator& __x)
 294   { return __x + __n; }
 295
 296   struct _Bit_const_iterator : public _Bit_iterator_base
 297   {
 298     typedef bool                 reference;
 299     typedef bool                 const_reference;
 300     typedef const bool*          pointer;
 301     typedef _Bit_const_iterator  const_iterator;
 302
 303     _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
 304
 305     _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
 306     : _Bit_iterator_base(__x, __y) { }
 307
 308     _Bit_const_iterator(const _Bit_iterator& __x)
 309     : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
 310
 311     const_reference
 312     operator*() const
 313     { return _Bit_reference(_M_p, 1UL << _M_offset); }
 314
 315     const_iterator&
 316     operator++()
 317     {
 318       _M_bump_up();
 319       return *this;
 320     }
 321
 322     const_iterator
 323     operator++(int)
 324     {
 325       const_iterator __tmp = *this;
 326       _M_bump_up();
 327       return __tmp;
 328     }
 329
 330     const_iterator&
 331     operator--()
 332     {
 333       _M_bump_down();
 334       return *this;
 335     }
 336
 337     const_iterator
 338     operator--(int)
 339     {
 340       const_iterator __tmp = *this;
 341       _M_bump_down();
 342       return __tmp;
 343     }
 344
 345     const_iterator&
 346     operator+=(difference_type __i)
 347     {
 348       _M_incr(__i);
 349       return *this;
 350     }
 351
 352     const_iterator&
 353     operator-=(difference_type __i)
 354     {
 355       *this += -__i;
 356       return *this;
 357     }
 358
 359     const_iterator
 360     operator+(difference_type __i) const
 361     {
 362       const_iterator __tmp = *this;
 363       return __tmp += __i;
 364     }
 365
 366     const_iterator
 367     operator-(difference_type __i) const
 368     {
 369       const_iterator __tmp = *this;
 370       return __tmp -= __i;
 371     }
 372
 373     const_reference
 374     operator[](difference_type __i) const
 375     { return *(*this + __i); }
 376   };
 377
 378   inline _Bit_const_iterator
 379   operator+(ptrdiff_t __n, const _Bit_const_iterator& __x)
 380   { return __x + __n; }
 381
 382   inline void
 383   __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x)
 384   {
 385     for (; __first != __last; ++__first)
 386       *__first = __x;
 387   }
 388
 389   inline void
 390   fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x)
 391   {
 392     if (__first._M_p != __last._M_p)
 393       {
 394         std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0);
 395         __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x);
 396         __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x);
 397       }
 398     else
 399       __fill_bvector(__first, __last, __x);
 400   }
 401
 402   template<typename _Alloc>
 403     struct _Bvector_base
 404     {
 405       typedef typename _Alloc::template rebind<_Bit_type>::other
 406         _Bit_alloc_type;
 407
 408       struct _Bvector_impl
 409       : public _Bit_alloc_type
 410       {
 411         _Bit_iterator   _M_start;
 412         _Bit_iterator   _M_finish;
 413         _Bit_type*      _M_end_of_storage;
 414
 415         _Bvector_impl()
 416         : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage(0)
 417         { }
 418
 419         _Bvector_impl(const _Bit_alloc_type& __a)
 420         : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
 421         { }
 422
 423 #if __cplusplus >= 201103L
 424         _Bvector_impl(_Bit_alloc_type&& __a)
 425         : _Bit_alloc_type(std::move(__a)), _M_start(), _M_finish(),
 426           _M_end_of_storage(0)
 427         { }
 428 #endif
 429       };
 430
 431     public:
 432       typedef _Alloc allocator_type;
 433
 434       _Bit_alloc_type&
 435       _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT
 436       { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); }
 437
 438       const _Bit_alloc_type&
 439       _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT
 440       { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
 441
 442       allocator_type
 443       get_allocator() const _GLIBCXX_NOEXCEPT
 444       { return allocator_type(_M_get_Bit_allocator()); }
 445
 446       _Bvector_base()
 447       : _M_impl() { }
 448
 449       _Bvector_base(const allocator_type& __a)
 450       : _M_impl(__a) { }
 451
 452 #if __cplusplus >= 201103L
 453       _Bvector_base(_Bvector_base&& __x) noexcept
 454       : _M_impl(std::move(__x._M_get_Bit_allocator()))
 455       {
 456         this->_M_impl._M_start = __x._M_impl._M_start;
 457         this->_M_impl._M_finish = __x._M_impl._M_finish;
 458         this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
 459         __x._M_impl._M_start = _Bit_iterator();
 460         __x._M_impl._M_finish = _Bit_iterator();
 461         __x._M_impl._M_end_of_storage = 0;
 462       }
 463 #endif
 464
 465       ~_Bvector_base()
 466       { this->_M_deallocate(); }
 467
 468     protected:
 469       _Bvector_impl _M_impl;
 470
 471       _Bit_type*
 472       _M_allocate(size_t __n)
 473       { return _M_impl.allocate(_S_nword(__n)); }
 474
 475       void
 476       _M_deallocate()
 477       {
 478         if (_M_impl._M_start._M_p)
 479           _M_impl.deallocate(_M_impl._M_start._M_p,
 480                              _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
 481       }
 482
 483       static size_t
 484       _S_nword(size_t __n)
 485       { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); }
 486     };
 487
 488 _GLIBCXX_END_NAMESPACE_CONTAINER
 489 } // namespace std
 490
 491 // Declare a partial specialization of vector<T, Alloc>.
 492 #include <bits/stl_vector.h>
 493
 494 namespace std _GLIBCXX_VISIBILITY(default)
 495 {
 496 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 497
 498   /**
 499    *  @brief  A specialization of vector for booleans which offers fixed time
 500    *  access to individual elements in any order.
 501    *
 502    *  @ingroup sequences
 503    *
 504    *  @tparam _Alloc  Allocator type.
 505    *
 506    *  Note that vector<bool> does not actually meet the requirements for being
 507    *  a container.  This is because the reference and pointer types are not
 508    *  really references and pointers to bool.  See DR96 for details.  @see
 509    *  vector for function documentation.
 510    *
 511    *  In some terminology a %vector can be described as a dynamic
 512    *  C-style array, it offers fast and efficient access to individual
 513    *  elements in any order and saves the user from worrying about
 514    *  memory and size allocation.  Subscripting ( @c [] ) access is
 515    *  also provided as with C-style arrays.
 516   */
 517 template<typename _Alloc>
 518   class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
 519   {
 520     typedef _Bvector_base<_Alloc>                        _Base;
 521
 522 #if __cplusplus >= 201103L
 523     template<typename> friend class hash;
 524 #endif
 525
 526   public:
 527     typedef bool                                         value_type;
 528     typedef size_t                                       size_type;
 529     typedef ptrdiff_t                                    difference_type;
 530     typedef _Bit_reference                               reference;
 531     typedef bool                                         const_reference;
 532     typedef _Bit_reference*                              pointer;
 533     typedef const bool*                                  const_pointer;
 534     typedef _Bit_iterator                                iterator;
 535     typedef _Bit_const_iterator                          const_iterator;
 536     typedef std::reverse_iterator<const_iterator>        const_reverse_iterator;
 537     typedef std::reverse_iterator<iterator>              reverse_iterator;
 538     typedef _Alloc                                       allocator_type;
 539
 540     allocator_type get_allocator() const
 541     { return _Base::get_allocator(); }
 542
 543   protected:
 544     using _Base::_M_allocate;
 545     using _Base::_M_deallocate;
 546     using _Base::_S_nword;
 547     using _Base::_M_get_Bit_allocator;
 548
 549   public:
 550     vector()
 551     : _Base() { }
 552
 553     explicit
 554     vector(const allocator_type& __a)
 555     : _Base(__a) { }
 556
 557 #if __cplusplus >= 201103L
 558     explicit
 559     vector(size_type __n, const allocator_type& __a = allocator_type())
 560     : vector(__n, false, __a)
 561     { }
 562
 563     vector(size_type __n, const bool& __value,
 564            const allocator_type& __a = allocator_type())
 565     : _Base(__a)
 566     {
 567       _M_initialize(__n);
 568       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage,
 569                 __value ? ~0 : 0);
 570     }
 571 #else
 572     explicit
 573     vector(size_type __n, const bool& __value = bool(),
 574            const allocator_type& __a = allocator_type())
 575     : _Base(__a)
 576     {
 577       _M_initialize(__n);
 578       std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage,
 579                 __value ? ~0 : 0);
 580     }
 581 #endif
 582
 583     vector(const vector& __x)
 584     : _Base(__x._M_get_Bit_allocator())
 585     {
 586       _M_initialize(__x.size());
 587       _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start);
 588     }
 589
 590 #if __cplusplus >= 201103L
 591     vector(vector&& __x) noexcept
 592     : _Base(std::move(__x)) { }
 593
 594     vector(initializer_list<bool> __l,
 595            const allocator_type& __a = allocator_type())
 596     : _Base(__a)
 597     {
 598       _M_initialize_range(__l.begin(), __l.end(),
 599                           random_access_iterator_tag());
 600     }
 601 #endif
 602
 603 #if __cplusplus >= 201103L
 604     template<typename _InputIterator,
 605              typename = std::_RequireInputIter<_InputIterator>>
 606       vector(_InputIterator __first, _InputIterator __last,
 607              const allocator_type& __a = allocator_type())
 608       : _Base(__a)
 609       { _M_initialize_dispatch(__first, __last, __false_type()); }
 610 #else
 611     template<typename _InputIterator>
 612       vector(_InputIterator __first, _InputIterator __last,
 613              const allocator_type& __a = allocator_type())
 614       : _Base(__a)
 615       {
 616         typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 617         _M_initialize_dispatch(__first, __last, _Integral());
 618       }
 619 #endif
 620
 621     ~vector() _GLIBCXX_NOEXCEPT { }
 622
 623     vector&
 624     operator=(const vector& __x)
 625     {
 626       if (&__x == this)
 627         return *this;
 628       if (__x.size() > capacity())
 629         {
 630           this->_M_deallocate();
 631           _M_initialize(__x.size());
 632         }
 633       this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
 634                                                 begin());
 635       return *this;
 636     }
 637
 638 #if __cplusplus >= 201103L
 639     vector&
 640     operator=(vector&& __x)
 641     {
 642       // NB: DR 1204.
 643       // NB: DR 675.
 644       this->clear();
 645       this->swap(__x);
 646       return *this;
 647     }
 648
 649     vector&
 650     operator=(initializer_list<bool> __l)
 651     {
 652       this->assign (__l.begin(), __l.end());
 653       return *this;
 654     }
 655 #endif
 656
 657     // assign(), a generalized assignment member function.  Two
 658     // versions: one that takes a count, and one that takes a range.
 659     // The range version is a member template, so we dispatch on whether
 660     // or not the type is an integer.
 661     void
 662     assign(size_type __n, const bool& __x)
 663     { _M_fill_assign(__n, __x); }
 664
 665 #if __cplusplus >= 201103L
 666     template<typename _InputIterator,
 667              typename = std::_RequireInputIter<_InputIterator>>
 668       void
 669       assign(_InputIterator __first, _InputIterator __last)
 670       { _M_assign_dispatch(__first, __last, __false_type()); }
 671 #else
 672     template<typename _InputIterator>
 673       void
 674       assign(_InputIterator __first, _InputIterator __last)
 675       {
 676         typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 677         _M_assign_dispatch(__first, __last, _Integral());
 678       }
 679 #endif
 680
 681 #if __cplusplus >= 201103L
 682     void
 683     assign(initializer_list<bool> __l)
 684     { this->assign(__l.begin(), __l.end()); }
 685 #endif
 686
 687     iterator
 688     begin() _GLIBCXX_NOEXCEPT
 689     { return this->_M_impl._M_start; }
 690
 691     const_iterator
 692     begin() const _GLIBCXX_NOEXCEPT
 693     { return this->_M_impl._M_start; }
 694
 695     iterator
 696     end() _GLIBCXX_NOEXCEPT
 697     { return this->_M_impl._M_finish; }
 698
 699     const_iterator
 700     end() const _GLIBCXX_NOEXCEPT
 701     { return this->_M_impl._M_finish; }
 702
 703     reverse_iterator
 704     rbegin() _GLIBCXX_NOEXCEPT
 705     { return reverse_iterator(end()); }
 706
 707     const_reverse_iterator
 708     rbegin() const _GLIBCXX_NOEXCEPT
 709     { return const_reverse_iterator(end()); }
 710
 711     reverse_iterator
 712     rend() _GLIBCXX_NOEXCEPT
 713     { return reverse_iterator(begin()); }
 714
 715     const_reverse_iterator
 716     rend() const _GLIBCXX_NOEXCEPT
 717     { return const_reverse_iterator(begin()); }
 718
 719 #if __cplusplus >= 201103L
 720     const_iterator
 721     cbegin() const noexcept
 722     { return this->_M_impl._M_start; }
 723
 724     const_iterator
 725     cend() const noexcept
 726     { return this->_M_impl._M_finish; }
 727
 728     const_reverse_iterator
 729     crbegin() const noexcept
 730     { return const_reverse_iterator(end()); }
 731
 732     const_reverse_iterator
 733     crend() const noexcept
 734     { return const_reverse_iterator(begin()); }
 735 #endif
 736
 737     size_type
 738     size() const _GLIBCXX_NOEXCEPT
 739     { return size_type(end() - begin()); }
 740
 741     size_type
 742     max_size() const _GLIBCXX_NOEXCEPT
 743     {
 744       const size_type __isize =
 745         __gnu_cxx::__numeric_traits<difference_type>::__max
 746         - int(_S_word_bit) + 1;
 747       const size_type __asize = _M_get_Bit_allocator().max_size();
 748       return (__asize <= __isize / int(_S_word_bit)
 749               ? __asize * int(_S_word_bit) : __isize);
 750     }
 751
 752     size_type
 753     capacity() const _GLIBCXX_NOEXCEPT
 754     { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
 755                        - begin()); }
 756
 757     bool
 758     empty() const _GLIBCXX_NOEXCEPT
 759     { return begin() == end(); }
 760
 761     reference
 762     operator[](size_type __n)
 763     {
 764       return *iterator(this->_M_impl._M_start._M_p
 765                        + __n / int(_S_word_bit), __n % int(_S_word_bit));
 766     }
 767
 768     const_reference
 769     operator[](size_type __n) const
 770     {
 771       return *const_iterator(this->_M_impl._M_start._M_p
 772                              + __n / int(_S_word_bit), __n % int(_S_word_bit));
 773     }
 774
 775   protected:
 776     void
 777     _M_range_check(size_type __n) const
 778     {
 779       if (__n >= this->size())
 780         __throw_out_of_range(__N("vector<bool>::_M_range_check"));
 781     }
 782
 783   public:
 784     reference
 785     at(size_type __n)
 786     { _M_range_check(__n); return (*this)[__n]; }
 787
 788     const_reference
 789     at(size_type __n) const
 790     { _M_range_check(__n); return (*this)[__n]; }
 791
 792     void
 793     reserve(size_type __n)
 794     {
 795       if (__n > max_size())
 796         __throw_length_error(__N("vector::reserve"));
 797       if (capacity() < __n)
 798         _M_reallocate(__n);
 799     }
 800
 801     reference
 802     front()
 803     { return *begin(); }
 804
 805     const_reference
 806     front() const
 807     { return *begin(); }
 808
 809     reference
 810     back()
 811     { return *(end() - 1); }
 812
 813     const_reference
 814     back() const
 815     { return *(end() - 1); }
 816
 817     // _GLIBCXX_RESOLVE_LIB_DEFECTS
 818     // DR 464. Suggestion for new member functions in standard containers.
 819     // N.B. DR 464 says nothing about vector<bool> but we need something
 820     // here due to the way we are implementing DR 464 in the debug-mode
 821     // vector class.
 822     void
 823     data() _GLIBCXX_NOEXCEPT { }
 824
 825     void
 826     push_back(bool __x)
 827     {
 828       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
 829         *this->_M_impl._M_finish++ = __x;
 830       else
 831         _M_insert_aux(end(), __x);
 832     }
 833
 834     void
 835     swap(vector& __x)
 836     {
 837       std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
 838       std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
 839       std::swap(this->_M_impl._M_end_of_storage,
 840                 __x._M_impl._M_end_of_storage);
 841
 842       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 843       // 431. Swapping containers with unequal allocators.
 844       std::__alloc_swap<typename _Base::_Bit_alloc_type>::
 845         _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator());
 846     }
 847
 848     // [23.2.5]/1, third-to-last entry in synopsis listing
 849     static void
 850     swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT
 851     {
 852       bool __tmp = __x;
 853       __x = __y;
 854       __y = __tmp;
 855     }
 856
 857     iterator
 858     insert(iterator __position, const bool& __x = bool())
 859     {
 860       const difference_type __n = __position - begin();
 861       if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
 862           && __position == end())
 863         *this->_M_impl._M_finish++ = __x;
 864       else
 865         _M_insert_aux(__position, __x);
 866       return begin() + __n;
 867     }
 868
 869 #if __cplusplus >= 201103L
 870     template<typename _InputIterator,
 871              typename = std::_RequireInputIter<_InputIterator>>
 872       void
 873       insert(iterator __position,
 874              _InputIterator __first, _InputIterator __last)
 875       { _M_insert_dispatch(__position, __first, __last, __false_type()); }
 876 #else
 877     template<typename _InputIterator>
 878       void
 879       insert(iterator __position,
 880              _InputIterator __first, _InputIterator __last)
 881       {
 882         typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 883         _M_insert_dispatch(__position, __first, __last, _Integral());
 884       }
 885 #endif
 886
 887     void
 888     insert(iterator __position, size_type __n, const bool& __x)
 889     { _M_fill_insert(__position, __n, __x); }
 890
 891 #if __cplusplus >= 201103L
 892     void insert(iterator __p, initializer_list<bool> __l)
 893     { this->insert(__p, __l.begin(), __l.end()); }
 894 #endif
 895
 896     void
 897     pop_back()
 898     { --this->_M_impl._M_finish; }
 899
 900     iterator
 901     erase(iterator __position)
 902     {
 903       if (__position + 1 != end())
 904         std::copy(__position + 1, end(), __position);
 905       --this->_M_impl._M_finish;
 906       return __position;
 907     }
 908
 909     iterator
 910     erase(iterator __first, iterator __last)
 911     {
 912       if (__first != __last)
 913         _M_erase_at_end(std::copy(__last, end(), __first));
 914       return __first;
 915     }
 916
 917     void
 918     resize(size_type __new_size, bool __x = bool())
 919     {
 920       if (__new_size < size())
 921         _M_erase_at_end(begin() + difference_type(__new_size));
 922       else
 923         insert(end(), __new_size - size(), __x);
 924     }
 925
 926 #if __cplusplus >= 201103L
 927     void
 928     shrink_to_fit()
 929     { _M_shrink_to_fit(); }
 930 #endif
 931
 932     void
 933     flip() _GLIBCXX_NOEXCEPT
 934     {
 935       for (_Bit_type * __p = this->_M_impl._M_start._M_p;
 936            __p != this->_M_impl._M_end_of_storage; ++__p)
 937         *__p = ~*__p;
 938     }
 939
 940     void
 941     clear() _GLIBCXX_NOEXCEPT
 942     { _M_erase_at_end(begin()); }
 943
 944
 945   protected:
 946     // Precondition: __first._M_offset == 0 && __result._M_offset == 0.
 947     iterator
 948     _M_copy_aligned(const_iterator __first, const_iterator __last,
 949                     iterator __result)
 950     {
 951       _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
 952       return std::copy(const_iterator(__last._M_p, 0), __last,
 953                        iterator(__q, 0));
 954     }
 955
 956     void
 957     _M_initialize(size_type __n)
 958     {
 959       _Bit_type* __q = this->_M_allocate(__n);
 960       this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
 961       this->_M_impl._M_start = iterator(__q, 0);
 962       this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
 963     }
 964
 965     void
 966     _M_reallocate(size_type __n);
 967
 968 #if __cplusplus >= 201103L
 969     bool
 970     _M_shrink_to_fit();
 971 #endif
 972
 973     // Check whether it's an integral type.  If so, it's not an iterator.
 974
 975     // _GLIBCXX_RESOLVE_LIB_DEFECTS
 976     // 438. Ambiguity in the "do the right thing" clause
 977     template<typename _Integer>
 978       void
 979       _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
 980       {
 981         _M_initialize(static_cast<size_type>(__n));
 982         std::fill(this->_M_impl._M_start._M_p,
 983                   this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
 984       }
 985
 986     template<typename _InputIterator>
 987       void
 988       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
 989                              __false_type)
 990       { _M_initialize_range(__first, __last,
 991                             std::__iterator_category(__first)); }
 992
 993     template<typename _InputIterator>
 994       void
 995       _M_initialize_range(_InputIterator __first, _InputIterator __last,
 996                           std::input_iterator_tag)
 997       {
 998         for (; __first != __last; ++__first)
 999           push_back(*__first);
1000       }
1001
1002     template<typename _ForwardIterator>
1003       void
1004       _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
1005                           std::forward_iterator_tag)
1006       {
1007         const size_type __n = std::distance(__first, __last);
1008         _M_initialize(__n);
1009         std::copy(__first, __last, this->_M_impl._M_start);
1010       }
1011
1012     // _GLIBCXX_RESOLVE_LIB_DEFECTS
1013     // 438. Ambiguity in the "do the right thing" clause
1014     template<typename _Integer>
1015       void
1016       _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1017       { _M_fill_assign(__n, __val); }
1018
1019     template<class _InputIterator>
1020       void
1021       _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1022                          __false_type)
1023       { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1024
1025     void
1026     _M_fill_assign(size_t __n, bool __x)
1027     {
1028       if (__n > size())
1029         {
1030           std::fill(this->_M_impl._M_start._M_p,
1031                     this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
1032           insert(end(), __n - size(), __x);
1033         }
1034       else
1035         {
1036           _M_erase_at_end(begin() + __n);
1037           std::fill(this->_M_impl._M_start._M_p,
1038                     this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
1039         }
1040     }
1041
1042     template<typename _InputIterator>
1043       void
1044       _M_assign_aux(_InputIterator __first, _InputIterator __last,
1045                     std::input_iterator_tag)
1046       {
1047         iterator __cur = begin();
1048         for (; __first != __last && __cur != end(); ++__cur, ++__first)
1049           *__cur = *__first;
1050         if (__first == __last)
1051           _M_erase_at_end(__cur);
1052         else
1053           insert(end(), __first, __last);
1054       }
1055
1056     template<typename _ForwardIterator>
1057       void
1058       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1059                     std::forward_iterator_tag)
1060       {
1061         const size_type __len = std::distance(__first, __last);
1062         if (__len < size())
1063           _M_erase_at_end(std::copy(__first, __last, begin()));
1064         else
1065           {
1066             _ForwardIterator __mid = __first;
1067             std::advance(__mid, size());
1068             std::copy(__first, __mid, begin());
1069             insert(end(), __mid, __last);
1070           }
1071       }
1072
1073     // Check whether it's an integral type.  If so, it's not an iterator.
1074
1075     // _GLIBCXX_RESOLVE_LIB_DEFECTS
1076     // 438. Ambiguity in the "do the right thing" clause
1077     template<typename _Integer>
1078       void
1079       _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1080                          __true_type)
1081       { _M_fill_insert(__pos, __n, __x); }
1082
1083     template<typename _InputIterator>
1084       void
1085       _M_insert_dispatch(iterator __pos,
1086                          _InputIterator __first, _InputIterator __last,
1087                          __false_type)
1088       { _M_insert_range(__pos, __first, __last,
1089                         std::__iterator_category(__first)); }
1090
1091     void
1092     _M_fill_insert(iterator __position, size_type __n, bool __x);
1093
1094     template<typename _InputIterator>
1095       void
1096       _M_insert_range(iterator __pos, _InputIterator __first,
1097                       _InputIterator __last, std::input_iterator_tag)
1098       {
1099         for (; __first != __last; ++__first)
1100           {
1101             __pos = insert(__pos, *__first);
1102             ++__pos;
1103           }
1104       }
1105
1106     template<typename _ForwardIterator>
1107       void
1108       _M_insert_range(iterator __position, _ForwardIterator __first,
1109                       _ForwardIterator __last, std::forward_iterator_tag);
1110
1111     void
1112     _M_insert_aux(iterator __position, bool __x);
1113
1114     size_type
1115     _M_check_len(size_type __n, const char* __s) const
1116     {
1117       if (max_size() - size() < __n)
1118         __throw_length_error(__N(__s));
1119
1120       const size_type __len = size() + std::max(size(), __n);
1121       return (__len < size() || __len > max_size()) ? max_size() : __len;
1122     }
1123
1124     void
1125     _M_erase_at_end(iterator __pos)
1126     { this->_M_impl._M_finish = __pos; }
1127   };
1128
1129 _GLIBCXX_END_NAMESPACE_CONTAINER
1130 } // namespace std
1131
1132 #if __cplusplus >= 201103L
1133
1134 #include <bits/functional_hash.h>
1135
1136 namespace std _GLIBCXX_VISIBILITY(default)
1137 {
1138 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1139
1140   // DR 1182.
1141   /// std::hash specialization for vector<bool>.
1142   template<typename _Alloc>
1143     struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
1144     : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1145     {
1146       size_t
1147       operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
1148     };
1149
1150 _GLIBCXX_END_NAMESPACE_VERSION
1151 }// namespace std
1152
1153 #endif // C++11
1154
1155 #endif