1/* 2 * Copyright (c) 1997 3 * Silicon Graphics Computer Systems, Inc. 4 * 5 * Permission to use, copy, modify, distribute and sell this software 6 * and its documentation for any purpose is hereby granted without fee, 7 * provided that the above copyright notice appear in all copies and 8 * that both that copyright notice and this permission notice appear 9 * in supporting documentation. Silicon Graphics makes no 10 * representations about the suitability of this software for any 11 * purpose. It is provided "as is" without express or implied warranty. 12 * 13 */ 14 15/* NOTE: This is an internal header file, included by other STL headers. 16 * You should not attempt to use it directly. 17 */ 18 19#ifndef __SGI_STL_INTERNAL_SLIST_H 20#define __SGI_STL_INTERNAL_SLIST_H 21 22 23__STL_BEGIN_NAMESPACE 24 25#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 26#pragma set woff 1174 27#pragma set woff 1375 28#endif 29 30struct _Slist_node_base 31{ 32 _Slist_node_base* _M_next; 33}; 34 35inline _Slist_node_base* 36__slist_make_link(_Slist_node_base* __prev_node, 37 _Slist_node_base* __new_node) 38{ 39 __new_node->_M_next = __prev_node->_M_next; 40 __prev_node->_M_next = __new_node; 41 return __new_node; 42} 43 44inline _Slist_node_base* 45__slist_previous(_Slist_node_base* __head, 46 const _Slist_node_base* __node) 47{ 48 while (__head && __head->_M_next != __node) 49 __head = __head->_M_next; 50 return __head; 51} 52 53inline const _Slist_node_base* 54__slist_previous(const _Slist_node_base* __head, 55 const _Slist_node_base* __node) 56{ 57 while (__head && __head->_M_next != __node) 58 __head = __head->_M_next; 59 return __head; 60} 61 62inline void __slist_splice_after(_Slist_node_base* __pos, 63 _Slist_node_base* __before_first, 64 _Slist_node_base* __before_last) 65{ 66 if (__pos != __before_first && __pos != __before_last) { 67 _Slist_node_base* __first = __before_first->_M_next; 68 _Slist_node_base* __after = __pos->_M_next; 69 __before_first->_M_next = __before_last->_M_next; 70 __pos->_M_next = __first; 71 __before_last->_M_next = __after; 72 } 73} 74 75inline _Slist_node_base* __slist_reverse(_Slist_node_base* __node) 76{ 77 _Slist_node_base* __result = __node; 78 __node = __node->_M_next; 79 __result->_M_next = 0; 80 while(__node) { 81 _Slist_node_base* __next = __node->_M_next; 82 __node->_M_next = __result; 83 __result = __node; 84 __node = __next; 85 } 86 return __result; 87} 88 89inline size_t __slist_size(_Slist_node_base* __node) 90{ 91 size_t __result = 0; 92 for ( ; __node != 0; __node = __node->_M_next) 93 ++__result; 94 return __result; 95} 96 97template <class _Tp> 98struct _Slist_node : public _Slist_node_base 99{ 100 _Tp _M_data; 101}; 102 103struct _Slist_iterator_base 104{ 105 typedef size_t size_type; 106 typedef ptrdiff_t difference_type; 107 typedef forward_iterator_tag iterator_category; 108 109 _Slist_node_base* _M_node; 110 111 _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {} 112 void _M_incr() { _M_node = _M_node->_M_next; } 113 114 bool operator==(const _Slist_iterator_base& __x) const { 115 return _M_node == __x._M_node; 116 } 117 bool operator!=(const _Slist_iterator_base& __x) const { 118 return _M_node != __x._M_node; 119 } 120}; 121 122template <class _Tp, class _Ref, class _Ptr> 123struct _Slist_iterator : public _Slist_iterator_base 124{ 125 typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; 126 typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 127 typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self; 128 129 typedef _Tp value_type; 130 typedef _Ptr pointer; 131 typedef _Ref reference; 132 typedef _Slist_node<_Tp> _Node; 133 134 _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {} 135 _Slist_iterator() : _Slist_iterator_base(0) {} 136 _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {} 137 138 reference operator*() const { return ((_Node*) _M_node)->_M_data; } 139#ifndef __SGI_STL_NO_ARROW_OPERATOR 140 pointer operator->() const { return &(operator*()); } 141#endif /* __SGI_STL_NO_ARROW_OPERATOR */ 142 143 _Self& operator++() 144 { 145 _M_incr(); 146 return *this; 147 } 148 _Self operator++(int) 149 { 150 _Self __tmp = *this; 151 _M_incr(); 152 return __tmp; 153 } 154}; 155 156#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION 157 158inline ptrdiff_t* distance_type(const _Slist_iterator_base&) { 159 return 0; 160} 161 162inline forward_iterator_tag iterator_category(const _Slist_iterator_base&) { 163 return forward_iterator_tag(); 164} 165 166template <class _Tp, class _Ref, class _Ptr> 167inline _Tp* value_type(const _Slist_iterator<_Tp, _Ref, _Ptr>&) { 168 return 0; 169} 170 171#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 172 173// Base class that encapsulates details of allocators. Three cases: 174// an ordinary standard-conforming allocator, a standard-conforming 175// allocator with no non-static data, and an SGI-style allocator. 176// This complexity is necessary only because we're worrying about backward 177// compatibility and because we want to avoid wasting storage on an 178// allocator instance if it isn't necessary. 179 180#ifdef __STL_USE_STD_ALLOCATORS 181 182// Base for general standard-conforming allocators. 183template <class _Tp, class _Allocator, bool _IsStatic> 184class _Slist_alloc_base { 185public: 186 typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type 187 allocator_type; 188 allocator_type get_allocator() const { return _M_node_allocator; } 189 190 _Slist_alloc_base(const allocator_type& __a) : _M_node_allocator(__a) {} 191 192protected: 193 _Slist_node<_Tp>* _M_get_node() 194 { return _M_node_allocator.allocate(1); } 195 void _M_put_node(_Slist_node<_Tp>* __p) 196 { _M_node_allocator.deallocate(__p, 1); } 197 198protected: 199 typename _Alloc_traits<_Slist_node<_Tp>,_Allocator>::allocator_type 200 _M_node_allocator; 201 _Slist_node_base _M_head; 202}; 203 204// Specialization for instanceless allocators. 205template <class _Tp, class _Allocator> 206class _Slist_alloc_base<_Tp,_Allocator, true> { 207public: 208 typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type 209 allocator_type; 210 allocator_type get_allocator() const { return allocator_type(); } 211 212 _Slist_alloc_base(const allocator_type&) {} 213 214protected: 215 typedef typename _Alloc_traits<_Slist_node<_Tp>, _Allocator>::_Alloc_type 216 _Alloc_type; 217 _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); } 218 void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } 219 220protected: 221 _Slist_node_base _M_head; 222}; 223 224 225template <class _Tp, class _Alloc> 226struct _Slist_base 227 : public _Slist_alloc_base<_Tp, _Alloc, 228 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 229{ 230 typedef _Slist_alloc_base<_Tp, _Alloc, 231 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 232 _Base; 233 typedef typename _Base::allocator_type allocator_type; 234 235 _Slist_base(const allocator_type& __a) : _Base(__a) { _M_head._M_next = 0; } 236 ~_Slist_base() { _M_erase_after(&_M_head, 0); } 237 238protected: 239 240 _Slist_node_base* _M_erase_after(_Slist_node_base* __pos) 241 { 242 _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next); 243 _Slist_node_base* __next_next = __next->_M_next; 244 __pos->_M_next = __next_next; 245 destroy(&__next->_M_data); 246 _M_put_node(__next); 247 return __next_next; 248 } 249 _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*); 250}; 251 252#else /* __STL_USE_STD_ALLOCATORS */ 253 254template <class _Tp, class _Alloc> 255struct _Slist_base { 256 typedef _Alloc allocator_type; 257 allocator_type get_allocator() const { return allocator_type(); } 258 259 _Slist_base(const allocator_type&) { _M_head._M_next = 0; } 260 ~_Slist_base() { _M_erase_after(&_M_head, 0); } 261 262protected: 263 typedef simple_alloc<_Slist_node<_Tp>, _Alloc> _Alloc_type; 264 _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); } 265 void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } 266 267 _Slist_node_base* _M_erase_after(_Slist_node_base* __pos) 268 { 269 _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next); 270 _Slist_node_base* __next_next = __next->_M_next; 271 __pos->_M_next = __next_next; 272 destroy(&__next->_M_data); 273 _M_put_node(__next); 274 return __next_next; 275 } 276 _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*); 277 278protected: 279 _Slist_node_base _M_head; 280}; 281 282#endif /* __STL_USE_STD_ALLOCATORS */ 283 284template <class _Tp, class _Alloc> 285_Slist_node_base* 286_Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, 287 _Slist_node_base* __last_node) { 288 _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next); 289 while (__cur != __last_node) { 290 _Slist_node<_Tp>* __tmp = __cur; 291 __cur = (_Slist_node<_Tp>*) __cur->_M_next; 292 destroy(&__tmp->_M_data); 293 _M_put_node(__tmp); 294 } 295 __before_first->_M_next = __last_node; 296 return __last_node; 297} 298 299template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > 300class slist : private _Slist_base<_Tp,_Alloc> 301{ 302private: 303 typedef _Slist_base<_Tp,_Alloc> _Base; 304public: 305 typedef _Tp value_type; 306 typedef value_type* pointer; 307 typedef const value_type* const_pointer; 308 typedef value_type& reference; 309 typedef const value_type& const_reference; 310 typedef size_t size_type; 311 typedef ptrdiff_t difference_type; 312 313 typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; 314 typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 315 316 typedef typename _Base::allocator_type allocator_type; 317 allocator_type get_allocator() const { return _Base::get_allocator(); } 318 319private: 320 typedef _Slist_node<_Tp> _Node; 321 typedef _Slist_node_base _Node_base; 322 typedef _Slist_iterator_base _Iterator_base; 323 324 _Node* _M_create_node(const value_type& __x) { 325 _Node* __node = _M_get_node(); 326 __STL_TRY { 327 construct(&__node->_M_data, __x); 328 __node->_M_next = 0; 329 } 330 __STL_UNWIND(_M_put_node(__node)); 331 return __node; 332 } 333 334 _Node* _M_create_node() { 335 _Node* __node = _M_get_node(); 336 __STL_TRY { 337 construct(&__node->_M_data); 338 __node->_M_next = 0; 339 } 340 __STL_UNWIND(_M_put_node(__node)); 341 return __node; 342 } 343 344private: 345#ifdef __STL_USE_NAMESPACES 346 using _Base::_M_get_node; 347 using _Base::_M_put_node; 348 using _Base::_M_erase_after; 349 using _Base::_M_head; 350#endif /* __STL_USE_NAMESPACES */ 351 352public: 353 explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {} 354 355 slist(size_type __n, const value_type& __x, 356 const allocator_type& __a = allocator_type()) : _Base(__a) 357 { _M_insert_after_fill(&_M_head, __n, __x); } 358 359 explicit slist(size_type __n) : _Base(allocator_type()) 360 { _M_insert_after_fill(&_M_head, __n, value_type()); } 361 362#ifdef __STL_MEMBER_TEMPLATES 363 // We don't need any dispatching tricks here, because _M_insert_after_range 364 // already does them. 365 template <class _InputIterator> 366 slist(_InputIterator __first, _InputIterator __last, 367 const allocator_type& __a = allocator_type()) : _Base(__a) 368 { _M_insert_after_range(&_M_head, __first, __last); } 369 370#else /* __STL_MEMBER_TEMPLATES */ 371 slist(const_iterator __first, const_iterator __last, 372 const allocator_type& __a = allocator_type()) : _Base(__a) 373 { _M_insert_after_range(&_M_head, __first, __last); } 374 slist(const value_type* __first, const value_type* __last, 375 const allocator_type& __a = allocator_type()) : _Base(__a) 376 { _M_insert_after_range(&_M_head, __first, __last); } 377#endif /* __STL_MEMBER_TEMPLATES */ 378 379 slist(const slist& __x) : _Base(__x.get_allocator()) 380 { _M_insert_after_range(&_M_head, __x.begin(), __x.end()); } 381 382 slist& operator= (const slist& __x); 383 384 ~slist() {} 385 386public: 387 // assign(), a generalized assignment member function. Two 388 // versions: one that takes a count, and one that takes a range. 389 // The range version is a member template, so we dispatch on whether 390 // or not the type is an integer. 391 392 void assign(size_type __n, const _Tp& __val); 393 394#ifdef __STL_MEMBER_TEMPLATES 395 396 template <class _InputIterator> 397 void assign(_InputIterator __first, _InputIterator __last) { 398 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 399 _M_assign_dispatch(__first, __last, _Integral()); 400 } 401 402 template <class _Integer> 403 void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 404 { assign((size_type) __n, (_Tp) __val); } 405 406 template <class _InputIterator> 407 void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 408 __false_type); 409 410#endif /* __STL_MEMBER_TEMPLATES */ 411 412public: 413 414 iterator begin() { return iterator((_Node*)_M_head._M_next); } 415 const_iterator begin() const 416 { return const_iterator((_Node*)_M_head._M_next);} 417 418 iterator end() { return iterator(0); } 419 const_iterator end() const { return const_iterator(0); } 420 421 size_type size() const { return __slist_size(_M_head._M_next); } 422 423 size_type max_size() const { return size_type(-1); } 424 425 bool empty() const { return _M_head._M_next == 0; } 426 427 void swap(slist& __x) { __STD::swap(_M_head._M_next, __x._M_head._M_next); } 428 429public: 430 friend bool operator== __STL_NULL_TMPL_ARGS (const slist<_Tp,_Alloc>& _SL1, 431 const slist<_Tp,_Alloc>& _SL2); 432 433public: 434 435 reference front() { return ((_Node*) _M_head._M_next)->_M_data; } 436 const_reference front() const 437 { return ((_Node*) _M_head._M_next)->_M_data; } 438 void push_front(const value_type& __x) { 439 __slist_make_link(&_M_head, _M_create_node(__x)); 440 } 441 void push_front() { __slist_make_link(&_M_head, _M_create_node());} 442 void pop_front() { 443 _Node* __node = (_Node*) _M_head._M_next; 444 _M_head._M_next = __node->_M_next; 445 destroy(&__node->_M_data); 446 _M_put_node(__node); 447 } 448 449 iterator previous(const_iterator __pos) { 450 return iterator((_Node*) __slist_previous(&_M_head, __pos._M_node)); 451 } 452 const_iterator previous(const_iterator __pos) const { 453 return const_iterator((_Node*) __slist_previous(&_M_head, __pos._M_node)); 454 } 455 456private: 457 _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) { 458 return (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); 459 } 460 461 _Node* _M_insert_after(_Node_base* __pos) { 462 return (_Node*) (__slist_make_link(__pos, _M_create_node())); 463 } 464 465 void _M_insert_after_fill(_Node_base* __pos, 466 size_type __n, const value_type& __x) { 467 for (size_type __i = 0; __i < __n; ++__i) 468 __pos = __slist_make_link(__pos, _M_create_node(__x)); 469 } 470 471#ifdef __STL_MEMBER_TEMPLATES 472 473 // Check whether it's an integral type. If so, it's not an iterator. 474 template <class _InIter> 475 void _M_insert_after_range(_Node_base* __pos, 476 _InIter __first, _InIter __last) { 477 typedef typename _Is_integer<_InIter>::_Integral _Integral; 478 _M_insert_after_range(__pos, __first, __last, _Integral()); 479 } 480 481 template <class _Integer> 482 void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x, 483 __true_type) { 484 _M_insert_after_fill(__pos, __n, __x); 485 } 486 487 template <class _InIter> 488 void _M_insert_after_range(_Node_base* __pos, 489 _InIter __first, _InIter __last, 490 __false_type) { 491 while (__first != __last) { 492 __pos = __slist_make_link(__pos, _M_create_node(*__first)); 493 ++__first; 494 } 495 } 496 497#else /* __STL_MEMBER_TEMPLATES */ 498 499 void _M_insert_after_range(_Node_base* __pos, 500 const_iterator __first, const_iterator __last) { 501 while (__first != __last) { 502 __pos = __slist_make_link(__pos, _M_create_node(*__first)); 503 ++__first; 504 } 505 } 506 void _M_insert_after_range(_Node_base* __pos, 507 const value_type* __first, 508 const value_type* __last) { 509 while (__first != __last) { 510 __pos = __slist_make_link(__pos, _M_create_node(*__first)); 511 ++__first; 512 } 513 } 514 515#endif /* __STL_MEMBER_TEMPLATES */ 516 517public: 518 519 iterator insert_after(iterator __pos, const value_type& __x) { 520 return iterator(_M_insert_after(__pos._M_node, __x)); 521 } 522 523 iterator insert_after(iterator __pos) { 524 return insert_after(__pos, value_type()); 525 } 526 527 void insert_after(iterator __pos, size_type __n, const value_type& __x) { 528 _M_insert_after_fill(__pos._M_node, __n, __x); 529 } 530 531#ifdef __STL_MEMBER_TEMPLATES 532 533 // We don't need any dispatching tricks here, because _M_insert_after_range 534 // already does them. 535 template <class _InIter> 536 void insert_after(iterator __pos, _InIter __first, _InIter __last) { 537 _M_insert_after_range(__pos._M_node, __first, __last); 538 } 539 540#else /* __STL_MEMBER_TEMPLATES */ 541 542 void insert_after(iterator __pos, 543 const_iterator __first, const_iterator __last) { 544 _M_insert_after_range(__pos._M_node, __first, __last); 545 } 546 void insert_after(iterator __pos, 547 const value_type* __first, const value_type* __last) { 548 _M_insert_after_range(__pos._M_node, __first, __last); 549 } 550 551#endif /* __STL_MEMBER_TEMPLATES */ 552 553 iterator insert(iterator __pos, const value_type& __x) { 554 return iterator(_M_insert_after(__slist_previous(&_M_head, __pos._M_node), 555 __x)); 556 } 557 558 iterator insert(iterator __pos) { 559 return iterator(_M_insert_after(__slist_previous(&_M_head, __pos._M_node), 560 value_type())); 561 } 562 563 void insert(iterator __pos, size_type __n, const value_type& __x) { 564 _M_insert_after_fill(__slist_previous(&_M_head, __pos._M_node), __n, __x); 565 } 566 567#ifdef __STL_MEMBER_TEMPLATES 568 569 // We don't need any dispatching tricks here, because _M_insert_after_range 570 // already does them. 571 template <class _InIter> 572 void insert(iterator __pos, _InIter __first, _InIter __last) { 573 _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node), 574 __first, __last); 575 } 576 577#else /* __STL_MEMBER_TEMPLATES */ 578 579 void insert(iterator __pos, const_iterator __first, const_iterator __last) { 580 _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node), 581 __first, __last); 582 } 583 void insert(iterator __pos, const value_type* __first, 584 const value_type* __last) { 585 _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node), 586 __first, __last); 587 } 588 589#endif /* __STL_MEMBER_TEMPLATES */ 590 591 592public: 593 iterator erase_after(iterator __pos) { 594 return iterator((_Node*) _M_erase_after(__pos._M_node)); 595 } 596 iterator erase_after(iterator __before_first, iterator __last) { 597 return iterator((_Node*) _M_erase_after(__before_first._M_node, 598 __last._M_node)); 599 } 600 601 iterator erase(iterator __pos) { 602 return (_Node*) _M_erase_after(__slist_previous(&_M_head, 603 __pos._M_node)); 604 } 605 iterator erase(iterator __first, iterator __last) { 606 return (_Node*) _M_erase_after( 607 __slist_previous(&_M_head, __first._M_node), __last._M_node); 608 } 609 610 void resize(size_type new_size, const _Tp& __x); 611 void resize(size_type new_size) { resize(new_size, _Tp()); } 612 void clear() { _M_erase_after(&_M_head, 0); } 613 614public: 615 // Moves the range [__before_first + 1, __before_last + 1) to *this, 616 // inserting it immediately after __pos. This is constant time. 617 void splice_after(iterator __pos, 618 iterator __before_first, iterator __before_last) 619 { 620 if (__before_first != __before_last) 621 __slist_splice_after(__pos._M_node, __before_first._M_node, 622 __before_last._M_node); 623 } 624 625 // Moves the element that follows __prev to *this, inserting it immediately 626 // after __pos. This is constant time. 627 void splice_after(iterator __pos, iterator __prev) 628 { 629 __slist_splice_after(__pos._M_node, 630 __prev._M_node, __prev._M_node->_M_next); 631 } 632 633 634 // Linear in distance(begin(), __pos), and linear in __x.size(). 635 void splice(iterator __pos, slist& __x) { 636 if (__x._M_head._M_next) 637 __slist_splice_after(__slist_previous(&_M_head, __pos._M_node), 638 &__x._M_head, __slist_previous(&__x._M_head, 0)); 639 } 640 641 // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i). 642 void splice(iterator __pos, slist& __x, iterator __i) { 643 __slist_splice_after(__slist_previous(&_M_head, __pos._M_node), 644 __slist_previous(&__x._M_head, __i._M_node), 645 __i._M_node); 646 } 647 648 // Linear in distance(begin(), __pos), in distance(__x.begin(), __first), 649 // and in distance(__first, __last). 650 void splice(iterator __pos, slist& __x, iterator __first, iterator __last) 651 { 652 if (__first != __last) 653 __slist_splice_after(__slist_previous(&_M_head, __pos._M_node), 654 __slist_previous(&__x._M_head, __first._M_node), 655 __slist_previous(__first._M_node, __last._M_node)); 656 } 657 658public: 659 void reverse() { 660 if (_M_head._M_next) 661 _M_head._M_next = __slist_reverse(_M_head._M_next); 662 } 663 664 void remove(const _Tp& __val); 665 void unique(); 666 void merge(slist& __x); 667 void sort(); 668 669#ifdef __STL_MEMBER_TEMPLATES 670 template <class _Predicate> 671 void remove_if(_Predicate __pred); 672 673 template <class _BinaryPredicate> 674 void unique(_BinaryPredicate __pred); 675 676 template <class _StrictWeakOrdering> 677 void merge(slist&, _StrictWeakOrdering); 678 679 template <class _StrictWeakOrdering> 680 void sort(_StrictWeakOrdering __comp); 681#endif /* __STL_MEMBER_TEMPLATES */ 682}; 683 684template <class _Tp, class _Alloc> 685slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x) 686{ 687 if (&__x != this) { 688 _Node_base* __p1 = &_M_head; 689 _Node* __n1 = (_Node*) _M_head._M_next; 690 const _Node* __n2 = (const _Node*) __x._M_head._M_next; 691 while (__n1 && __n2) { 692 __n1->_M_data = __n2->_M_data; 693 __p1 = __n1; 694 __n1 = (_Node*) __n1->_M_next; 695 __n2 = (const _Node*) __n2->_M_next; 696 } 697 if (__n2 == 0) 698 _M_erase_after(__p1, 0); 699 else 700 _M_insert_after_range(__p1, const_iterator((_Node*)__n2), 701 const_iterator(0)); 702 } 703 return *this; 704} 705 706template <class _Tp, class _Alloc> 707void slist<_Tp, _Alloc>::assign(size_type __n, const _Tp& __val) { 708 _Node_base* __prev = &_M_head; 709 _Node* __node = (_Node*) _M_head._M_next; 710 for ( ; __node != 0 && __n > 0 ; --__n) { 711 __node->_M_data = __val; 712 __prev = __node; 713 __node = (_Node*) __node->_M_next; 714 } 715 if (__n > 0) 716 _M_insert_after_fill(__prev, __n, __val); 717 else 718 _M_erase_after(__prev, 0); 719} 720 721#ifdef __STL_MEMBER_TEMPLATES 722 723template <class _Tp, class _Alloc> template <class _InputIter> 724void 725slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first, _InputIter __last, 726 __false_type) 727{ 728 _Node_base* __prev = &_M_head; 729 _Node* __node = (_Node*) _M_head._M_next; 730 while (__node != 0 && __first != __last) { 731 __node->_M_data = *__first; 732 __prev = __node; 733 __node = (_Node*) __node->_M_next; 734 ++__first; 735 } 736 if (__first != __last) 737 _M_insert_after_range(__prev, __first, __last); 738 else 739 _M_erase_after(__prev, 0); 740} 741 742#endif /* __STL_MEMBER_TEMPLATES */ 743 744template <class _Tp, class _Alloc> 745inline bool 746operator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) 747{ 748 typedef typename slist<_Tp,_Alloc>::_Node _Node; 749 _Node* __n1 = (_Node*) _SL1._M_head._M_next; 750 _Node* __n2 = (_Node*) _SL2._M_head._M_next; 751 while (__n1 && __n2 && __n1->_M_data == __n2->_M_data) { 752 __n1 = (_Node*) __n1->_M_next; 753 __n2 = (_Node*) __n2->_M_next; 754 } 755 return __n1 == 0 && __n2 == 0; 756} 757 758template <class _Tp, class _Alloc> 759inline bool operator<(const slist<_Tp,_Alloc>& _SL1, 760 const slist<_Tp,_Alloc>& _SL2) 761{ 762 return lexicographical_compare(_SL1.begin(), _SL1.end(), 763 _SL2.begin(), _SL2.end()); 764} 765 766#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER 767 768template <class _Tp, class _Alloc> 769inline void swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) { 770 __x.swap(__y); 771} 772 773#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ 774 775 776template <class _Tp, class _Alloc> 777void slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x) 778{ 779 _Node_base* __cur = &_M_head; 780 while (__cur->_M_next != 0 && __len > 0) { 781 --__len; 782 __cur = __cur->_M_next; 783 } 784 if (__cur->_M_next) 785 _M_erase_after(__cur, 0); 786 else 787 _M_insert_after_fill(__cur, __len, __x); 788} 789 790template <class _Tp, class _Alloc> 791void slist<_Tp,_Alloc>::remove(const _Tp& __val) 792{ 793 _Node_base* __cur = &_M_head; 794 while (__cur && __cur->_M_next) { 795 if (((_Node*) __cur->_M_next)->_M_data == __val) 796 _M_erase_after(__cur); 797 else 798 __cur = __cur->_M_next; 799 } 800} 801 802template <class _Tp, class _Alloc> 803void slist<_Tp,_Alloc>::unique() 804{ 805 _Node_base* __cur = _M_head._M_next; 806 if (__cur) { 807 while (__cur->_M_next) { 808 if (((_Node*)__cur)->_M_data == 809 ((_Node*)(__cur->_M_next))->_M_data) 810 _M_erase_after(__cur); 811 else 812 __cur = __cur->_M_next; 813 } 814 } 815} 816 817template <class _Tp, class _Alloc> 818void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x) 819{ 820 _Node_base* __n1 = &_M_head; 821 while (__n1->_M_next && __x._M_head._M_next) { 822 if (((_Node*) __x._M_head._M_next)->_M_data < 823 ((_Node*) __n1->_M_next)->_M_data) 824 __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); 825 __n1 = __n1->_M_next; 826 } 827 if (__x._M_head._M_next) { 828 __n1->_M_next = __x._M_head._M_next; 829 __x._M_head._M_next = 0; 830 } 831} 832 833template <class _Tp, class _Alloc> 834void slist<_Tp,_Alloc>::sort() 835{ 836 if (_M_head._M_next && _M_head._M_next->_M_next) { 837 slist __carry; 838 slist __counter[64]; 839 int __fill = 0; 840 while (!empty()) { 841 __slist_splice_after(&__carry._M_head, &_M_head, _M_head._M_next); 842 int __i = 0; 843 while (__i < __fill && !__counter[__i].empty()) { 844 __counter[__i].merge(__carry); 845 __carry.swap(__counter[__i]); 846 ++__i; 847 } 848 __carry.swap(__counter[__i]); 849 if (__i == __fill) 850 ++__fill; 851 } 852 853 for (int __i = 1; __i < __fill; ++__i) 854 __counter[__i].merge(__counter[__i-1]); 855 this->swap(__counter[__fill-1]); 856 } 857} 858 859#ifdef __STL_MEMBER_TEMPLATES 860 861template <class _Tp, class _Alloc> 862template <class _Predicate> 863void slist<_Tp,_Alloc>::remove_if(_Predicate __pred) 864{ 865 _Node_base* __cur = &_M_head; 866 while (__cur->_M_next) { 867 if (__pred(((_Node*) __cur->_M_next)->_M_data)) 868 _M_erase_after(__cur); 869 else 870 __cur = __cur->_M_next; 871 } 872} 873 874template <class _Tp, class _Alloc> template <class _BinaryPredicate> 875void slist<_Tp,_Alloc>::unique(_BinaryPredicate __pred) 876{ 877 _Node* __cur = (_Node*) _M_head._M_next; 878 if (__cur) { 879 while (__cur->_M_next) { 880 if (__pred(((_Node*)__cur)->_M_data, 881 ((_Node*)(__cur->_M_next))->_M_data)) 882 _M_erase_after(__cur); 883 else 884 __cur = (_Node*) __cur->_M_next; 885 } 886 } 887} 888 889template <class _Tp, class _Alloc> template <class _StrictWeakOrdering> 890void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x, 891 _StrictWeakOrdering __comp) 892{ 893 _Node_base* __n1 = &_M_head; 894 while (__n1->_M_next && __x._M_head._M_next) { 895 if (__comp(((_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 __n1->_M_next = __x._M_head._M_next; 902 __x._M_head._M_next = 0; 903 } 904} 905 906template <class _Tp, class _Alloc> template <class _StrictWeakOrdering> 907void slist<_Tp,_Alloc>::sort(_StrictWeakOrdering __comp) 908{ 909 if (_M_head._M_next && _M_head._M_next->_M_next) { 910 slist __carry; 911 slist __counter[64]; 912 int __fill = 0; 913 while (!empty()) { 914 __slist_splice_after(&__carry._M_head, &_M_head, _M_head._M_next); 915 int __i = 0; 916 while (__i < __fill && !__counter[__i].empty()) { 917 __counter[__i].merge(__carry, __comp); 918 __carry.swap(__counter[__i]); 919 ++__i; 920 } 921 __carry.swap(__counter[__i]); 922 if (__i == __fill) 923 ++__fill; 924 } 925 926 for (int __i = 1; __i < __fill; ++__i) 927 __counter[__i].merge(__counter[__i-1], __comp); 928 this->swap(__counter[__fill-1]); 929 } 930} 931 932#endif /* __STL_MEMBER_TEMPLATES */ 933 934#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 935#pragma reset woff 1174 936#pragma reset woff 1375 937#endif 938 939__STL_END_NAMESPACE 940 941#endif /* __SGI_STL_INTERNAL_SLIST_H */ 942 943// Local Variables: 944// mode:C++ 945// End: 946