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