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