libstdc++
|
00001 // Singly-linked list implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2004, 2005, 2007, 2008, 2009 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * Copyright (c) 1997 00028 * Silicon Graphics Computer Systems, Inc. 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Silicon Graphics makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 * 00038 */ 00039 00040 /** @file ext/slist 00041 * This file is a GNU extension to the Standard C++ Library (possibly 00042 * containing extensions from the HP/SGI STL subset). 00043 */ 00044 00045 #ifndef _SLIST 00046 #define _SLIST 1 00047 00048 #include <algorithm> 00049 #include <bits/allocator.h> 00050 #include <bits/stl_construct.h> 00051 #include <bits/stl_uninitialized.h> 00052 #include <bits/concept_check.h> 00053 00054 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 00055 00056 using std::size_t; 00057 using std::ptrdiff_t; 00058 using std::_Construct; 00059 using std::_Destroy; 00060 using std::allocator; 00061 using std::__true_type; 00062 using std::__false_type; 00063 00064 struct _Slist_node_base 00065 { 00066 _Slist_node_base* _M_next; 00067 }; 00068 00069 inline _Slist_node_base* 00070 __slist_make_link(_Slist_node_base* __prev_node, 00071 _Slist_node_base* __new_node) 00072 { 00073 __new_node->_M_next = __prev_node->_M_next; 00074 __prev_node->_M_next = __new_node; 00075 return __new_node; 00076 } 00077 00078 inline _Slist_node_base* 00079 __slist_previous(_Slist_node_base* __head, 00080 const _Slist_node_base* __node) 00081 { 00082 while (__head && __head->_M_next != __node) 00083 __head = __head->_M_next; 00084 return __head; 00085 } 00086 00087 inline const _Slist_node_base* 00088 __slist_previous(const _Slist_node_base* __head, 00089 const _Slist_node_base* __node) 00090 { 00091 while (__head && __head->_M_next != __node) 00092 __head = __head->_M_next; 00093 return __head; 00094 } 00095 00096 inline void 00097 __slist_splice_after(_Slist_node_base* __pos, 00098 _Slist_node_base* __before_first, 00099 _Slist_node_base* __before_last) 00100 { 00101 if (__pos != __before_first && __pos != __before_last) 00102 { 00103 _Slist_node_base* __first = __before_first->_M_next; 00104 _Slist_node_base* __after = __pos->_M_next; 00105 __before_first->_M_next = __before_last->_M_next; 00106 __pos->_M_next = __first; 00107 __before_last->_M_next = __after; 00108 } 00109 } 00110 00111 inline void 00112 __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head) 00113 { 00114 _Slist_node_base* __before_last = __slist_previous(__head, 0); 00115 if (__before_last != __head) 00116 { 00117 _Slist_node_base* __after = __pos->_M_next; 00118 __pos->_M_next = __head->_M_next; 00119 __head->_M_next = 0; 00120 __before_last->_M_next = __after; 00121 } 00122 } 00123 00124 inline _Slist_node_base* 00125 __slist_reverse(_Slist_node_base* __node) 00126 { 00127 _Slist_node_base* __result = __node; 00128 __node = __node->_M_next; 00129 __result->_M_next = 0; 00130 while(__node) 00131 { 00132 _Slist_node_base* __next = __node->_M_next; 00133 __node->_M_next = __result; 00134 __result = __node; 00135 __node = __next; 00136 } 00137 return __result; 00138 } 00139 00140 inline size_t 00141 __slist_size(_Slist_node_base* __node) 00142 { 00143 size_t __result = 0; 00144 for (; __node != 0; __node = __node->_M_next) 00145 ++__result; 00146 return __result; 00147 } 00148 00149 template <class _Tp> 00150 struct _Slist_node : public _Slist_node_base 00151 { 00152 _Tp _M_data; 00153 }; 00154 00155 struct _Slist_iterator_base 00156 { 00157 typedef size_t size_type; 00158 typedef ptrdiff_t difference_type; 00159 typedef std::forward_iterator_tag iterator_category; 00160 00161 _Slist_node_base* _M_node; 00162 00163 _Slist_iterator_base(_Slist_node_base* __x) 00164 : _M_node(__x) {} 00165 00166 void 00167 _M_incr() 00168 { _M_node = _M_node->_M_next; } 00169 00170 bool 00171 operator==(const _Slist_iterator_base& __x) const 00172 { return _M_node == __x._M_node; } 00173 00174 bool 00175 operator!=(const _Slist_iterator_base& __x) const 00176 { return _M_node != __x._M_node; } 00177 }; 00178 00179 template <class _Tp, class _Ref, class _Ptr> 00180 struct _Slist_iterator : public _Slist_iterator_base 00181 { 00182 typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; 00183 typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 00184 typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self; 00185 00186 typedef _Tp value_type; 00187 typedef _Ptr pointer; 00188 typedef _Ref reference; 00189 typedef _Slist_node<_Tp> _Node; 00190 00191 explicit 00192 _Slist_iterator(_Node* __x) 00193 : _Slist_iterator_base(__x) {} 00194 00195 _Slist_iterator() 00196 : _Slist_iterator_base(0) {} 00197 00198 _Slist_iterator(const iterator& __x) 00199 : _Slist_iterator_base(__x._M_node) {} 00200 00201 reference 00202 operator*() const 00203 { return ((_Node*) _M_node)->_M_data; } 00204 00205 pointer 00206 operator->() const 00207 { return &(operator*()); } 00208 00209 _Self& 00210 operator++() 00211 { 00212 _M_incr(); 00213 return *this; 00214 } 00215 00216 _Self 00217 operator++(int) 00218 { 00219 _Self __tmp = *this; 00220 _M_incr(); 00221 return __tmp; 00222 } 00223 }; 00224 00225 template <class _Tp, class _Alloc> 00226 struct _Slist_base 00227 : public _Alloc::template rebind<_Slist_node<_Tp> >::other 00228 { 00229 typedef typename _Alloc::template rebind<_Slist_node<_Tp> >::other 00230 _Node_alloc; 00231 typedef _Alloc allocator_type; 00232 00233 allocator_type 00234 get_allocator() const 00235 { return *static_cast<const _Node_alloc*>(this); } 00236 00237 _Slist_base(const allocator_type& __a) 00238 : _Node_alloc(__a) 00239 { this->_M_head._M_next = 0; } 00240 00241 ~_Slist_base() 00242 { _M_erase_after(&this->_M_head, 0); } 00243 00244 protected: 00245 _Slist_node_base _M_head; 00246 00247 _Slist_node<_Tp>* 00248 _M_get_node() 00249 { return _Node_alloc::allocate(1); } 00250 00251 void 00252 _M_put_node(_Slist_node<_Tp>* __p) 00253 { _Node_alloc::deallocate(__p, 1); } 00254 00255 protected: 00256 _Slist_node_base* _M_erase_after(_Slist_node_base* __pos) 00257 { 00258 _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next); 00259 _Slist_node_base* __next_next = __next->_M_next; 00260 __pos->_M_next = __next_next; 00261 get_allocator().destroy(&__next->_M_data); 00262 _M_put_node(__next); 00263 return __next_next; 00264 } 00265 _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*); 00266 }; 00267 00268 template <class _Tp, class _Alloc> 00269 _Slist_node_base* 00270 _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, 00271 _Slist_node_base* __last_node) 00272 { 00273 _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next); 00274 while (__cur != __last_node) 00275 { 00276 _Slist_node<_Tp>* __tmp = __cur; 00277 __cur = (_Slist_node<_Tp>*) __cur->_M_next; 00278 get_allocator().destroy(&__tmp->_M_data); 00279 _M_put_node(__tmp); 00280 } 00281 __before_first->_M_next = __last_node; 00282 return __last_node; 00283 } 00284 00285 /** 00286 * This is an SGI extension. 00287 * @ingroup SGIextensions 00288 * @doctodo 00289 */ 00290 template <class _Tp, class _Alloc = allocator<_Tp> > 00291 class slist : private _Slist_base<_Tp,_Alloc> 00292 { 00293 // concept requirements 00294 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00295 00296 private: 00297 typedef _Slist_base<_Tp,_Alloc> _Base; 00298 00299 public: 00300 typedef _Tp value_type; 00301 typedef value_type* pointer; 00302 typedef const value_type* const_pointer; 00303 typedef value_type& reference; 00304 typedef const value_type& const_reference; 00305 typedef size_t size_type; 00306 typedef ptrdiff_t difference_type; 00307 00308 typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; 00309 typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 00310 00311 typedef typename _Base::allocator_type allocator_type; 00312 00313 allocator_type 00314 get_allocator() const 00315 { return _Base::get_allocator(); } 00316 00317 private: 00318 typedef _Slist_node<_Tp> _Node; 00319 typedef _Slist_node_base _Node_base; 00320 typedef _Slist_iterator_base _Iterator_base; 00321 00322 _Node* 00323 _M_create_node(const value_type& __x) 00324 { 00325 _Node* __node = this->_M_get_node(); 00326 __try 00327 { 00328 get_allocator().construct(&__node->_M_data, __x); 00329 __node->_M_next = 0; 00330 } 00331 __catch(...) 00332 { 00333 this->_M_put_node(__node); 00334 __throw_exception_again; 00335 } 00336 return __node; 00337 } 00338 00339 _Node* 00340 _M_create_node() 00341 { 00342 _Node* __node = this->_M_get_node(); 00343 __try 00344 { 00345 get_allocator().construct(&__node->_M_data, value_type()); 00346 __node->_M_next = 0; 00347 } 00348 __catch(...) 00349 { 00350 this->_M_put_node(__node); 00351 __throw_exception_again; 00352 } 00353 return __node; 00354 } 00355 00356 public: 00357 explicit 00358 slist(const allocator_type& __a = allocator_type()) 00359 : _Base(__a) {} 00360 00361 slist(size_type __n, const value_type& __x, 00362 const allocator_type& __a = allocator_type()) 00363 : _Base(__a) 00364 { _M_insert_after_fill(&this->_M_head, __n, __x); } 00365 00366 explicit 00367 slist(size_type __n) 00368 : _Base(allocator_type()) 00369 { _M_insert_after_fill(&this->_M_head, __n, value_type()); } 00370 00371 // We don't need any dispatching tricks here, because 00372 // _M_insert_after_range already does them. 00373 template <class _InputIterator> 00374 slist(_InputIterator __first, _InputIterator __last, 00375 const allocator_type& __a = allocator_type()) 00376 : _Base(__a) 00377 { _M_insert_after_range(&this->_M_head, __first, __last); } 00378 00379 slist(const slist& __x) 00380 : _Base(__x.get_allocator()) 00381 { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); } 00382 00383 slist& 00384 operator= (const slist& __x); 00385 00386 ~slist() {} 00387 00388 public: 00389 // assign(), a generalized assignment member function. Two 00390 // versions: one that takes a count, and one that takes a range. 00391 // The range version is a member template, so we dispatch on whether 00392 // or not the type is an integer. 00393 00394 void 00395 assign(size_type __n, const _Tp& __val) 00396 { _M_fill_assign(__n, __val); } 00397 00398 void 00399 _M_fill_assign(size_type __n, const _Tp& __val); 00400 00401 template <class _InputIterator> 00402 void 00403 assign(_InputIterator __first, _InputIterator __last) 00404 { 00405 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00406 _M_assign_dispatch(__first, __last, _Integral()); 00407 } 00408 00409 template <class _Integer> 00410 void 00411 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 00412 { _M_fill_assign((size_type) __n, (_Tp) __val); } 00413 00414 template <class _InputIterator> 00415 void 00416 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 00417 __false_type); 00418 00419 public: 00420 00421 iterator 00422 begin() 00423 { return iterator((_Node*)this->_M_head._M_next); } 00424 00425 const_iterator 00426 begin() const 00427 { return const_iterator((_Node*)this->_M_head._M_next);} 00428 00429 iterator 00430 end() 00431 { return iterator(0); } 00432 00433 const_iterator 00434 end() const 00435 { return const_iterator(0); } 00436 00437 // Experimental new feature: before_begin() returns a 00438 // non-dereferenceable iterator that, when incremented, yields 00439 // begin(). This iterator may be used as the argument to 00440 // insert_after, erase_after, etc. Note that even for an empty 00441 // slist, before_begin() is not the same iterator as end(). It 00442 // is always necessary to increment before_begin() at least once to 00443 // obtain end(). 00444 iterator 00445 before_begin() 00446 { return iterator((_Node*) &this->_M_head); } 00447 00448 const_iterator 00449 before_begin() const 00450 { return const_iterator((_Node*) &this->_M_head); } 00451 00452 size_type 00453 size() const 00454 { return __slist_size(this->_M_head._M_next); } 00455 00456 size_type 00457 max_size() const 00458 { return size_type(-1); } 00459 00460 bool 00461 empty() const 00462 { return this->_M_head._M_next == 0; } 00463 00464 void 00465 swap(slist& __x) 00466 { std::swap(this->_M_head._M_next, __x._M_head._M_next); } 00467 00468 public: 00469 00470 reference 00471 front() 00472 { return ((_Node*) this->_M_head._M_next)->_M_data; } 00473 00474 const_reference 00475 front() const 00476 { return ((_Node*) this->_M_head._M_next)->_M_data; } 00477 00478 void 00479 push_front(const value_type& __x) 00480 { __slist_make_link(&this->_M_head, _M_create_node(__x)); } 00481 00482 void 00483 push_front() 00484 { __slist_make_link(&this->_M_head, _M_create_node()); } 00485 00486 void 00487 pop_front() 00488 { 00489 _Node* __node = (_Node*) this->_M_head._M_next; 00490 this->_M_head._M_next = __node->_M_next; 00491 get_allocator().destroy(&__node->_M_data); 00492 this->_M_put_node(__node); 00493 } 00494 00495 iterator 00496 previous(const_iterator __pos) 00497 { return iterator((_Node*) __slist_previous(&this->_M_head, 00498 __pos._M_node)); } 00499 00500 const_iterator 00501 previous(const_iterator __pos) const 00502 { return const_iterator((_Node*) __slist_previous(&this->_M_head, 00503 __pos._M_node)); } 00504 00505 private: 00506 _Node* 00507 _M_insert_after(_Node_base* __pos, const value_type& __x) 00508 { return (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); } 00509 00510 _Node* 00511 _M_insert_after(_Node_base* __pos) 00512 { return (_Node*) (__slist_make_link(__pos, _M_create_node())); } 00513 00514 void 00515 _M_insert_after_fill(_Node_base* __pos, 00516 size_type __n, const value_type& __x) 00517 { 00518 for (size_type __i = 0; __i < __n; ++__i) 00519 __pos = __slist_make_link(__pos, _M_create_node(__x)); 00520 } 00521 00522 // Check whether it's an integral type. If so, it's not an iterator. 00523 template <class _InIterator> 00524 void 00525 _M_insert_after_range(_Node_base* __pos, 00526 _InIterator __first, _InIterator __last) 00527 { 00528 typedef typename std::__is_integer<_InIterator>::__type _Integral; 00529 _M_insert_after_range(__pos, __first, __last, _Integral()); 00530 } 00531 00532 template <class _Integer> 00533 void 00534 _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x, 00535 __true_type) 00536 { _M_insert_after_fill(__pos, __n, __x); } 00537 00538 template <class _InIterator> 00539 void 00540 _M_insert_after_range(_Node_base* __pos, 00541 _InIterator __first, _InIterator __last, 00542 __false_type) 00543 { 00544 while (__first != __last) 00545 { 00546 __pos = __slist_make_link(__pos, _M_create_node(*__first)); 00547 ++__first; 00548 } 00549 } 00550 00551 public: 00552 iterator 00553 insert_after(iterator __pos, const value_type& __x) 00554 { return iterator(_M_insert_after(__pos._M_node, __x)); } 00555 00556 iterator 00557 insert_after(iterator __pos) 00558 { return insert_after(__pos, value_type()); } 00559 00560 void 00561 insert_after(iterator __pos, size_type __n, const value_type& __x) 00562 { _M_insert_after_fill(__pos._M_node, __n, __x); } 00563 00564 // We don't need any dispatching tricks here, because 00565 // _M_insert_after_range already does them. 00566 template <class _InIterator> 00567 void 00568 insert_after(iterator __pos, _InIterator __first, _InIterator __last) 00569 { _M_insert_after_range(__pos._M_node, __first, __last); } 00570 00571 iterator 00572 insert(iterator __pos, const value_type& __x) 00573 { return iterator(_M_insert_after(__slist_previous(&this->_M_head, 00574 __pos._M_node), 00575 __x)); } 00576 00577 iterator 00578 insert(iterator __pos) 00579 { return iterator(_M_insert_after(__slist_previous(&this->_M_head, 00580 __pos._M_node), 00581 value_type())); } 00582 00583 void 00584 insert(iterator __pos, size_type __n, const value_type& __x) 00585 { _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node), 00586 __n, __x); } 00587 00588 // We don't need any dispatching tricks here, because 00589 // _M_insert_after_range already does them. 00590 template <class _InIterator> 00591 void 00592 insert(iterator __pos, _InIterator __first, _InIterator __last) 00593 { _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), 00594 __first, __last); } 00595 00596 public: 00597 iterator 00598 erase_after(iterator __pos) 00599 { return iterator((_Node*) this->_M_erase_after(__pos._M_node)); } 00600 00601 iterator 00602 erase_after(iterator __before_first, iterator __last) 00603 { 00604 return iterator((_Node*) this->_M_erase_after(__before_first._M_node, 00605 __last._M_node)); 00606 } 00607 00608 iterator 00609 erase(iterator __pos) 00610 { 00611 return iterator((_Node*) this->_M_erase_after 00612 (__slist_previous(&this->_M_head, __pos._M_node))); 00613 } 00614 00615 iterator 00616 erase(iterator __first, iterator __last) 00617 { 00618 return iterator((_Node*) this->_M_erase_after 00619 (__slist_previous(&this->_M_head, __first._M_node), 00620 __last._M_node)); 00621 } 00622 00623 void 00624 resize(size_type new_size, const _Tp& __x); 00625 00626 void 00627 resize(size_type new_size) 00628 { resize(new_size, _Tp()); } 00629 00630 void 00631 clear() 00632 { this->_M_erase_after(&this->_M_head, 0); } 00633 00634 public: 00635 // Moves the range [__before_first + 1, __before_last + 1) to *this, 00636 // inserting it immediately after __pos. This is constant time. 00637 void 00638 splice_after(iterator __pos, 00639 iterator __before_first, iterator __before_last) 00640 { 00641 if (__before_first != __before_last) 00642 __slist_splice_after(__pos._M_node, __before_first._M_node, 00643 __before_last._M_node); 00644 } 00645 00646 // Moves the element that follows __prev to *this, inserting it 00647 // immediately after __pos. This is constant time. 00648 void 00649 splice_after(iterator __pos, iterator __prev) 00650 { __slist_splice_after(__pos._M_node, 00651 __prev._M_node, __prev._M_node->_M_next); } 00652 00653 // Removes all of the elements from the list __x to *this, inserting 00654 // them immediately after __pos. __x must not be *this. Complexity: 00655 // linear in __x.size(). 00656 void 00657 splice_after(iterator __pos, slist& __x) 00658 { __slist_splice_after(__pos._M_node, &__x._M_head); } 00659 00660 // Linear in distance(begin(), __pos), and linear in __x.size(). 00661 void 00662 splice(iterator __pos, slist& __x) 00663 { 00664 if (__x._M_head._M_next) 00665 __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), 00666 &__x._M_head, 00667 __slist_previous(&__x._M_head, 0)); } 00668 00669 // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i). 00670 void 00671 splice(iterator __pos, slist& __x, iterator __i) 00672 { __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), 00673 __slist_previous(&__x._M_head, __i._M_node), 00674 __i._M_node); } 00675 00676 // Linear in distance(begin(), __pos), in distance(__x.begin(), __first), 00677 // and in distance(__first, __last). 00678 void 00679 splice(iterator __pos, slist& __x, iterator __first, iterator __last) 00680 { 00681 if (__first != __last) 00682 __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), 00683 __slist_previous(&__x._M_head, __first._M_node), 00684 __slist_previous(__first._M_node, 00685 __last._M_node)); 00686 } 00687 00688 public: 00689 void 00690 reverse() 00691 { 00692 if (this->_M_head._M_next) 00693 this->_M_head._M_next = __slist_reverse(this->_M_head._M_next); 00694 } 00695 00696 void 00697 remove(const _Tp& __val); 00698 00699 void 00700 unique(); 00701 00702 void 00703 merge(slist& __x); 00704 00705 void 00706 sort(); 00707 00708 template <class _Predicate> 00709 void 00710 remove_if(_Predicate __pred); 00711 00712 template <class _BinaryPredicate> 00713 void 00714 unique(_BinaryPredicate __pred); 00715 00716 template <class _StrictWeakOrdering> 00717 void 00718 merge(slist&, _StrictWeakOrdering); 00719 00720 template <class _StrictWeakOrdering> 00721 void 00722 sort(_StrictWeakOrdering __comp); 00723 }; 00724 00725 template <class _Tp, class _Alloc> 00726 slist<_Tp, _Alloc>& 00727 slist<_Tp, _Alloc>::operator=(const slist<_Tp, _Alloc>& __x) 00728 { 00729 if (&__x != this) 00730 { 00731 _Node_base* __p1 = &this->_M_head; 00732 _Node* __n1 = (_Node*) this->_M_head._M_next; 00733 const _Node* __n2 = (const _Node*) __x._M_head._M_next; 00734 while (__n1 && __n2) 00735 { 00736 __n1->_M_data = __n2->_M_data; 00737 __p1 = __n1; 00738 __n1 = (_Node*) __n1->_M_next; 00739 __n2 = (const _Node*) __n2->_M_next; 00740 } 00741 if (__n2 == 0) 00742 this->_M_erase_after(__p1, 0); 00743 else 00744 _M_insert_after_range(__p1, const_iterator((_Node*)__n2), 00745 const_iterator(0)); 00746 } 00747 return *this; 00748 } 00749 00750 template <class _Tp, class _Alloc> 00751 void 00752 slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) 00753 { 00754 _Node_base* __prev = &this->_M_head; 00755 _Node* __node = (_Node*) this->_M_head._M_next; 00756 for (; __node != 0 && __n > 0; --__n) 00757 { 00758 __node->_M_data = __val; 00759 __prev = __node; 00760 __node = (_Node*) __node->_M_next; 00761 } 00762 if (__n > 0) 00763 _M_insert_after_fill(__prev, __n, __val); 00764 else 00765 this->_M_erase_after(__prev, 0); 00766 } 00767 00768 template <class _Tp, class _Alloc> 00769 template <class _InputIterator> 00770 void 00771 slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIterator __first, 00772 _InputIterator __last, 00773 __false_type) 00774 { 00775 _Node_base* __prev = &this->_M_head; 00776 _Node* __node = (_Node*) this->_M_head._M_next; 00777 while (__node != 0 && __first != __last) 00778 { 00779 __node->_M_data = *__first; 00780 __prev = __node; 00781 __node = (_Node*) __node->_M_next; 00782 ++__first; 00783 } 00784 if (__first != __last) 00785 _M_insert_after_range(__prev, __first, __last); 00786 else 00787 this->_M_erase_after(__prev, 0); 00788 } 00789 00790 template <class _Tp, class _Alloc> 00791 inline bool 00792 operator==(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 00793 { 00794 typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator; 00795 const_iterator __end1 = _SL1.end(); 00796 const_iterator __end2 = _SL2.end(); 00797 00798 const_iterator __i1 = _SL1.begin(); 00799 const_iterator __i2 = _SL2.begin(); 00800 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) 00801 { 00802 ++__i1; 00803 ++__i2; 00804 } 00805 return __i1 == __end1 && __i2 == __end2; 00806 } 00807 00808 00809 template <class _Tp, class _Alloc> 00810 inline bool 00811 operator<(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 00812 { return std::lexicographical_compare(_SL1.begin(), _SL1.end(), 00813 _SL2.begin(), _SL2.end()); } 00814 00815 template <class _Tp, class _Alloc> 00816 inline bool 00817 operator!=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 00818 { return !(_SL1 == _SL2); } 00819 00820 template <class _Tp, class _Alloc> 00821 inline bool 00822 operator>(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 00823 { return _SL2 < _SL1; } 00824 00825 template <class _Tp, class _Alloc> 00826 inline bool 00827 operator<=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 00828 { return !(_SL2 < _SL1); } 00829 00830 template <class _Tp, class _Alloc> 00831 inline bool 00832 operator>=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 00833 { return !(_SL1 < _SL2); } 00834 00835 template <class _Tp, class _Alloc> 00836 inline void 00837 swap(slist<_Tp, _Alloc>& __x, slist<_Tp, _Alloc>& __y) 00838 { __x.swap(__y); } 00839 00840 template <class _Tp, class _Alloc> 00841 void 00842 slist<_Tp, _Alloc>::resize(size_type __len, const _Tp& __x) 00843 { 00844 _Node_base* __cur = &this->_M_head; 00845 while (__cur->_M_next != 0 && __len > 0) 00846 { 00847 --__len; 00848 __cur = __cur->_M_next; 00849 } 00850 if (__cur->_M_next) 00851 this->_M_erase_after(__cur, 0); 00852 else 00853 _M_insert_after_fill(__cur, __len, __x); 00854 } 00855 00856 template <class _Tp, class _Alloc> 00857 void 00858 slist<_Tp, _Alloc>::remove(const _Tp& __val) 00859 { 00860 _Node_base* __cur = &this->_M_head; 00861 while (__cur && __cur->_M_next) 00862 { 00863 if (((_Node*) __cur->_M_next)->_M_data == __val) 00864 this->_M_erase_after(__cur); 00865 else 00866 __cur = __cur->_M_next; 00867 } 00868 } 00869 00870 template <class _Tp, class _Alloc> 00871 void 00872 slist<_Tp, _Alloc>::unique() 00873 { 00874 _Node_base* __cur = this->_M_head._M_next; 00875 if (__cur) 00876 { 00877 while (__cur->_M_next) 00878 { 00879 if (((_Node*)__cur)->_M_data 00880 == ((_Node*)(__cur->_M_next))->_M_data) 00881 this->_M_erase_after(__cur); 00882 else 00883 __cur = __cur->_M_next; 00884 } 00885 } 00886 } 00887 00888 template <class _Tp, class _Alloc> 00889 void 00890 slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x) 00891 { 00892 _Node_base* __n1 = &this->_M_head; 00893 while (__n1->_M_next && __x._M_head._M_next) 00894 { 00895 if (((_Node*) __x._M_head._M_next)->_M_data 00896 < ((_Node*) __n1->_M_next)->_M_data) 00897 __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); 00898 __n1 = __n1->_M_next; 00899 } 00900 if (__x._M_head._M_next) 00901 { 00902 __n1->_M_next = __x._M_head._M_next; 00903 __x._M_head._M_next = 0; 00904 } 00905 } 00906 00907 template <class _Tp, class _Alloc> 00908 void 00909 slist<_Tp, _Alloc>::sort() 00910 { 00911 if (this->_M_head._M_next && this->_M_head._M_next->_M_next) 00912 { 00913 slist __carry; 00914 slist __counter[64]; 00915 int __fill = 0; 00916 while (!empty()) 00917 { 00918 __slist_splice_after(&__carry._M_head, 00919 &this->_M_head, this->_M_head._M_next); 00920 int __i = 0; 00921 while (__i < __fill && !__counter[__i].empty()) 00922 { 00923 __counter[__i].merge(__carry); 00924 __carry.swap(__counter[__i]); 00925 ++__i; 00926 } 00927 __carry.swap(__counter[__i]); 00928 if (__i == __fill) 00929 ++__fill; 00930 } 00931 00932 for (int __i = 1; __i < __fill; ++__i) 00933 __counter[__i].merge(__counter[__i-1]); 00934 this->swap(__counter[__fill-1]); 00935 } 00936 } 00937 00938 template <class _Tp, class _Alloc> 00939 template <class _Predicate> 00940 void slist<_Tp, _Alloc>::remove_if(_Predicate __pred) 00941 { 00942 _Node_base* __cur = &this->_M_head; 00943 while (__cur->_M_next) 00944 { 00945 if (__pred(((_Node*) __cur->_M_next)->_M_data)) 00946 this->_M_erase_after(__cur); 00947 else 00948 __cur = __cur->_M_next; 00949 } 00950 } 00951 00952 template <class _Tp, class _Alloc> 00953 template <class _BinaryPredicate> 00954 void 00955 slist<_Tp, _Alloc>::unique(_BinaryPredicate __pred) 00956 { 00957 _Node* __cur = (_Node*) this->_M_head._M_next; 00958 if (__cur) 00959 { 00960 while (__cur->_M_next) 00961 { 00962 if (__pred(((_Node*)__cur)->_M_data, 00963 ((_Node*)(__cur->_M_next))->_M_data)) 00964 this->_M_erase_after(__cur); 00965 else 00966 __cur = (_Node*) __cur->_M_next; 00967 } 00968 } 00969 } 00970 00971 template <class _Tp, class _Alloc> 00972 template <class _StrictWeakOrdering> 00973 void 00974 slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x, 00975 _StrictWeakOrdering __comp) 00976 { 00977 _Node_base* __n1 = &this->_M_head; 00978 while (__n1->_M_next && __x._M_head._M_next) 00979 { 00980 if (__comp(((_Node*) __x._M_head._M_next)->_M_data, 00981 ((_Node*) __n1->_M_next)->_M_data)) 00982 __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); 00983 __n1 = __n1->_M_next; 00984 } 00985 if (__x._M_head._M_next) 00986 { 00987 __n1->_M_next = __x._M_head._M_next; 00988 __x._M_head._M_next = 0; 00989 } 00990 } 00991 00992 template <class _Tp, class _Alloc> 00993 template <class _StrictWeakOrdering> 00994 void 00995 slist<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp) 00996 { 00997 if (this->_M_head._M_next && this->_M_head._M_next->_M_next) 00998 { 00999 slist __carry; 01000 slist __counter[64]; 01001 int __fill = 0; 01002 while (!empty()) 01003 { 01004 __slist_splice_after(&__carry._M_head, 01005 &this->_M_head, this->_M_head._M_next); 01006 int __i = 0; 01007 while (__i < __fill && !__counter[__i].empty()) 01008 { 01009 __counter[__i].merge(__carry, __comp); 01010 __carry.swap(__counter[__i]); 01011 ++__i; 01012 } 01013 __carry.swap(__counter[__i]); 01014 if (__i == __fill) 01015 ++__fill; 01016 } 01017 01018 for (int __i = 1; __i < __fill; ++__i) 01019 __counter[__i].merge(__counter[__i-1], __comp); 01020 this->swap(__counter[__fill-1]); 01021 } 01022 } 01023 01024 _GLIBCXX_END_NAMESPACE 01025 01026 _GLIBCXX_BEGIN_NAMESPACE(std) 01027 01028 // Specialization of insert_iterator so that insertions will be constant 01029 // time rather than linear time. 01030 template <class _Tp, class _Alloc> 01031 class insert_iterator<__gnu_cxx::slist<_Tp, _Alloc> > 01032 { 01033 protected: 01034 typedef __gnu_cxx::slist<_Tp, _Alloc> _Container; 01035 _Container* container; 01036 typename _Container::iterator iter; 01037 01038 public: 01039 typedef _Container container_type; 01040 typedef output_iterator_tag iterator_category; 01041 typedef void value_type; 01042 typedef void difference_type; 01043 typedef void pointer; 01044 typedef void reference; 01045 01046 insert_iterator(_Container& __x, typename _Container::iterator __i) 01047 : container(&__x) 01048 { 01049 if (__i == __x.begin()) 01050 iter = __x.before_begin(); 01051 else 01052 iter = __x.previous(__i); 01053 } 01054 01055 insert_iterator<_Container>& 01056 operator=(const typename _Container::value_type& __value) 01057 { 01058 iter = container->insert_after(iter, __value); 01059 return *this; 01060 } 01061 01062 insert_iterator<_Container>& 01063 operator*() 01064 { return *this; } 01065 01066 insert_iterator<_Container>& 01067 operator++() 01068 { return *this; } 01069 01070 insert_iterator<_Container>& 01071 operator++(int) 01072 { return *this; } 01073 }; 01074 01075 _GLIBCXX_END_NAMESPACE 01076 01077 #endif