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