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