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