1 // Singly-linked list implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2024 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 /* 26 * Copyright (c) 1997 27 * Silicon Graphics Computer Systems, Inc. 28 * 29 * Permission to use, copy, modify, distribute and sell this software 30 * and its documentation for any purpose is hereby granted without fee, 31 * provided that the above copyright notice appear in all copies and 32 * that both that copyright notice and this permission notice appear 33 * in supporting documentation. Silicon Graphics makes no 34 * representations about the suitability of this software for any 35 * purpose. It is provided "as is" without express or implied warranty. 36 * 37 */ 38 39 /** @file ext/slist 40 * This file is a GNU extension to the Standard C++ Library (possibly 41 * containing extensions from the HP/SGI STL subset). 42 */ 43 44 #ifndef _SLIST 45 #define _SLIST 1 46 47 #include <bits/requires_hosted.h> // std::allocator 48 49 #include <algorithm> 50 #include <bits/allocator.h> 51 #include <bits/stl_construct.h> 52 #include <bits/stl_uninitialized.h> 53 #include <bits/concept_check.h> 54 #include <ext/alloc_traits.h> 55 56 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 57 { 58 _GLIBCXX_BEGIN_NAMESPACE_VERSION 59 60 struct _Slist_node_base 61 { 62 _Slist_node_base* _M_next; 63 }; 64 65 inline _Slist_node_base* 66 __slist_make_link(_Slist_node_base* __prev_node, 67 _Slist_node_base* __new_node) 68 { 69 __new_node->_M_next = __prev_node->_M_next; 70 __prev_node->_M_next = __new_node; 71 return __new_node; 72 } 73 74 inline _Slist_node_base* 75 __slist_previous(_Slist_node_base* __head, 76 const _Slist_node_base* __node) 77 { 78 while (__head && __head->_M_next != __node) 79 __head = __head->_M_next; 80 return __head; 81 } 82 83 inline const _Slist_node_base* 84 __slist_previous(const _Slist_node_base* __head, 85 const _Slist_node_base* __node) 86 { 87 while (__head && __head->_M_next != __node) 88 __head = __head->_M_next; 89 return __head; 90 } 91 92 inline void 93 __slist_splice_after(_Slist_node_base* __pos, 94 _Slist_node_base* __before_first, 95 _Slist_node_base* __before_last) 96 { 97 if (__pos != __before_first && __pos != __before_last) 98 { 99 _Slist_node_base* __first = __before_first->_M_next; 100 _Slist_node_base* __after = __pos->_M_next; 101 __before_first->_M_next = __before_last->_M_next; 102 __pos->_M_next = __first; 103 __before_last->_M_next = __after; 104 } 105 } 106 107 inline void 108 __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head) 109 { 110 _Slist_node_base* __before_last = __slist_previous(__head, 0); 111 if (__before_last != __head) 112 { 113 _Slist_node_base* __after = __pos->_M_next; 114 __pos->_M_next = __head->_M_next; 115 __head->_M_next = 0; 116 __before_last->_M_next = __after; 117 } 118 } 119 120 inline _Slist_node_base* 121 __slist_reverse(_Slist_node_base* __node) 122 { 123 _Slist_node_base* __result = __node; 124 __node = __node->_M_next; 125 __result->_M_next = 0; 126 while(__node) 127 { 128 _Slist_node_base* __next = __node->_M_next; 129 __node->_M_next = __result; 130 __result = __node; 131 __node = __next; 132 } 133 return __result; 134 } 135 136 inline std::size_t 137 __slist_size(_Slist_node_base* __node) 138 { 139 std::size_t __result = 0; 140 for (; __node != 0; __node = __node->_M_next) 141 ++__result; 142 return __result; 143 } 144 145 template <class _Tp> 146 struct _Slist_node : public _Slist_node_base 147 { 148 _Tp _M_data; 149 }; 150 151 struct _Slist_iterator_base 152 { 153 typedef std::size_t size_type; 154 typedef std::ptrdiff_t difference_type; 155 typedef std::forward_iterator_tag iterator_category; 156 157 _Slist_node_base* _M_node; 158 159 _Slist_iterator_base(_Slist_node_base* __x) 160 : _M_node(__x) {} 161 162 void 163 _M_incr() 164 { _M_node = _M_node->_M_next; } 165 166 bool 167 operator==(const _Slist_iterator_base& __x) const 168 { return _M_node == __x._M_node; } 169 170 bool 171 operator!=(const _Slist_iterator_base& __x) const 172 { return _M_node != __x._M_node; } 173 }; 174 175 template <class _Tp, class _Ref, class _Ptr> 176 struct _Slist_iterator : public _Slist_iterator_base 177 { 178 typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; 179 typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 180 typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self; 181 182 typedef _Tp value_type; 183 typedef _Ptr pointer; 184 typedef _Ref reference; 185 typedef _Slist_node<_Tp> _Node; 186 187 explicit 188 _Slist_iterator(_Node* __x) 189 : _Slist_iterator_base(__x) {} 190 191 _Slist_iterator() 192 : _Slist_iterator_base(0) {} 193 194 _Slist_iterator(const iterator& __x) 195 : _Slist_iterator_base(__x._M_node) {} 196 197 reference 198 operator*() const 199 { return ((_Node*) _M_node)->_M_data; } 200 201 pointer 202 operator->() const 203 { return &(operator*()); } 204 205 _Self& 206 operator++() 207 { 208 _M_incr(); 209 return *this; 210 } 211 212 _Self 213 operator++(int) 214 { 215 _Self __tmp = *this; 216 _M_incr(); 217 return __tmp; 218 } 219 }; 220 221 template <class _Tp, class _Alloc> 222 struct _Slist_base 223 : public __alloc_traits<_Alloc>::template rebind<_Slist_node<_Tp> >::other 224 { 225 typedef typename __alloc_traits<_Alloc>::template 226 rebind<_Slist_node<_Tp> >::other _Node_alloc; 227 typedef _Alloc allocator_type; 228 229 allocator_type 230 get_allocator() const 231 { return *static_cast<const _Node_alloc*>(this); } 232 233 _Slist_base(const allocator_type& __a) 234 : _Node_alloc(__a) 235 { this->_M_head._M_next = 0; } 236 237 ~_Slist_base() 238 { _M_erase_after(&this->_M_head, 0); } 239 240 protected: 241 _Slist_node_base _M_head; 242 243 _Slist_node<_Tp>* 244 _M_get_node() 245 { return _Node_alloc::allocate(1); } 246 247 void 248 _M_put_node(_Slist_node<_Tp>* __p) 249 { _Node_alloc::deallocate(__p, 1); } 250 251 protected: 252 _Slist_node_base* _M_erase_after(_Slist_node_base* __pos) 253 { 254 _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next); 255 _Slist_node_base* __next_next = __next->_M_next; 256 __pos->_M_next = __next_next; 257 allocator_type __a = get_allocator(); 258 __alloc_traits<allocator_type>::destroy(__a, &__next->_M_data); 259 _M_put_node(__next); 260 return __next_next; 261 } 262 _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*); 263 }; 264 265 template <class _Tp, class _Alloc> 266 _Slist_node_base* 267 _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, 268 _Slist_node_base* __last_node) 269 { 270 _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next); 271 while (__cur != __last_node) 272 { 273 _Slist_node<_Tp>* __tmp = __cur; 274 __cur = (_Slist_node<_Tp>*) __cur->_M_next; 275 allocator_type __a = get_allocator(); 276 __alloc_traits<allocator_type>::destroy(__a, &__tmp->_M_data); 277 _M_put_node(__tmp); 278 } 279 __before_first->_M_next = __last_node; 280 return __last_node; 281 } 282 283 /** 284 * This is an SGI extension. 285 * @ingroup SGIextensions 286 * @doctodo 287 */ 288 template <class _Tp, class _Alloc = std::allocator<_Tp> > 289 class slist : private _Slist_base<_Tp,_Alloc> 290 { 291 // concept requirements 292 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 293 294 private: 295 typedef _Slist_base<_Tp,_Alloc> _Base; 296 297 public: 298 typedef _Tp value_type; 299 typedef value_type* pointer; 300 typedef const value_type* const_pointer; 301 typedef value_type& reference; 302 typedef const value_type& const_reference; 303 typedef std::size_t size_type; 304 typedef std::ptrdiff_t difference_type; 305 306 typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; 307 typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 308 309 typedef typename _Base::allocator_type allocator_type; 310 311 allocator_type 312 get_allocator() const 313 { return _Base::get_allocator(); } 314 315 private: 316 typedef _Slist_node<_Tp> _Node; 317 typedef _Slist_node_base _Node_base; 318 typedef _Slist_iterator_base _Iterator_base; 319 320 _Node* 321 _M_create_node(const value_type& __x) 322 { 323 _Node* __node = this->_M_get_node(); 324 __try 325 { 326 allocator_type __a = get_allocator(); 327 __alloc_traits<allocator_type>::construct(__a, &__node->_M_data, 328 __x); 329 __node->_M_next = 0; 330 } 331 __catch(...) 332 { 333 this->_M_put_node(__node); 334 __throw_exception_again; 335 } 336 return __node; 337 } 338 339 _Node* 340 _M_create_node() 341 { 342 _Node* __node = this->_M_get_node(); 343 __try 344 { 345 allocator_type __a = get_allocator(); 346 __alloc_traits<allocator_type>::construct(__a, &__node->_M_data, 347 value_type()); 348 __node->_M_next = 0; 349 } 350 __catch(...) 351 { 352 this->_M_put_node(__node); 353 __throw_exception_again; 354 } 355 return __node; 356 } 357 358 public: 359 explicit 360 slist(const allocator_type& __a = allocator_type()) 361 : _Base(__a) {} 362 363 slist(size_type __n, const value_type& __x, 364 const allocator_type& __a = allocator_type()) 365 : _Base(__a) 366 { _M_insert_after_fill(&this->_M_head, __n, __x); } 367 368 explicit 369 slist(size_type __n) 370 : _Base(allocator_type()) 371 { _M_insert_after_fill(&this->_M_head, __n, value_type()); } 372 373 // We don't need any dispatching tricks here, because 374 // _M_insert_after_range already does them. 375 template <class _InputIterator> 376 slist(_InputIterator __first, _InputIterator __last, 377 const allocator_type& __a = allocator_type()) 378 : _Base(__a) 379 { _M_insert_after_range(&this->_M_head, __first, __last); } 380 381 slist(const slist& __x) 382 : _Base(__x.get_allocator()) 383 { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); } 384 385 slist& 386 operator= (const slist& __x); 387 388 ~slist() {} 389 390 public: 391 // assign(), a generalized assignment member function. Two 392 // versions: one that takes a count, and one that takes a range. 393 // The range version is a member template, so we dispatch on whether 394 // or not the type is an integer. 395 396 void 397 assign(size_type __n, const _Tp& __val) 398 { _M_fill_assign(__n, __val); } 399 400 void 401 _M_fill_assign(size_type __n, const _Tp& __val); 402 403 template <class _InputIterator> 404 void 405 assign(_InputIterator __first, _InputIterator __last) 406 { 407 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 408 _M_assign_dispatch(__first, __last, _Integral()); 409 } 410 411 template <class _Integer> 412 void 413 _M_assign_dispatch(_Integer __n, _Integer __val, std::__true_type) 414 { _M_fill_assign((size_type) __n, (_Tp) __val); } 415 416 template <class _InputIterator> 417 void 418 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 419 std::__false_type); 420 421 public: 422 423 iterator 424 begin() 425 { return iterator((_Node*)this->_M_head._M_next); } 426 427 const_iterator 428 begin() const 429 { return const_iterator((_Node*)this->_M_head._M_next);} 430 431 iterator 432 end() 433 { return iterator(0); } 434 435 const_iterator 436 end() const 437 { return const_iterator(0); } 438 439 // Experimental new feature: before_begin() returns a 440 // non-dereferenceable iterator that, when incremented, yields 441 // begin(). This iterator may be used as the argument to 442 // insert_after, erase_after, etc. Note that even for an empty 443 // slist, before_begin() is not the same iterator as end(). It 444 // is always necessary to increment before_begin() at least once to 445 // obtain end(). 446 iterator 447 before_begin() 448 { return iterator((_Node*) &this->_M_head); } 449 450 const_iterator 451 before_begin() const 452 { return const_iterator((_Node*) &this->_M_head); } 453 454 size_type 455 size() const 456 { return __slist_size(this->_M_head._M_next); } 457 458 size_type 459 max_size() const 460 { return size_type(-1); } 461 462 _GLIBCXX_NODISCARD bool 463 empty() const 464 { return this->_M_head._M_next == 0; } 465 466 void 467 swap(slist& __x) 468 { std::swap(this->_M_head._M_next, __x._M_head._M_next); } 469 470 public: 471 472 reference 473 front() 474 { return ((_Node*) this->_M_head._M_next)->_M_data; } 475 476 const_reference 477 front() const 478 { return ((_Node*) this->_M_head._M_next)->_M_data; } 479 480 void 481 push_front(const value_type& __x) 482 { __slist_make_link(&this->_M_head, _M_create_node(__x)); } 483 484 void 485 push_front() 486 { __slist_make_link(&this->_M_head, _M_create_node()); } 487 488 void 489 pop_front() 490 { 491 _Node* __node = (_Node*) this->_M_head._M_next; 492 this->_M_head._M_next = __node->_M_next; 493 allocator_type __a = get_allocator(); 494 __alloc_traits<allocator_type>::destroy(__a, &__node->_M_data); 495 this->_M_put_node(__node); 496 } 497 498 iterator 499 previous(const_iterator __pos) 500 { return iterator((_Node*) __slist_previous(&this->_M_head, 501 __pos._M_node)); } 502 503 const_iterator 504 previous(const_iterator __pos) const 505 { return const_iterator((_Node*) __slist_previous(&this->_M_head, 506 __pos._M_node)); } 507 508 private: 509 _Node* 510 _M_insert_after(_Node_base* __pos, const value_type& __x) 511 { return (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); } 512 513 _Node* 514 _M_insert_after(_Node_base* __pos) 515 { return (_Node*) (__slist_make_link(__pos, _M_create_node())); } 516 517 void 518 _M_insert_after_fill(_Node_base* __pos, 519 size_type __n, const value_type& __x) 520 { 521 for (size_type __i = 0; __i < __n; ++__i) 522 __pos = __slist_make_link(__pos, _M_create_node(__x)); 523 } 524 525 // Check whether it's an integral type. If so, it's not an iterator. 526 template <class _InIterator> 527 void 528 _M_insert_after_range(_Node_base* __pos, 529 _InIterator __first, _InIterator __last) 530 { 531 typedef typename std::__is_integer<_InIterator>::__type _Integral; 532 _M_insert_after_range(__pos, __first, __last, _Integral()); 533 } 534 535 template <class _Integer> 536 void 537 _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x, 538 std::__true_type) 539 { _M_insert_after_fill(__pos, __n, __x); } 540 541 template <class _InIterator> 542 void 543 _M_insert_after_range(_Node_base* __pos, 544 _InIterator __first, _InIterator __last, 545 std::__false_type) 546 { 547 while (__first != __last) 548 { 549 __pos = __slist_make_link(__pos, _M_create_node(*__first)); 550 ++__first; 551 } 552 } 553 554 public: 555 iterator 556 insert_after(iterator __pos, const value_type& __x) 557 { return iterator(_M_insert_after(__pos._M_node, __x)); } 558 559 iterator 560 insert_after(iterator __pos) 561 { return insert_after(__pos, value_type()); } 562 563 void 564 insert_after(iterator __pos, size_type __n, const value_type& __x) 565 { _M_insert_after_fill(__pos._M_node, __n, __x); } 566 567 // We don't need any dispatching tricks here, because 568 // _M_insert_after_range already does them. 569 template <class _InIterator> 570 void 571 insert_after(iterator __pos, _InIterator __first, _InIterator __last) 572 { _M_insert_after_range(__pos._M_node, __first, __last); } 573 574 iterator 575 insert(iterator __pos, const value_type& __x) 576 { return iterator(_M_insert_after(__slist_previous(&this->_M_head, 577 __pos._M_node), 578 __x)); } 579 580 iterator 581 insert(iterator __pos) 582 { return iterator(_M_insert_after(__slist_previous(&this->_M_head, 583 __pos._M_node), 584 value_type())); } 585 586 void 587 insert(iterator __pos, size_type __n, const value_type& __x) 588 { _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node), 589 __n, __x); } 590 591 // We don't need any dispatching tricks here, because 592 // _M_insert_after_range already does them. 593 template <class _InIterator> 594 void 595 insert(iterator __pos, _InIterator __first, _InIterator __last) 596 { _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), 597 __first, __last); } 598 599 public: 600 iterator 601 erase_after(iterator __pos) 602 { return iterator((_Node*) this->_M_erase_after(__pos._M_node)); } 603 604 iterator 605 erase_after(iterator __before_first, iterator __last) 606 { 607 return iterator((_Node*) this->_M_erase_after(__before_first._M_node, 608 __last._M_node)); 609 } 610 611 iterator 612 erase(iterator __pos) 613 { 614 return iterator((_Node*) this->_M_erase_after 615 (__slist_previous(&this->_M_head, __pos._M_node))); 616 } 617 618 iterator 619 erase(iterator __first, iterator __last) 620 { 621 return iterator((_Node*) this->_M_erase_after 622 (__slist_previous(&this->_M_head, __first._M_node), 623 __last._M_node)); 624 } 625 626 void 627 resize(size_type new_size, const _Tp& __x); 628 629 void 630 resize(size_type new_size) 631 { resize(new_size, _Tp()); } 632 633 void 634 clear() 635 { this->_M_erase_after(&this->_M_head, 0); } 636 637 public: 638 // Moves the range [__before_first + 1, __before_last + 1) to *this, 639 // inserting it immediately after __pos. This is constant time. 640 void 641 splice_after(iterator __pos, 642 iterator __before_first, iterator __before_last) 643 { 644 if (__before_first != __before_last) 645 __slist_splice_after(__pos._M_node, __before_first._M_node, 646 __before_last._M_node); 647 } 648 649 // Moves the element that follows __prev to *this, inserting it 650 // immediately after __pos. This is constant time. 651 void 652 splice_after(iterator __pos, iterator __prev) 653 { __slist_splice_after(__pos._M_node, 654 __prev._M_node, __prev._M_node->_M_next); } 655 656 // Removes all of the elements from the list __x to *this, inserting 657 // them immediately after __pos. __x must not be *this. Complexity: 658 // linear in __x.size(). 659 void 660 splice_after(iterator __pos, slist& __x) 661 { __slist_splice_after(__pos._M_node, &__x._M_head); } 662 663 // Linear in distance(begin(), __pos), and linear in __x.size(). 664 void 665 splice(iterator __pos, slist& __x) 666 { 667 if (__x._M_head._M_next) 668 __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), 669 &__x._M_head, 670 __slist_previous(&__x._M_head, 0)); } 671 672 // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i). 673 void 674 splice(iterator __pos, slist& __x, iterator __i) 675 { __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), 676 __slist_previous(&__x._M_head, __i._M_node), 677 __i._M_node); } 678 679 // Linear in distance(begin(), __pos), in distance(__x.begin(), __first), 680 // and in distance(__first, __last). 681 void 682 splice(iterator __pos, slist& __x, iterator __first, iterator __last) 683 { 684 if (__first != __last) 685 __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), 686 __slist_previous(&__x._M_head, __first._M_node), 687 __slist_previous(__first._M_node, 688 __last._M_node)); 689 } 690 691 public: 692 void 693 reverse() 694 { 695 if (this->_M_head._M_next) 696 this->_M_head._M_next = __slist_reverse(this->_M_head._M_next); 697 } 698 699 void 700 remove(const _Tp& __val); 701 702 void 703 unique(); 704 705 void 706 merge(slist& __x); 707 708 void 709 sort(); 710 711 template <class _Predicate> 712 void 713 remove_if(_Predicate __pred); 714 715 template <class _BinaryPredicate> 716 void 717 unique(_BinaryPredicate __pred); 718 719 template <class _StrictWeakOrdering> 720 void 721 merge(slist&, _StrictWeakOrdering); 722 723 template <class _StrictWeakOrdering> 724 void 725 sort(_StrictWeakOrdering __comp); 726 }; 727 728 template <class _Tp, class _Alloc> 729 slist<_Tp, _Alloc>& 730 slist<_Tp, _Alloc>::operator=(const slist<_Tp, _Alloc>& __x) 731 { 732 if (&__x != this) 733 { 734 _Node_base* __p1 = &this->_M_head; 735 _Node* __n1 = (_Node*) this->_M_head._M_next; 736 const _Node* __n2 = (const _Node*) __x._M_head._M_next; 737 while (__n1 && __n2) 738 { 739 __n1->_M_data = __n2->_M_data; 740 __p1 = __n1; 741 __n1 = (_Node*) __n1->_M_next; 742 __n2 = (const _Node*) __n2->_M_next; 743 } 744 if (__n2 == 0) 745 this->_M_erase_after(__p1, 0); 746 else 747 _M_insert_after_range(__p1, const_iterator((_Node*)__n2), 748 const_iterator(0)); 749 } 750 return *this; 751 } 752 753 template <class _Tp, class _Alloc> 754 void 755 slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) 756 { 757 _Node_base* __prev = &this->_M_head; 758 _Node* __node = (_Node*) this->_M_head._M_next; 759 for (; __node != 0 && __n > 0; --__n) 760 { 761 __node->_M_data = __val; 762 __prev = __node; 763 __node = (_Node*) __node->_M_next; 764 } 765 if (__n > 0) 766 _M_insert_after_fill(__prev, __n, __val); 767 else 768 this->_M_erase_after(__prev, 0); 769 } 770 771 template <class _Tp, class _Alloc> 772 template <class _InputIterator> 773 void 774 slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIterator __first, 775 _InputIterator __last, 776 std::__false_type) 777 { 778 _Node_base* __prev = &this->_M_head; 779 _Node* __node = (_Node*) this->_M_head._M_next; 780 while (__node != 0 && __first != __last) 781 { 782 __node->_M_data = *__first; 783 __prev = __node; 784 __node = (_Node*) __node->_M_next; 785 ++__first; 786 } 787 if (__first != __last) 788 _M_insert_after_range(__prev, __first, __last); 789 else 790 this->_M_erase_after(__prev, 0); 791 } 792 793 template <class _Tp, class _Alloc> 794 inline bool 795 operator==(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 796 { 797 typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator; 798 const_iterator __end1 = _SL1.end(); 799 const_iterator __end2 = _SL2.end(); 800 801 const_iterator __i1 = _SL1.begin(); 802 const_iterator __i2 = _SL2.begin(); 803 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) 804 { 805 ++__i1; 806 ++__i2; 807 } 808 return __i1 == __end1 && __i2 == __end2; 809 } 810 811 812 template <class _Tp, class _Alloc> 813 inline bool 814 operator<(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 815 { return std::lexicographical_compare(_SL1.begin(), _SL1.end(), 816 _SL2.begin(), _SL2.end()); } 817 818 template <class _Tp, class _Alloc> 819 inline bool 820 operator!=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 821 { return !(_SL1 == _SL2); } 822 823 template <class _Tp, class _Alloc> 824 inline bool 825 operator>(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 826 { return _SL2 < _SL1; } 827 828 template <class _Tp, class _Alloc> 829 inline bool 830 operator<=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 831 { return !(_SL2 < _SL1); } 832 833 template <class _Tp, class _Alloc> 834 inline bool 835 operator>=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 836 { return !(_SL1 < _SL2); } 837 838 template <class _Tp, class _Alloc> 839 inline void 840 swap(slist<_Tp, _Alloc>& __x, slist<_Tp, _Alloc>& __y) 841 { __x.swap(__y); } 842 843 template <class _Tp, class _Alloc> 844 void 845 slist<_Tp, _Alloc>::resize(size_type __len, const _Tp& __x) 846 { 847 _Node_base* __cur = &this->_M_head; 848 while (__cur->_M_next != 0 && __len > 0) 849 { 850 --__len; 851 __cur = __cur->_M_next; 852 } 853 if (__cur->_M_next) 854 this->_M_erase_after(__cur, 0); 855 else 856 _M_insert_after_fill(__cur, __len, __x); 857 } 858 859 template <class _Tp, class _Alloc> 860 void 861 slist<_Tp, _Alloc>::remove(const _Tp& __val) 862 { 863 _Node_base* __cur = &this->_M_head; 864 while (__cur && __cur->_M_next) 865 { 866 if (((_Node*) __cur->_M_next)->_M_data == __val) 867 this->_M_erase_after(__cur); 868 else 869 __cur = __cur->_M_next; 870 } 871 } 872 873 template <class _Tp, class _Alloc> 874 void 875 slist<_Tp, _Alloc>::unique() 876 { 877 _Node_base* __cur = this->_M_head._M_next; 878 if (__cur) 879 { 880 while (__cur->_M_next) 881 { 882 if (((_Node*)__cur)->_M_data 883 == ((_Node*)(__cur->_M_next))->_M_data) 884 this->_M_erase_after(__cur); 885 else 886 __cur = __cur->_M_next; 887 } 888 } 889 } 890 891 template <class _Tp, class _Alloc> 892 void 893 slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x) 894 { 895 _Node_base* __n1 = &this->_M_head; 896 while (__n1->_M_next && __x._M_head._M_next) 897 { 898 if (((_Node*) __x._M_head._M_next)->_M_data 899 < ((_Node*) __n1->_M_next)->_M_data) 900 __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); 901 __n1 = __n1->_M_next; 902 } 903 if (__x._M_head._M_next) 904 { 905 __n1->_M_next = __x._M_head._M_next; 906 __x._M_head._M_next = 0; 907 } 908 } 909 910 template <class _Tp, class _Alloc> 911 void 912 slist<_Tp, _Alloc>::sort() 913 { 914 if (this->_M_head._M_next && this->_M_head._M_next->_M_next) 915 { 916 slist __carry; 917 slist __counter[64]; 918 int __fill = 0; 919 while (!empty()) 920 { 921 __slist_splice_after(&__carry._M_head, 922 &this->_M_head, this->_M_head._M_next); 923 int __i = 0; 924 while (__i < __fill && !__counter[__i].empty()) 925 { 926 __counter[__i].merge(__carry); 927 __carry.swap(__counter[__i]); 928 ++__i; 929 } 930 __carry.swap(__counter[__i]); 931 if (__i == __fill) 932 ++__fill; 933 } 934 935 for (int __i = 1; __i < __fill; ++__i) 936 __counter[__i].merge(__counter[__i-1]); 937 this->swap(__counter[__fill-1]); 938 } 939 } 940 941 template <class _Tp, class _Alloc> 942 template <class _Predicate> 943 void slist<_Tp, _Alloc>::remove_if(_Predicate __pred) 944 { 945 _Node_base* __cur = &this->_M_head; 946 while (__cur->_M_next) 947 { 948 if (__pred(((_Node*) __cur->_M_next)->_M_data)) 949 this->_M_erase_after(__cur); 950 else 951 __cur = __cur->_M_next; 952 } 953 } 954 955 template <class _Tp, class _Alloc> 956 template <class _BinaryPredicate> 957 void 958 slist<_Tp, _Alloc>::unique(_BinaryPredicate __pred) 959 { 960 _Node* __cur = (_Node*) this->_M_head._M_next; 961 if (__cur) 962 { 963 while (__cur->_M_next) 964 { 965 if (__pred(((_Node*)__cur)->_M_data, 966 ((_Node*)(__cur->_M_next))->_M_data)) 967 this->_M_erase_after(__cur); 968 else 969 __cur = (_Node*) __cur->_M_next; 970 } 971 } 972 } 973 974 template <class _Tp, class _Alloc> 975 template <class _StrictWeakOrdering> 976 void 977 slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x, 978 _StrictWeakOrdering __comp) 979 { 980 _Node_base* __n1 = &this->_M_head; 981 while (__n1->_M_next && __x._M_head._M_next) 982 { 983 if (__comp(((_Node*) __x._M_head._M_next)->_M_data, 984 ((_Node*) __n1->_M_next)->_M_data)) 985 __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); 986 __n1 = __n1->_M_next; 987 } 988 if (__x._M_head._M_next) 989 { 990 __n1->_M_next = __x._M_head._M_next; 991 __x._M_head._M_next = 0; 992 } 993 } 994 995 template <class _Tp, class _Alloc> 996 template <class _StrictWeakOrdering> 997 void 998 slist<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp) 999 { 1000 if (this->_M_head._M_next && this->_M_head._M_next->_M_next) 1001 { 1002 slist __carry; 1003 slist __counter[64]; 1004 int __fill = 0; 1005 while (!empty()) 1006 { 1007 __slist_splice_after(&__carry._M_head, 1008 &this->_M_head, this->_M_head._M_next); 1009 int __i = 0; 1010 while (__i < __fill && !__counter[__i].empty()) 1011 { 1012 __counter[__i].merge(__carry, __comp); 1013 __carry.swap(__counter[__i]); 1014 ++__i; 1015 } 1016 __carry.swap(__counter[__i]); 1017 if (__i == __fill) 1018 ++__fill; 1019 } 1020 1021 for (int __i = 1; __i < __fill; ++__i) 1022 __counter[__i].merge(__counter[__i-1], __comp); 1023 this->swap(__counter[__fill-1]); 1024 } 1025 } 1026 1027 _GLIBCXX_END_NAMESPACE_VERSION 1028 } // namespace 1029 1030 namespace std _GLIBCXX_VISIBILITY(default) 1031 { 1032 _GLIBCXX_BEGIN_NAMESPACE_VERSION 1033 1034 // Specialization of insert_iterator so that insertions will be constant 1035 // time rather than linear time. 1036 template <class _Tp, class _Alloc> 1037 class insert_iterator<__gnu_cxx::slist<_Tp, _Alloc> > 1038 { 1039 protected: 1040 typedef __gnu_cxx::slist<_Tp, _Alloc> _Container; 1041 _Container* container; 1042 typename _Container::iterator iter; 1043 1044 public: 1045 typedef _Container container_type; 1046 typedef output_iterator_tag iterator_category; 1047 typedef void value_type; 1048 typedef void difference_type; 1049 typedef void pointer; 1050 typedef void reference; 1051 1052 insert_iterator(_Container& __x, typename _Container::iterator __i) 1053 : container(&__x) 1054 { 1055 if (__i == __x.begin()) 1056 iter = __x.before_begin(); 1057 else 1058 iter = __x.previous(__i); 1059 } 1060 1061 insert_iterator<_Container>& 1062 operator=(const typename _Container::value_type& __value) 1063 { 1064 iter = container->insert_after(iter, __value); 1065 return *this; 1066 } 1067 1068 insert_iterator<_Container>& 1069 operator*() 1070 { return *this; } 1071 1072 insert_iterator<_Container>& 1073 operator++() 1074 { return *this; } 1075 1076 insert_iterator<_Container>& 1077 operator++(int) 1078 { return *this; } 1079 }; 1080 1081 _GLIBCXX_END_NAMESPACE_VERSION 1082 } // namespace 1083 1084 #endif 1085
Indexes created Sat Feb 28 05:31:39 UTC 2026