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