Where Online Learning is simpler!
The C and C++ Include Header Files
/usr/include/c++/13/bits/stl_bvector.h
$ cat -n /usr/include/c++/13/bits/stl_bvector.h 1 // vector<bool> specialization -*- C++ -*- 2 3 // Copyright (C) 2001-2023 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 #ifndef _GLIBCXX_ALWAYS_INLINE 60 #define _GLIBCXX_ALWAYS_INLINE inline __attribute__((__always_inline__)) 61 #endif 62 63 #if __cplusplus >= 201103L 64 #include <initializer_list> 65 #include <bits/functional_hash.h> 66 #endif 67 68 namespace std _GLIBCXX_VISIBILITY(default) 69 { 70 _GLIBCXX_BEGIN_NAMESPACE_VERSION 71 72 typedef unsigned long _Bit_type; 73 enum { _S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type)) }; 74 75 __attribute__((__nonnull__)) 76 _GLIBCXX20_CONSTEXPR 77 void 78 __fill_bvector_n(_Bit_type*, size_t, bool) _GLIBCXX_NOEXCEPT; 79 80 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 81 82 struct _Bit_reference 83 { 84 _Bit_type * _M_p; 85 _Bit_type _M_mask; 86 87 _GLIBCXX20_CONSTEXPR 88 _Bit_reference(_Bit_type * __x, _Bit_type __y) 89 : _M_p(__x), _M_mask(__y) { } 90 91 _GLIBCXX20_CONSTEXPR 92 _Bit_reference() _GLIBCXX_NOEXCEPT : _M_p(0), _M_mask(0) { } 93 94 #if __cplusplus >= 201103L 95 _Bit_reference(const _Bit_reference&) = default; 96 #endif 97 98 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 99 operator bool() const _GLIBCXX_NOEXCEPT 100 { return !!(*_M_p & _M_mask); } 101 102 _GLIBCXX20_CONSTEXPR 103 _Bit_reference& 104 operator=(bool __x) _GLIBCXX_NOEXCEPT 105 { 106 if (__x) 107 *_M_p |= _M_mask; 108 else 109 *_M_p &= ~_M_mask; 110 return *this; 111 } 112 113 #if __cplusplus > 202002L 114 constexpr const _Bit_reference& 115 operator=(bool __x) const noexcept 116 { 117 if (__x) 118 *_M_p |= _M_mask; 119 else 120 *_M_p &= ~_M_mask; 121 return *this; 122 } 123 #endif // C++23 124 125 _GLIBCXX20_CONSTEXPR 126 _Bit_reference& 127 operator=(const _Bit_reference& __x) _GLIBCXX_NOEXCEPT 128 { return *this = bool(__x); } 129 130 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 131 bool 132 operator==(const _Bit_reference& __x) const 133 { return bool(*this) == bool(__x); } 134 135 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 136 bool 137 operator<(const _Bit_reference& __x) const 138 { return !bool(*this) && bool(__x); } 139 140 _GLIBCXX20_CONSTEXPR 141 void 142 flip() _GLIBCXX_NOEXCEPT 143 { *_M_p ^= _M_mask; } 144 145 #if __cplusplus >= 201103L 146 _GLIBCXX20_CONSTEXPR 147 friend void 148 swap(_Bit_reference __x, _Bit_reference __y) noexcept 149 { 150 bool __tmp = __x; 151 __x = __y; 152 __y = __tmp; 153 } 154 155 _GLIBCXX20_CONSTEXPR 156 friend void 157 swap(_Bit_reference __x, bool& __y) noexcept 158 { 159 bool __tmp = __x; 160 __x = __y; 161 __y = __tmp; 162 } 163 164 _GLIBCXX20_CONSTEXPR 165 friend void 166 swap(bool& __x, _Bit_reference __y) noexcept 167 { 168 bool __tmp = __x; 169 __x = __y; 170 __y = __tmp; 171 } 172 #endif 173 }; 174 175 // Ignore warnings about std::iterator. 176 #pragma GCC diagnostic push 177 #pragma GCC diagnostic ignored "-Wdeprecated-declarations" 178 struct _Bit_iterator_base 179 : public std::iterator<std::random_access_iterator_tag, bool> 180 { 181 _Bit_type * _M_p; 182 unsigned int _M_offset; 183 184 _GLIBCXX20_CONSTEXPR _GLIBCXX_ALWAYS_INLINE 185 void 186 _M_assume_normalized() const 187 { 188 #if __has_attribute(__assume__) && !defined(__clang__) 189 unsigned int __ofst = _M_offset; 190 __attribute__ ((__assume__ (__ofst < unsigned(_S_word_bit)))); 191 #endif 192 } 193 194 _GLIBCXX20_CONSTEXPR 195 _Bit_iterator_base(_Bit_type * __x, unsigned int __y) 196 : _M_p(__x), _M_offset(__y) { } 197 198 _GLIBCXX20_CONSTEXPR 199 void 200 _M_bump_up() 201 { 202 _M_assume_normalized(); 203 if (_M_offset++ == int(_S_word_bit) - 1) 204 { 205 _M_offset = 0; 206 ++_M_p; 207 } 208 } 209 210 _GLIBCXX20_CONSTEXPR 211 void 212 _M_bump_down() 213 { 214 _M_assume_normalized(); 215 if (_M_offset-- == 0) 216 { 217 _M_offset = int(_S_word_bit) - 1; 218 --_M_p; 219 } 220 } 221 222 _GLIBCXX20_CONSTEXPR 223 void 224 _M_incr(ptrdiff_t __i) 225 { 226 _M_assume_normalized(); 227 difference_type __n = __i + _M_offset; 228 _M_p += __n / int(_S_word_bit); 229 __n = __n % int(_S_word_bit); 230 if (__n < 0) 231 { 232 __n += int(_S_word_bit); 233 --_M_p; 234 } 235 _M_offset = static_cast<unsigned int>(__n); 236 } 237 238 _GLIBCXX_NODISCARD 239 friend _GLIBCXX20_CONSTEXPR bool 240 operator==(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 241 { 242 __x._M_assume_normalized(); 243 __y._M_assume_normalized(); 244 return __x._M_p == __y._M_p && __x._M_offset == __y._M_offset; 245 } 246 247 #if __cpp_lib_three_way_comparison 248 [[nodiscard]] 249 friend constexpr strong_ordering 250 operator<=>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 251 noexcept 252 { 253 __x._M_assume_normalized(); 254 __y._M_assume_normalized(); 255 if (const auto __cmp = __x._M_p <=> __y._M_p; __cmp != 0) 256 return __cmp; 257 return __x._M_offset <=> __y._M_offset; 258 } 259 #else 260 _GLIBCXX_NODISCARD 261 friend bool 262 operator<(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 263 { 264 __x._M_assume_normalized(); 265 __y._M_assume_normalized(); 266 return __x._M_p < __y._M_p 267 || (__x._M_p == __y._M_p && __x._M_offset < __y._M_offset); 268 } 269 270 _GLIBCXX_NODISCARD 271 friend bool 272 operator!=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 273 { return !(__x == __y); } 274 275 _GLIBCXX_NODISCARD 276 friend bool 277 operator>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 278 { return __y < __x; } 279 280 _GLIBCXX_NODISCARD 281 friend bool 282 operator<=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 283 { return !(__y < __x); } 284 285 _GLIBCXX_NODISCARD 286 friend bool 287 operator>=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 288 { return !(__x < __y); } 289 #endif // three-way comparison 290 291 friend _GLIBCXX20_CONSTEXPR ptrdiff_t 292 operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 293 { 294 __x._M_assume_normalized(); 295 __y._M_assume_normalized(); 296 return (int(_S_word_bit) * (__x._M_p - __y._M_p) 297 + __x._M_offset - __y._M_offset); 298 } 299 }; 300 #pragma GCC diagnostic pop 301 302 struct _Bit_iterator : public _Bit_iterator_base 303 { 304 typedef _Bit_reference reference; 305 #if __cplusplus > 201703L 306 typedef void pointer; 307 #else 308 typedef _Bit_reference* pointer; 309 #endif 310 typedef _Bit_iterator iterator; 311 312 _GLIBCXX20_CONSTEXPR 313 _Bit_iterator() : _Bit_iterator_base(0, 0) { } 314 315 _GLIBCXX20_CONSTEXPR 316 _Bit_iterator(_Bit_type * __x, unsigned int __y) 317 : _Bit_iterator_base(__x, __y) { } 318 319 _GLIBCXX20_CONSTEXPR 320 iterator 321 _M_const_cast() const 322 { return *this; } 323 324 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 325 reference 326 operator*() const 327 { 328 _M_assume_normalized(); 329 return reference(_M_p, 1UL << _M_offset); 330 } 331 332 _GLIBCXX20_CONSTEXPR 333 iterator& 334 operator++() 335 { 336 _M_bump_up(); 337 return *this; 338 } 339 340 _GLIBCXX20_CONSTEXPR 341 iterator 342 operator++(int) 343 { 344 iterator __tmp = *this; 345 _M_bump_up(); 346 return __tmp; 347 } 348 349 _GLIBCXX20_CONSTEXPR 350 iterator& 351 operator--() 352 { 353 _M_bump_down(); 354 return *this; 355 } 356 357 _GLIBCXX20_CONSTEXPR 358 iterator 359 operator--(int) 360 { 361 iterator __tmp = *this; 362 _M_bump_down(); 363 return __tmp; 364 } 365 366 _GLIBCXX20_CONSTEXPR 367 iterator& 368 operator+=(difference_type __i) 369 { 370 _M_incr(__i); 371 return *this; 372 } 373 374 _GLIBCXX20_CONSTEXPR 375 iterator& 376 operator-=(difference_type __i) 377 { 378 *this += -__i; 379 return *this; 380 } 381 382 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 383 reference 384 operator[](difference_type __i) const 385 { return *(*this + __i); } 386 387 _GLIBCXX_NODISCARD 388 friend _GLIBCXX20_CONSTEXPR iterator 389 operator+(const iterator& __x, difference_type __n) 390 { 391 iterator __tmp = __x; 392 __tmp += __n; 393 return __tmp; 394 } 395 396 _GLIBCXX_NODISCARD 397 friend _GLIBCXX20_CONSTEXPR iterator 398 operator+(difference_type __n, const iterator& __x) 399 { return __x + __n; } 400 401 _GLIBCXX_NODISCARD 402 friend _GLIBCXX20_CONSTEXPR iterator 403 operator-(const iterator& __x, difference_type __n) 404 { 405 iterator __tmp = __x; 406 __tmp -= __n; 407 return __tmp; 408 } 409 }; 410 411 struct _Bit_const_iterator : public _Bit_iterator_base 412 { 413 typedef bool reference; 414 typedef bool const_reference; 415 #if __cplusplus > 201703L 416 typedef void pointer; 417 #else 418 typedef const bool* pointer; 419 #endif 420 typedef _Bit_const_iterator const_iterator; 421 422 _GLIBCXX20_CONSTEXPR 423 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { } 424 425 _GLIBCXX20_CONSTEXPR 426 _Bit_const_iterator(_Bit_type * __x, unsigned int __y) 427 : _Bit_iterator_base(__x, __y) { } 428 429 _GLIBCXX20_CONSTEXPR 430 _Bit_const_iterator(const _Bit_iterator& __x) 431 : _Bit_iterator_base(__x._M_p, __x._M_offset) { } 432 433 _GLIBCXX20_CONSTEXPR 434 _Bit_iterator 435 _M_const_cast() const 436 { return _Bit_iterator(_M_p, _M_offset); } 437 438 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 439 const_reference 440 operator*() const 441 { 442 _M_assume_normalized(); 443 return _Bit_reference(_M_p, 1UL << _M_offset); 444 } 445 446 _GLIBCXX20_CONSTEXPR 447 const_iterator& 448 operator++() 449 { 450 _M_bump_up(); 451 return *this; 452 } 453 454 _GLIBCXX20_CONSTEXPR 455 const_iterator 456 operator++(int) 457 { 458 const_iterator __tmp = *this; 459 _M_bump_up(); 460 return __tmp; 461 } 462 463 _GLIBCXX20_CONSTEXPR 464 const_iterator& 465 operator--() 466 { 467 _M_bump_down(); 468 return *this; 469 } 470 471 _GLIBCXX20_CONSTEXPR 472 const_iterator 473 operator--(int) 474 { 475 const_iterator __tmp = *this; 476 _M_bump_down(); 477 return __tmp; 478 } 479 480 _GLIBCXX20_CONSTEXPR 481 const_iterator& 482 operator+=(difference_type __i) 483 { 484 _M_incr(__i); 485 return *this; 486 } 487 488 _GLIBCXX20_CONSTEXPR 489 const_iterator& 490 operator-=(difference_type __i) 491 { 492 *this += -__i; 493 return *this; 494 } 495 496 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 497 const_reference 498 operator[](difference_type __i) const 499 { return *(*this + __i); } 500 501 _GLIBCXX_NODISCARD 502 friend _GLIBCXX20_CONSTEXPR const_iterator 503 operator+(const const_iterator& __x, difference_type __n) 504 { 505 const_iterator __tmp = __x; 506 __tmp += __n; 507 return __tmp; 508 } 509 510 _GLIBCXX_NODISCARD 511 friend _GLIBCXX20_CONSTEXPR const_iterator 512 operator-(const const_iterator& __x, difference_type __n) 513 { 514 const_iterator __tmp = __x; 515 __tmp -= __n; 516 return __tmp; 517 } 518 519 _GLIBCXX_NODISCARD 520 friend _GLIBCXX20_CONSTEXPR const_iterator 521 operator+(difference_type __n, const const_iterator& __x) 522 { return __x + __n; } 523 }; 524 525 template<typename _Alloc> 526 struct _Bvector_base 527 { 528 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 529 rebind<_Bit_type>::other _Bit_alloc_type; 530 typedef typename __gnu_cxx::__alloc_traits<_Bit_alloc_type> 531 _Bit_alloc_traits; 532 typedef typename _Bit_alloc_traits::pointer _Bit_pointer; 533 534 struct _Bvector_impl_data 535 { 536 #if !_GLIBCXX_INLINE_VERSION 537 _Bit_iterator _M_start; 538 #else 539 // We don't need the offset field for the start, it's always zero. 540 struct { 541 _Bit_type* _M_p; 542 // Allow assignment from iterators (assume offset is zero): 543 _GLIBCXX20_CONSTEXPR 544 void operator=(_Bit_iterator __it) { _M_p = __it._M_p; } 545 } _M_start; 546 #endif 547 _Bit_iterator _M_finish; 548 _Bit_pointer _M_end_of_storage; 549 550 _GLIBCXX20_CONSTEXPR 551 _Bvector_impl_data() _GLIBCXX_NOEXCEPT 552 : _M_start(), _M_finish(), _M_end_of_storage() 553 { } 554 555 #if __cplusplus >= 201103L 556 _Bvector_impl_data(const _Bvector_impl_data&) = default; 557 558 _Bvector_impl_data& 559 operator=(const _Bvector_impl_data&) = default; 560 561 _GLIBCXX20_CONSTEXPR 562 _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept 563 : _Bvector_impl_data(__x) 564 { __x._M_reset(); } 565 566 _GLIBCXX20_CONSTEXPR 567 void 568 _M_move_data(_Bvector_impl_data&& __x) noexcept 569 { 570 *this = __x; 571 __x._M_reset(); 572 } 573 #endif 574 575 _GLIBCXX20_CONSTEXPR 576 void 577 _M_reset() _GLIBCXX_NOEXCEPT 578 { *this = _Bvector_impl_data(); } 579 580 _GLIBCXX20_CONSTEXPR 581 void 582 _M_swap_data(_Bvector_impl_data& __x) _GLIBCXX_NOEXCEPT 583 { 584 // Do not use std::swap(_M_start, __x._M_start), etc as it loses 585 // information used by TBAA. 586 std::swap(*this, __x); 587 } 588 }; 589 590 struct _Bvector_impl 591 : public _Bit_alloc_type, public _Bvector_impl_data 592 { 593 _GLIBCXX20_CONSTEXPR 594 _Bvector_impl() _GLIBCXX_NOEXCEPT_IF( 595 is_nothrow_default_constructible<_Bit_alloc_type>::value) 596 #if __cpp_concepts && __cpp_lib_type_trait_variable_templates 597 requires is_default_constructible_v<_Bit_alloc_type> 598 #endif 599 : _Bit_alloc_type() 600 { } 601 602 _GLIBCXX20_CONSTEXPR 603 _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT 604 : _Bit_alloc_type(__a) 605 { } 606 607 #if __cplusplus >= 201103L 608 // Not defaulted, to enforce noexcept(true) even when 609 // !is_nothrow_move_constructible<_Bit_alloc_type>. 610 _GLIBCXX20_CONSTEXPR 611 _Bvector_impl(_Bvector_impl&& __x) noexcept 612 : _Bit_alloc_type(std::move(__x)), _Bvector_impl_data(std::move(__x)) 613 { } 614 615 _GLIBCXX20_CONSTEXPR 616 _Bvector_impl(_Bit_alloc_type&& __a, _Bvector_impl&& __x) noexcept 617 : _Bit_alloc_type(std::move(__a)), _Bvector_impl_data(std::move(__x)) 618 { } 619 #endif 620 621 _GLIBCXX20_CONSTEXPR 622 _Bit_type* 623 _M_end_addr() const _GLIBCXX_NOEXCEPT 624 { 625 if (this->_M_end_of_storage) 626 return std::__addressof(this->_M_end_of_storage[-1]) + 1; 627 return 0; 628 } 629 }; 630 631 public: 632 typedef _Alloc allocator_type; 633 634 _GLIBCXX20_CONSTEXPR 635 _Bit_alloc_type& 636 _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT 637 { return this->_M_impl; } 638 639 _GLIBCXX20_CONSTEXPR 640 const _Bit_alloc_type& 641 _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT 642 { return this->_M_impl; } 643 644 _GLIBCXX20_CONSTEXPR 645 allocator_type 646 get_allocator() const _GLIBCXX_NOEXCEPT 647 { return allocator_type(_M_get_Bit_allocator()); } 648 649 #if __cplusplus >= 201103L 650 _Bvector_base() = default; 651 #else 652 _Bvector_base() { } 653 #endif 654 655 _GLIBCXX20_CONSTEXPR 656 _Bvector_base(const allocator_type& __a) 657 : _M_impl(__a) { } 658 659 #if __cplusplus >= 201103L 660 _Bvector_base(_Bvector_base&&) = default; 661 662 _GLIBCXX20_CONSTEXPR 663 _Bvector_base(_Bvector_base&& __x, const allocator_type& __a) noexcept 664 : _M_impl(_Bit_alloc_type(__a), std::move(__x._M_impl)) 665 { } 666 #endif 667 668 _GLIBCXX20_CONSTEXPR 669 ~_Bvector_base() 670 { this->_M_deallocate(); } 671 672 protected: 673 _Bvector_impl _M_impl; 674 675 _GLIBCXX20_CONSTEXPR 676 _Bit_pointer 677 _M_allocate(size_t __n) 678 { 679 _Bit_pointer __p = _Bit_alloc_traits::allocate(_M_impl, _S_nword(__n)); 680 #if __cpp_lib_is_constant_evaluated && __cpp_constexpr_dynamic_alloc 681 if (std::is_constant_evaluated()) 682 { 683 __n = _S_nword(__n); 684 for (size_t __i = 0; __i < __n; ++__i) 685 std::construct_at(std::to_address(__p) + __i); 686 } 687 #endif 688 return __p; 689 } 690 691 _GLIBCXX20_CONSTEXPR 692 void 693 _M_deallocate() 694 { 695 if (_M_impl._M_start._M_p) 696 { 697 const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p; 698 _Bit_alloc_traits::deallocate(_M_impl, 699 _M_impl._M_end_of_storage - __n, 700 __n); 701 _M_impl._M_reset(); 702 } 703 } 704 705 #if __cplusplus >= 201103L 706 _GLIBCXX20_CONSTEXPR 707 void 708 _M_move_data(_Bvector_base&& __x) noexcept 709 { _M_impl._M_move_data(std::move(__x._M_impl)); } 710 #endif 711 712 _GLIBCXX_CONSTEXPR 713 static size_t 714 _S_nword(size_t __n) 715 { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); } 716 }; 717 718 /** 719 * @brief A specialization of vector for booleans which offers fixed time 720 * access to individual elements in any order. 721 * 722 * @ingroup sequences 723 * @headerfile vector 724 * @since C++98 725 * 726 * @tparam _Alloc Allocator type. 727 * 728 * Note that vector<bool> does not actually meet the requirements for being 729 * a container. This is because the reference and pointer types are not 730 * really references and pointers to bool. See DR96 for details. @see 731 * vector for function documentation. 732 * 733 * In some terminology a %vector can be described as a dynamic 734 * C-style array, it offers fast and efficient access to individual 735 * elements in any order and saves the user from worrying about 736 * memory and size allocation. Subscripting ( @c [] ) access is 737 * also provided as with C-style arrays. 738 */ 739 template<typename _Alloc> 740 class vector<bool, _Alloc> : protected _Bvector_base<_Alloc> 741 { 742 typedef _Bvector_base<_Alloc> _Base; 743 typedef typename _Base::_Bit_pointer _Bit_pointer; 744 typedef typename _Base::_Bit_alloc_traits _Bit_alloc_traits; 745 746 #if __cplusplus >= 201103L 747 friend struct std::hash<vector>; 748 #endif 749 750 public: 751 typedef bool value_type; 752 typedef size_t size_type; 753 typedef ptrdiff_t difference_type; 754 typedef _Bit_reference reference; 755 typedef bool const_reference; 756 typedef _Bit_reference* pointer; 757 typedef const bool* const_pointer; 758 typedef _Bit_iterator iterator; 759 typedef _Bit_const_iterator const_iterator; 760 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 761 typedef std::reverse_iterator<iterator> reverse_iterator; 762 typedef _Alloc allocator_type; 763 764 _GLIBCXX20_CONSTEXPR 765 allocator_type 766 get_allocator() const 767 { return _Base::get_allocator(); } 768 769 protected: 770 using _Base::_M_allocate; 771 using _Base::_M_deallocate; 772 using _Base::_S_nword; 773 using _Base::_M_get_Bit_allocator; 774 775 public: 776 #if __cplusplus >= 201103L 777 vector() = default; 778 #else 779 vector() { } 780 #endif 781 782 _GLIBCXX20_CONSTEXPR 783 explicit 784 vector(const allocator_type& __a) 785 : _Base(__a) { } 786 787 #if __cplusplus >= 201103L 788 _GLIBCXX20_CONSTEXPR 789 explicit 790 vector(size_type __n, const allocator_type& __a = allocator_type()) 791 : vector(__n, false, __a) 792 { } 793 794 _GLIBCXX20_CONSTEXPR 795 vector(size_type __n, const bool& __value, 796 const allocator_type& __a = allocator_type()) 797 #else 798 explicit 799 vector(size_type __n, const bool& __value = bool(), 800 const allocator_type& __a = allocator_type()) 801 #endif 802 : _Base(__a) 803 { 804 _M_initialize(__n); 805 _M_initialize_value(__value); 806 } 807 808 _GLIBCXX20_CONSTEXPR 809 vector(const vector& __x) 810 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) 811 { 812 const_iterator __xbegin = __x.begin(), __xend = __x.end(); 813 _M_initialize(__x.size()); 814 _M_copy_aligned(__xbegin, __xend, begin()); 815 } 816 817 #if __cplusplus >= 201103L 818 vector(vector&&) = default; 819 820 private: 821 _GLIBCXX20_CONSTEXPR 822 vector(vector&& __x, const allocator_type& __a, true_type) noexcept 823 : _Base(std::move(__x), __a) 824 { } 825 826 _GLIBCXX20_CONSTEXPR 827 vector(vector&& __x, const allocator_type& __a, false_type) 828 : _Base(__a) 829 { 830 if (__x.get_allocator() == __a) 831 this->_M_move_data(std::move(__x)); 832 else 833 { 834 _M_initialize(__x.size()); 835 _M_copy_aligned(__x.begin(), __x.end(), begin()); 836 __x.clear(); 837 } 838 } 839 840 public: 841 _GLIBCXX20_CONSTEXPR 842 vector(vector&& __x, const __type_identity_t<allocator_type>& __a) 843 noexcept(_Bit_alloc_traits::_S_always_equal()) 844 : vector(std::move(__x), __a, 845 typename _Bit_alloc_traits::is_always_equal{}) 846 { } 847 848 _GLIBCXX20_CONSTEXPR 849 vector(const vector& __x, const __type_identity_t<allocator_type>& __a) 850 : _Base(__a) 851 { 852 _M_initialize(__x.size()); 853 _M_copy_aligned(__x.begin(), __x.end(), begin()); 854 } 855 856 _GLIBCXX20_CONSTEXPR 857 vector(initializer_list<bool> __l, 858 const allocator_type& __a = allocator_type()) 859 : _Base(__a) 860 { 861 _M_initialize_range(__l.begin(), __l.end(), 862 random_access_iterator_tag()); 863 } 864 #endif 865 866 #if __cplusplus >= 201103L 867 template<typename _InputIterator, 868 typename = std::_RequireInputIter<_InputIterator>> 869 _GLIBCXX20_CONSTEXPR 870 vector(_InputIterator __first, _InputIterator __last, 871 const allocator_type& __a = allocator_type()) 872 : _Base(__a) 873 { 874 _M_initialize_range(__first, __last, 875 std::__iterator_category(__first)); 876 } 877 #else 878 template<typename _InputIterator> 879 vector(_InputIterator __first, _InputIterator __last, 880 const allocator_type& __a = allocator_type()) 881 : _Base(__a) 882 { 883 // Check whether it's an integral type. If so, it's not an iterator. 884 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 885 _M_initialize_dispatch(__first, __last, _Integral()); 886 } 887 #endif 888 889 _GLIBCXX20_CONSTEXPR 890 ~vector() _GLIBCXX_NOEXCEPT { } 891 892 _GLIBCXX20_CONSTEXPR 893 vector& 894 operator=(const vector& __x) 895 { 896 if (&__x == this) 897 return *this; 898 #if __cplusplus >= 201103L 899 if (_Bit_alloc_traits::_S_propagate_on_copy_assign()) 900 { 901 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator()) 902 { 903 this->_M_deallocate(); 904 std::__alloc_on_copy(_M_get_Bit_allocator(), 905 __x._M_get_Bit_allocator()); 906 _M_initialize(__x.size()); 907 } 908 else 909 std::__alloc_on_copy(_M_get_Bit_allocator(), 910 __x._M_get_Bit_allocator()); 911 } 912 #endif 913 if (__x.size() > capacity()) 914 { 915 this->_M_deallocate(); 916 _M_initialize(__x.size()); 917 } 918 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(), 919 begin()); 920 return *this; 921 } 922 923 #if __cplusplus >= 201103L 924 _GLIBCXX20_CONSTEXPR 925 vector& 926 operator=(vector&& __x) noexcept(_Bit_alloc_traits::_S_nothrow_move()) 927 { 928 if (_Bit_alloc_traits::_S_propagate_on_move_assign() 929 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator()) 930 { 931 this->_M_deallocate(); 932 this->_M_move_data(std::move(__x)); 933 std::__alloc_on_move(_M_get_Bit_allocator(), 934 __x._M_get_Bit_allocator()); 935 } 936 else 937 { 938 if (__x.size() > capacity()) 939 { 940 this->_M_deallocate(); 941 _M_initialize(__x.size()); 942 } 943 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(), 944 begin()); 945 __x.clear(); 946 } 947 return *this; 948 } 949 950 _GLIBCXX20_CONSTEXPR 951 vector& 952 operator=(initializer_list<bool> __l) 953 { 954 this->assign(__l.begin(), __l.end()); 955 return *this; 956 } 957 #endif 958 959 // assign(), a generalized assignment member function. Two 960 // versions: one that takes a count, and one that takes a range. 961 // The range version is a member template, so we dispatch on whether 962 // or not the type is an integer. 963 _GLIBCXX20_CONSTEXPR 964 void 965 assign(size_type __n, const bool& __x) 966 { _M_fill_assign(__n, __x); } 967 968 #if __cplusplus >= 201103L 969 template<typename _InputIterator, 970 typename = std::_RequireInputIter<_InputIterator>> 971 _GLIBCXX20_CONSTEXPR 972 void 973 assign(_InputIterator __first, _InputIterator __last) 974 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 975 #else 976 template<typename _InputIterator> 977 void 978 assign(_InputIterator __first, _InputIterator __last) 979 { 980 // Check whether it's an integral type. If so, it's not an iterator. 981 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 982 _M_assign_dispatch(__first, __last, _Integral()); 983 } 984 #endif 985 986 #if __cplusplus >= 201103L 987 _GLIBCXX20_CONSTEXPR 988 void 989 assign(initializer_list<bool> __l) 990 { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); } 991 #endif 992 993 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 994 iterator 995 begin() _GLIBCXX_NOEXCEPT 996 { return iterator(this->_M_impl._M_start._M_p, 0); } 997 998 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 999 const_iterator 1000 begin() const _GLIBCXX_NOEXCEPT 1001 { return const_iterator(this->_M_impl._M_start._M_p, 0); } 1002 1003 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1004 iterator 1005 end() _GLIBCXX_NOEXCEPT 1006 { return this->_M_impl._M_finish; } 1007 1008 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1009 const_iterator 1010 end() const _GLIBCXX_NOEXCEPT 1011 { return this->_M_impl._M_finish; } 1012 1013 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1014 reverse_iterator 1015 rbegin() _GLIBCXX_NOEXCEPT 1016 { return reverse_iterator(end()); } 1017 1018 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1019 const_reverse_iterator 1020 rbegin() const _GLIBCXX_NOEXCEPT 1021 { return const_reverse_iterator(end()); } 1022 1023 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1024 reverse_iterator 1025 rend() _GLIBCXX_NOEXCEPT 1026 { return reverse_iterator(begin()); } 1027 1028 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1029 const_reverse_iterator 1030 rend() const _GLIBCXX_NOEXCEPT 1031 { return const_reverse_iterator(begin()); } 1032 1033 #if __cplusplus >= 201103L 1034 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR 1035 const_iterator 1036 cbegin() const noexcept 1037 { return const_iterator(this->_M_impl._M_start._M_p, 0); } 1038 1039 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR 1040 const_iterator 1041 cend() const noexcept 1042 { return this->_M_impl._M_finish; } 1043 1044 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR 1045 const_reverse_iterator 1046 crbegin() const noexcept 1047 { return const_reverse_iterator(end()); } 1048 1049 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR 1050 const_reverse_iterator 1051 crend() const noexcept 1052 { return const_reverse_iterator(begin()); } 1053 #endif 1054 1055 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1056 size_type 1057 size() const _GLIBCXX_NOEXCEPT 1058 { return size_type(end() - begin()); } 1059 1060 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1061 size_type 1062 max_size() const _GLIBCXX_NOEXCEPT 1063 { 1064 const size_type __isize = 1065 __gnu_cxx::__numeric_traits<difference_type>::__max 1066 - int(_S_word_bit) + 1; 1067 const size_type __asize 1068 = _Bit_alloc_traits::max_size(_M_get_Bit_allocator()); 1069 return (__asize <= __isize / int(_S_word_bit) 1070 ? __asize * int(_S_word_bit) : __isize); 1071 } 1072 1073 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1074 size_type 1075 capacity() const _GLIBCXX_NOEXCEPT 1076 { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0) 1077 - begin()); } 1078 1079 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1080 bool 1081 empty() const _GLIBCXX_NOEXCEPT 1082 { return begin() == end(); } 1083 1084 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1085 reference 1086 operator[](size_type __n) 1087 { return begin()[__n]; } 1088 1089 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1090 const_reference 1091 operator[](size_type __n) const 1092 { return begin()[__n]; } 1093 1094 protected: 1095 _GLIBCXX20_CONSTEXPR 1096 void 1097 _M_range_check(size_type __n) const 1098 { 1099 if (__n >= this->size()) 1100 __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n " 1101 "(which is %zu) >= this->size() " 1102 "(which is %zu)"), 1103 __n, this->size()); 1104 } 1105 1106 public: 1107 _GLIBCXX20_CONSTEXPR 1108 reference 1109 at(size_type __n) 1110 { 1111 _M_range_check(__n); 1112 return (*this)[__n]; 1113 } 1114 1115 _GLIBCXX20_CONSTEXPR 1116 const_reference 1117 at(size_type __n) const 1118 { 1119 _M_range_check(__n); 1120 return (*this)[__n]; 1121 } 1122 1123 _GLIBCXX20_CONSTEXPR 1124 void 1125 reserve(size_type __n) 1126 { 1127 if (__n > max_size()) 1128 __throw_length_error(__N("vector::reserve")); 1129 if (capacity() < __n) 1130 _M_reallocate(__n); 1131 } 1132 1133 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1134 reference 1135 front() 1136 { return *begin(); } 1137 1138 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1139 const_reference 1140 front() const 1141 { return *begin(); } 1142 1143 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1144 reference 1145 back() 1146 { return *(end() - 1); } 1147 1148 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1149 const_reference 1150 back() const 1151 { return *(end() - 1); } 1152 1153 _GLIBCXX20_CONSTEXPR 1154 void 1155 push_back(bool __x) 1156 { 1157 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()) 1158 *this->_M_impl._M_finish++ = __x; 1159 else 1160 _M_insert_aux(end(), __x); 1161 } 1162 1163 _GLIBCXX20_CONSTEXPR 1164 void 1165 swap(vector& __x) _GLIBCXX_NOEXCEPT 1166 { 1167 #if __cplusplus >= 201103L 1168 __glibcxx_assert(_Bit_alloc_traits::propagate_on_container_swap::value 1169 || _M_get_Bit_allocator() == __x._M_get_Bit_allocator()); 1170 #endif 1171 this->_M_impl._M_swap_data(__x._M_impl); 1172 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(), 1173 __x._M_get_Bit_allocator()); 1174 } 1175 1176 // [23.2.5]/1, third-to-last entry in synopsis listing 1177 _GLIBCXX20_CONSTEXPR 1178 static void 1179 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT 1180 { 1181 bool __tmp = __x; 1182 __x = __y; 1183 __y = __tmp; 1184 } 1185 1186 _GLIBCXX20_CONSTEXPR 1187 iterator 1188 #if __cplusplus >= 201103L 1189 insert(const_iterator __position, const bool& __x) 1190 #else 1191 insert(iterator __position, const bool& __x) 1192 #endif 1193 { 1194 const difference_type __n = __position - begin(); 1195 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr() 1196 && __position == end()) 1197 *this->_M_impl._M_finish++ = __x; 1198 else 1199 _M_insert_aux(__position._M_const_cast(), __x); 1200 return begin() + __n; 1201 } 1202 1203 #if _GLIBCXX_USE_DEPRECATED 1204 _GLIBCXX_DEPRECATED_SUGGEST("insert(position, false)") 1205 iterator 1206 insert(const_iterator __position) 1207 { return this->insert(__position._M_const_cast(), false); } 1208 #endif 1209 1210 #if __cplusplus >= 201103L 1211 template<typename _InputIterator, 1212 typename = std::_RequireInputIter<_InputIterator>> 1213 _GLIBCXX20_CONSTEXPR 1214 iterator 1215 insert(const_iterator __position, 1216 _InputIterator __first, _InputIterator __last) 1217 { 1218 difference_type __offset = __position - cbegin(); 1219 _M_insert_range(__position._M_const_cast(), 1220 __first, __last, 1221 std::__iterator_category(__first)); 1222 return begin() + __offset; 1223 } 1224 #else 1225 template<typename _InputIterator> 1226 void 1227 insert(iterator __position, 1228 _InputIterator __first, _InputIterator __last) 1229 { 1230 // Check whether it's an integral type. If so, it's not an iterator. 1231 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 1232 _M_insert_dispatch(__position, __first, __last, _Integral()); 1233 } 1234 #endif 1235 1236 #if __cplusplus >= 201103L 1237 _GLIBCXX20_CONSTEXPR 1238 iterator 1239 insert(const_iterator __position, size_type __n, const bool& __x) 1240 { 1241 difference_type __offset = __position - cbegin(); 1242 _M_fill_insert(__position._M_const_cast(), __n, __x); 1243 return begin() + __offset; 1244 } 1245 #else 1246 void 1247 insert(iterator __position, size_type __n, const bool& __x) 1248 { _M_fill_insert(__position, __n, __x); } 1249 #endif 1250 1251 #if __cplusplus >= 201103L 1252 _GLIBCXX20_CONSTEXPR 1253 iterator 1254 insert(const_iterator __p, initializer_list<bool> __l) 1255 { return this->insert(__p, __l.begin(), __l.end()); } 1256 #endif 1257 1258 _GLIBCXX20_CONSTEXPR 1259 void 1260 pop_back() 1261 { --this->_M_impl._M_finish; } 1262 1263 _GLIBCXX20_CONSTEXPR 1264 iterator 1265 #if __cplusplus >= 201103L 1266 erase(const_iterator __position) 1267 #else 1268 erase(iterator __position) 1269 #endif 1270 { return _M_erase(__position._M_const_cast()); } 1271 1272 _GLIBCXX20_CONSTEXPR 1273 iterator 1274 #if __cplusplus >= 201103L 1275 erase(const_iterator __first, const_iterator __last) 1276 #else 1277 erase(iterator __first, iterator __last) 1278 #endif 1279 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); } 1280 1281 _GLIBCXX20_CONSTEXPR 1282 void 1283 resize(size_type __new_size, bool __x = bool()) 1284 { 1285 if (__new_size < size()) 1286 _M_erase_at_end(begin() + difference_type(__new_size)); 1287 else 1288 insert(end(), __new_size - size(), __x); 1289 } 1290 1291 #if __cplusplus >= 201103L 1292 _GLIBCXX20_CONSTEXPR 1293 void 1294 shrink_to_fit() 1295 { _M_shrink_to_fit(); } 1296 #endif 1297 1298 _GLIBCXX20_CONSTEXPR 1299 void 1300 flip() _GLIBCXX_NOEXCEPT 1301 { 1302 _Bit_type * const __end = this->_M_impl._M_end_addr(); 1303 for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p) 1304 *__p = ~*__p; 1305 } 1306 1307 _GLIBCXX20_CONSTEXPR 1308 void 1309 clear() _GLIBCXX_NOEXCEPT 1310 { _M_erase_at_end(begin()); } 1311 1312 #if __cplusplus >= 201103L 1313 template<typename... _Args> 1314 #if __cplusplus > 201402L 1315 _GLIBCXX20_CONSTEXPR 1316 reference 1317 #else 1318 void 1319 #endif 1320 emplace_back(_Args&&... __args) 1321 { 1322 push_back(bool(__args...)); 1323 #if __cplusplus > 201402L 1324 return back(); 1325 #endif 1326 } 1327 1328 template<typename... _Args> 1329 _GLIBCXX20_CONSTEXPR 1330 iterator 1331 emplace(const_iterator __pos, _Args&&... __args) 1332 { return insert(__pos, bool(__args...)); } 1333 #endif 1334 1335 protected: 1336 // Precondition: __first._M_offset == 0 && __result._M_offset == 0. 1337 _GLIBCXX20_CONSTEXPR 1338 iterator 1339 _M_copy_aligned(const_iterator __first, const_iterator __last, 1340 iterator __result) 1341 { 1342 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p); 1343 return std::copy(const_iterator(__last._M_p, 0), __last, 1344 iterator(__q, 0)); 1345 } 1346 1347 _GLIBCXX20_CONSTEXPR 1348 void 1349 _M_initialize(size_type __n) 1350 { 1351 if (__n) 1352 { 1353 _Bit_pointer __q = this->_M_allocate(__n); 1354 this->_M_impl._M_end_of_storage = __q + _S_nword(__n); 1355 iterator __start = iterator(std::__addressof(*__q), 0); 1356 this->_M_impl._M_start = __start; 1357 this->_M_impl._M_finish = __start + difference_type(__n); 1358 } 1359 } 1360 1361 _GLIBCXX20_CONSTEXPR 1362 void 1363 _M_initialize_value(bool __x) _GLIBCXX_NOEXCEPT 1364 { 1365 if (_Bit_type* __p = this->_M_impl._M_start._M_p) 1366 __fill_bvector_n(__p, this->_M_impl._M_end_addr() - __p, __x); 1367 } 1368 1369 _GLIBCXX20_CONSTEXPR 1370 void 1371 _M_reallocate(size_type __n); 1372 1373 #if __cplusplus >= 201103L 1374 _GLIBCXX20_CONSTEXPR 1375 bool 1376 _M_shrink_to_fit(); 1377 #endif 1378 1379 #if __cplusplus < 201103L 1380 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1381 // 438. Ambiguity in the "do the right thing" clause 1382 template<typename _Integer> 1383 void 1384 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 1385 { 1386 _M_initialize(static_cast<size_type>(__n)); 1387 _M_initialize_value(__x); 1388 } 1389 1390 template<typename _InputIterator> 1391 void 1392 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 1393 __false_type) 1394 { _M_initialize_range(__first, __last, 1395 std::__iterator_category(__first)); } 1396 #endif 1397 1398 template<typename _InputIterator> 1399 _GLIBCXX20_CONSTEXPR 1400 void 1401 _M_initialize_range(_InputIterator __first, _InputIterator __last, 1402 std::input_iterator_tag) 1403 { 1404 for (; __first != __last; ++__first) 1405 push_back(*__first); 1406 } 1407 1408 template<typename _ForwardIterator> 1409 _GLIBCXX20_CONSTEXPR 1410 void 1411 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 1412 std::forward_iterator_tag) 1413 { 1414 const size_type __n = std::distance(__first, __last); 1415 _M_initialize(__n); 1416 std::copy(__first, __last, begin()); 1417 } 1418 1419 #if __cplusplus < 201103L 1420 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1421 // 438. Ambiguity in the "do the right thing" clause 1422 template<typename _Integer> 1423 void 1424 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 1425 { _M_fill_assign(__n, __val); } 1426 1427 template<class _InputIterator> 1428 void 1429 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 1430 __false_type) 1431 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 1432 #endif 1433 1434 _GLIBCXX20_CONSTEXPR 1435 void 1436 _M_fill_assign(size_t __n, bool __x) 1437 { 1438 if (__n > size()) 1439 { 1440 _M_initialize_value(__x); 1441 insert(end(), __n - size(), __x); 1442 } 1443 else 1444 { 1445 _M_erase_at_end(begin() + __n); 1446 _M_initialize_value(__x); 1447 } 1448 } 1449 1450 template<typename _InputIterator> 1451 _GLIBCXX20_CONSTEXPR 1452 void 1453 _M_assign_aux(_InputIterator __first, _InputIterator __last, 1454 std::input_iterator_tag) 1455 { 1456 iterator __cur = begin(); 1457 for (; __first != __last && __cur != end(); ++__cur, (void)++__first) 1458 *__cur = *__first; 1459 if (__first == __last) 1460 _M_erase_at_end(__cur); 1461 else 1462 insert(end(), __first, __last); 1463 } 1464 1465 template<typename _ForwardIterator> 1466 _GLIBCXX20_CONSTEXPR 1467 void 1468 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 1469 std::forward_iterator_tag) 1470 { 1471 const size_type __len = std::distance(__first, __last); 1472 if (__len < size()) 1473 _M_erase_at_end(std::copy(__first, __last, begin())); 1474 else 1475 { 1476 _ForwardIterator __mid = __first; 1477 std::advance(__mid, size()); 1478 std::copy(__first, __mid, begin()); 1479 insert(end(), __mid, __last); 1480 } 1481 } 1482 1483 #if __cplusplus < 201103L 1484 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1485 // 438. Ambiguity in the "do the right thing" clause 1486 template<typename _Integer> 1487 void 1488 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 1489 __true_type) 1490 { _M_fill_insert(__pos, __n, __x); } 1491 1492 template<typename _InputIterator> 1493 void 1494 _M_insert_dispatch(iterator __pos, 1495 _InputIterator __first, _InputIterator __last, 1496 __false_type) 1497 { _M_insert_range(__pos, __first, __last, 1498 std::__iterator_category(__first)); } 1499 #endif 1500 1501 _GLIBCXX20_CONSTEXPR 1502 void 1503 _M_fill_insert(iterator __position, size_type __n, bool __x); 1504 1505 template<typename _InputIterator> 1506 _GLIBCXX20_CONSTEXPR 1507 void 1508 _M_insert_range(iterator __pos, _InputIterator __first, 1509 _InputIterator __last, std::input_iterator_tag) 1510 { 1511 for (; __first != __last; ++__first) 1512 { 1513 __pos = insert(__pos, *__first); 1514 ++__pos; 1515 } 1516 } 1517 1518 template<typename _ForwardIterator> 1519 _GLIBCXX20_CONSTEXPR 1520 void 1521 _M_insert_range(iterator __position, _ForwardIterator __first, 1522 _ForwardIterator __last, std::forward_iterator_tag); 1523 1524 _GLIBCXX20_CONSTEXPR 1525 void 1526 _M_insert_aux(iterator __position, bool __x); 1527 1528 _GLIBCXX20_CONSTEXPR 1529 size_type 1530 _M_check_len(size_type __n, const char* __s) const 1531 { 1532 if (max_size() - size() < __n) 1533 __throw_length_error(__N(__s)); 1534 1535 const size_type __len = size() + std::max(size(), __n); 1536 return (__len < size() || __len > max_size()) ? max_size() : __len; 1537 } 1538 1539 _GLIBCXX20_CONSTEXPR 1540 void 1541 _M_erase_at_end(iterator __pos) 1542 { this->_M_impl._M_finish = __pos; } 1543 1544 _GLIBCXX20_CONSTEXPR 1545 iterator 1546 _M_erase(iterator __pos); 1547 1548 _GLIBCXX20_CONSTEXPR 1549 iterator 1550 _M_erase(iterator __first, iterator __last); 1551 1552 protected: 1553 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1554 // DR 464. Suggestion for new member functions in standard containers. 1555 // N.B. DR 464 says nothing about vector<bool> but we need something 1556 // here due to the using-declaration in __gnu_debug::vector. 1557 // vector class. 1558 #if __cplusplus >= 201103L 1559 void data() = delete; 1560 #else 1561 void data() { } 1562 #endif 1563 }; 1564 1565 _GLIBCXX_END_NAMESPACE_CONTAINER 1566 1567 // Fill a partial word. 1568 _GLIBCXX20_CONSTEXPR 1569 inline void 1570 __fill_bvector(_Bit_type* __v, unsigned int __first, unsigned int __last, 1571 bool __x) _GLIBCXX_NOEXCEPT 1572 { 1573 const _Bit_type __fmask = ~0ul << __first; 1574 const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last); 1575 const _Bit_type __mask = __fmask & __lmask; 1576 1577 if (__x) 1578 *__v |= __mask; 1579 else 1580 *__v &= ~__mask; 1581 } 1582 1583 // Fill N full words, as if using memset, but usable in constant expressions. 1584 __attribute__((__nonnull__)) 1585 _GLIBCXX20_CONSTEXPR 1586 inline void 1587 __fill_bvector_n(_Bit_type* __p, size_t __n, bool __x) _GLIBCXX_NOEXCEPT 1588 { 1589 #if __cpp_lib_is_constant_evaluated 1590 if (std::is_constant_evaluated()) 1591 { 1592 for (size_t __i = 0; __i < __n; ++__i) 1593 __p[__i] = __x ? ~0ul : 0ul; 1594 return; 1595 } 1596 #endif 1597 __builtin_memset(__p, __x ? ~0 : 0, __n * sizeof(_Bit_type)); 1598 } 1599 1600 1601 _GLIBCXX20_CONSTEXPR 1602 inline void 1603 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator __first, 1604 _GLIBCXX_STD_C::_Bit_iterator __last, const bool& __x) 1605 { 1606 if (__first._M_p != __last._M_p) 1607 { 1608 _Bit_type* __first_p = __first._M_p; 1609 if (__first._M_offset != 0) 1610 __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x); 1611 1612 __fill_bvector_n(__first_p, __last._M_p - __first_p, __x); 1613 1614 if (__last._M_offset != 0) 1615 __fill_bvector(__last._M_p, 0, __last._M_offset, __x); 1616 } 1617 else if (__first._M_offset != __last._M_offset) 1618 __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x); 1619 } 1620 1621 #if __cplusplus >= 201103L 1622 // DR 1182. 1623 /// std::hash specialization for vector<bool>. 1624 template<typename _Alloc> 1625 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>> 1626 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>> 1627 { 1628 size_t 1629 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept; 1630 }; 1631 #endif // C++11 1632 1633 _GLIBCXX_END_NAMESPACE_VERSION 1634 } // namespace std 1635 1636 #endif
Contact us
|
About us
|
Term of use
|
Copyright © 2000-2025 MyWebUniversity.com ™
