1 // Singly-linked list implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2013 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 53 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 54 { 55 _GLIBCXX_BEGIN_NAMESPACE_VERSION 56 57 using std::size_t; 58 using std::ptrdiff_t; 59 using std::_Construct; 60 using std::_Destroy; 61 using std::allocator; 62 using std::__true_type; 63 using std::__false_type; 64 65 struct _Slist_node_base 66 { 67 _Slist_node_base* _M_next; 68 }; 69 70 inline _Slist_node_base* 71 __slist_make_link(_Slist_node_base* __prev_node, 72 _Slist_node_base* __new_node) 73 { 74 __new_node->_M_next = __prev_node->_M_next; 75 __prev_node->_M_next = __new_node; 76 return __new_node; 77 } 78 79 inline _Slist_node_base* 80 __slist_previous(_Slist_node_base* __head, 81 const _Slist_node_base* __node) 82 { 83 while (__head && __head->_M_next != __node) 84 __head = __head->_M_next; 85 return __head; 86 } 87 88 inline const _Slist_node_base* 89 __slist_previous(const _Slist_node_base* __head, 90 const _Slist_node_base* __node) 91 { 92 while (__head && __head->_M_next != __node) 93 __head = __head->_M_next; 94 return __head; 95 } 96 97 inline void 98 __slist_splice_after(_Slist_node_base* __pos, 99 _Slist_node_base* __before_first, 100 _Slist_node_base* __before_last) 101 { 102 if (__pos != __before_first && __pos != __before_last) 103 { 104 _Slist_node_base* __first = __before_first->_M_next; 105 _Slist_node_base* __after = __pos->_M_next; 106 __before_first->_M_next = __before_last->_M_next; 107 __pos->_M_next = __first; 108 __before_last->_M_next = __after; 109 } 110 } 111 112 inline void 113 __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head) 114 { 115 _Slist_node_base* __before_last = __slist_previous(__head, 0); 116 if (__before_last != __head) 117 { 118 _Slist_node_base* __after = __pos->_M_next; 119 __pos->_M_next = __head->_M_next; 120 __head->_M_next = 0; 121 __before_last->_M_next = __after; 122 } 123 } 124 125 inline _Slist_node_base* 126 __slist_reverse(_Slist_node_base* __node) 127 { 128 _Slist_node_base* __result = __node; 129 __node = __node->_M_next; 130 __result->_M_next = 0; 131 while(__node) 132 { 133 _Slist_node_base* __next = __node->_M_next; 134 __node->_M_next = __result; 135 __result = __node; 136 __node = __next; 137 } 138 return __result; 139 } 140 141 inline size_t 142 __slist_size(_Slist_node_base* __node) 143 { 144 size_t __result = 0; 145 for (; __node != 0; __node = __node->_M_next) 146 ++__result; 147 return __result; 148 } 149 150 template <class _Tp> 151 struct _Slist_node : public _Slist_node_base 152 { 153 _Tp _M_data; 154 }; 155 156 struct _Slist_iterator_base 157 { 158 typedef size_t size_type; 159 typedef ptrdiff_t difference_type; 160 typedef std::forward_iterator_tag iterator_category; 161 162 _Slist_node_base* _M_node; 163 164 _Slist_iterator_base(_Slist_node_base* __x) 165 : _M_node(__x) {} 166 167 void 168 _M_incr() 169 { _M_node = _M_node->_M_next; } 170 171 bool 172 operator==(const _Slist_iterator_base& __x) const 173 { return _M_node == __x._M_node; } 174 175 bool 176 operator!=(const _Slist_iterator_base& __x) const 177 { return _M_node != __x._M_node; } 178 }; 179 180 template <class _Tp, class _Ref, class _Ptr> 181 struct _Slist_iterator : public _Slist_iterator_base 182 { 183 typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; 184 typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 185 typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self; 186 187 typedef _Tp value_type; 188 typedef _Ptr pointer; 189 typedef _Ref reference; 190 typedef _Slist_node<_Tp> _Node; 191 192 explicit 193 _Slist_iterator(_Node* __x) 194 : _Slist_iterator_base(__x) {} 195 196 _Slist_iterator() 197 : _Slist_iterator_base(0) {} 198 199 _Slist_iterator(const iterator& __x) 200 : _Slist_iterator_base(__x._M_node) {} 201 202 reference 203 operator*() const 204 { return ((_Node*) _M_node)->_M_data; } 205 206 pointer 207 operator->() const 208 { return &(operator*()); } 209 210 _Self& 211 operator++() 212 { 213 _M_incr(); 214 return *this; 215 } 216 217 _Self 218 operator++(int) 219 { 220 _Self __tmp = *this; 221 _M_incr(); 222 return __tmp; 223 } 224 }; 225 226 template <class _Tp, class _Alloc> 227 struct _Slist_base 228 : public _Alloc::template rebind<_Slist_node<_Tp> >::other 229 { 230 typedef typename _Alloc::template rebind<_Slist_node<_Tp> >::other 231 _Node_alloc; 232 typedef _Alloc allocator_type; 233 234 allocator_type 235 get_allocator() const 236 { return *static_cast<const _Node_alloc*>(this); } 237 238 _Slist_base(const allocator_type& __a) 239 : _Node_alloc(__a) 240 { this->_M_head._M_next = 0; } 241 242 ~_Slist_base() 243 { _M_erase_after(&this->_M_head, 0); } 244 245 protected: 246 _Slist_node_base _M_head; 247 248 _Slist_node<_Tp>* 249 _M_get_node() 250 { return _Node_alloc::allocate(1); } 251 252 void 253 _M_put_node(_Slist_node<_Tp>* __p) 254 { _Node_alloc::deallocate(__p, 1); } 255 256 protected: 257 _Slist_node_base* _M_erase_after(_Slist_node_base* __pos) 258 { 259 _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next); 260 _Slist_node_base* __next_next = __next->_M_next; 261 __pos->_M_next = __next_next; 262 get_allocator().destroy(&__next->_M_data); 263 _M_put_node(__next); 264 return __next_next; 265 } 266 _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*); 267 }; 268 269 template <class _Tp, class _Alloc> 270 _Slist_node_base* 271 _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, 272 _Slist_node_base* __last_node) 273 { 274 _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next); 275 while (__cur != __last_node) 276 { 277 _Slist_node<_Tp>* __tmp = __cur; 278 __cur = (_Slist_node<_Tp>*) __cur->_M_next; 279 get_allocator().destroy(&__tmp->_M_data); 280 _M_put_node(__tmp); 281 } 282 __before_first->_M_next = __last_node; 283 return __last_node; 284 } 285 286 /** 287 * This is an SGI extension. 288 * @ingroup SGIextensions 289 * @doctodo 290 */ 291 template <class _Tp, class _Alloc = allocator<_Tp> > 292 class slist : private _Slist_base<_Tp,_Alloc> 293 { 294 // concept requirements 295 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 296 297 private: 298 typedef _Slist_base<_Tp,_Alloc> _Base; 299 300 public: 301 typedef _Tp value_type; 302 typedef value_type* pointer; 303 typedef const value_type* const_pointer; 304 typedef value_type& reference; 305 typedef const value_type& const_reference; 306 typedef size_t size_type; 307 typedef ptrdiff_t difference_type; 308 309 typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; 310 typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 311 312 typedef typename _Base::allocator_type allocator_type; 313 314 allocator_type 315 get_allocator() const 316 { return _Base::get_allocator(); } 317 318 private: 319 typedef _Slist_node<_Tp> _Node; 320 typedef _Slist_node_base _Node_base; 321 typedef _Slist_iterator_base _Iterator_base; 322 323 _Node* 324 _M_create_node(const value_type& __x) 325 { 326 _Node* __node = this->_M_get_node(); 327 __try 328 { 329 get_allocator().construct(&__node->_M_data, __x); 330 __node->_M_next = 0; 331 } 332 __catch(...) 333 { 334 this->_M_put_node(__node); 335 __throw_exception_again; 336 } 337 return __node; 338 } 339 340 _Node* 341 _M_create_node() 342 { 343 _Node* __node = this->_M_get_node(); 344 __try 345 { 346 get_allocator().construct(&__node->_M_data, value_type()); 347 __node->_M_next = 0; 348 } 349 __catch(...) 350 { 351 this->_M_put_node(__node); 352 __throw_exception_again; 353 } 354 return __node; 355 } 356 357 public: 358 explicit 359 slist(const allocator_type& __a = allocator_type()) 360 : _Base(__a) {} 361 362 slist(size_type __n, const value_type& __x, 363 const allocator_type& __a = allocator_type()) 364 : _Base(__a) 365 { _M_insert_after_fill(&this->_M_head, __n, __x); } 366 367 explicit 368 slist(size_type __n) 369 : _Base(allocator_type()) 370 { _M_insert_after_fill(&this->_M_head, __n, value_type()); } 371 372 // We don't need any dispatching tricks here, because 373 // _M_insert_after_range already does them. 374 template <class _InputIterator> 375 slist(_InputIterator __first, _InputIterator __last, 376 const allocator_type& __a = allocator_type()) 377 : _Base(__a) 378 { _M_insert_after_range(&this->_M_head, __first, __last); } 379 380 slist(const slist& __x) 381 : _Base(__x.get_allocator()) 382 { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); } 383 384 slist& 385 operator= (const slist& __x); 386 387 ~slist() {} 388 389 public: 390 // assign(), a generalized assignment member function. Two 391 // versions: one that takes a count, and one that takes a range. 392 // The range version is a member template, so we dispatch on whether 393 // or not the type is an integer. 394 395 void 396 assign(size_type __n, const _Tp& __val) 397 { _M_fill_assign(__n, __val); } 398 399 void 400 _M_fill_assign(size_type __n, const _Tp& __val); 401 402 template <class _InputIterator> 403 void 404 assign(_InputIterator __first, _InputIterator __last) 405 { 406 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 407 _M_assign_dispatch(__first, __last, _Integral()); 408 } 409 410 template <class _Integer> 411 void 412 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 413 { _M_fill_assign((size_type) __n, (_Tp) __val); } 414 415 template <class _InputIterator> 416 void 417 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 418 __false_type); 419 420 public: 421 422 iterator 423 begin() 424 { return iterator((_Node*)this->_M_head._M_next); } 425 426 const_iterator 427 begin() const 428 { return const_iterator((_Node*)this->_M_head._M_next);} 429 430 iterator 431 end() 432 { return iterator(0); } 433 434 const_iterator 435 end() const 436 { return const_iterator(0); } 437 438 // Experimental new feature: before_begin() returns a 439 // non-dereferenceable iterator that, when incremented, yields 440 // begin(). This iterator may be used as the argument to 441 // insert_after, erase_after, etc. Note that even for an empty 442 // slist, before_begin() is not the same iterator as end(). It 443 // is always necessary to increment before_begin() at least once to 444 // obtain end(). 445 iterator 446 before_begin() 447 { return iterator((_Node*) &this->_M_head); } 448 449 const_iterator 450 before_begin() const 451 { return const_iterator((_Node*) &this->_M_head); } 452 453 size_type 454 size() const 455 { return __slist_size(this->_M_head._M_next); } 456 457 size_type 458 max_size() const 459 { return size_type(-1); } 460 461 bool 462 empty() const 463 { return this->_M_head._M_next == 0; } 464 465 void 466 swap(slist& __x) 467 { std::swap(this->_M_head._M_next, __x._M_head._M_next); } 468 469 public: 470 471 reference 472 front() 473 { return ((_Node*) this->_M_head._M_next)->_M_data; } 474 475 const_reference 476 front() const 477 { return ((_Node*) this->_M_head._M_next)->_M_data; } 478 479 void 480 push_front(const value_type& __x) 481 { __slist_make_link(&this->_M_head, _M_create_node(__x)); } 482 483 void 484 push_front() 485 { __slist_make_link(&this->_M_head, _M_create_node()); } 486 487 void 488 pop_front() 489 { 490 _Node* __node = (_Node*) this->_M_head._M_next; 491 this->_M_head._M_next = __node->_M_next; 492 get_allocator().destroy(&__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 __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 __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 __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 1028 namespace 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
