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