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