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