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