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