stl_list.h

Go to the documentation of this file.
00001 // List implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002 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 2, 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 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * 00044 * Copyright (c) 1996,1997 00045 * Silicon Graphics Computer Systems, Inc. 00046 * 00047 * Permission to use, copy, modify, distribute and sell this software 00048 * and its documentation for any purpose is hereby granted without fee, 00049 * provided that the above copyright notice appear in all copies and 00050 * that both that copyright notice and this permission notice appear 00051 * in supporting documentation. Silicon Graphics makes no 00052 * representations about the suitability of this software for any 00053 * purpose. It is provided "as is" without express or implied warranty. 00054 */ 00055 00061 #ifndef __GLIBCPP_INTERNAL_LIST_H 00062 #define __GLIBCPP_INTERNAL_LIST_H 00063 00064 #include <bits/concept_check.h> 00065 00066 namespace std 00067 { 00068 00069 struct _List_node_base 00070 { 00071 _List_node_base* _M_next; 00072 _List_node_base* _M_prev; 00073 }; 00074 00075 template<typename _Tp> 00076 struct _List_node : public _List_node_base 00077 { 00078 _Tp _M_data; 00079 }; 00080 00081 struct _List_iterator_base 00082 { 00083 typedef size_t size_type; 00084 typedef ptrdiff_t difference_type; 00085 typedef bidirectional_iterator_tag iterator_category; 00086 00087 _List_node_base* _M_node; 00088 00089 _List_iterator_base(_List_node_base* __x) 00090 : _M_node(__x) 00091 { } 00092 00093 _List_iterator_base() 00094 { } 00095 00096 void 00097 _M_incr() 00098 { _M_node = _M_node->_M_next; } 00099 00100 void 00101 _M_decr() 00102 { _M_node = _M_node->_M_prev; } 00103 00104 bool 00105 operator==(const _List_iterator_base& __x) const 00106 { return _M_node == __x._M_node; } 00107 00108 bool 00109 operator!=(const _List_iterator_base& __x) const 00110 { return _M_node != __x._M_node; } 00111 }; 00112 00113 template<typename _Tp, typename _Ref, typename _Ptr> 00114 struct _List_iterator : public _List_iterator_base 00115 { 00116 typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; 00117 typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; 00118 typedef _List_iterator<_Tp,_Ref,_Ptr> _Self; 00119 00120 typedef _Tp value_type; 00121 typedef _Ptr pointer; 00122 typedef _Ref reference; 00123 typedef _List_node<_Tp> _Node; 00124 00125 _List_iterator(_Node* __x) 00126 : _List_iterator_base(__x) 00127 { } 00128 00129 _List_iterator() 00130 { } 00131 00132 _List_iterator(const iterator& __x) 00133 : _List_iterator_base(__x._M_node) 00134 { } 00135 00136 reference 00137 operator*() const 00138 { return ((_Node*) _M_node)->_M_data; } 00139 00140 pointer 00141 operator->() const 00142 { return &(operator*()); } 00143 00144 _Self& 00145 operator++() 00146 { 00147 this->_M_incr(); 00148 return *this; 00149 } 00150 00151 _Self 00152 operator++(int) 00153 { 00154 _Self __tmp = *this; 00155 this->_M_incr(); 00156 return __tmp; 00157 } 00158 00159 _Self& 00160 operator--() 00161 { 00162 this->_M_decr(); 00163 return *this; 00164 } 00165 00166 _Self 00167 operator--(int) 00168 { 00169 _Self __tmp = *this; 00170 this->_M_decr(); 00171 return __tmp; 00172 } 00173 }; 00174 00175 00176 // Base class that encapsulates details of allocators. Three cases: 00177 // an ordinary standard-conforming allocator, a standard-conforming 00178 // allocator with no non-static data, and an SGI-style allocator. 00179 // This complexity is necessary only because we're worrying about backward 00180 // compatibility and because we want to avoid wasting storage on an 00181 // allocator instance if it isn't necessary. 00182 00183 00184 // Base for general standard-conforming allocators. 00185 template<typename _Tp, typename _Allocator, bool _IsStatic> 00186 class _List_alloc_base 00187 { 00188 public: 00189 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type 00190 allocator_type; 00191 00192 allocator_type 00193 get_allocator() const 00194 { return _Node_allocator; } 00195 00196 _List_alloc_base(const allocator_type& __a) 00197 : _Node_allocator(__a) 00198 { } 00199 00200 protected: 00201 _List_node<_Tp>* 00202 _M_get_node() 00203 { return _Node_allocator.allocate(1); } 00204 00205 void 00206 _M_put_node(_List_node<_Tp>* __p) 00207 { _Node_allocator.deallocate(__p, 1); } 00208 00209 protected: 00210 typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type 00211 _Node_allocator; 00212 00213 _List_node<_Tp>* _M_node; 00214 }; 00215 00216 // Specialization for instanceless allocators. 00217 00218 template<typename _Tp, typename _Allocator> 00219 class _List_alloc_base<_Tp, _Allocator, true> 00220 { 00221 public: 00222 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type 00223 allocator_type; 00224 00225 allocator_type 00226 get_allocator() const 00227 { return allocator_type(); } 00228 00229 _List_alloc_base(const allocator_type&) 00230 { } 00231 00232 protected: 00233 typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type 00234 _Alloc_type; 00235 00236 _List_node<_Tp>* 00237 _M_get_node() 00238 { return _Alloc_type::allocate(1); } 00239 00240 void 00241 _M_put_node(_List_node<_Tp>* __p) 00242 { _Alloc_type::deallocate(__p, 1); } 00243 00244 protected: 00245 _List_node<_Tp>* _M_node; 00246 }; 00247 00248 template<typename _Tp, typename _Alloc> 00249 class _List_base 00250 : public _List_alloc_base<_Tp, _Alloc, 00251 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 00252 { 00253 public: 00254 typedef _List_alloc_base<_Tp, _Alloc, 00255 _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 00256 _Base; 00257 typedef typename _Base::allocator_type allocator_type; 00258 00259 _List_base(const allocator_type& __a) 00260 : _Base(__a) 00261 { 00262 _M_node = _M_get_node(); 00263 _M_node->_M_next = _M_node; 00264 _M_node->_M_prev = _M_node; 00265 } 00266 00267 ~_List_base() 00268 { 00269 clear(); 00270 _M_put_node(_M_node); 00271 } 00272 00273 void clear(); 00274 }; 00275 00289 template<typename _Tp, typename _Alloc = allocator<_Tp> > 00290 class list : protected _List_base<_Tp, _Alloc> 00291 { 00292 // concept requirements 00293 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 00294 00295 typedef _List_base<_Tp, _Alloc> _Base; 00296 protected: 00297 typedef void* _Void_pointer; 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 _List_node<_Tp> _Node; 00306 typedef size_t size_type; 00307 typedef ptrdiff_t difference_type; 00308 00309 typedef typename _Base::allocator_type allocator_type; 00310 00311 typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; 00312 typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; 00313 00314 typedef reverse_iterator<const_iterator> const_reverse_iterator; 00315 typedef reverse_iterator<iterator> reverse_iterator; 00316 00317 protected: 00318 using _Base::_M_node; 00319 using _Base::_M_put_node; 00320 using _Base::_M_get_node; 00321 00322 protected: 00323 _Node* 00324 _M_create_node(const _Tp& __x) 00325 { 00326 _Node* __p = _M_get_node(); 00327 try { 00328 _Construct(&__p->_M_data, __x); 00329 } 00330 catch(...) 00331 { 00332 _M_put_node(__p); 00333 __throw_exception_again; 00334 } 00335 return __p; 00336 } 00337 00338 _Node* 00339 _M_create_node() 00340 { 00341 _Node* __p = _M_get_node(); 00342 try { 00343 _Construct(&__p->_M_data); 00344 } 00345 catch(...) 00346 { 00347 _M_put_node(__p); 00348 __throw_exception_again; 00349 } 00350 return __p; 00351 } 00352 00353 public: 00354 allocator_type 00355 get_allocator() const 00356 { return _Base::get_allocator(); } 00357 00358 explicit 00359 list(const allocator_type& __a = allocator_type()) 00360 : _Base(__a) 00361 { } 00362 00363 iterator 00364 begin() 00365 { return static_cast<_Node*>(_M_node->_M_next); } 00366 00367 const_iterator 00368 begin() const 00369 { return static_cast<_Node*>(_M_node->_M_next); } 00370 00371 iterator 00372 end() 00373 { return _M_node; } 00374 00375 const_iterator 00376 end() const 00377 { return _M_node; } 00378 00379 reverse_iterator 00380 rbegin() 00381 { return reverse_iterator(end()); } 00382 00383 const_reverse_iterator 00384 rbegin() const 00385 { return const_reverse_iterator(end()); } 00386 00387 reverse_iterator 00388 rend() 00389 { return reverse_iterator(begin()); } 00390 00391 const_reverse_iterator 00392 rend() const 00393 { return const_reverse_iterator(begin()); } 00394 00395 bool 00396 empty() const 00397 { return _M_node->_M_next == _M_node; } 00398 00399 size_type 00400 size() const 00401 { return distance(begin(), end()); } 00402 00403 size_type 00404 max_size() const 00405 { return size_type(-1); } 00406 00407 reference 00408 front() 00409 { return *begin(); } 00410 00411 const_reference 00412 front() const 00413 { return *begin(); } 00414 00415 reference 00416 back() 00417 { return *(--end()); } 00418 00419 const_reference 00420 back() const 00421 { return *(--end()); } 00422 00423 void 00424 swap(list<_Tp, _Alloc>& __x) 00425 { std::swap(_M_node, __x._M_node); } 00426 00427 iterator 00428 insert(iterator __position, const _Tp& __x) 00429 { 00430 _Node* __tmp = _M_create_node(__x); 00431 __tmp->_M_next = __position._M_node; 00432 __tmp->_M_prev = __position._M_node->_M_prev; 00433 __position._M_node->_M_prev->_M_next = __tmp; 00434 __position._M_node->_M_prev = __tmp; 00435 return __tmp; 00436 } 00437 00438 iterator 00439 insert(iterator __position) 00440 { return insert(__position, _Tp()); } 00441 00442 // Check whether it's an integral type. If so, it's not an iterator. 00443 template<typename _Integer> 00444 void 00445 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type) 00446 { _M_fill_insert(__pos, (size_type) __n, (_Tp) __x); } 00447 00448 template<typename _InputIterator> 00449 void 00450 _M_insert_dispatch(iterator __pos, 00451 _InputIterator __first, _InputIterator __last, 00452 __false_type); 00453 00454 template<typename _InputIterator> 00455 void 00456 insert(iterator __pos, _InputIterator __first, _InputIterator __last) 00457 { 00458 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 00459 _M_insert_dispatch(__pos, __first, __last, _Integral()); 00460 } 00461 00462 void 00463 insert(iterator __pos, size_type __n, const _Tp& __x) 00464 { _M_fill_insert(__pos, __n, __x); } 00465 00466 void 00467 _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x); 00468 00469 void 00470 push_front(const _Tp& __x) 00471 { insert(begin(), __x); } 00472 00473 void 00474 push_front() 00475 { insert(begin()); } 00476 00477 void 00478 push_back(const _Tp& __x) 00479 { insert(end(), __x); } 00480 00481 void 00482 push_back() 00483 { insert(end()); } 00484 00485 iterator 00486 erase(iterator __position) 00487 { 00488 _List_node_base* __next_node = __position._M_node->_M_next; 00489 _List_node_base* __prev_node = __position._M_node->_M_prev; 00490 _Node* __n = static_cast<_Node*>(__position._M_node); 00491 __prev_node->_M_next = __next_node; 00492 __next_node->_M_prev = __prev_node; 00493 _Destroy(&__n->_M_data); 00494 _M_put_node(__n); 00495 return iterator(static_cast<_Node*>(__next_node)); 00496 } 00497 00498 iterator 00499 erase(iterator __first, iterator __last); 00500 00501 void 00502 clear() 00503 { _Base::clear(); } 00504 00505 void 00506 resize(size_type __new_size, const _Tp& __x); 00507 00508 void 00509 resize(size_type __new_size) 00510 { this->resize(__new_size, _Tp()); } 00511 00512 void 00513 pop_front() 00514 { erase(begin()); } 00515 00516 void 00517 pop_back() 00518 { 00519 iterator __tmp = end(); 00520 erase(--__tmp); 00521 } 00522 00523 list(size_type __n, const _Tp& __value, 00524 const allocator_type& __a = allocator_type()) 00525 : _Base(__a) 00526 { insert(begin(), __n, __value); } 00527 00528 explicit 00529 list(size_type __n) 00530 : _Base(allocator_type()) 00531 { insert(begin(), __n, _Tp()); } 00532 00533 // We don't need any dispatching tricks here, because insert does all of 00534 // that anyway. 00535 template<typename _InputIterator> 00536 list(_InputIterator __first, _InputIterator __last, 00537 const allocator_type& __a = allocator_type()) 00538 : _Base(__a) 00539 { insert(begin(), __first, __last); } 00540 00541 list(const list<_Tp, _Alloc>& __x) 00542 : _Base(__x.get_allocator()) 00543 { insert(begin(), __x.begin(), __x.end()); } 00544 00545 ~list() 00546 { } 00547 00548 list<_Tp, _Alloc>& 00549 operator=(const list<_Tp, _Alloc>& __x); 00550 00551 public: 00552 // assign(), a generalized assignment member function. Two 00553 // versions: one that takes a count, and one that takes a range. 00554 // The range version is a member template, so we dispatch on whether 00555 // or not the type is an integer. 00556 00557 void 00558 assign(size_type __n, const _Tp& __val) 00559 { _M_fill_assign(__n, __val); } 00560 00561 void 00562 _M_fill_assign(size_type __n, const _Tp& __val); 00563 00564 template<typename _InputIterator> 00565 void 00566 assign(_InputIterator __first, _InputIterator __last) 00567 { 00568 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 00569 _M_assign_dispatch(__first, __last, _Integral()); 00570 } 00571 00572 template<typename _Integer> 00573 void 00574 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 00575 { _M_fill_assign((size_type) __n, (_Tp) __val); } 00576 00577 template<typename _InputIterator> 00578 void 00579 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 00580 __false_type); 00581 00582 protected: 00583 void 00584 _M_transfer(iterator __position, iterator __first, iterator __last) 00585 { 00586 if (__position != __last) { 00587 // Remove [first, last) from its old position. 00588 __last._M_node->_M_prev->_M_next = __position._M_node; 00589 __first._M_node->_M_prev->_M_next = __last._M_node; 00590 __position._M_node->_M_prev->_M_next = __first._M_node; 00591 00592 // Splice [first, last) into its new position. 00593 _List_node_base* __tmp = __position._M_node->_M_prev; 00594 __position._M_node->_M_prev = __last._M_node->_M_prev; 00595 __last._M_node->_M_prev = __first._M_node->_M_prev; 00596 __first._M_node->_M_prev = __tmp; 00597 } 00598 } 00599 00600 public: 00601 void 00602 splice(iterator __position, list& __x) 00603 { 00604 if (!__x.empty()) 00605 this->_M_transfer(__position, __x.begin(), __x.end()); 00606 } 00607 00608 void 00609 splice(iterator __position, list&, iterator __i) 00610 { 00611 iterator __j = __i; 00612 ++__j; 00613 if (__position == __i || __position == __j) return; 00614 this->_M_transfer(__position, __i, __j); 00615 } 00616 00617 void 00618 splice(iterator __position, list&, iterator __first, iterator __last) 00619 { 00620 if (__first != __last) 00621 this->_M_transfer(__position, __first, __last); 00622 } 00623 00624 void 00625 remove(const _Tp& __value); 00626 00627 void 00628 unique(); 00629 00630 void 00631 merge(list& __x); 00632 00633 void 00634 reverse(); 00635 00636 void 00637 sort(); 00638 00639 template<typename _Predicate> 00640 void 00641 remove_if(_Predicate); 00642 00643 template<typename _BinaryPredicate> 00644 void 00645 unique(_BinaryPredicate); 00646 00647 template<typename _StrictWeakOrdering> 00648 void 00649 merge(list&, _StrictWeakOrdering); 00650 00651 template<typename _StrictWeakOrdering> 00652 void 00653 sort(_StrictWeakOrdering); 00654 }; 00655 00656 template<typename _Tp, typename _Alloc> 00657 inline bool 00658 operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) 00659 { 00660 typedef typename list<_Tp,_Alloc>::const_iterator const_iterator; 00661 const_iterator __end1 = __x.end(); 00662 const_iterator __end2 = __y.end(); 00663 00664 const_iterator __i1 = __x.begin(); 00665 const_iterator __i2 = __y.begin(); 00666 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) { 00667 ++__i1; 00668 ++__i2; 00669 } 00670 return __i1 == __end1 && __i2 == __end2; 00671 } 00672 00673 template<typename _Tp, typename _Alloc> 00674 inline bool 00675 operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) 00676 { 00677 return lexicographical_compare(__x.begin(), __x.end(), 00678 __y.begin(), __y.end()); 00679 } 00680 00681 template<typename _Tp, typename _Alloc> 00682 inline bool 00683 operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) 00684 { return !(__x == __y); } 00685 00686 template<typename _Tp, typename _Alloc> 00687 inline bool 00688 operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) 00689 { return __y < __x; } 00690 00691 template<typename _Tp, typename _Alloc> 00692 inline bool 00693 operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) 00694 { return !(__y < __x); } 00695 00696 template<typename _Tp, typename _Alloc> 00697 inline bool 00698 operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) 00699 { return !(__x < __y); } 00700 00701 template<typename _Tp, typename _Alloc> 00702 inline void 00703 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 00704 { __x.swap(__y); } 00705 00706 // move these to stl_list.tcc 00707 00708 template<typename _Tp, typename _Alloc> 00709 void _List_base<_Tp,_Alloc>:: 00710 clear() 00711 { 00712 _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node->_M_next); 00713 while (__cur != _M_node) { 00714 _List_node<_Tp>* __tmp = __cur; 00715 __cur = static_cast<_List_node<_Tp>*>(__cur->_M_next); 00716 _Destroy(&__tmp->_M_data); 00717 _M_put_node(__tmp); 00718 } 00719 _M_node->_M_next = _M_node; 00720 _M_node->_M_prev = _M_node; 00721 } 00722 00723 template<typename _Tp, typename _Alloc> 00724 template <typename _InputIter> 00725 void list<_Tp, _Alloc>:: 00726 _M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last, 00727 __false_type) 00728 { 00729 for ( ; __first != __last; ++__first) 00730 insert(__position, *__first); 00731 00732 } 00733 00734 template<typename _Tp, typename _Alloc> 00735 void list<_Tp, _Alloc>:: 00736 _M_fill_insert(iterator __position, size_type __n, const _Tp& __x) 00737 { 00738 for ( ; __n > 0; --__n) 00739 insert(__position, __x); 00740 } 00741 00742 template<typename _Tp, typename _Alloc> 00743 typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>:: 00744 erase(iterator __first, iterator __last) 00745 { 00746 while (__first != __last) 00747 erase(__first++); 00748 return __last; 00749 } 00750 00751 template<typename _Tp, typename _Alloc> 00752 void list<_Tp, _Alloc>:: 00753 resize(size_type __new_size, const _Tp& __x) 00754 { 00755 iterator __i = begin(); 00756 size_type __len = 0; 00757 for ( ; __i != end() && __len < __new_size; ++__i, ++__len) 00758 ; 00759 if (__len == __new_size) 00760 erase(__i, end()); 00761 else // __i == end() 00762 insert(end(), __new_size - __len, __x); 00763 } 00764 00765 template<typename _Tp, typename _Alloc> 00766 list<_Tp, _Alloc>& list<_Tp, _Alloc>:: 00767 operator=(const list<_Tp, _Alloc>& __x) 00768 { 00769 if (this != &__x) { 00770 iterator __first1 = begin(); 00771 iterator __last1 = end(); 00772 const_iterator __first2 = __x.begin(); 00773 const_iterator __last2 = __x.end(); 00774 while (__first1 != __last1 && __first2 != __last2) 00775 *__first1++ = *__first2++; 00776 if (__first2 == __last2) 00777 erase(__first1, __last1); 00778 else 00779 insert(__last1, __first2, __last2); 00780 } 00781 return *this; 00782 } 00783 00784 template<typename _Tp, typename _Alloc> 00785 void list<_Tp, _Alloc>:: 00786 _M_fill_assign(size_type __n, const _Tp& __val) { 00787 iterator __i = begin(); 00788 for ( ; __i != end() && __n > 0; ++__i, --__n) 00789 *__i = __val; 00790 if (__n > 0) 00791 insert(end(), __n, __val); 00792 else 00793 erase(__i, end()); 00794 } 00795 00796 template<typename _Tp, typename _Alloc> 00797 template <typename _InputIter> 00798 void list<_Tp, _Alloc>:: 00799 _M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type) 00800 { 00801 iterator __first1 = begin(); 00802 iterator __last1 = end(); 00803 for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) 00804 *__first1 = *__first2; 00805 if (__first2 == __last2) 00806 erase(__first1, __last1); 00807 else 00808 insert(__last1, __first2, __last2); 00809 } 00810 00811 template<typename _Tp, typename _Alloc> 00812 void list<_Tp, _Alloc>:: 00813 remove(const _Tp& __value) 00814 { 00815 iterator __first = begin(); 00816 iterator __last = end(); 00817 while (__first != __last) { 00818 iterator __next = __first; 00819 ++__next; 00820 if (*__first == __value) erase(__first); 00821 __first = __next; 00822 } 00823 } 00824 00825 template<typename _Tp, typename _Alloc> 00826 void list<_Tp, _Alloc>:: 00827 unique() 00828 { 00829 iterator __first = begin(); 00830 iterator __last = end(); 00831 if (__first == __last) return; 00832 iterator __next = __first; 00833 while (++__next != __last) { 00834 if (*__first == *__next) 00835 erase(__next); 00836 else 00837 __first = __next; 00838 __next = __first; 00839 } 00840 } 00841 00842 template<typename _Tp, typename _Alloc> 00843 void list<_Tp, _Alloc>:: 00844 merge(list<_Tp, _Alloc>& __x) 00845 { 00846 iterator __first1 = begin(); 00847 iterator __last1 = end(); 00848 iterator __first2 = __x.begin(); 00849 iterator __last2 = __x.end(); 00850 while (__first1 != __last1 && __first2 != __last2) 00851 if (*__first2 < *__first1) { 00852 iterator __next = __first2; 00853 _M_transfer(__first1, __first2, ++__next); 00854 __first2 = __next; 00855 } 00856 else 00857 ++__first1; 00858 if (__first2 != __last2) _M_transfer(__last1, __first2, __last2); 00859 } 00860 00861 inline void 00862 __List_base_reverse(_List_node_base* __p) 00863 { 00864 _List_node_base* __tmp = __p; 00865 do { 00866 std::swap(__tmp->_M_next, __tmp->_M_prev); 00867 __tmp = __tmp->_M_prev; // Old next node is now prev. 00868 } while (__tmp != __p); 00869 } 00870 00871 template<typename _Tp, typename _Alloc> 00872 inline void list<_Tp, _Alloc>:: 00873 reverse() 00874 { __List_base_reverse(this->_M_node); } 00875 00876 template<typename _Tp, typename _Alloc> 00877 void list<_Tp, _Alloc>:: 00878 sort() 00879 { 00880 // Do nothing if the list has length 0 or 1. 00881 if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) { 00882 list<_Tp, _Alloc> __carry; 00883 list<_Tp, _Alloc> __counter[64]; 00884 int __fill = 0; 00885 while (!empty()) { 00886 __carry.splice(__carry.begin(), *this, begin()); 00887 int __i = 0; 00888 while(__i < __fill && !__counter[__i].empty()) { 00889 __counter[__i].merge(__carry); 00890 __carry.swap(__counter[__i++]); 00891 } 00892 __carry.swap(__counter[__i]); 00893 if (__i == __fill) ++__fill; 00894 } 00895 00896 for (int __i = 1; __i < __fill; ++__i) 00897 __counter[__i].merge(__counter[__i-1]); 00898 swap(__counter[__fill-1]); 00899 } 00900 } 00901 00902 template<typename _Tp, typename _Alloc> 00903 template <typename _Predicate> 00904 void list<_Tp, _Alloc>:: 00905 remove_if(_Predicate __pred) 00906 { 00907 iterator __first = begin(); 00908 iterator __last = end(); 00909 while (__first != __last) { 00910 iterator __next = __first; 00911 ++__next; 00912 if (__pred(*__first)) erase(__first); 00913 __first = __next; 00914 } 00915 } 00916 00917 template<typename _Tp, typename _Alloc> 00918 template <typename _BinaryPredicate> 00919 void list<_Tp, _Alloc>:: 00920 unique(_BinaryPredicate __binary_pred) 00921 { 00922 iterator __first = begin(); 00923 iterator __last = end(); 00924 if (__first == __last) return; 00925 iterator __next = __first; 00926 while (++__next != __last) { 00927 if (__binary_pred(*__first, *__next)) 00928 erase(__next); 00929 else 00930 __first = __next; 00931 __next = __first; 00932 } 00933 } 00934 00935 template<typename _Tp, typename _Alloc> 00936 template <typename _StrictWeakOrdering> 00937 void list<_Tp, _Alloc>:: 00938 merge(list<_Tp, _Alloc>& __x, _StrictWeakOrdering __comp) 00939 { 00940 iterator __first1 = begin(); 00941 iterator __last1 = end(); 00942 iterator __first2 = __x.begin(); 00943 iterator __last2 = __x.end(); 00944 while (__first1 != __last1 && __first2 != __last2) 00945 if (__comp(*__first2, *__first1)) { 00946 iterator __next = __first2; 00947 _M_transfer(__first1, __first2, ++__next); 00948 __first2 = __next; 00949 } 00950 else 00951 ++__first1; 00952 if (__first2 != __last2) _M_transfer(__last1, __first2, __last2); 00953 } 00954 00955 template<typename _Tp, typename _Alloc> 00956 template <typename _StrictWeakOrdering> 00957 void list<_Tp, _Alloc>:: 00958 sort(_StrictWeakOrdering __comp) 00959 { 00960 // Do nothing if the list has length 0 or 1. 00961 if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) { 00962 list<_Tp, _Alloc> __carry; 00963 list<_Tp, _Alloc> __counter[64]; 00964 int __fill = 0; 00965 while (!empty()) { 00966 __carry.splice(__carry.begin(), *this, begin()); 00967 int __i = 0; 00968 while(__i < __fill && !__counter[__i].empty()) { 00969 __counter[__i].merge(__carry, __comp); 00970 __carry.swap(__counter[__i++]); 00971 } 00972 __carry.swap(__counter[__i]); 00973 if (__i == __fill) ++__fill; 00974 } 00975 00976 for (int __i = 1; __i < __fill; ++__i) 00977 __counter[__i].merge(__counter[__i-1], __comp); 00978 swap(__counter[__fill-1]); 00979 } 00980 } 00981 00982 } // namespace std 00983 00984 #endif /* __GLIBCPP_INTERNAL_LIST_H */ 00985 00986 // vi:set ts=2 sw=2: 00987 // Local Variables: 00988 // mode:C++ 00989 // End:

Generated on Wed Sep 29 13:54:52 2004 for libstdc++-v3 Source by doxygen 1.3.7