Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/debug/vector
1 // Debugging vector implementation -*- C++ -*- 2 3 // Copyright (C) 2003-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 /** @file debug/vector 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_VECTOR 30 #define _GLIBCXX_DEBUG_VECTOR 1 31 32 #ifdef _GLIBCXX_SYSHDR 33 #pragma GCC system_header 34 #endif 35 36 #include <bits/c++config.h> 37 namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug { 38 template<typename _Tp, typename _Allocator> class vector; 39 } } // namespace std::__debug 40 41 #include <vector> 42 #include <debug/safe_sequence.h> 43 #include <debug/safe_container.h> 44 #include <debug/safe_iterator.h> 45 46 namespace __gnu_debug 47 { 48 /** @brief Base class for Debug Mode vector. 49 * 50 * Adds information about the guaranteed capacity, which is useful for 51 * detecting code which relies on non-portable implementation details of 52 * the libstdc++ reallocation policy. 53 */ 54 template<typename _SafeSequence, 55 typename _BaseSequence> 56 class _Safe_vector 57 { 58 typedef typename _BaseSequence::size_type size_type; 59 60 _GLIBCXX20_CONSTEXPR 61 const _SafeSequence& 62 _M_seq() const { return *static_cast<const _SafeSequence*>(this); } 63 64 protected: 65 _GLIBCXX20_CONSTEXPR 66 _Safe_vector() _GLIBCXX_NOEXCEPT 67 : _M_guaranteed_capacity(0) 68 { _M_update_guaranteed_capacity(); } 69 70 _GLIBCXX20_CONSTEXPR 71 _Safe_vector(const _Safe_vector&) _GLIBCXX_NOEXCEPT 72 : _M_guaranteed_capacity(0) 73 { _M_update_guaranteed_capacity(); } 74 75 _GLIBCXX20_CONSTEXPR 76 _Safe_vector(size_type __n) _GLIBCXX_NOEXCEPT 77 : _M_guaranteed_capacity(__n) 78 { } 79 80 _GLIBCXX20_CONSTEXPR 81 _Safe_vector& 82 operator=(const _Safe_vector&) _GLIBCXX_NOEXCEPT 83 { 84 _M_update_guaranteed_capacity(); 85 return *this; 86 } 87 88 #if __cplusplus >= 201103L 89 _GLIBCXX20_CONSTEXPR 90 _Safe_vector(_Safe_vector&& __x) noexcept 91 : _Safe_vector() 92 { __x._M_guaranteed_capacity = 0; } 93 94 _GLIBCXX20_CONSTEXPR 95 _Safe_vector& 96 operator=(_Safe_vector&& __x) noexcept 97 { 98 _M_update_guaranteed_capacity(); 99 __x._M_guaranteed_capacity = 0; 100 return *this; 101 } 102 #endif 103 104 size_type _M_guaranteed_capacity; 105 106 bool 107 _M_requires_reallocation(size_type __elements) const _GLIBCXX_NOEXCEPT 108 { return __elements > _M_seq().capacity(); } 109 110 _GLIBCXX20_CONSTEXPR 111 void 112 _M_update_guaranteed_capacity() _GLIBCXX_NOEXCEPT 113 { 114 if (_M_seq().size() > _M_guaranteed_capacity) 115 _M_guaranteed_capacity = _M_seq().size(); 116 } 117 }; 118 } 119 120 namespace std _GLIBCXX_VISIBILITY(default) 121 { 122 namespace __debug 123 { 124 /// Class std::vector with safety/checking/debug instrumentation. 125 template<typename _Tp, 126 typename _Allocator = std::allocator<_Tp> > 127 class vector 128 : public __gnu_debug::_Safe_container< 129 vector<_Tp, _Allocator>, _Allocator, __gnu_debug::_Safe_sequence>, 130 public _GLIBCXX_STD_C::vector<_Tp, _Allocator>, 131 public __gnu_debug::_Safe_vector< 132 vector<_Tp, _Allocator>, 133 _GLIBCXX_STD_C::vector<_Tp, _Allocator> > 134 { 135 typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base; 136 typedef __gnu_debug::_Safe_container< 137 vector, _Allocator, __gnu_debug::_Safe_sequence> _Safe; 138 typedef __gnu_debug::_Safe_vector<vector, _Base> _Safe_vector; 139 140 typedef typename _Base::iterator _Base_iterator; 141 typedef typename _Base::const_iterator _Base_const_iterator; 142 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 143 144 template<typename _ItT, typename _SeqT, typename _CatT> 145 friend class ::__gnu_debug::_Safe_iterator; 146 147 // Reference wrapper for base class. Disambiguates vector(const _Base&) 148 // from copy constructor by requiring a user-defined conversion. 149 // See PR libstdc++/90102. 150 struct _Base_ref 151 { 152 _Base_ref(const _Base& __r) : _M_ref(__r) { } 153 154 const _Base& _M_ref; 155 }; 156 157 public: 158 typedef typename _Base::reference reference; 159 typedef typename _Base::const_reference const_reference; 160 161 typedef __gnu_debug::_Safe_iterator< 162 _Base_iterator, vector> iterator; 163 typedef __gnu_debug::_Safe_iterator< 164 _Base_const_iterator, vector> const_iterator; 165 166 typedef typename _Base::size_type size_type; 167 typedef typename _Base::difference_type difference_type; 168 169 typedef _Tp value_type; 170 typedef _Allocator allocator_type; 171 typedef typename _Base::pointer pointer; 172 typedef typename _Base::const_pointer const_pointer; 173 typedef std::reverse_iterator<iterator> reverse_iterator; 174 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 175 176 // 23.2.4.1 construct/copy/destroy: 177 178 #if __cplusplus < 201103L 179 vector() _GLIBCXX_NOEXCEPT 180 : _Base() { } 181 #else 182 vector() = default; 183 #endif 184 185 _GLIBCXX20_CONSTEXPR 186 explicit 187 vector(const _Allocator& __a) _GLIBCXX_NOEXCEPT 188 : _Base(__a) { } 189 190 #if __cplusplus >= 201103L 191 _GLIBCXX20_CONSTEXPR 192 explicit 193 vector(size_type __n, const _Allocator& __a = _Allocator()) 194 : _Base(__n, __a), _Safe_vector(__n) { } 195 196 _GLIBCXX20_CONSTEXPR 197 vector(size_type __n, const __type_identity_t<_Tp>& __value, 198 const _Allocator& __a = _Allocator()) 199 : _Base(__n, __value, __a) { } 200 #else 201 explicit 202 vector(size_type __n, const _Tp& __value = _Tp(), 203 const _Allocator& __a = _Allocator()) 204 : _Base(__n, __value, __a) { } 205 #endif 206 207 #if __cplusplus >= 201103L 208 template<class _InputIterator, 209 typename = std::_RequireInputIter<_InputIterator>> 210 #else 211 template<class _InputIterator> 212 #endif 213 _GLIBCXX20_CONSTEXPR 214 vector(_InputIterator __first, _InputIterator __last, 215 const _Allocator& __a = _Allocator()) 216 : _Base(__gnu_debug::__base(std::__is_constant_evaluated() ? __first 217 : __glibcxx_check_valid_constructor_range(__first, __last)), 218 __gnu_debug::__base(__last), __a) { } 219 220 #if __cplusplus < 201103L 221 vector(const vector& __x) 222 : _Base(__x) { } 223 224 ~vector() _GLIBCXX_NOEXCEPT { } 225 #else 226 vector(const vector&) = default; 227 vector(vector&&) = default; 228 229 _GLIBCXX20_CONSTEXPR 230 vector(const vector& __x, const __type_identity_t<allocator_type>& __a) 231 : _Base(__x, __a) { } 232 233 _GLIBCXX20_CONSTEXPR 234 vector(vector&& __x, const __type_identity_t<allocator_type>& __a) 235 noexcept( 236 std::is_nothrow_constructible<_Base, 237 _Base, const allocator_type&>::value ) 238 : _Safe(std::move(__x), __a), 239 _Base(std::move(__x), __a), 240 _Safe_vector(std::move(__x)) { } 241 242 _GLIBCXX20_CONSTEXPR 243 vector(initializer_list<value_type> __l, 244 const allocator_type& __a = allocator_type()) 245 : _Base(__l, __a) { } 246 247 #if __glibcxx_containers_ranges // C++ >= 23 248 /** 249 * @brief Construct a vector from a range. 250 * @since C++23 251 */ 252 template<std::__detail::__container_compatible_range<_Tp> _Rg> 253 constexpr 254 vector(std::from_range_t __t, _Rg&& __rg, 255 const allocator_type& __a = allocator_type()) 256 : _Base(__t, std::forward<_Rg>(__rg), __a) 257 { } 258 #endif 259 260 ~vector() = default; 261 #endif 262 263 /// Construction from a normal-mode vector 264 _GLIBCXX20_CONSTEXPR 265 vector(_Base_ref __x) 266 : _Base(__x._M_ref) { } 267 268 #if __cplusplus >= 201103L 269 vector& 270 operator=(const vector&) = default; 271 272 vector& 273 operator=(vector&&) = default; 274 275 _GLIBCXX20_CONSTEXPR 276 vector& 277 operator=(initializer_list<value_type> __l) 278 { 279 _Base::operator=(__l); 280 if (!std::__is_constant_evaluated()) 281 { 282 this->_M_invalidate_all(); 283 this->_M_update_guaranteed_capacity(); 284 } 285 return *this; 286 } 287 #endif 288 289 #if __cplusplus >= 201103L 290 template<typename _InputIterator, 291 typename = std::_RequireInputIter<_InputIterator>> 292 #else 293 template<typename _InputIterator> 294 #endif 295 _GLIBCXX20_CONSTEXPR 296 void 297 assign(_InputIterator __first, _InputIterator __last) 298 { 299 if (std::__is_constant_evaluated()) 300 return _Base::assign(__gnu_debug::__unsafe(__first), 301 __gnu_debug::__unsafe(__last)); 302 303 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 304 __glibcxx_check_valid_range2(__first, __last, __dist); 305 306 if (__dist.second >= __gnu_debug::__dp_sign) 307 _Base::assign(__gnu_debug::__unsafe(__first), 308 __gnu_debug::__unsafe(__last)); 309 else 310 _Base::assign(__first, __last); 311 312 this->_M_invalidate_all(); 313 this->_M_update_guaranteed_capacity(); 314 } 315 316 _GLIBCXX20_CONSTEXPR 317 void 318 assign(size_type __n, const _Tp& __u) 319 { 320 _Base::assign(__n, __u); 321 if (!std::__is_constant_evaluated()) 322 { 323 this->_M_invalidate_all(); 324 this->_M_update_guaranteed_capacity(); 325 } 326 } 327 328 #if __cplusplus >= 201103L 329 _GLIBCXX20_CONSTEXPR 330 void 331 assign(initializer_list<value_type> __l) 332 { 333 _Base::assign(__l); 334 if (!std::__is_constant_evaluated()) 335 { 336 this->_M_invalidate_all(); 337 this->_M_update_guaranteed_capacity(); 338 } 339 } 340 #endif 341 342 using _Base::get_allocator; 343 344 // iterators: 345 _GLIBCXX_NODISCARD 346 _GLIBCXX20_CONSTEXPR 347 iterator 348 begin() _GLIBCXX_NOEXCEPT 349 { return iterator(_Base::begin(), this); } 350 351 _GLIBCXX_NODISCARD 352 _GLIBCXX20_CONSTEXPR 353 const_iterator 354 begin() const _GLIBCXX_NOEXCEPT 355 { return const_iterator(_Base::begin(), this); } 356 357 _GLIBCXX_NODISCARD 358 _GLIBCXX20_CONSTEXPR 359 iterator 360 end() _GLIBCXX_NOEXCEPT 361 { return iterator(_Base::end(), this); } 362 363 _GLIBCXX_NODISCARD 364 _GLIBCXX20_CONSTEXPR 365 const_iterator 366 end() const _GLIBCXX_NOEXCEPT 367 { return const_iterator(_Base::end(), this); } 368 369 _GLIBCXX_NODISCARD 370 _GLIBCXX20_CONSTEXPR 371 reverse_iterator 372 rbegin() _GLIBCXX_NOEXCEPT 373 { return reverse_iterator(end()); } 374 375 _GLIBCXX_NODISCARD 376 _GLIBCXX20_CONSTEXPR 377 const_reverse_iterator 378 rbegin() const _GLIBCXX_NOEXCEPT 379 { return const_reverse_iterator(end()); } 380 381 _GLIBCXX_NODISCARD 382 _GLIBCXX20_CONSTEXPR 383 reverse_iterator 384 rend() _GLIBCXX_NOEXCEPT 385 { return reverse_iterator(begin()); } 386 387 _GLIBCXX_NODISCARD 388 _GLIBCXX20_CONSTEXPR 389 const_reverse_iterator 390 rend() const _GLIBCXX_NOEXCEPT 391 { return const_reverse_iterator(begin()); } 392 393 #if __cplusplus >= 201103L 394 [[__nodiscard__]] 395 _GLIBCXX20_CONSTEXPR 396 const_iterator 397 cbegin() const noexcept 398 { return const_iterator(_Base::begin(), this); } 399 400 [[__nodiscard__]] 401 _GLIBCXX20_CONSTEXPR 402 const_iterator 403 cend() const noexcept 404 { return const_iterator(_Base::end(), this); } 405 406 [[__nodiscard__]] 407 _GLIBCXX20_CONSTEXPR 408 const_reverse_iterator 409 crbegin() const noexcept 410 { return const_reverse_iterator(end()); } 411 412 [[__nodiscard__]] 413 _GLIBCXX20_CONSTEXPR 414 const_reverse_iterator 415 crend() const noexcept 416 { return const_reverse_iterator(begin()); } 417 #endif 418 419 // 23.2.4.2 capacity: 420 using _Base::size; 421 using _Base::max_size; 422 423 #if __cplusplus >= 201103L 424 _GLIBCXX20_CONSTEXPR 425 void 426 resize(size_type __sz) 427 { 428 if (std::__is_constant_evaluated()) 429 return _Base::resize(__sz); 430 431 bool __realloc = this->_M_requires_reallocation(__sz); 432 if (__sz < this->size()) 433 this->_M_invalidate_after_nth(__sz); 434 _Base::resize(__sz); 435 if (__realloc) 436 this->_M_invalidate_all(); 437 this->_M_update_guaranteed_capacity(); 438 } 439 440 _GLIBCXX20_CONSTEXPR 441 void 442 resize(size_type __sz, const _Tp& __c) 443 { 444 if (std::__is_constant_evaluated()) 445 return _Base::resize(__sz, __c); 446 447 bool __realloc = this->_M_requires_reallocation(__sz); 448 if (__sz < this->size()) 449 this->_M_invalidate_after_nth(__sz); 450 _Base::resize(__sz, __c); 451 if (__realloc) 452 this->_M_invalidate_all(); 453 this->_M_update_guaranteed_capacity(); 454 } 455 #else 456 void 457 resize(size_type __sz, _Tp __c = _Tp()) 458 { 459 bool __realloc = this->_M_requires_reallocation(__sz); 460 if (__sz < this->size()) 461 this->_M_invalidate_after_nth(__sz); 462 _Base::resize(__sz, __c); 463 if (__realloc) 464 this->_M_invalidate_all(); 465 this->_M_update_guaranteed_capacity(); 466 } 467 #endif 468 469 #if __cplusplus >= 201103L 470 _GLIBCXX20_CONSTEXPR 471 void 472 shrink_to_fit() 473 { 474 if (std::__is_constant_evaluated()) 475 return _Base::shrink_to_fit(); 476 477 if (_Base::_M_shrink_to_fit()) 478 { 479 this->_M_guaranteed_capacity = _Base::capacity(); 480 this->_M_invalidate_all(); 481 } 482 } 483 #endif 484 485 _GLIBCXX_NODISCARD 486 _GLIBCXX20_CONSTEXPR 487 size_type 488 capacity() const _GLIBCXX_NOEXCEPT 489 { 490 if (std::__is_constant_evaluated()) 491 return _Base::capacity(); 492 493 #ifdef _GLIBCXX_DEBUG_PEDANTIC 494 return this->_M_guaranteed_capacity; 495 #else 496 return _Base::capacity(); 497 #endif 498 } 499 500 using _Base::empty; 501 502 _GLIBCXX20_CONSTEXPR 503 void 504 reserve(size_type __n) 505 { 506 if (std::__is_constant_evaluated()) 507 return _Base::reserve(__n); 508 509 bool __realloc = this->_M_requires_reallocation(__n); 510 _Base::reserve(__n); 511 if (__n > this->_M_guaranteed_capacity) 512 this->_M_guaranteed_capacity = __n; 513 if (__realloc) 514 this->_M_invalidate_all(); 515 } 516 517 // element access: 518 _GLIBCXX_NODISCARD 519 _GLIBCXX20_CONSTEXPR 520 reference 521 operator[](size_type __n) _GLIBCXX_NOEXCEPT 522 { 523 __glibcxx_check_subscript(__n); 524 return _Base::operator[](__n); 525 } 526 527 _GLIBCXX_NODISCARD 528 _GLIBCXX20_CONSTEXPR 529 const_reference 530 operator[](size_type __n) const _GLIBCXX_NOEXCEPT 531 { 532 __glibcxx_check_subscript(__n); 533 return _Base::operator[](__n); 534 } 535 536 using _Base::at; 537 538 _GLIBCXX_NODISCARD 539 _GLIBCXX20_CONSTEXPR 540 reference 541 front() _GLIBCXX_NOEXCEPT 542 { 543 __glibcxx_check_nonempty(); 544 return _Base::front(); 545 } 546 547 _GLIBCXX_NODISCARD 548 _GLIBCXX20_CONSTEXPR 549 const_reference 550 front() const _GLIBCXX_NOEXCEPT 551 { 552 __glibcxx_check_nonempty(); 553 return _Base::front(); 554 } 555 556 _GLIBCXX_NODISCARD 557 _GLIBCXX20_CONSTEXPR 558 reference 559 back() _GLIBCXX_NOEXCEPT 560 { 561 __glibcxx_check_nonempty(); 562 return _Base::back(); 563 } 564 565 _GLIBCXX_NODISCARD 566 _GLIBCXX20_CONSTEXPR 567 const_reference 568 back() const _GLIBCXX_NOEXCEPT 569 { 570 __glibcxx_check_nonempty(); 571 return _Base::back(); 572 } 573 574 // _GLIBCXX_RESOLVE_LIB_DEFECTS 575 // DR 464. Suggestion for new member functions in standard containers. 576 using _Base::data; 577 578 // 23.2.4.3 modifiers: 579 _GLIBCXX20_CONSTEXPR 580 void 581 push_back(const _Tp& __x) 582 { 583 if (std::__is_constant_evaluated()) 584 return _Base::push_back(__x); 585 586 bool __realloc = this->_M_requires_reallocation(this->size() + 1); 587 _Base::push_back(__x); 588 if (__realloc) 589 this->_M_invalidate_all(); 590 this->_M_update_guaranteed_capacity(); 591 } 592 593 #if __cplusplus >= 201103L 594 template<typename _Up = _Tp> 595 _GLIBCXX20_CONSTEXPR 596 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value, 597 void>::__type 598 push_back(_Tp&& __x) 599 { emplace_back(std::move(__x)); } 600 601 template<typename... _Args> 602 _GLIBCXX20_CONSTEXPR 603 #if __cplusplus > 201402L 604 reference 605 #else 606 void 607 #endif 608 emplace_back(_Args&&... __args) 609 { 610 if (std::__is_constant_evaluated()) 611 return _Base::emplace_back(std::forward<_Args>(__args)...); 612 613 bool __realloc = this->_M_requires_reallocation(this->size() + 1); 614 _Base::emplace_back(std::forward<_Args>(__args)...); 615 if (__realloc) 616 this->_M_invalidate_all(); 617 this->_M_update_guaranteed_capacity(); 618 #if __cplusplus > 201402L 619 return back(); 620 #endif 621 } 622 #endif 623 624 _GLIBCXX20_CONSTEXPR 625 void 626 pop_back() _GLIBCXX_NOEXCEPT 627 { 628 if (!std::__is_constant_evaluated()) 629 { 630 __glibcxx_check_nonempty(); 631 this->_M_invalidate_if(_Equal(--_Base::end())); 632 } 633 _Base::pop_back(); 634 } 635 636 #if __cplusplus >= 201103L 637 template<typename... _Args> 638 _GLIBCXX20_CONSTEXPR 639 iterator 640 emplace(const_iterator __position, _Args&&... __args) 641 { 642 if (std::__is_constant_evaluated()) 643 return iterator(_Base::emplace(__position.base(), 644 std::forward<_Args>(__args)...), 645 this); 646 647 __glibcxx_check_insert(__position); 648 bool __realloc = this->_M_requires_reallocation(this->size() + 1); 649 difference_type __offset = __position.base() - _Base::cbegin(); 650 _Base_iterator __res = _Base::emplace(__position.base(), 651 std::forward<_Args>(__args)...); 652 if (__realloc) 653 this->_M_invalidate_all(); 654 else 655 this->_M_invalidate_after_nth(__offset); 656 this->_M_update_guaranteed_capacity(); 657 return { __res, this }; 658 } 659 #endif 660 661 _GLIBCXX20_CONSTEXPR 662 iterator 663 #if __cplusplus >= 201103L 664 insert(const_iterator __position, const _Tp& __x) 665 #else 666 insert(iterator __position, const _Tp& __x) 667 #endif 668 { 669 if (std::__is_constant_evaluated()) 670 return iterator(_Base::insert(__position.base(), __x), this); 671 672 __glibcxx_check_insert(__position); 673 bool __realloc = this->_M_requires_reallocation(this->size() + 1); 674 difference_type __offset = __position.base() - _Base::begin(); 675 _Base_iterator __res = _Base::insert(__position.base(), __x); 676 if (__realloc) 677 this->_M_invalidate_all(); 678 else 679 this->_M_invalidate_after_nth(__offset); 680 this->_M_update_guaranteed_capacity(); 681 return iterator(__res, this); 682 } 683 684 #if __cplusplus >= 201103L 685 template<typename _Up = _Tp> 686 _GLIBCXX20_CONSTEXPR 687 typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value, 688 iterator>::__type 689 insert(const_iterator __position, _Tp&& __x) 690 { return emplace(__position, std::move(__x)); } 691 692 _GLIBCXX20_CONSTEXPR 693 iterator 694 insert(const_iterator __position, initializer_list<value_type> __l) 695 { return this->insert(__position, __l.begin(), __l.end()); } 696 #endif 697 698 #if __cplusplus >= 201103L 699 _GLIBCXX20_CONSTEXPR 700 iterator 701 insert(const_iterator __position, size_type __n, const _Tp& __x) 702 { 703 if (std::__is_constant_evaluated()) 704 return iterator(_Base::insert(__position.base(), __n, __x), this); 705 706 __glibcxx_check_insert(__position); 707 bool __realloc = this->_M_requires_reallocation(this->size() + __n); 708 difference_type __offset = __position.base() - _Base::cbegin(); 709 _Base_iterator __res = _Base::insert(__position.base(), __n, __x); 710 if (__realloc) 711 this->_M_invalidate_all(); 712 else 713 this->_M_invalidate_after_nth(__offset); 714 this->_M_update_guaranteed_capacity(); 715 return { __res, this }; 716 } 717 #else 718 void 719 insert(iterator __position, size_type __n, const _Tp& __x) 720 { 721 __glibcxx_check_insert(__position); 722 bool __realloc = this->_M_requires_reallocation(this->size() + __n); 723 difference_type __offset = __position.base() - _Base::begin(); 724 _Base::insert(__position.base(), __n, __x); 725 if (__realloc) 726 this->_M_invalidate_all(); 727 else 728 this->_M_invalidate_after_nth(__offset); 729 this->_M_update_guaranteed_capacity(); 730 } 731 #endif 732 733 #if __cplusplus >= 201103L 734 template<class _InputIterator, 735 typename = std::_RequireInputIter<_InputIterator>> 736 _GLIBCXX20_CONSTEXPR 737 iterator 738 insert(const_iterator __position, 739 _InputIterator __first, _InputIterator __last) 740 { 741 if (std::__is_constant_evaluated()) 742 return iterator(_Base::insert(__position.base(), 743 __gnu_debug::__unsafe(__first), 744 __gnu_debug::__unsafe(__last)), this); 745 746 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 747 __glibcxx_check_insert_range(__position, __first, __last, __dist); 748 749 /* Hard to guess if invalidation will occur, because __last 750 - __first can't be calculated in all cases, so we just 751 punt here by checking if it did occur. */ 752 _Base_iterator __old_begin = _M_base().begin(); 753 difference_type __offset = __position.base() - _Base::cbegin(); 754 _Base_iterator __res; 755 if (__dist.second >= __gnu_debug::__dp_sign) 756 __res = _Base::insert(__position.base(), 757 __gnu_debug::__unsafe(__first), 758 __gnu_debug::__unsafe(__last)); 759 else 760 __res = _Base::insert(__position.base(), __first, __last); 761 762 if (_M_base().begin() != __old_begin) 763 this->_M_invalidate_all(); 764 else 765 this->_M_invalidate_after_nth(__offset); 766 this->_M_update_guaranteed_capacity(); 767 return { __res, this }; 768 } 769 #else 770 template<class _InputIterator> 771 void 772 insert(iterator __position, 773 _InputIterator __first, _InputIterator __last) 774 { 775 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 776 __glibcxx_check_insert_range(__position, __first, __last, __dist); 777 778 /* Hard to guess if invalidation will occur, because __last 779 - __first can't be calculated in all cases, so we just 780 punt here by checking if it did occur. */ 781 _Base_iterator __old_begin = _M_base().begin(); 782 difference_type __offset = __position.base() - _Base::begin(); 783 if (__dist.second >= __gnu_debug::__dp_sign) 784 _Base::insert(__position.base(), __gnu_debug::__unsafe(__first), 785 __gnu_debug::__unsafe(__last)); 786 else 787 _Base::insert(__position.base(), __first, __last); 788 789 if (_M_base().begin() != __old_begin) 790 this->_M_invalidate_all(); 791 else 792 this->_M_invalidate_after_nth(__offset); 793 this->_M_update_guaranteed_capacity(); 794 } 795 #endif 796 797 _GLIBCXX20_CONSTEXPR 798 iterator 799 #if __cplusplus >= 201103L 800 erase(const_iterator __position) 801 #else 802 erase(iterator __position) 803 #endif 804 { 805 if (std::__is_constant_evaluated()) 806 return iterator(_Base::erase(__position.base()), this); 807 808 __glibcxx_check_erase(__position); 809 difference_type __offset = __position.base() - _Base::begin(); 810 _Base_iterator __res = _Base::erase(__position.base()); 811 this->_M_invalidate_after_nth(__offset); 812 return iterator(__res, this); 813 } 814 815 _GLIBCXX20_CONSTEXPR 816 iterator 817 #if __cplusplus >= 201103L 818 erase(const_iterator __first, const_iterator __last) 819 #else 820 erase(iterator __first, iterator __last) 821 #endif 822 { 823 if (std::__is_constant_evaluated()) 824 return iterator(_Base::erase(__first.base(), __last.base()), this); 825 826 // _GLIBCXX_RESOLVE_LIB_DEFECTS 827 // 151. can't currently clear() empty container 828 __glibcxx_check_erase_range(__first, __last); 829 830 if (__first.base() != __last.base()) 831 { 832 difference_type __offset = __first.base() - _Base::begin(); 833 _Base_iterator __res = _Base::erase(__first.base(), 834 __last.base()); 835 this->_M_invalidate_after_nth(__offset); 836 return iterator(__res, this); 837 } 838 else 839 #if __cplusplus >= 201103L 840 return { _Base::begin() + (__first.base() - _Base::cbegin()), this }; 841 #else 842 return __first; 843 #endif 844 } 845 846 _GLIBCXX20_CONSTEXPR 847 void 848 swap(vector& __x) 849 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 850 { 851 if (!std::__is_constant_evaluated()) 852 _Safe::_M_swap(__x); 853 _Base::swap(__x); 854 std::swap(this->_M_guaranteed_capacity, __x._M_guaranteed_capacity); 855 } 856 857 _GLIBCXX20_CONSTEXPR 858 void 859 clear() _GLIBCXX_NOEXCEPT 860 { 861 _Base::clear(); 862 if (!std::__is_constant_evaluated()) 863 this->_M_invalidate_all(); 864 } 865 866 _GLIBCXX20_CONSTEXPR 867 _Base& 868 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 869 870 _GLIBCXX20_CONSTEXPR 871 const _Base& 872 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 873 874 #if __glibcxx_containers_ranges // C++ >= 23 875 template<std::__detail::__container_compatible_range<_Tp> _Rg> 876 constexpr void 877 assign_range(_Rg&& __rg) 878 { 879 auto __old_capacity = _Base::capacity(); 880 auto __old_size = _Base::size(); 881 _Base::assign_range(__rg); 882 if (!std::__is_constant_evaluated()) 883 { 884 if (_Base::capacity() != __old_capacity) 885 this->_M_invalidate_all(); 886 else if (_Base::size() < __old_size) 887 this->_M_invalidate_after_nth(_Base::size()); 888 this->_M_update_guaranteed_capacity(); 889 } 890 } 891 892 template<__detail::__container_compatible_range<_Tp> _Rg> 893 constexpr iterator 894 insert_range(const_iterator __pos, _Rg&& __rg) 895 { 896 auto __old_capacity = _Base::capacity(); 897 auto __res = _Base::insert_range(__pos.base(), __rg); 898 if (!std::__is_constant_evaluated()) 899 { 900 if (_Base::capacity() != __old_capacity) 901 this->_M_invalidate_all(); 902 this->_M_update_guaranteed_capacity(); 903 } 904 return iterator(__res, this); 905 } 906 907 template<__detail::__container_compatible_range<_Tp> _Rg> 908 constexpr void 909 append_range(_Rg&& __rg) 910 { 911 auto __old_capacity = _Base::capacity(); 912 _Base::append_range(__rg); 913 if (!std::__is_constant_evaluated()) 914 { 915 if (_Base::capacity() != __old_capacity) 916 this->_M_invalidate_all(); 917 this->_M_update_guaranteed_capacity(); 918 } 919 } 920 #endif 921 922 private: 923 void 924 _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT 925 { 926 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth; 927 this->_M_invalidate_if(_After_nth(__n, _Base::begin())); 928 } 929 }; 930 931 template<typename _Tp, typename _Alloc> 932 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 933 inline bool 934 operator==(const vector<_Tp, _Alloc>& __lhs, 935 const vector<_Tp, _Alloc>& __rhs) 936 { return __lhs._M_base() == __rhs._M_base(); } 937 938 #if __cpp_lib_three_way_comparison 939 template<typename _Tp, typename _Alloc> 940 [[nodiscard]] 941 constexpr __detail::__synth3way_t<_Tp> 942 operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) 943 { return __x._M_base() <=> __y._M_base(); } 944 #else 945 template<typename _Tp, typename _Alloc> 946 _GLIBCXX_NODISCARD 947 inline bool 948 operator!=(const vector<_Tp, _Alloc>& __lhs, 949 const vector<_Tp, _Alloc>& __rhs) 950 { return __lhs._M_base() != __rhs._M_base(); } 951 952 template<typename _Tp, typename _Alloc> 953 _GLIBCXX_NODISCARD 954 inline bool 955 operator<(const vector<_Tp, _Alloc>& __lhs, 956 const vector<_Tp, _Alloc>& __rhs) 957 { return __lhs._M_base() < __rhs._M_base(); } 958 959 template<typename _Tp, typename _Alloc> 960 _GLIBCXX_NODISCARD 961 inline bool 962 operator<=(const vector<_Tp, _Alloc>& __lhs, 963 const vector<_Tp, _Alloc>& __rhs) 964 { return __lhs._M_base() <= __rhs._M_base(); } 965 966 template<typename _Tp, typename _Alloc> 967 _GLIBCXX_NODISCARD 968 inline bool 969 operator>=(const vector<_Tp, _Alloc>& __lhs, 970 const vector<_Tp, _Alloc>& __rhs) 971 { return __lhs._M_base() >= __rhs._M_base(); } 972 973 template<typename _Tp, typename _Alloc> 974 _GLIBCXX_NODISCARD 975 inline bool 976 operator>(const vector<_Tp, _Alloc>& __lhs, 977 const vector<_Tp, _Alloc>& __rhs) 978 { return __lhs._M_base() > __rhs._M_base(); } 979 #endif // three-way comparison 980 981 template<typename _Tp, typename _Alloc> 982 _GLIBCXX20_CONSTEXPR 983 inline void 984 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs) 985 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs))) 986 { __lhs.swap(__rhs); } 987 988 #if __cpp_deduction_guides >= 201606 989 template<typename _InputIterator, typename _ValT 990 = typename iterator_traits<_InputIterator>::value_type, 991 typename _Allocator = allocator<_ValT>, 992 typename = _RequireInputIter<_InputIterator>, 993 typename = _RequireAllocator<_Allocator>> 994 vector(_InputIterator, _InputIterator, _Allocator = _Allocator()) 995 -> vector<_ValT, _Allocator>; 996 997 template<typename _Tp, typename _Allocator = allocator<_Tp>, 998 typename = _RequireAllocator<_Allocator>> 999 vector(size_t, _Tp, _Allocator = _Allocator()) 1000 -> vector<_Tp, _Allocator>; 1001 1002 #if __glibcxx_containers_ranges // C++ >= 23 1003 template<ranges::input_range _Rg, 1004 typename _Alloc = allocator<ranges::range_value_t<_Rg>>> 1005 vector(from_range_t, _Rg&&, _Alloc = _Alloc()) 1006 -> vector<ranges::range_value_t<_Rg>, _Alloc>; 1007 #endif 1008 #endif 1009 1010 } // namespace __debug 1011 1012 _GLIBCXX_BEGIN_NAMESPACE_VERSION 1013 1014 #if __cplusplus >= 201103L 1015 // DR 1182. 1016 /// std::hash specialization for vector<bool>. 1017 template<typename _Alloc> 1018 struct hash<__debug::vector<bool, _Alloc>> 1019 : public __hash_base<size_t, __debug::vector<bool, _Alloc>> 1020 { 1021 size_t 1022 operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept 1023 { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); } 1024 }; 1025 #endif 1026 1027 #if __cplusplus >= 201703L 1028 namespace __detail::__variant 1029 { 1030 template<typename> struct _Never_valueless_alt; // see <variant> 1031 1032 // Provide the strong exception-safety guarantee when emplacing a 1033 // vector into a variant, but only if move assignment cannot throw. 1034 template<typename _Tp, typename _Alloc> 1035 struct _Never_valueless_alt<__debug::vector<_Tp, _Alloc>> 1036 : std::is_nothrow_move_assignable<__debug::vector<_Tp, _Alloc>> 1037 { }; 1038 } // namespace __detail::__variant 1039 #endif // C++17 1040 1041 _GLIBCXX_END_NAMESPACE_VERSION 1042 } // namespace std 1043 1044 namespace __gnu_debug 1045 { 1046 template<typename _Tp, typename _Alloc> 1047 struct _Is_contiguous_sequence<std::__debug::vector<_Tp, _Alloc> > 1048 : std::__true_type 1049 { }; 1050 1051 template<typename _Alloc> 1052 struct _Is_contiguous_sequence<std::__debug::vector<bool, _Alloc> > 1053 : std::__false_type 1054 { }; 1055 } 1056 1057 #endif
