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