stl_bvector.h source code [include/c++/7/bits/stl

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(.._M_range_check. __n " "(which is %zu) >= this->size() " "(which is %zu)")" file_link="../../../x86_64-linux-gnu/c++/7/bits/c++config.h.html#595" macro="true">__N("vector<bool>::_M_range_check: __n "
875	.._M_range_check. __n " "(which is %zu) >= this->size() " "(which is %zu)")" file_link="../../../x86_64-linux-gnu/c++/7/bits/c++config.h.html#595" macro="true"> "(which is %zu) >= this->size() "
876	.._M_range_check. __n " "(which is %zu) >= this->size() " "(which is %zu)")" file_link="../../../x86_64-linux-gnu/c++/7/bits/c++config.h.html#595" macro="true"> "(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