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