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