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