1    	// vector<bool> specialization -*- C++ -*-
2    	
3    	// Copyright (C) 2001-2017 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 	      if (__n)
1093 		{
1094 		  _Bit_pointer __q = this->_M_allocate(__n);
1095 		  this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
1096 		  this->_M_impl._M_start = iterator(std::__addressof(*__q), 0);
1097 		}
1098 	      else
1099 		{
1100 		  this->_M_impl._M_end_of_storage = _Bit_pointer();
1101 		  this->_M_impl._M_start = iterator(0, 0);
1102 		}
1103 	      this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
1104 	    }
1105 	
1106 	    void
1107 	    _M_reallocate(size_type __n);
1108 	
1109 	#if __cplusplus >= 201103L
1110 	    bool
1111 	    _M_shrink_to_fit();
1112 	#endif
1113 	
1114 	    // Check whether it's an integral type.  If so, it's not an iterator.
1115 	
1116 	    // _GLIBCXX_RESOLVE_LIB_DEFECTS
1117 	    // 438. Ambiguity in the "do the right thing" clause
1118 	    template<typename _Integer>
1119 	      void
1120 	      _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1121 	      {
1122 		_M_initialize(static_cast<size_type>(__n));
1123 		std::fill(this->_M_impl._M_start._M_p, 
1124 			  this->_M_impl._M_end_addr(), __x ? ~0 : 0);
1125 	      }
1126 	
1127 	    template<typename _InputIterator>
1128 	      void 
1129 	      _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1130 				     __false_type)
1131 	      { _M_initialize_range(__first, __last, 
1132 				    std::__iterator_category(__first)); }
1133 	
1134 	    template<typename _InputIterator>
1135 	      void
1136 	      _M_initialize_range(_InputIterator __first, _InputIterator __last,
1137 				  std::input_iterator_tag)
1138 	      {
1139 		for (; __first != __last; ++__first)
1140 		  push_back(*__first);
1141 	      }
1142 	
1143 	    template<typename _ForwardIterator>
1144 	      void
1145 	      _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
1146 				  std::forward_iterator_tag)
1147 	      {
1148 		const size_type __n = std::distance(__first, __last);
1149 		_M_initialize(__n);
1150 		std::copy(__first, __last, this->_M_impl._M_start);
1151 	      }
1152 	
1153 	    // _GLIBCXX_RESOLVE_LIB_DEFECTS
1154 	    // 438. Ambiguity in the "do the right thing" clause
1155 	    template<typename _Integer>
1156 	      void
1157 	      _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1158 	      { _M_fill_assign(__n, __val); }
1159 	
1160 	    template<class _InputIterator>
1161 	      void
1162 	      _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1163 				 __false_type)
1164 	      { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
1165 	
1166 	    void
1167 	    _M_fill_assign(size_t __n, bool __x)
1168 	    {
1169 	      if (__n > size())
1170 		{
1171 		  std::fill(this->_M_impl._M_start._M_p, 
1172 			    this->_M_impl._M_end_addr(), __x ? ~0 : 0);
1173 		  insert(end(), __n - size(), __x);
1174 		}
1175 	      else
1176 		{
1177 		  _M_erase_at_end(begin() + __n);
1178 		  std::fill(this->_M_impl._M_start._M_p, 
1179 			    this->_M_impl._M_end_addr(), __x ? ~0 : 0);
1180 		}
1181 	    }
1182 	
1183 	    template<typename _InputIterator>
1184 	      void
1185 	      _M_assign_aux(_InputIterator __first, _InputIterator __last,
1186 			    std::input_iterator_tag)
1187 	      {
1188 		iterator __cur = begin();
1189 		for (; __first != __last && __cur != end(); ++__cur, ++__first)
1190 		  *__cur = *__first;
1191 		if (__first == __last)
1192 		  _M_erase_at_end(__cur);
1193 		else
1194 		  insert(end(), __first, __last);
1195 	      }
1196 	    
1197 	    template<typename _ForwardIterator>
1198 	      void
1199 	      _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1200 			    std::forward_iterator_tag)
1201 	      {
1202 		const size_type __len = std::distance(__first, __last);
1203 		if (__len < size())
1204 		  _M_erase_at_end(std::copy(__first, __last, begin()));
1205 		else
1206 		  {
1207 		    _ForwardIterator __mid = __first;
1208 		    std::advance(__mid, size());
1209 		    std::copy(__first, __mid, begin());
1210 		    insert(end(), __mid, __last);
1211 		  }
1212 	      }
1213 	
1214 	    // Check whether it's an integral type.  If so, it's not an iterator.
1215 	
1216 	    // _GLIBCXX_RESOLVE_LIB_DEFECTS
1217 	    // 438. Ambiguity in the "do the right thing" clause
1218 	    template<typename _Integer>
1219 	      void
1220 	      _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1221 				 __true_type)
1222 	      { _M_fill_insert(__pos, __n, __x); }
1223 	
1224 	    template<typename _InputIterator>
1225 	      void
1226 	      _M_insert_dispatch(iterator __pos,
1227 				 _InputIterator __first, _InputIterator __last,
1228 				 __false_type)
1229 	      { _M_insert_range(__pos, __first, __last,
1230 				std::__iterator_category(__first)); }
1231 	
1232 	    void
1233 	    _M_fill_insert(iterator __position, size_type __n, bool __x);
1234 	
1235 	    template<typename _InputIterator>
1236 	      void
1237 	      _M_insert_range(iterator __pos, _InputIterator __first, 
1238 			      _InputIterator __last, std::input_iterator_tag)
1239 	      {
1240 		for (; __first != __last; ++__first)
1241 		  {
1242 		    __pos = insert(__pos, *__first);
1243 		    ++__pos;
1244 		  }
1245 	      }
1246 	
1247 	    template<typename _ForwardIterator>
1248 	      void
1249 	      _M_insert_range(iterator __position, _ForwardIterator __first, 
1250 			      _ForwardIterator __last, std::forward_iterator_tag);
1251 	
1252 	    void
1253 	    _M_insert_aux(iterator __position, bool __x);
1254 	
1255 	    size_type
1256 	    _M_check_len(size_type __n, const char* __s) const
1257 	    {
1258 	      if (max_size() - size() < __n)
1259 		__throw_length_error(__N(__s));
1260 	
1261 	      const size_type __len = size() + std::max(size(), __n);
1262 	      return (__len < size() || __len > max_size()) ? max_size() : __len;
1263 	    }
1264 	
1265 	    void
1266 	    _M_erase_at_end(iterator __pos)
1267 	    { this->_M_impl._M_finish = __pos; }
1268 	
1269 	    iterator
1270 	    _M_erase(iterator __pos);
1271 	
1272 	    iterator
1273 	    _M_erase(iterator __first, iterator __last);
1274 	  };
1275 	
1276 	_GLIBCXX_END_NAMESPACE_CONTAINER
1277 	} // namespace std
1278 	
1279 	#if __cplusplus >= 201103L
1280 	
1281 	#include <bits/functional_hash.h>
1282 	
1283 	namespace std _GLIBCXX_VISIBILITY(default)
1284 	{
1285 	_GLIBCXX_BEGIN_NAMESPACE_VERSION
1286 	
1287 	  // DR 1182.
1288 	  /// std::hash specialization for vector<bool>.
1289 	  template<typename _Alloc>
1290 	    struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
1291 	    : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
1292 	    {
1293 	      size_t
1294 	      operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept;
1295 	    };
1296 	
1297 	_GLIBCXX_END_NAMESPACE_VERSION
1298 	}// namespace std
1299 	
1300 	#endif // C++11
1301 	
1302 	#endif
1303