1// Debugging list implementation -*- C++ -*- 2 3// Copyright (C) 2003-2018 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/list 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29#ifndef _GLIBCXX_DEBUG_LIST 30#define _GLIBCXX_DEBUG_LIST 1 31 32#pragma GCC system_header 33 34#include <list> 35#include <debug/safe_sequence.h> 36#include <debug/safe_container.h> 37#include <debug/safe_iterator.h> 38 39namespace std _GLIBCXX_VISIBILITY(default) 40{ 41namespace __debug 42{ 43 /// Class std::list with safety/checking/debug instrumentation. 44 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 45 class list 46 : public __gnu_debug::_Safe_container< 47 list<_Tp, _Allocator>, _Allocator, 48 __gnu_debug::_Safe_node_sequence>, 49 public _GLIBCXX_STD_C::list<_Tp, _Allocator> 50 { 51 typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base; 52 typedef __gnu_debug::_Safe_container< 53 list, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe; 54 55 typedef typename _Base::iterator _Base_iterator; 56 typedef typename _Base::const_iterator _Base_const_iterator; 57 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 58 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 59 60 public: 61 typedef typename _Base::reference reference; 62 typedef typename _Base::const_reference const_reference; 63 64 typedef __gnu_debug::_Safe_iterator<_Base_iterator, list> 65 iterator; 66 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list> 67 const_iterator; 68 69 typedef typename _Base::size_type size_type; 70 typedef typename _Base::difference_type difference_type; 71 72 typedef _Tp value_type; 73 typedef _Allocator allocator_type; 74 typedef typename _Base::pointer pointer; 75 typedef typename _Base::const_pointer const_pointer; 76 typedef std::reverse_iterator<iterator> reverse_iterator; 77 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 78 79 // 23.2.2.1 construct/copy/destroy: 80 81#if __cplusplus < 201103L 82 list() 83 : _Base() { } 84 85 list(const list& __x) 86 : _Base(__x) { } 87 88 ~list() { } 89#else 90 list() = default; 91 list(const list&) = default; 92 list(list&&) = default; 93 94 list(initializer_list<value_type> __l, 95 const allocator_type& __a = allocator_type()) 96 : _Base(__l, __a) { } 97 98 ~list() = default; 99 100 list(const list& __x, const allocator_type& __a) 101 : _Base(__x, __a) { } 102 103 list(list&& __x, const allocator_type& __a) 104 : _Base(std::move(__x), __a) { } 105#endif 106 107 explicit 108 list(const _Allocator& __a) _GLIBCXX_NOEXCEPT 109 : _Base(__a) { } 110 111#if __cplusplus >= 201103L 112 explicit 113 list(size_type __n, const allocator_type& __a = allocator_type()) 114 : _Base(__n, __a) { } 115 116 list(size_type __n, const _Tp& __value, 117 const _Allocator& __a = _Allocator()) 118 : _Base(__n, __value, __a) { } 119#else 120 explicit 121 list(size_type __n, const _Tp& __value = _Tp(), 122 const _Allocator& __a = _Allocator()) 123 : _Base(__n, __value, __a) { } 124#endif 125 126#if __cplusplus >= 201103L 127 template<class _InputIterator, 128 typename = std::_RequireInputIter<_InputIterator>> 129#else 130 template<class _InputIterator> 131#endif 132 list(_InputIterator __first, _InputIterator __last, 133 const _Allocator& __a = _Allocator()) 134 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 135 __last)), 136 __gnu_debug::__base(__last), __a) 137 { } 138 139 list(const _Base& __x) 140 : _Base(__x) { } 141 142#if __cplusplus < 201103L 143 list& 144 operator=(const list& __x) 145 { 146 this->_M_safe() = __x; 147 _M_base() = __x; 148 return *this; 149 } 150#else 151 list& 152 operator=(const list&) = default; 153 154 list& 155 operator=(list&&) = default; 156 157 list& 158 operator=(initializer_list<value_type> __l) 159 { 160 this->_M_invalidate_all(); 161 _M_base() = __l; 162 return *this; 163 } 164 165 void 166 assign(initializer_list<value_type> __l) 167 { 168 _Base::assign(__l); 169 this->_M_invalidate_all(); 170 } 171#endif 172 173#if __cplusplus >= 201103L 174 template<class _InputIterator, 175 typename = std::_RequireInputIter<_InputIterator>> 176#else 177 template<class _InputIterator> 178#endif 179 void 180 assign(_InputIterator __first, _InputIterator __last) 181 { 182 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 183 __glibcxx_check_valid_range2(__first, __last, __dist); 184 185 if (__dist.second >= __gnu_debug::__dp_sign) 186 _Base::assign(__gnu_debug::__unsafe(__first), 187 __gnu_debug::__unsafe(__last)); 188 else 189 _Base::assign(__first, __last); 190 191 this->_M_invalidate_all(); 192 } 193 194 void 195 assign(size_type __n, const _Tp& __t) 196 { 197 _Base::assign(__n, __t); 198 this->_M_invalidate_all(); 199 } 200 201 using _Base::get_allocator; 202 203 // iterators: 204 iterator 205 begin() _GLIBCXX_NOEXCEPT 206 { return iterator(_Base::begin(), this); } 207 208 const_iterator 209 begin() const _GLIBCXX_NOEXCEPT 210 { return const_iterator(_Base::begin(), this); } 211 212 iterator 213 end() _GLIBCXX_NOEXCEPT 214 { return iterator(_Base::end(), this); } 215 216 const_iterator 217 end() const _GLIBCXX_NOEXCEPT 218 { return const_iterator(_Base::end(), this); } 219 220 reverse_iterator 221 rbegin() _GLIBCXX_NOEXCEPT 222 { return reverse_iterator(end()); } 223 224 const_reverse_iterator 225 rbegin() const _GLIBCXX_NOEXCEPT 226 { return const_reverse_iterator(end()); } 227 228 reverse_iterator 229 rend() _GLIBCXX_NOEXCEPT 230 { return reverse_iterator(begin()); } 231 232 const_reverse_iterator 233 rend() const _GLIBCXX_NOEXCEPT 234 { return const_reverse_iterator(begin()); } 235 236#if __cplusplus >= 201103L 237 const_iterator 238 cbegin() const noexcept 239 { return const_iterator(_Base::begin(), this); } 240 241 const_iterator 242 cend() const noexcept 243 { return const_iterator(_Base::end(), this); } 244 245 const_reverse_iterator 246 crbegin() const noexcept 247 { return const_reverse_iterator(end()); } 248 249 const_reverse_iterator 250 crend() const noexcept 251 { return const_reverse_iterator(begin()); } 252#endif 253 254 // 23.2.2.2 capacity: 255 using _Base::empty; 256 using _Base::size; 257 using _Base::max_size; 258 259#if __cplusplus >= 201103L 260 void 261 resize(size_type __sz) 262 { 263 this->_M_detach_singular(); 264 265 // if __sz < size(), invalidate all iterators in [begin + __sz, end()) 266 _Base_iterator __victim = _Base::begin(); 267 _Base_iterator __end = _Base::end(); 268 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 269 ++__victim; 270 271 for (; __victim != __end; ++__victim) 272 this->_M_invalidate_if(_Equal(__victim)); 273 274 __try 275 { 276 _Base::resize(__sz); 277 } 278 __catch(...) 279 { 280 this->_M_revalidate_singular(); 281 __throw_exception_again; 282 } 283 } 284 285 void 286 resize(size_type __sz, const _Tp& __c) 287 { 288 this->_M_detach_singular(); 289 290 // if __sz < size(), invalidate all iterators in [begin + __sz, end()) 291 _Base_iterator __victim = _Base::begin(); 292 _Base_iterator __end = _Base::end(); 293 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 294 ++__victim; 295 296 for (; __victim != __end; ++__victim) 297 this->_M_invalidate_if(_Equal(__victim)); 298 299 __try 300 { 301 _Base::resize(__sz, __c); 302 } 303 __catch(...) 304 { 305 this->_M_revalidate_singular(); 306 __throw_exception_again; 307 } 308 } 309#else 310 void 311 resize(size_type __sz, _Tp __c = _Tp()) 312 { 313 this->_M_detach_singular(); 314 315 // if __sz < size(), invalidate all iterators in [begin + __sz, end()) 316 _Base_iterator __victim = _Base::begin(); 317 _Base_iterator __end = _Base::end(); 318 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 319 ++__victim; 320 321 for (; __victim != __end; ++__victim) 322 this->_M_invalidate_if(_Equal(__victim)); 323 324 __try 325 { 326 _Base::resize(__sz, __c); 327 } 328 __catch(...) 329 { 330 this->_M_revalidate_singular(); 331 __throw_exception_again; 332 } 333 } 334#endif 335 336 // element access: 337 reference 338 front() _GLIBCXX_NOEXCEPT 339 { 340 __glibcxx_check_nonempty(); 341 return _Base::front(); 342 } 343 344 const_reference 345 front() const _GLIBCXX_NOEXCEPT 346 { 347 __glibcxx_check_nonempty(); 348 return _Base::front(); 349 } 350 351 reference 352 back() _GLIBCXX_NOEXCEPT 353 { 354 __glibcxx_check_nonempty(); 355 return _Base::back(); 356 } 357 358 const_reference 359 back() const _GLIBCXX_NOEXCEPT 360 { 361 __glibcxx_check_nonempty(); 362 return _Base::back(); 363 } 364 365 // 23.2.2.3 modifiers: 366 using _Base::push_front; 367 368#if __cplusplus >= 201103L 369 using _Base::emplace_front; 370#endif 371 372 void 373 pop_front() _GLIBCXX_NOEXCEPT 374 { 375 __glibcxx_check_nonempty(); 376 this->_M_invalidate_if(_Equal(_Base::begin())); 377 _Base::pop_front(); 378 } 379 380 using _Base::push_back; 381 382#if __cplusplus >= 201103L 383 using _Base::emplace_back; 384#endif 385 386 void 387 pop_back() _GLIBCXX_NOEXCEPT 388 { 389 __glibcxx_check_nonempty(); 390 this->_M_invalidate_if(_Equal(--_Base::end())); 391 _Base::pop_back(); 392 } 393 394#if __cplusplus >= 201103L 395 template<typename... _Args> 396 iterator 397 emplace(const_iterator __position, _Args&&... __args) 398 { 399 __glibcxx_check_insert(__position); 400 return iterator(_Base::emplace(__position.base(), 401 std::forward<_Args>(__args)...), this); 402 } 403#endif 404 405 iterator 406#if __cplusplus >= 201103L 407 insert(const_iterator __position, const _Tp& __x) 408#else 409 insert(iterator __position, const _Tp& __x) 410#endif 411 { 412 __glibcxx_check_insert(__position); 413 return iterator(_Base::insert(__position.base(), __x), this); 414 } 415 416#if __cplusplus >= 201103L 417 iterator 418 insert(const_iterator __position, _Tp&& __x) 419 { return emplace(__position, std::move(__x)); } 420 421 iterator 422 insert(const_iterator __p, initializer_list<value_type> __l) 423 { 424 __glibcxx_check_insert(__p); 425 return iterator(_Base::insert(__p.base(), __l), this); 426 } 427#endif 428 429#if __cplusplus >= 201103L 430 iterator 431 insert(const_iterator __position, size_type __n, const _Tp& __x) 432 { 433 __glibcxx_check_insert(__position); 434 return iterator(_Base::insert(__position.base(), __n, __x), this); 435 } 436#else 437 void 438 insert(iterator __position, size_type __n, const _Tp& __x) 439 { 440 __glibcxx_check_insert(__position); 441 _Base::insert(__position.base(), __n, __x); 442 } 443#endif 444 445#if __cplusplus >= 201103L 446 template<class _InputIterator, 447 typename = std::_RequireInputIter<_InputIterator>> 448 iterator 449 insert(const_iterator __position, _InputIterator __first, 450 _InputIterator __last) 451 { 452 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 453 __glibcxx_check_insert_range(__position, __first, __last, __dist); 454 if (__dist.second >= __gnu_debug::__dp_sign) 455 return 456 { 457 _Base::insert(__position.base(), 458 __gnu_debug::__unsafe(__first), 459 __gnu_debug::__unsafe(__last)), 460 this 461 }; 462 else 463 return { _Base::insert(__position.base(), __first, __last), this }; 464 } 465#else 466 template<class _InputIterator> 467 void 468 insert(iterator __position, _InputIterator __first, 469 _InputIterator __last) 470 { 471 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 472 __glibcxx_check_insert_range(__position, __first, __last, __dist); 473 474 if (__dist.second >= __gnu_debug::__dp_sign) 475 _Base::insert(__position.base(), __gnu_debug::__unsafe(__first), 476 __gnu_debug::__unsafe(__last)); 477 else 478 _Base::insert(__position.base(), __first, __last); 479 } 480#endif 481 482 private: 483 _Base_iterator 484#if __cplusplus >= 201103L 485 _M_erase(_Base_const_iterator __position) noexcept 486#else 487 _M_erase(_Base_iterator __position) 488#endif 489 { 490 this->_M_invalidate_if(_Equal(__position)); 491 return _Base::erase(__position); 492 } 493 494 public: 495 iterator 496#if __cplusplus >= 201103L 497 erase(const_iterator __position) noexcept 498#else 499 erase(iterator __position) 500#endif 501 { 502 __glibcxx_check_erase(__position); 503 return iterator(_M_erase(__position.base()), this); 504 } 505 506 iterator 507#if __cplusplus >= 201103L 508 erase(const_iterator __first, const_iterator __last) noexcept 509#else 510 erase(iterator __first, iterator __last) 511#endif 512 { 513 // _GLIBCXX_RESOLVE_LIB_DEFECTS 514 // 151. can't currently clear() empty container 515 __glibcxx_check_erase_range(__first, __last); 516 for (_Base_const_iterator __victim = __first.base(); 517 __victim != __last.base(); ++__victim) 518 { 519 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 520 _M_message(__gnu_debug::__msg_valid_range) 521 ._M_iterator(__first, "position") 522 ._M_iterator(__last, "last")); 523 this->_M_invalidate_if(_Equal(__victim)); 524 } 525 return iterator(_Base::erase(__first.base(), __last.base()), this); 526 } 527 528 void 529 swap(list& __x) 530 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 531 { 532 _Safe::_M_swap(__x); 533 _Base::swap(__x); 534 } 535 536 void 537 clear() _GLIBCXX_NOEXCEPT 538 { 539 _Base::clear(); 540 this->_M_invalidate_all(); 541 } 542 543 // 23.2.2.4 list operations: 544 void 545#if __cplusplus >= 201103L 546 splice(const_iterator __position, list&& __x) noexcept 547#else 548 splice(iterator __position, list& __x) 549#endif 550 { 551 _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this, 552 _M_message(__gnu_debug::__msg_self_splice) 553 ._M_sequence(*this, "this")); 554 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end())); 555 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base())); 556 } 557 558#if __cplusplus >= 201103L 559 void 560 splice(const_iterator __position, list& __x) noexcept 561 { splice(__position, std::move(__x)); } 562#endif 563 564 void 565#if __cplusplus >= 201103L 566 splice(const_iterator __position, list&& __x, const_iterator __i) noexcept 567#else 568 splice(iterator __position, list& __x, iterator __i) 569#endif 570 { 571 __glibcxx_check_insert(__position); 572 573 // We used to perform the splice_alloc check: not anymore, redundant 574 // after implementing the relevant bits of N1599. 575 576 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(), 577 _M_message(__gnu_debug::__msg_splice_bad) 578 ._M_iterator(__i, "__i")); 579 _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(std::__addressof(__x)), 580 _M_message(__gnu_debug::__msg_splice_other) 581 ._M_iterator(__i, "__i")._M_sequence(__x, "__x")); 582 583 // _GLIBCXX_RESOLVE_LIB_DEFECTS 584 // 250. splicing invalidates iterators 585 this->_M_transfer_from_if(__x, _Equal(__i.base())); 586 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()), 587 __i.base()); 588 } 589 590#if __cplusplus >= 201103L 591 void 592 splice(const_iterator __position, list& __x, const_iterator __i) noexcept 593 { splice(__position, std::move(__x), __i); } 594#endif 595 596 void 597#if __cplusplus >= 201103L 598 splice(const_iterator __position, list&& __x, const_iterator __first, 599 const_iterator __last) noexcept 600#else 601 splice(iterator __position, list& __x, iterator __first, 602 iterator __last) 603#endif 604 { 605 __glibcxx_check_insert(__position); 606 __glibcxx_check_valid_range(__first, __last); 607 _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(std::__addressof(__x)), 608 _M_message(__gnu_debug::__msg_splice_other) 609 ._M_sequence(__x, "x") 610 ._M_iterator(__first, "first")); 611 612 // We used to perform the splice_alloc check: not anymore, redundant 613 // after implementing the relevant bits of N1599. 614 615 for (_Base_const_iterator __tmp = __first.base(); 616 __tmp != __last.base(); ++__tmp) 617 { 618 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 619 _M_message(__gnu_debug::__msg_valid_range) 620 ._M_iterator(__first, "first") 621 ._M_iterator(__last, "last")); 622 _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this 623 || __tmp != __position.base(), 624 _M_message(__gnu_debug::__msg_splice_overlap) 625 ._M_iterator(__tmp, "position") 626 ._M_iterator(__first, "first") 627 ._M_iterator(__last, "last")); 628 // _GLIBCXX_RESOLVE_LIB_DEFECTS 629 // 250. splicing invalidates iterators 630 this->_M_transfer_from_if(__x, _Equal(__tmp)); 631 } 632 633 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()), 634 __first.base(), __last.base()); 635 } 636 637#if __cplusplus >= 201103L 638 void 639 splice(const_iterator __position, list& __x, 640 const_iterator __first, const_iterator __last) noexcept 641 { splice(__position, std::move(__x), __first, __last); } 642#endif 643 644 void 645 remove(const _Tp& __value) 646 { 647 for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); ) 648 { 649 if (*__x == __value) 650 __x = _M_erase(__x); 651 else 652 ++__x; 653 } 654 } 655 656 template<class _Predicate> 657 void 658 remove_if(_Predicate __pred) 659 { 660 for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); ) 661 { 662 if (__pred(*__x)) 663 __x = _M_erase(__x); 664 else 665 ++__x; 666 } 667 } 668 669 void 670 unique() 671 { 672 _Base_iterator __first = _Base::begin(); 673 _Base_iterator __last = _Base::end(); 674 if (__first == __last) 675 return; 676 _Base_iterator __next = __first; ++__next; 677 while (__next != __last) 678 { 679 if (*__first == *__next) 680 __next = _M_erase(__next); 681 else 682 __first = __next++; 683 } 684 } 685 686 template<class _BinaryPredicate> 687 void 688 unique(_BinaryPredicate __binary_pred) 689 { 690 _Base_iterator __first = _Base::begin(); 691 _Base_iterator __last = _Base::end(); 692 if (__first == __last) 693 return; 694 _Base_iterator __next = __first; ++__next; 695 while (__next != __last) 696 { 697 if (__binary_pred(*__first, *__next)) 698 __next = _M_erase(__next); 699 else 700 __first = __next++; 701 } 702 } 703 704 void 705#if __cplusplus >= 201103L 706 merge(list&& __x) 707#else 708 merge(list& __x) 709#endif 710 { 711 // _GLIBCXX_RESOLVE_LIB_DEFECTS 712 // 300. list::merge() specification incomplete 713 if (this != std::__addressof(__x)) 714 { 715 __glibcxx_check_sorted(_Base::begin(), _Base::end()); 716 __glibcxx_check_sorted(__x.begin().base(), __x.end().base()); 717 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end())); 718 _Base::merge(_GLIBCXX_MOVE(__x._M_base())); 719 } 720 } 721 722#if __cplusplus >= 201103L 723 void 724 merge(list& __x) 725 { merge(std::move(__x)); } 726#endif 727 728 template<class _Compare> 729 void 730#if __cplusplus >= 201103L 731 merge(list&& __x, _Compare __comp) 732#else 733 merge(list& __x, _Compare __comp) 734#endif 735 { 736 // _GLIBCXX_RESOLVE_LIB_DEFECTS 737 // 300. list::merge() specification incomplete 738 if (this != std::__addressof(__x)) 739 { 740 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), 741 __comp); 742 __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(), 743 __comp); 744 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end())); 745 _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp); 746 } 747 } 748 749#if __cplusplus >= 201103L 750 template<typename _Compare> 751 void 752 merge(list& __x, _Compare __comp) 753 { merge(std::move(__x), __comp); } 754#endif 755 756 void 757 sort() { _Base::sort(); } 758 759 template<typename _StrictWeakOrdering> 760 void 761 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); } 762 763 using _Base::reverse; 764 765 _Base& 766 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 767 768 const _Base& 769 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 770 }; 771 772#if __cpp_deduction_guides >= 201606 773 template<typename _InputIterator, typename _ValT 774 = typename iterator_traits<_InputIterator>::value_type, 775 typename _Allocator = allocator<_ValT>, 776 typename = _RequireInputIter<_InputIterator>, 777 typename = _RequireAllocator<_Allocator>> 778 list(_InputIterator, _InputIterator, _Allocator = _Allocator()) 779 -> list<_ValT, _Allocator>; 780#endif 781 782 template<typename _Tp, typename _Alloc> 783 inline bool 784 operator==(const list<_Tp, _Alloc>& __lhs, 785 const list<_Tp, _Alloc>& __rhs) 786 { return __lhs._M_base() == __rhs._M_base(); } 787 788 template<typename _Tp, typename _Alloc> 789 inline bool 790 operator!=(const list<_Tp, _Alloc>& __lhs, 791 const list<_Tp, _Alloc>& __rhs) 792 { return __lhs._M_base() != __rhs._M_base(); } 793 794 template<typename _Tp, typename _Alloc> 795 inline bool 796 operator<(const list<_Tp, _Alloc>& __lhs, 797 const list<_Tp, _Alloc>& __rhs) 798 { return __lhs._M_base() < __rhs._M_base(); } 799 800 template<typename _Tp, typename _Alloc> 801 inline bool 802 operator<=(const list<_Tp, _Alloc>& __lhs, 803 const list<_Tp, _Alloc>& __rhs) 804 { return __lhs._M_base() <= __rhs._M_base(); } 805 806 template<typename _Tp, typename _Alloc> 807 inline bool 808 operator>=(const list<_Tp, _Alloc>& __lhs, 809 const list<_Tp, _Alloc>& __rhs) 810 { return __lhs._M_base() >= __rhs._M_base(); } 811 812 template<typename _Tp, typename _Alloc> 813 inline bool 814 operator>(const list<_Tp, _Alloc>& __lhs, 815 const list<_Tp, _Alloc>& __rhs) 816 { return __lhs._M_base() > __rhs._M_base(); } 817 818 template<typename _Tp, typename _Alloc> 819 inline void 820 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs) 821 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs))) 822 { __lhs.swap(__rhs); } 823 824} // namespace __debug 825} // namespace std 826 827namespace __gnu_debug 828{ 829#ifndef _GLIBCXX_USE_CXX11_ABI 830 // If not using C++11 list::size() is not in O(1) so we do not use it. 831 template<typename _Tp, typename _Alloc> 832 struct _Sequence_traits<std::__debug::list<_Tp, _Alloc> > 833 { 834 typedef typename std::__debug::list<_Tp, _Alloc>::iterator _It; 835 836 static typename _Distance_traits<_It>::__type 837 _S_size(const std::__debug::list<_Tp, _Alloc>& __seq) 838 { 839 return __seq.empty() 840 ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_equality); 841 } 842 }; 843#endif 844 845#ifndef _GLIBCXX_DEBUG_PEDANTIC 846 template<class _Tp, class _Alloc> 847 struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> > 848 { enum { __value = 1 }; }; 849#endif 850} 851 852#endif 853