Where Online Learning is simpler!
The C and C++ Include Header Files
/usr/include/c++/11/bits/stl_bvector.h
$ cat -n /usr/include/c++/11/bits/stl_bvector.h 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 _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 operator bool() const _GLIBCXX_NOEXCEPT 87 { return !!(*_M_p & _M_mask); } 88 89 _Bit_reference& 90 operator=(bool __x) _GLIBCXX_NOEXCEPT 91 { 92 if (__x) 93 *_M_p |= _M_mask; 94 else 95 *_M_p &= ~_M_mask; 96 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 _Bit_iterator_base(_Bit_type * __x, unsigned int __y) 149 : _M_p(__x), _M_offset(__y) { } 150 151 void 152 _M_bump_up() 153 { 154 if (_M_offset++ == int(_S_word_bit) - 1) 155 { 156 _M_offset = 0; 157 ++_M_p; 158 } 159 } 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 _M_incr(ptrdiff_t __i) 173 { 174 difference_type __n = __i + _M_offset; 175 _M_p += __n / int(_S_word_bit); 176 __n = __n % int(_S_word_bit); 177 if (__n < 0) 178 { 179 __n += int(_S_word_bit); 180 --_M_p; 181 } 182 _M_offset = static_cast<unsigned int>(__n); 183 } 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 operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 225 { 226 return (int(_S_word_bit) * (__x._M_p - __y._M_p) 227 + __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 _Bit_iterator() : _Bit_iterator_base(0, 0) { } 242 243 _Bit_iterator(_Bit_type * __x, unsigned int __y) 244 : _Bit_iterator_base(__x, __y) { } 245 246 iterator 247 _M_const_cast() const 248 { return *this; } 249 250 reference 251 operator*() const 252 { return reference(_M_p, 1UL << _M_offset); } 253 254 iterator& 255 operator++() 256 { 257 _M_bump_up(); 258 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 operator+=(difference_type __i) 286 { 287 _M_incr(__i); 288 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 operator+(const iterator& __x, difference_type __n) 304 { 305 iterator __tmp = __x; 306 __tmp += __n; 307 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 _Bit_const_iterator(_Bit_type * __x, unsigned int __y) 337 : _Bit_iterator_base(__x, __y) { } 338 339 _Bit_const_iterator(const _Bit_iterator& __x) 340 : _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 operator*() const 348 { return _Bit_reference(_M_p, 1UL << _M_offset); } 349 350 const_iterator& 351 operator++() 352 { 353 _M_bump_up(); 354 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 operator+=(difference_type __i) 382 { 383 _M_incr(__i); 384 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 operator[](difference_type __i) const 396 { return *(*this + __i); } 397 398 friend const_iterator 399 operator+(const const_iterator& __x, difference_type __n) 400 { 401 const_iterator __tmp = __x; 402 __tmp += __n; 403 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 _Bvector_impl_data() _GLIBCXX_NOEXCEPT 444 : _M_start(), _M_finish(), _M_end_of_storage() 445 { } 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 _M_reset() _GLIBCXX_NOEXCEPT 466 { *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 _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT 486 : _Bit_alloc_type(__a) 487 { } 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 _M_end_addr() const _GLIBCXX_NOEXCEPT 503 { 504 if (this->_M_end_of_storage) 505 return std::__addressof(this->_M_end_of_storage[-1]) + 1; 506 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 _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT 519 { 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 _Bvector_base(const allocator_type& __a) 532 : _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 ~_Bvector_base() 543 { this->_M_deallocate(); } 544 545 protected: 546 _Bvector_impl _M_impl; 547 548 _Bit_pointer 549 _M_allocate(size_t __n) 550 { return _Bit_alloc_traits::allocate(_M_impl, _S_nword(__n)); } 551 552 void 553 _M_deallocate() 554 { 555 if (_M_impl._M_start._M_p) 556 { 557 const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p; 558 _Bit_alloc_traits::deallocate(_M_impl, 559 _M_impl._M_end_of_storage - __n, 560 __n); 561 _M_impl._M_reset(); 562 } 563 } 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 _S_nword(size_t __n) 573 { 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 vector(const vector& __x) 661 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) 662 { 663 _M_initialize(__x.size()); 664 _M_copy_aligned(__x.begin(), __x.end(), begin()); 665 } 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 vector(initializer_list<bool> __l, 703 const allocator_type& __a = allocator_type()) 704 : _Base(__a) 705 { 706 _M_initialize_range(__l.begin(), __l.end(), 707 random_access_iterator_tag()); 708 } 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 ~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 begin() _GLIBCXX_NOEXCEPT 832 { return iterator(this->_M_impl._M_start._M_p, 0); } 833 834 const_iterator 835 begin() const _GLIBCXX_NOEXCEPT 836 { 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 end() const _GLIBCXX_NOEXCEPT 844 { 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 size() const _GLIBCXX_NOEXCEPT 882 { 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 operator[](size_type __n) const 911 { 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 _M_copy_aligned(const_iterator __first, const_iterator __last, 1129 iterator __result) 1130 { 1131 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p); 1132 return std::copy(const_iterator(__last._M_p, 0), __last, 1133 iterator(__q, 0)); 1134 } 1135 1136 void 1137 _M_initialize(size_type __n) 1138 { 1139 if (__n) 1140 { 1141 _Bit_pointer __q = this->_M_allocate(__n); 1142 this->_M_impl._M_end_of_storage = __q + _S_nword(__n); 1143 iterator __start = iterator(std::__addressof(*__q), 0); 1144 this->_M_impl._M_start = __start; 1145 this->_M_impl._M_finish = __start + difference_type(__n); 1146 } 1147 } 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 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 1197 std::forward_iterator_tag) 1198 { 1199 const size_type __n = std::distance(__first, __last); 1200 _M_initialize(__n); 1201 std::copy(__first, __last, begin()); 1202 } 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
Contact us
|
About us
|
Term of use
|
Copyright © 2000-2025 MyWebUniversity.com ™
