<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/> <title>libstdc++: slist Source File</title> <link href="tabs.css" rel="stylesheet" type="text/css"/> <link href="navtree.css" rel="stylesheet" type="text/css"/> <script type="text/javascript" src="jquery.js"></script> <script type="text/javascript" src="navtree.js"></script> <script type="text/javascript" src="resize.js"></script> <script type="text/javascript"> $(document).ready(initResizable); </script> <link href="doxygen.css" rel="stylesheet" type="text/css"/> </head> <body> <!-- Generated by Doxygen 1.7.4 --> <div id="top"> <div id="titlearea"> <table cellspacing="0" cellpadding="0"> <tbody> <tr style="height: 56px;"> <td style="padding-left: 0.5em;"> <div id="projectname">libstdc++</div> </td> </tr> </tbody> </table> </div> </div> <div id="side-nav" class="ui-resizable side-nav-resizable"> <div id="nav-tree"> <div id="nav-tree-contents"> </div> </div> <div id="splitbar" style="-moz-user-select:none;" class="ui-resizable-handle"> </div> </div> <script type="text/javascript"> initNavTree('a01033.html',''); </script> <div id="doc-content"> <div class="header"> <div class="headertitle"> <div class="title">slist</div> </div> </div> <div class="contents"> <a href="a01033.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">// Singly-linked list implementation -*- C++ -*-</span> <a name="l00002"></a>00002 <a name="l00003"></a>00003 <span class="comment">// Copyright (C) 2001, 2002, 2004, 2005, 2007, 2008, 2009</span> <a name="l00004"></a>00004 <span class="comment">// Free Software Foundation, Inc.</span> <a name="l00005"></a>00005 <span class="comment">//</span> <a name="l00006"></a>00006 <span class="comment">// This file is part of the GNU ISO C++ Library. This library is free</span> <a name="l00007"></a>00007 <span class="comment">// software; you can redistribute it and/or modify it under the</span> <a name="l00008"></a>00008 <span class="comment">// terms of the GNU General Public License as published by the</span> <a name="l00009"></a>00009 <span class="comment">// Free Software Foundation; either version 3, or (at your option)</span> <a name="l00010"></a>00010 <span class="comment">// any later version.</span> <a name="l00011"></a>00011 <a name="l00012"></a>00012 <span class="comment">// This library is distributed in the hope that it will be useful,</span> <a name="l00013"></a>00013 <span class="comment">// but WITHOUT ANY WARRANTY; without even the implied warranty of</span> <a name="l00014"></a>00014 <span class="comment">// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the</span> <a name="l00015"></a>00015 <span class="comment">// GNU General Public License for more details.</span> <a name="l00016"></a>00016 <a name="l00017"></a>00017 <span class="comment">// Under Section 7 of GPL version 3, you are granted additional</span> <a name="l00018"></a>00018 <span class="comment">// permissions described in the GCC Runtime Library Exception, version</span> <a name="l00019"></a>00019 <span class="comment">// 3.1, as published by the Free Software Foundation.</span> <a name="l00020"></a>00020 <a name="l00021"></a>00021 <span class="comment">// You should have received a copy of the GNU General Public License and</span> <a name="l00022"></a>00022 <span class="comment">// a copy of the GCC Runtime Library Exception along with this program;</span> <a name="l00023"></a>00023 <span class="comment">// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see</span> <a name="l00024"></a>00024 <span class="comment">// <http://www.gnu.org/licenses/>.</span> <a name="l00025"></a>00025 <a name="l00026"></a>00026 <span class="comment">/*</span> <a name="l00027"></a>00027 <span class="comment"> * Copyright (c) 1997</span> <a name="l00028"></a>00028 <span class="comment"> * Silicon Graphics Computer Systems, Inc.</span> <a name="l00029"></a>00029 <span class="comment"> *</span> <a name="l00030"></a>00030 <span class="comment"> * Permission to use, copy, modify, distribute and sell this software</span> <a name="l00031"></a>00031 <span class="comment"> * and its documentation for any purpose is hereby granted without fee,</span> <a name="l00032"></a>00032 <span class="comment"> * provided that the above copyright notice appear in all copies and</span> <a name="l00033"></a>00033 <span class="comment"> * that both that copyright notice and this permission notice appear</span> <a name="l00034"></a>00034 <span class="comment"> * in supporting documentation. Silicon Graphics makes no</span> <a name="l00035"></a>00035 <span class="comment"> * representations about the suitability of this software for any</span> <a name="l00036"></a>00036 <span class="comment"> * purpose. It is provided "as is" without express or implied warranty.</span> <a name="l00037"></a>00037 <span class="comment"> *</span> <a name="l00038"></a>00038 <span class="comment"> */</span> <a name="l00039"></a>00039 <span class="comment"></span> <a name="l00040"></a>00040 <span class="comment">/** @file ext/slist</span> <a name="l00041"></a>00041 <span class="comment"> * This file is a GNU extension to the Standard C++ Library (possibly</span> <a name="l00042"></a>00042 <span class="comment"> * containing extensions from the HP/SGI STL subset). </span> <a name="l00043"></a>00043 <span class="comment"> */</span> <a name="l00044"></a>00044 <a name="l00045"></a>00045 <span class="preprocessor">#ifndef _SLIST</span> <a name="l00046"></a>00046 <span class="preprocessor"></span><span class="preprocessor">#define _SLIST 1</span> <a name="l00047"></a>00047 <span class="preprocessor"></span> <a name="l00048"></a>00048 <span class="preprocessor">#include <algorithm></span> <a name="l00049"></a>00049 <span class="preprocessor">#include <<a class="code" href="a00751.html">bits/allocator.h</a>></span> <a name="l00050"></a>00050 <span class="preprocessor">#include <<a class="code" href="a01048.html">bits/stl_construct.h</a>></span> <a name="l00051"></a>00051 <span class="preprocessor">#include <<a class="code" href="a01068.html">bits/stl_uninitialized.h</a>></span> <a name="l00052"></a>00052 <span class="preprocessor">#include <<a class="code" href="a00815.html">bits/concept_check.h</a>></span> <a name="l00053"></a>00053 <a name="l00054"></a>00054 <span class="keyword">namespace </span>__gnu_cxx _GLIBCXX_VISIBILITY(default) <a name="l00055"></a>00055 { <a name="l00056"></a>00056 _GLIBCXX_BEGIN_NAMESPACE_VERSION <a name="l00057"></a>00057 <a name="l00058"></a>00058 <span class="keyword">using</span> std::size_t; <a name="l00059"></a>00059 <span class="keyword">using</span> std::ptrdiff_t; <a name="l00060"></a>00060 <span class="keyword">using</span> <a class="code" href="a01137.html#a850d6f37669d9ef68beb276a2623ad75">std::_Construct</a>; <a name="l00061"></a>00061 <span class="keyword">using</span> <a class="code" href="a01137.html#a81deec3b993a64a7a9e1c955fe98f556">std::_Destroy</a>; <a name="l00062"></a>00062 <span class="keyword">using</span> <a class="code" href="a00246.html" title="The standard allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manual...">std::allocator</a>; <a name="l00063"></a>00063 <span class="keyword">using</span> std::__true_type; <a name="l00064"></a>00064 <span class="keyword">using</span> std::__false_type; <a name="l00065"></a>00065 <a name="l00066"></a>00066 <span class="keyword">struct </span>_Slist_node_base <a name="l00067"></a>00067 { <a name="l00068"></a>00068 _Slist_node_base* _M_next; <a name="l00069"></a>00069 }; <a name="l00070"></a>00070 <a name="l00071"></a>00071 <span class="keyword">inline</span> _Slist_node_base* <a name="l00072"></a>00072 __slist_make_link(_Slist_node_base* __prev_node, <a name="l00073"></a>00073 _Slist_node_base* __new_node) <a name="l00074"></a>00074 { <a name="l00075"></a>00075 __new_node->_M_next = __prev_node->_M_next; <a name="l00076"></a>00076 __prev_node->_M_next = __new_node; <a name="l00077"></a>00077 <span class="keywordflow">return</span> __new_node; <a name="l00078"></a>00078 } <a name="l00079"></a>00079 <a name="l00080"></a>00080 <span class="keyword">inline</span> _Slist_node_base* <a name="l00081"></a>00081 __slist_previous(_Slist_node_base* __head, <a name="l00082"></a>00082 <span class="keyword">const</span> _Slist_node_base* __node) <a name="l00083"></a>00083 { <a name="l00084"></a>00084 <span class="keywordflow">while</span> (__head && __head->_M_next != __node) <a name="l00085"></a>00085 __head = __head->_M_next; <a name="l00086"></a>00086 <span class="keywordflow">return</span> __head; <a name="l00087"></a>00087 } <a name="l00088"></a>00088 <a name="l00089"></a>00089 <span class="keyword">inline</span> <span class="keyword">const</span> _Slist_node_base* <a name="l00090"></a>00090 __slist_previous(<span class="keyword">const</span> _Slist_node_base* __head, <a name="l00091"></a>00091 <span class="keyword">const</span> _Slist_node_base* __node) <a name="l00092"></a>00092 { <a name="l00093"></a>00093 <span class="keywordflow">while</span> (__head && __head->_M_next != __node) <a name="l00094"></a>00094 __head = __head->_M_next; <a name="l00095"></a>00095 <span class="keywordflow">return</span> __head; <a name="l00096"></a>00096 } <a name="l00097"></a>00097 <a name="l00098"></a>00098 <span class="keyword">inline</span> <span class="keywordtype">void</span> <a name="l00099"></a>00099 __slist_splice_after(_Slist_node_base* __pos, <a name="l00100"></a>00100 _Slist_node_base* __before_first, <a name="l00101"></a>00101 _Slist_node_base* __before_last) <a name="l00102"></a>00102 { <a name="l00103"></a>00103 <span class="keywordflow">if</span> (__pos != __before_first && __pos != __before_last) <a name="l00104"></a>00104 { <a name="l00105"></a>00105 _Slist_node_base* __first = __before_first->_M_next; <a name="l00106"></a>00106 _Slist_node_base* __after = __pos->_M_next; <a name="l00107"></a>00107 __before_first->_M_next = __before_last->_M_next; <a name="l00108"></a>00108 __pos->_M_next = __first; <a name="l00109"></a>00109 __before_last->_M_next = __after; <a name="l00110"></a>00110 } <a name="l00111"></a>00111 } <a name="l00112"></a>00112 <a name="l00113"></a>00113 <span class="keyword">inline</span> <span class="keywordtype">void</span> <a name="l00114"></a>00114 __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head) <a name="l00115"></a>00115 { <a name="l00116"></a>00116 _Slist_node_base* __before_last = __slist_previous(__head, 0); <a name="l00117"></a>00117 <span class="keywordflow">if</span> (__before_last != __head) <a name="l00118"></a>00118 { <a name="l00119"></a>00119 _Slist_node_base* __after = __pos->_M_next; <a name="l00120"></a>00120 __pos->_M_next = __head->_M_next; <a name="l00121"></a>00121 __head->_M_next = 0; <a name="l00122"></a>00122 __before_last->_M_next = __after; <a name="l00123"></a>00123 } <a name="l00124"></a>00124 } <a name="l00125"></a>00125 <a name="l00126"></a>00126 <span class="keyword">inline</span> _Slist_node_base* <a name="l00127"></a>00127 __slist_reverse(_Slist_node_base* __node) <a name="l00128"></a>00128 { <a name="l00129"></a>00129 _Slist_node_base* __result = __node; <a name="l00130"></a>00130 __node = __node->_M_next; <a name="l00131"></a>00131 __result->_M_next = 0; <a name="l00132"></a>00132 <span class="keywordflow">while</span>(__node) <a name="l00133"></a>00133 { <a name="l00134"></a>00134 _Slist_node_base* __next = __node->_M_next; <a name="l00135"></a>00135 __node->_M_next = __result; <a name="l00136"></a>00136 __result = __node; <a name="l00137"></a>00137 __node = __next; <a name="l00138"></a>00138 } <a name="l00139"></a>00139 <span class="keywordflow">return</span> __result; <a name="l00140"></a>00140 } <a name="l00141"></a>00141 <a name="l00142"></a>00142 <span class="keyword">inline</span> <span class="keywordtype">size_t</span> <a name="l00143"></a>00143 __slist_size(_Slist_node_base* __node) <a name="l00144"></a>00144 { <a name="l00145"></a>00145 <span class="keywordtype">size_t</span> __result = 0; <a name="l00146"></a>00146 <span class="keywordflow">for</span> (; __node != 0; __node = __node->_M_next) <a name="l00147"></a>00147 ++__result; <a name="l00148"></a>00148 <span class="keywordflow">return</span> __result; <a name="l00149"></a>00149 } <a name="l00150"></a>00150 <a name="l00151"></a>00151 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp> <a name="l00152"></a>00152 <span class="keyword">struct </span>_Slist_node : <span class="keyword">public</span> _Slist_node_base <a name="l00153"></a>00153 { <a name="l00154"></a>00154 _Tp _M_data; <a name="l00155"></a>00155 }; <a name="l00156"></a>00156 <a name="l00157"></a>00157 <span class="keyword">struct </span>_Slist_iterator_base <a name="l00158"></a>00158 { <a name="l00159"></a>00159 <span class="keyword">typedef</span> <span class="keywordtype">size_t</span> size_type; <a name="l00160"></a>00160 <span class="keyword">typedef</span> ptrdiff_t difference_type; <a name="l00161"></a>00161 <span class="keyword">typedef</span> <a class="code" href="a00474.html" title="Forward iterators support a superset of input iterator operations.">std::forward_iterator_tag</a> iterator_category; <a name="l00162"></a>00162 <a name="l00163"></a>00163 _Slist_node_base* _M_node; <a name="l00164"></a>00164 <a name="l00165"></a>00165 _Slist_iterator_base(_Slist_node_base* __x) <a name="l00166"></a>00166 : _M_node(__x) {} <a name="l00167"></a>00167 <a name="l00168"></a>00168 <span class="keywordtype">void</span> <a name="l00169"></a>00169 _M_incr() <a name="l00170"></a>00170 { _M_node = _M_node->_M_next; } <a name="l00171"></a>00171 <a name="l00172"></a>00172 <span class="keywordtype">bool</span> <a name="l00173"></a>00173 operator==(<span class="keyword">const</span> _Slist_iterator_base& __x)<span class="keyword"> const</span> <a name="l00174"></a>00174 <span class="keyword"> </span>{ <span class="keywordflow">return</span> _M_node == __x._M_node; } <a name="l00175"></a>00175 <a name="l00176"></a>00176 <span class="keywordtype">bool</span> <a name="l00177"></a>00177 operator!=(<span class="keyword">const</span> _Slist_iterator_base& __x)<span class="keyword"> const</span> <a name="l00178"></a>00178 <span class="keyword"> </span>{ <span class="keywordflow">return</span> _M_node != __x._M_node; } <a name="l00179"></a>00179 }; <a name="l00180"></a>00180 <a name="l00181"></a>00181 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Ref, <span class="keyword">class</span> _Ptr> <a name="l00182"></a>00182 <span class="keyword">struct </span>_Slist_iterator : <span class="keyword">public</span> _Slist_iterator_base <a name="l00183"></a>00183 { <a name="l00184"></a>00184 <span class="keyword">typedef</span> _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; <a name="l00185"></a>00185 <span class="keyword">typedef</span> _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; <a name="l00186"></a>00186 <span class="keyword">typedef</span> _Slist_iterator<_Tp, _Ref, _Ptr> _Self; <a name="l00187"></a>00187 <a name="l00188"></a>00188 <span class="keyword">typedef</span> _Tp value_type; <a name="l00189"></a>00189 <span class="keyword">typedef</span> _Ptr pointer; <a name="l00190"></a>00190 <span class="keyword">typedef</span> _Ref reference; <a name="l00191"></a>00191 <span class="keyword">typedef</span> _Slist_node<_Tp> _Node; <a name="l00192"></a>00192 <a name="l00193"></a>00193 <span class="keyword">explicit</span> <a name="l00194"></a>00194 _Slist_iterator(_Node* __x) <a name="l00195"></a>00195 : _Slist_iterator_base(__x) {} <a name="l00196"></a>00196 <a name="l00197"></a>00197 _Slist_iterator() <a name="l00198"></a>00198 : _Slist_iterator_base(0) {} <a name="l00199"></a>00199 <a name="l00200"></a>00200 _Slist_iterator(<span class="keyword">const</span> iterator& __x) <a name="l00201"></a>00201 : _Slist_iterator_base(__x._M_node) {} <a name="l00202"></a>00202 <a name="l00203"></a>00203 reference <a name="l00204"></a>00204 operator*()<span class="keyword"> const</span> <a name="l00205"></a>00205 <span class="keyword"> </span>{ <span class="keywordflow">return</span> ((_Node*) _M_node)->_M_data; } <a name="l00206"></a>00206 <a name="l00207"></a>00207 pointer <a name="l00208"></a>00208 operator->()<span class="keyword"> const</span> <a name="l00209"></a>00209 <span class="keyword"> </span>{ <span class="keywordflow">return</span> &(operator*()); } <a name="l00210"></a>00210 <a name="l00211"></a>00211 _Self& <a name="l00212"></a>00212 operator++() <a name="l00213"></a>00213 { <a name="l00214"></a>00214 _M_incr(); <a name="l00215"></a>00215 <span class="keywordflow">return</span> *<span class="keyword">this</span>; <a name="l00216"></a>00216 } <a name="l00217"></a>00217 <a name="l00218"></a>00218 _Self <a name="l00219"></a>00219 operator++(<span class="keywordtype">int</span>) <a name="l00220"></a>00220 { <a name="l00221"></a>00221 _Self __tmp = *<span class="keyword">this</span>; <a name="l00222"></a>00222 _M_incr(); <a name="l00223"></a>00223 <span class="keywordflow">return</span> __tmp; <a name="l00224"></a>00224 } <a name="l00225"></a>00225 }; <a name="l00226"></a>00226 <a name="l00227"></a>00227 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00228"></a>00228 <span class="keyword">struct </span>_Slist_base <a name="l00229"></a>00229 : <span class="keyword">public</span> _Alloc::template rebind<_Slist_node<_Tp> >::other <a name="l00230"></a>00230 { <a name="l00231"></a>00231 <span class="keyword">typedef</span> <span class="keyword">typename</span> _Alloc::template rebind<_Slist_node<_Tp> >::other <a name="l00232"></a>00232 _Node_alloc; <a name="l00233"></a>00233 <span class="keyword">typedef</span> _Alloc allocator_type; <a name="l00234"></a>00234 <a name="l00235"></a>00235 allocator_type <a name="l00236"></a>00236 get_allocator()<span class="keyword"> const</span> <a name="l00237"></a>00237 <span class="keyword"> </span>{ <span class="keywordflow">return</span> *<span class="keyword">static_cast<</span><span class="keyword">const </span>_Node_alloc*<span class="keyword">></span>(<span class="keyword">this</span>); } <a name="l00238"></a>00238 <a name="l00239"></a>00239 _Slist_base(<span class="keyword">const</span> allocator_type& __a) <a name="l00240"></a>00240 : _Node_alloc(__a) <a name="l00241"></a>00241 { this->_M_head._M_next = 0; } <a name="l00242"></a>00242 <a name="l00243"></a>00243 ~_Slist_base() <a name="l00244"></a>00244 { _M_erase_after(&this->_M_head, 0); } <a name="l00245"></a>00245 <a name="l00246"></a>00246 <span class="keyword">protected</span>: <a name="l00247"></a>00247 _Slist_node_base _M_head; <a name="l00248"></a>00248 <a name="l00249"></a>00249 _Slist_node<_Tp>* <a name="l00250"></a>00250 _M_get_node() <a name="l00251"></a>00251 { <span class="keywordflow">return</span> _Node_alloc::allocate(1); } <a name="l00252"></a>00252 <a name="l00253"></a>00253 <span class="keywordtype">void</span> <a name="l00254"></a>00254 _M_put_node(_Slist_node<_Tp>* __p) <a name="l00255"></a>00255 { _Node_alloc::deallocate(__p, 1); } <a name="l00256"></a>00256 <a name="l00257"></a>00257 <span class="keyword">protected</span>: <a name="l00258"></a>00258 _Slist_node_base* _M_erase_after(_Slist_node_base* __pos) <a name="l00259"></a>00259 { <a name="l00260"></a>00260 _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next); <a name="l00261"></a>00261 _Slist_node_base* __next_next = __next->_M_next; <a name="l00262"></a>00262 __pos->_M_next = __next_next; <a name="l00263"></a>00263 get_allocator().destroy(&__next->_M_data); <a name="l00264"></a>00264 _M_put_node(__next); <a name="l00265"></a>00265 <span class="keywordflow">return</span> __next_next; <a name="l00266"></a>00266 } <a name="l00267"></a>00267 _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*); <a name="l00268"></a>00268 }; <a name="l00269"></a>00269 <a name="l00270"></a>00270 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00271"></a>00271 _Slist_node_base* <a name="l00272"></a>00272 _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, <a name="l00273"></a>00273 _Slist_node_base* __last_node) <a name="l00274"></a>00274 { <a name="l00275"></a>00275 _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next); <a name="l00276"></a>00276 <span class="keywordflow">while</span> (__cur != __last_node) <a name="l00277"></a>00277 { <a name="l00278"></a>00278 _Slist_node<_Tp>* __tmp = __cur; <a name="l00279"></a>00279 __cur = (_Slist_node<_Tp>*) __cur->_M_next; <a name="l00280"></a>00280 get_allocator().destroy(&__tmp->_M_data); <a name="l00281"></a>00281 _M_put_node(__tmp); <a name="l00282"></a>00282 } <a name="l00283"></a>00283 __before_first->_M_next = __last_node; <a name="l00284"></a>00284 <span class="keywordflow">return</span> __last_node; <a name="l00285"></a>00285 } <a name="l00286"></a>00286 <span class="comment"></span> <a name="l00287"></a>00287 <span class="comment"> /**</span> <a name="l00288"></a>00288 <span class="comment"> * This is an SGI extension.</span> <a name="l00289"></a>00289 <span class="comment"> * @ingroup SGIextensions</span> <a name="l00290"></a>00290 <span class="comment"> * @doctodo</span> <a name="l00291"></a>00291 <span class="comment"> */</span> <a name="l00292"></a>00292 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc = allocator<_Tp> > <a name="l00293"></a><a class="code" href="a00067.html">00293</a> <span class="keyword">class </span><a class="code" href="a00067.html">slist</a> : <span class="keyword">private</span> _Slist_base<_Tp,_Alloc> <a name="l00294"></a>00294 { <a name="l00295"></a>00295 <span class="comment">// concept requirements</span> <a name="l00296"></a>00296 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) <a name="l00297"></a>00297 <a name="l00298"></a>00298 <span class="keyword">private</span>: <a name="l00299"></a>00299 <span class="keyword">typedef</span> _Slist_base<_Tp,_Alloc> _Base; <a name="l00300"></a>00300 <a name="l00301"></a>00301 <span class="keyword">public</span>: <a name="l00302"></a>00302 <span class="keyword">typedef</span> _Tp value_type; <a name="l00303"></a>00303 <span class="keyword">typedef</span> value_type* pointer; <a name="l00304"></a>00304 <span class="keyword">typedef</span> <span class="keyword">const</span> value_type* const_pointer; <a name="l00305"></a>00305 <span class="keyword">typedef</span> value_type& reference; <a name="l00306"></a>00306 <span class="keyword">typedef</span> <span class="keyword">const</span> value_type& const_reference; <a name="l00307"></a>00307 <span class="keyword">typedef</span> <span class="keywordtype">size_t</span> size_type; <a name="l00308"></a>00308 <span class="keyword">typedef</span> ptrdiff_t difference_type; <a name="l00309"></a>00309 <a name="l00310"></a>00310 <span class="keyword">typedef</span> _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; <a name="l00311"></a>00311 <span class="keyword">typedef</span> _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; <a name="l00312"></a>00312 <a name="l00313"></a>00313 <span class="keyword">typedef</span> <span class="keyword">typename</span> _Base::allocator_type allocator_type; <a name="l00314"></a>00314 <a name="l00315"></a>00315 allocator_type <a name="l00316"></a>00316 get_allocator()<span class="keyword"> const</span> <a name="l00317"></a>00317 <span class="keyword"> </span>{ <span class="keywordflow">return</span> _Base::get_allocator(); } <a name="l00318"></a>00318 <a name="l00319"></a>00319 <span class="keyword">private</span>: <a name="l00320"></a>00320 <span class="keyword">typedef</span> _Slist_node<_Tp> _Node; <a name="l00321"></a>00321 <span class="keyword">typedef</span> _Slist_node_base _Node_base; <a name="l00322"></a>00322 <span class="keyword">typedef</span> _Slist_iterator_base _Iterator_base; <a name="l00323"></a>00323 <a name="l00324"></a>00324 _Node* <a name="l00325"></a>00325 _M_create_node(<span class="keyword">const</span> value_type& __x) <a name="l00326"></a>00326 { <a name="l00327"></a>00327 _Node* __node = this->_M_get_node(); <a name="l00328"></a>00328 __try <a name="l00329"></a>00329 { <a name="l00330"></a>00330 get_allocator().construct(&__node->_M_data, __x); <a name="l00331"></a>00331 __node->_M_next = 0; <a name="l00332"></a>00332 } <a name="l00333"></a>00333 __catch(...) <a name="l00334"></a>00334 { <a name="l00335"></a>00335 this->_M_put_node(__node); <a name="l00336"></a>00336 __throw_exception_again; <a name="l00337"></a>00337 } <a name="l00338"></a>00338 <span class="keywordflow">return</span> __node; <a name="l00339"></a>00339 } <a name="l00340"></a>00340 <a name="l00341"></a>00341 _Node* <a name="l00342"></a>00342 _M_create_node() <a name="l00343"></a>00343 { <a name="l00344"></a>00344 _Node* __node = this->_M_get_node(); <a name="l00345"></a>00345 __try <a name="l00346"></a>00346 { <a name="l00347"></a>00347 get_allocator().construct(&__node->_M_data, value_type()); <a name="l00348"></a>00348 __node->_M_next = 0; <a name="l00349"></a>00349 } <a name="l00350"></a>00350 __catch(...) <a name="l00351"></a>00351 { <a name="l00352"></a>00352 this->_M_put_node(__node); <a name="l00353"></a>00353 __throw_exception_again; <a name="l00354"></a>00354 } <a name="l00355"></a>00355 <span class="keywordflow">return</span> __node; <a name="l00356"></a>00356 } <a name="l00357"></a>00357 <a name="l00358"></a>00358 <span class="keyword">public</span>: <a name="l00359"></a>00359 <span class="keyword">explicit</span> <a name="l00360"></a>00360 <a class="code" href="a00067.html">slist</a>(<span class="keyword">const</span> allocator_type& __a = allocator_type()) <a name="l00361"></a>00361 : _Base(__a) {} <a name="l00362"></a>00362 <a name="l00363"></a>00363 <a class="code" href="a00067.html">slist</a>(size_type __n, <span class="keyword">const</span> value_type& __x, <a name="l00364"></a>00364 <span class="keyword">const</span> allocator_type& __a = allocator_type()) <a name="l00365"></a>00365 : _Base(__a) <a name="l00366"></a>00366 { _M_insert_after_fill(&this->_M_head, __n, __x); } <a name="l00367"></a>00367 <a name="l00368"></a>00368 <span class="keyword">explicit</span> <a name="l00369"></a>00369 <a class="code" href="a00067.html">slist</a>(size_type __n) <a name="l00370"></a>00370 : _Base(allocator_type()) <a name="l00371"></a>00371 { _M_insert_after_fill(&this->_M_head, __n, value_type()); } <a name="l00372"></a>00372 <a name="l00373"></a>00373 <span class="comment">// We don't need any dispatching tricks here, because</span> <a name="l00374"></a>00374 <span class="comment">// _M_insert_after_range already does them.</span> <a name="l00375"></a>00375 <span class="keyword">template</span> <<span class="keyword">class</span> _InputIterator> <a name="l00376"></a>00376 <a class="code" href="a00067.html">slist</a>(_InputIterator __first, _InputIterator __last, <a name="l00377"></a>00377 <span class="keyword">const</span> allocator_type& __a = allocator_type()) <a name="l00378"></a>00378 : _Base(__a) <a name="l00379"></a>00379 { _M_insert_after_range(&this->_M_head, __first, __last); } <a name="l00380"></a>00380 <a name="l00381"></a>00381 <a class="code" href="a00067.html">slist</a>(<span class="keyword">const</span> <a class="code" href="a00067.html">slist</a>& __x) <a name="l00382"></a>00382 : _Base(__x.get_allocator()) <a name="l00383"></a>00383 { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); } <a name="l00384"></a>00384 <a name="l00385"></a>00385 <a class="code" href="a00067.html">slist</a>& <a name="l00386"></a>00386 operator= (<span class="keyword">const</span> <a class="code" href="a00067.html">slist</a>& __x); <a name="l00387"></a>00387 <a name="l00388"></a>00388 ~<a class="code" href="a00067.html">slist</a>() {} <a name="l00389"></a>00389 <a name="l00390"></a>00390 <span class="keyword">public</span>: <a name="l00391"></a>00391 <span class="comment">// assign(), a generalized assignment member function. Two</span> <a name="l00392"></a>00392 <span class="comment">// versions: one that takes a count, and one that takes a range.</span> <a name="l00393"></a>00393 <span class="comment">// The range version is a member template, so we dispatch on whether</span> <a name="l00394"></a>00394 <span class="comment">// or not the type is an integer.</span> <a name="l00395"></a>00395 <a name="l00396"></a>00396 <span class="keywordtype">void</span> <a name="l00397"></a>00397 assign(size_type __n, <span class="keyword">const</span> _Tp& __val) <a name="l00398"></a>00398 { _M_fill_assign(__n, __val); } <a name="l00399"></a>00399 <a name="l00400"></a>00400 <span class="keywordtype">void</span> <a name="l00401"></a>00401 _M_fill_assign(size_type __n, <span class="keyword">const</span> _Tp& __val); <a name="l00402"></a>00402 <a name="l00403"></a>00403 <span class="keyword">template</span> <<span class="keyword">class</span> _InputIterator> <a name="l00404"></a>00404 <span class="keywordtype">void</span> <a name="l00405"></a>00405 assign(_InputIterator __first, _InputIterator __last) <a name="l00406"></a>00406 { <a name="l00407"></a>00407 <span class="keyword">typedef</span> <span class="keyword">typename</span> std::__is_integer<_InputIterator>::__type _Integral; <a name="l00408"></a>00408 _M_assign_dispatch(__first, __last, _Integral()); <a name="l00409"></a>00409 } <a name="l00410"></a>00410 <a name="l00411"></a>00411 <span class="keyword">template</span> <<span class="keyword">class</span> _Integer> <a name="l00412"></a>00412 <span class="keywordtype">void</span> <a name="l00413"></a>00413 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) <a name="l00414"></a>00414 { _M_fill_assign((size_type) __n, (_Tp) __val); } <a name="l00415"></a>00415 <a name="l00416"></a>00416 <span class="keyword">template</span> <<span class="keyword">class</span> _InputIterator> <a name="l00417"></a>00417 <span class="keywordtype">void</span> <a name="l00418"></a>00418 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, <a name="l00419"></a>00419 __false_type); <a name="l00420"></a>00420 <a name="l00421"></a>00421 <span class="keyword">public</span>: <a name="l00422"></a>00422 <a name="l00423"></a>00423 iterator <a name="l00424"></a>00424 begin() <a name="l00425"></a>00425 { <span class="keywordflow">return</span> iterator((_Node*)this->_M_head._M_next); } <a name="l00426"></a>00426 <a name="l00427"></a>00427 const_iterator <a name="l00428"></a>00428 begin()<span class="keyword"> const</span> <a name="l00429"></a>00429 <span class="keyword"> </span>{ <span class="keywordflow">return</span> const_iterator((_Node*)this->_M_head._M_next);} <a name="l00430"></a>00430 <a name="l00431"></a>00431 iterator <a name="l00432"></a>00432 end() <a name="l00433"></a>00433 { <span class="keywordflow">return</span> iterator(0); } <a name="l00434"></a>00434 <a name="l00435"></a>00435 const_iterator <a name="l00436"></a>00436 end()<span class="keyword"> const</span> <a name="l00437"></a>00437 <span class="keyword"> </span>{ <span class="keywordflow">return</span> const_iterator(0); } <a name="l00438"></a>00438 <a name="l00439"></a>00439 <span class="comment">// Experimental new feature: before_begin() returns a</span> <a name="l00440"></a>00440 <span class="comment">// non-dereferenceable iterator that, when incremented, yields</span> <a name="l00441"></a>00441 <span class="comment">// begin(). This iterator may be used as the argument to</span> <a name="l00442"></a>00442 <span class="comment">// insert_after, erase_after, etc. Note that even for an empty</span> <a name="l00443"></a>00443 <span class="comment">// slist, before_begin() is not the same iterator as end(). It</span> <a name="l00444"></a>00444 <span class="comment">// is always necessary to increment before_begin() at least once to</span> <a name="l00445"></a>00445 <span class="comment">// obtain end().</span> <a name="l00446"></a>00446 iterator <a name="l00447"></a>00447 before_begin() <a name="l00448"></a>00448 { <span class="keywordflow">return</span> iterator((_Node*) &this->_M_head); } <a name="l00449"></a>00449 <a name="l00450"></a>00450 const_iterator <a name="l00451"></a>00451 before_begin()<span class="keyword"> const</span> <a name="l00452"></a>00452 <span class="keyword"> </span>{ <span class="keywordflow">return</span> const_iterator((_Node*) &this->_M_head); } <a name="l00453"></a>00453 <a name="l00454"></a>00454 size_type <a name="l00455"></a>00455 size()<span class="keyword"> const</span> <a name="l00456"></a>00456 <span class="keyword"> </span>{ <span class="keywordflow">return</span> __slist_size(this->_M_head._M_next); } <a name="l00457"></a>00457 <a name="l00458"></a>00458 size_type <a name="l00459"></a>00459 max_size()<span class="keyword"> const</span> <a name="l00460"></a>00460 <span class="keyword"> </span>{ <span class="keywordflow">return</span> size_type(-1); } <a name="l00461"></a>00461 <a name="l00462"></a>00462 <span class="keywordtype">bool</span> <a name="l00463"></a>00463 empty()<span class="keyword"> const</span> <a name="l00464"></a>00464 <span class="keyword"> </span>{ <span class="keywordflow">return</span> this->_M_head._M_next == 0; } <a name="l00465"></a>00465 <a name="l00466"></a>00466 <span class="keywordtype">void</span> <a name="l00467"></a>00467 swap(<a class="code" href="a00067.html">slist</a>& __x) <a name="l00468"></a>00468 { std::swap(this->_M_head._M_next, __x._M_head._M_next); } <a name="l00469"></a>00469 <a name="l00470"></a>00470 <span class="keyword">public</span>: <a name="l00471"></a>00471 <a name="l00472"></a>00472 reference <a name="l00473"></a>00473 front() <a name="l00474"></a>00474 { <span class="keywordflow">return</span> ((_Node*) this->_M_head._M_next)->_M_data; } <a name="l00475"></a>00475 <a name="l00476"></a>00476 const_reference <a name="l00477"></a>00477 front()<span class="keyword"> const</span> <a name="l00478"></a>00478 <span class="keyword"> </span>{ <span class="keywordflow">return</span> ((_Node*) this->_M_head._M_next)->_M_data; } <a name="l00479"></a>00479 <a name="l00480"></a>00480 <span class="keywordtype">void</span> <a name="l00481"></a>00481 push_front(<span class="keyword">const</span> value_type& __x) <a name="l00482"></a>00482 { __slist_make_link(&this->_M_head, _M_create_node(__x)); } <a name="l00483"></a>00483 <a name="l00484"></a>00484 <span class="keywordtype">void</span> <a name="l00485"></a>00485 push_front() <a name="l00486"></a>00486 { __slist_make_link(&this->_M_head, _M_create_node()); } <a name="l00487"></a>00487 <a name="l00488"></a>00488 <span class="keywordtype">void</span> <a name="l00489"></a>00489 pop_front() <a name="l00490"></a>00490 { <a name="l00491"></a>00491 _Node* __node = (_Node*) this->_M_head._M_next; <a name="l00492"></a>00492 this->_M_head._M_next = __node->_M_next; <a name="l00493"></a>00493 get_allocator().destroy(&__node->_M_data); <a name="l00494"></a>00494 this->_M_put_node(__node); <a name="l00495"></a>00495 } <a name="l00496"></a>00496 <a name="l00497"></a>00497 iterator <a name="l00498"></a>00498 previous(const_iterator __pos) <a name="l00499"></a>00499 { <span class="keywordflow">return</span> iterator((_Node*) __slist_previous(&this->_M_head, <a name="l00500"></a>00500 __pos._M_node)); } <a name="l00501"></a>00501 <a name="l00502"></a>00502 const_iterator <a name="l00503"></a>00503 previous(const_iterator __pos)<span class="keyword"> const</span> <a name="l00504"></a>00504 <span class="keyword"> </span>{ <span class="keywordflow">return</span> const_iterator((_Node*) __slist_previous(&this->_M_head, <a name="l00505"></a>00505 __pos._M_node)); } <a name="l00506"></a>00506 <a name="l00507"></a>00507 <span class="keyword">private</span>: <a name="l00508"></a>00508 _Node* <a name="l00509"></a>00509 _M_insert_after(_Node_base* __pos, <span class="keyword">const</span> value_type& __x) <a name="l00510"></a>00510 { <span class="keywordflow">return</span> (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); } <a name="l00511"></a>00511 <a name="l00512"></a>00512 _Node* <a name="l00513"></a>00513 _M_insert_after(_Node_base* __pos) <a name="l00514"></a>00514 { <span class="keywordflow">return</span> (_Node*) (__slist_make_link(__pos, _M_create_node())); } <a name="l00515"></a>00515 <a name="l00516"></a>00516 <span class="keywordtype">void</span> <a name="l00517"></a>00517 _M_insert_after_fill(_Node_base* __pos, <a name="l00518"></a>00518 size_type __n, <span class="keyword">const</span> value_type& __x) <a name="l00519"></a>00519 { <a name="l00520"></a>00520 <span class="keywordflow">for</span> (size_type __i = 0; __i < __n; ++__i) <a name="l00521"></a>00521 __pos = __slist_make_link(__pos, _M_create_node(__x)); <a name="l00522"></a>00522 } <a name="l00523"></a>00523 <a name="l00524"></a>00524 <span class="comment">// Check whether it's an integral type. If so, it's not an iterator.</span> <a name="l00525"></a>00525 <span class="keyword">template</span> <<span class="keyword">class</span> _InIterator> <a name="l00526"></a>00526 <span class="keywordtype">void</span> <a name="l00527"></a>00527 _M_insert_after_range(_Node_base* __pos, <a name="l00528"></a>00528 _InIterator __first, _InIterator __last) <a name="l00529"></a>00529 { <a name="l00530"></a>00530 <span class="keyword">typedef</span> <span class="keyword">typename</span> std::__is_integer<_InIterator>::__type _Integral; <a name="l00531"></a>00531 _M_insert_after_range(__pos, __first, __last, _Integral()); <a name="l00532"></a>00532 } <a name="l00533"></a>00533 <a name="l00534"></a>00534 <span class="keyword">template</span> <<span class="keyword">class</span> _Integer> <a name="l00535"></a>00535 <span class="keywordtype">void</span> <a name="l00536"></a>00536 _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x, <a name="l00537"></a>00537 __true_type) <a name="l00538"></a>00538 { _M_insert_after_fill(__pos, __n, __x); } <a name="l00539"></a>00539 <a name="l00540"></a>00540 <span class="keyword">template</span> <<span class="keyword">class</span> _InIterator> <a name="l00541"></a>00541 <span class="keywordtype">void</span> <a name="l00542"></a>00542 _M_insert_after_range(_Node_base* __pos, <a name="l00543"></a>00543 _InIterator __first, _InIterator __last, <a name="l00544"></a>00544 __false_type) <a name="l00545"></a>00545 { <a name="l00546"></a>00546 <span class="keywordflow">while</span> (__first != __last) <a name="l00547"></a>00547 { <a name="l00548"></a>00548 __pos = __slist_make_link(__pos, _M_create_node(*__first)); <a name="l00549"></a>00549 ++__first; <a name="l00550"></a>00550 } <a name="l00551"></a>00551 } <a name="l00552"></a>00552 <a name="l00553"></a>00553 <span class="keyword">public</span>: <a name="l00554"></a>00554 iterator <a name="l00555"></a>00555 insert_after(iterator __pos, <span class="keyword">const</span> value_type& __x) <a name="l00556"></a>00556 { <span class="keywordflow">return</span> iterator(_M_insert_after(__pos._M_node, __x)); } <a name="l00557"></a>00557 <a name="l00558"></a>00558 iterator <a name="l00559"></a>00559 insert_after(iterator __pos) <a name="l00560"></a>00560 { <span class="keywordflow">return</span> insert_after(__pos, value_type()); } <a name="l00561"></a>00561 <a name="l00562"></a>00562 <span class="keywordtype">void</span> <a name="l00563"></a>00563 insert_after(iterator __pos, size_type __n, <span class="keyword">const</span> value_type& __x) <a name="l00564"></a>00564 { _M_insert_after_fill(__pos._M_node, __n, __x); } <a name="l00565"></a>00565 <a name="l00566"></a>00566 <span class="comment">// We don't need any dispatching tricks here, because</span> <a name="l00567"></a>00567 <span class="comment">// _M_insert_after_range already does them.</span> <a name="l00568"></a>00568 <span class="keyword">template</span> <<span class="keyword">class</span> _InIterator> <a name="l00569"></a>00569 <span class="keywordtype">void</span> <a name="l00570"></a>00570 insert_after(iterator __pos, _InIterator __first, _InIterator __last) <a name="l00571"></a>00571 { _M_insert_after_range(__pos._M_node, __first, __last); } <a name="l00572"></a>00572 <a name="l00573"></a>00573 iterator <a name="l00574"></a>00574 insert(iterator __pos, <span class="keyword">const</span> value_type& __x) <a name="l00575"></a>00575 { <span class="keywordflow">return</span> iterator(_M_insert_after(__slist_previous(&this->_M_head, <a name="l00576"></a>00576 __pos._M_node), <a name="l00577"></a>00577 __x)); } <a name="l00578"></a>00578 <a name="l00579"></a>00579 iterator <a name="l00580"></a>00580 insert(iterator __pos) <a name="l00581"></a>00581 { <span class="keywordflow">return</span> iterator(_M_insert_after(__slist_previous(&this->_M_head, <a name="l00582"></a>00582 __pos._M_node), <a name="l00583"></a>00583 value_type())); } <a name="l00584"></a>00584 <a name="l00585"></a>00585 <span class="keywordtype">void</span> <a name="l00586"></a>00586 insert(iterator __pos, size_type __n, <span class="keyword">const</span> value_type& __x) <a name="l00587"></a>00587 { _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node), <a name="l00588"></a>00588 __n, __x); } <a name="l00589"></a>00589 <a name="l00590"></a>00590 <span class="comment">// We don't need any dispatching tricks here, because</span> <a name="l00591"></a>00591 <span class="comment">// _M_insert_after_range already does them.</span> <a name="l00592"></a>00592 <span class="keyword">template</span> <<span class="keyword">class</span> _InIterator> <a name="l00593"></a>00593 <span class="keywordtype">void</span> <a name="l00594"></a>00594 insert(iterator __pos, _InIterator __first, _InIterator __last) <a name="l00595"></a>00595 { _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), <a name="l00596"></a>00596 __first, __last); } <a name="l00597"></a>00597 <a name="l00598"></a>00598 <span class="keyword">public</span>: <a name="l00599"></a>00599 iterator <a name="l00600"></a>00600 erase_after(iterator __pos) <a name="l00601"></a>00601 { <span class="keywordflow">return</span> iterator((_Node*) this->_M_erase_after(__pos._M_node)); } <a name="l00602"></a>00602 <a name="l00603"></a>00603 iterator <a name="l00604"></a>00604 erase_after(iterator __before_first, iterator __last) <a name="l00605"></a>00605 { <a name="l00606"></a>00606 <span class="keywordflow">return</span> iterator((_Node*) this->_M_erase_after(__before_first._M_node, <a name="l00607"></a>00607 __last._M_node)); <a name="l00608"></a>00608 } <a name="l00609"></a>00609 <a name="l00610"></a>00610 iterator <a name="l00611"></a>00611 erase(iterator __pos) <a name="l00612"></a>00612 { <a name="l00613"></a>00613 <span class="keywordflow">return</span> iterator((_Node*) this->_M_erase_after <a name="l00614"></a>00614 (__slist_previous(&this->_M_head, __pos._M_node))); <a name="l00615"></a>00615 } <a name="l00616"></a>00616 <a name="l00617"></a>00617 iterator <a name="l00618"></a>00618 erase(iterator __first, iterator __last) <a name="l00619"></a>00619 { <a name="l00620"></a>00620 <span class="keywordflow">return</span> iterator((_Node*) this->_M_erase_after <a name="l00621"></a>00621 (__slist_previous(&this->_M_head, __first._M_node), <a name="l00622"></a>00622 __last._M_node)); <a name="l00623"></a>00623 } <a name="l00624"></a>00624 <a name="l00625"></a>00625 <span class="keywordtype">void</span> <a name="l00626"></a>00626 resize(size_type new_size, <span class="keyword">const</span> _Tp& __x); <a name="l00627"></a>00627 <a name="l00628"></a>00628 <span class="keywordtype">void</span> <a name="l00629"></a>00629 resize(size_type new_size) <a name="l00630"></a>00630 { resize(new_size, _Tp()); } <a name="l00631"></a>00631 <a name="l00632"></a>00632 <span class="keywordtype">void</span> <a name="l00633"></a>00633 clear() <a name="l00634"></a>00634 { this->_M_erase_after(&this->_M_head, 0); } <a name="l00635"></a>00635 <a name="l00636"></a>00636 <span class="keyword">public</span>: <a name="l00637"></a>00637 <span class="comment">// Moves the range [__before_first + 1, __before_last + 1) to *this,</span> <a name="l00638"></a>00638 <span class="comment">// inserting it immediately after __pos. This is constant time.</span> <a name="l00639"></a>00639 <span class="keywordtype">void</span> <a name="l00640"></a>00640 splice_after(iterator __pos, <a name="l00641"></a>00641 iterator __before_first, iterator __before_last) <a name="l00642"></a>00642 { <a name="l00643"></a>00643 <span class="keywordflow">if</span> (__before_first != __before_last) <a name="l00644"></a>00644 __slist_splice_after(__pos._M_node, __before_first._M_node, <a name="l00645"></a>00645 __before_last._M_node); <a name="l00646"></a>00646 } <a name="l00647"></a>00647 <a name="l00648"></a>00648 <span class="comment">// Moves the element that follows __prev to *this, inserting it</span> <a name="l00649"></a>00649 <span class="comment">// immediately after __pos. This is constant time.</span> <a name="l00650"></a>00650 <span class="keywordtype">void</span> <a name="l00651"></a>00651 splice_after(iterator __pos, iterator __prev) <a name="l00652"></a>00652 { __slist_splice_after(__pos._M_node, <a name="l00653"></a>00653 __prev._M_node, __prev._M_node->_M_next); } <a name="l00654"></a>00654 <a name="l00655"></a>00655 <span class="comment">// Removes all of the elements from the list __x to *this, inserting</span> <a name="l00656"></a>00656 <span class="comment">// them immediately after __pos. __x must not be *this. Complexity:</span> <a name="l00657"></a>00657 <span class="comment">// linear in __x.size().</span> <a name="l00658"></a>00658 <span class="keywordtype">void</span> <a name="l00659"></a>00659 splice_after(iterator __pos, <a class="code" href="a00067.html">slist</a>& __x) <a name="l00660"></a>00660 { __slist_splice_after(__pos._M_node, &__x._M_head); } <a name="l00661"></a>00661 <a name="l00662"></a>00662 <span class="comment">// Linear in distance(begin(), __pos), and linear in __x.size().</span> <a name="l00663"></a>00663 <span class="keywordtype">void</span> <a name="l00664"></a>00664 splice(iterator __pos, <a class="code" href="a00067.html">slist</a>& __x) <a name="l00665"></a>00665 { <a name="l00666"></a>00666 <span class="keywordflow">if</span> (__x._M_head._M_next) <a name="l00667"></a>00667 __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), <a name="l00668"></a>00668 &__x._M_head, <a name="l00669"></a>00669 __slist_previous(&__x._M_head, 0)); } <a name="l00670"></a>00670 <a name="l00671"></a>00671 <span class="comment">// Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).</span> <a name="l00672"></a>00672 <span class="keywordtype">void</span> <a name="l00673"></a>00673 splice(iterator __pos, <a class="code" href="a00067.html">slist</a>& __x, iterator __i) <a name="l00674"></a>00674 { __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), <a name="l00675"></a>00675 __slist_previous(&__x._M_head, __i._M_node), <a name="l00676"></a>00676 __i._M_node); } <a name="l00677"></a>00677 <a name="l00678"></a>00678 <span class="comment">// Linear in distance(begin(), __pos), in distance(__x.begin(), __first),</span> <a name="l00679"></a>00679 <span class="comment">// and in distance(__first, __last).</span> <a name="l00680"></a>00680 <span class="keywordtype">void</span> <a name="l00681"></a>00681 splice(iterator __pos, <a class="code" href="a00067.html">slist</a>& __x, iterator __first, iterator __last) <a name="l00682"></a>00682 { <a name="l00683"></a>00683 <span class="keywordflow">if</span> (__first != __last) <a name="l00684"></a>00684 __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), <a name="l00685"></a>00685 __slist_previous(&__x._M_head, __first._M_node), <a name="l00686"></a>00686 __slist_previous(__first._M_node, <a name="l00687"></a>00687 __last._M_node)); <a name="l00688"></a>00688 } <a name="l00689"></a>00689 <a name="l00690"></a>00690 <span class="keyword">public</span>: <a name="l00691"></a>00691 <span class="keywordtype">void</span> <a name="l00692"></a>00692 reverse() <a name="l00693"></a>00693 { <a name="l00694"></a>00694 <span class="keywordflow">if</span> (this->_M_head._M_next) <a name="l00695"></a>00695 this->_M_head._M_next = __slist_reverse(this->_M_head._M_next); <a name="l00696"></a>00696 } <a name="l00697"></a>00697 <a name="l00698"></a>00698 <span class="keywordtype">void</span> <a name="l00699"></a>00699 <span class="keyword">remove</span>(<span class="keyword">const</span> _Tp& __val); <a name="l00700"></a>00700 <a name="l00701"></a>00701 <span class="keywordtype">void</span> <a name="l00702"></a>00702 unique(); <a name="l00703"></a>00703 <a name="l00704"></a>00704 <span class="keywordtype">void</span> <a name="l00705"></a>00705 merge(<a class="code" href="a00067.html">slist</a>& __x); <a name="l00706"></a>00706 <a name="l00707"></a>00707 <span class="keywordtype">void</span> <a name="l00708"></a>00708 sort(); <a name="l00709"></a>00709 <a name="l00710"></a>00710 <span class="keyword">template</span> <<span class="keyword">class</span> _Predicate> <a name="l00711"></a>00711 <span class="keywordtype">void</span> <a name="l00712"></a>00712 remove_if(_Predicate __pred); <a name="l00713"></a>00713 <a name="l00714"></a>00714 <span class="keyword">template</span> <<span class="keyword">class</span> _BinaryPredicate> <a name="l00715"></a>00715 <span class="keywordtype">void</span> <a name="l00716"></a>00716 unique(_BinaryPredicate __pred); <a name="l00717"></a>00717 <a name="l00718"></a>00718 <span class="keyword">template</span> <<span class="keyword">class</span> _StrictWeakOrdering> <a name="l00719"></a>00719 <span class="keywordtype">void</span> <a name="l00720"></a>00720 merge(<a class="code" href="a00067.html">slist</a>&, _StrictWeakOrdering); <a name="l00721"></a>00721 <a name="l00722"></a>00722 <span class="keyword">template</span> <<span class="keyword">class</span> _StrictWeakOrdering> <a name="l00723"></a>00723 <span class="keywordtype">void</span> <a name="l00724"></a>00724 sort(_StrictWeakOrdering __comp); <a name="l00725"></a>00725 }; <a name="l00726"></a>00726 <a name="l00727"></a>00727 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00728"></a>00728 <a class="code" href="a00067.html">slist<_Tp, _Alloc></a>& <a name="l00729"></a>00729 <a class="code" href="a00067.html">slist<_Tp, _Alloc>::operator=</a>(<span class="keyword">const</span> <a class="code" href="a00067.html">slist<_Tp, _Alloc></a>& __x) <a name="l00730"></a>00730 { <a name="l00731"></a>00731 <span class="keywordflow">if</span> (&__x != <span class="keyword">this</span>) <a name="l00732"></a>00732 { <a name="l00733"></a>00733 _Node_base* __p1 = &this->_M_head; <a name="l00734"></a>00734 _Node* __n1 = (_Node*) this->_M_head._M_next; <a name="l00735"></a>00735 <span class="keyword">const</span> _Node* __n2 = (<span class="keyword">const</span> _Node*) __x._M_head._M_next; <a name="l00736"></a>00736 <span class="keywordflow">while</span> (__n1 && __n2) <a name="l00737"></a>00737 { <a name="l00738"></a>00738 __n1->_M_data = __n2->_M_data; <a name="l00739"></a>00739 __p1 = __n1; <a name="l00740"></a>00740 __n1 = (_Node*) __n1->_M_next; <a name="l00741"></a>00741 __n2 = (<span class="keyword">const</span> _Node*) __n2->_M_next; <a name="l00742"></a>00742 } <a name="l00743"></a>00743 <span class="keywordflow">if</span> (__n2 == 0) <a name="l00744"></a>00744 this->_M_erase_after(__p1, 0); <a name="l00745"></a>00745 <span class="keywordflow">else</span> <a name="l00746"></a>00746 _M_insert_after_range(__p1, const_iterator((_Node*)__n2), <a name="l00747"></a>00747 const_iterator(0)); <a name="l00748"></a>00748 } <a name="l00749"></a>00749 <span class="keywordflow">return</span> *<span class="keyword">this</span>; <a name="l00750"></a>00750 } <a name="l00751"></a>00751 <a name="l00752"></a>00752 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00753"></a>00753 <span class="keywordtype">void</span> <a name="l00754"></a>00754 slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, <span class="keyword">const</span> _Tp& __val) <a name="l00755"></a>00755 { <a name="l00756"></a>00756 _Node_base* __prev = &this->_M_head; <a name="l00757"></a>00757 _Node* __node = (_Node*) this->_M_head._M_next; <a name="l00758"></a>00758 for (; __node != 0 && __n > 0; --__n) <a name="l00759"></a>00759 { <a name="l00760"></a>00760 __node->_M_data = __val; <a name="l00761"></a>00761 __prev = __node; <a name="l00762"></a>00762 __node = (_Node*) __node->_M_next; <a name="l00763"></a>00763 } <a name="l00764"></a>00764 <span class="keywordflow">if</span> (__n > 0) <a name="l00765"></a>00765 _M_insert_after_fill(__prev, __n, __val); <a name="l00766"></a>00766 <span class="keywordflow">else</span> <a name="l00767"></a>00767 this->_M_erase_after(__prev, 0); <a name="l00768"></a>00768 } <a name="l00769"></a>00769 <a name="l00770"></a>00770 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00771"></a>00771 <span class="keyword">template</span> <<span class="keyword">class</span> _InputIterator> <a name="l00772"></a>00772 <span class="keywordtype">void</span> <a name="l00773"></a>00773 slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIterator __first, <a name="l00774"></a>00774 _InputIterator __last, <a name="l00775"></a>00775 __false_type) <a name="l00776"></a>00776 { <a name="l00777"></a>00777 _Node_base* __prev = &this->_M_head; <a name="l00778"></a>00778 _Node* __node = (_Node*) this->_M_head._M_next; <a name="l00779"></a>00779 while (__node != 0 && __first != __last) <a name="l00780"></a>00780 { <a name="l00781"></a>00781 __node->_M_data = *__first; <a name="l00782"></a>00782 __prev = __node; <a name="l00783"></a>00783 __node = (_Node*) __node->_M_next; <a name="l00784"></a>00784 ++__first; <a name="l00785"></a>00785 } <a name="l00786"></a>00786 <span class="keywordflow">if</span> (__first != __last) <a name="l00787"></a>00787 _M_insert_after_range(__prev, __first, __last); <a name="l00788"></a>00788 <span class="keywordflow">else</span> <a name="l00789"></a>00789 this->_M_erase_after(__prev, 0); <a name="l00790"></a>00790 } <a name="l00791"></a>00791 <a name="l00792"></a>00792 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00793"></a>00793 <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a name="l00794"></a>00794 operator==(<span class="keyword">const</span> slist<_Tp, _Alloc>& _SL1, <span class="keyword">const</span> slist<_Tp, _Alloc>& _SL2) <a name="l00795"></a>00795 { <a name="l00796"></a>00796 <span class="keyword">typedef</span> <span class="keyword">typename</span> slist<_Tp,_Alloc>::const_iterator const_iterator; <a name="l00797"></a>00797 const_iterator __end1 = _SL1.end(); <a name="l00798"></a>00798 const_iterator __end2 = _SL2.end(); <a name="l00799"></a>00799 <a name="l00800"></a>00800 const_iterator __i1 = _SL1.begin(); <a name="l00801"></a>00801 const_iterator __i2 = _SL2.begin(); <a name="l00802"></a>00802 <span class="keywordflow">while</span> (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) <a name="l00803"></a>00803 { <a name="l00804"></a>00804 ++__i1; <a name="l00805"></a>00805 ++__i2; <a name="l00806"></a>00806 } <a name="l00807"></a>00807 <span class="keywordflow">return</span> __i1 == __end1 && __i2 == __end2; <a name="l00808"></a>00808 } <a name="l00809"></a>00809 <a name="l00810"></a>00810 <a name="l00811"></a>00811 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00812"></a>00812 <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a name="l00813"></a>00813 operator<(const slist<_Tp, _Alloc>& _SL1, <span class="keyword">const</span> slist<_Tp, _Alloc>& _SL2) <a name="l00814"></a>00814 { <span class="keywordflow">return</span> <a class="code" href="a01184.html#ga50f3325e78776afb60221e2c180b9047" title="Performs dictionary comparison on ranges.">std::lexicographical_compare</a>(_SL1.begin(), _SL1.end(), <a name="l00815"></a>00815 _SL2.begin(), _SL2.end()); } <a name="l00816"></a>00816 <a name="l00817"></a>00817 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00818"></a>00818 <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a name="l00819"></a>00819 operator!=(<span class="keyword">const</span> slist<_Tp, _Alloc>& _SL1, <span class="keyword">const</span> slist<_Tp, _Alloc>& _SL2) <a name="l00820"></a>00820 { <span class="keywordflow">return</span> !(_SL1 == _SL2); } <a name="l00821"></a>00821 <a name="l00822"></a>00822 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00823"></a>00823 <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a name="l00824"></a>00824 operator>(<span class="keyword">const</span> slist<_Tp, _Alloc>& _SL1, <span class="keyword">const</span> slist<_Tp, _Alloc>& _SL2) <a name="l00825"></a>00825 { <span class="keywordflow">return</span> _SL2 < _SL1; } <a name="l00826"></a>00826 <a name="l00827"></a>00827 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00828"></a>00828 <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a name="l00829"></a>00829 operator<=(const slist<_Tp, _Alloc>& _SL1, <span class="keyword">const</span> slist<_Tp, _Alloc>& _SL2) <a name="l00830"></a>00830 { <span class="keywordflow">return</span> !(_SL2 < _SL1); } <a name="l00831"></a>00831 <a name="l00832"></a>00832 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00833"></a>00833 <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a name="l00834"></a>00834 operator>=(<span class="keyword">const</span> slist<_Tp, _Alloc>& _SL1, <span class="keyword">const</span> slist<_Tp, _Alloc>& _SL2) <a name="l00835"></a>00835 { <span class="keywordflow">return</span> !(_SL1 < _SL2); } <a name="l00836"></a>00836 <a name="l00837"></a>00837 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00838"></a>00838 <span class="keyword">inline</span> <span class="keywordtype">void</span> <a name="l00839"></a>00839 swap(slist<_Tp, _Alloc>& __x, slist<_Tp, _Alloc>& __y) <a name="l00840"></a>00840 { __x.swap(__y); } <a name="l00841"></a>00841 <a name="l00842"></a>00842 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00843"></a>00843 <span class="keywordtype">void</span> <a name="l00844"></a>00844 slist<_Tp, _Alloc>::resize(size_type __len, <span class="keyword">const</span> _Tp& __x) <a name="l00845"></a>00845 { <a name="l00846"></a>00846 _Node_base* __cur = &this->_M_head; <a name="l00847"></a>00847 <span class="keywordflow">while</span> (__cur->_M_next != 0 && __len > 0) <a name="l00848"></a>00848 { <a name="l00849"></a>00849 --__len; <a name="l00850"></a>00850 __cur = __cur->_M_next; <a name="l00851"></a>00851 } <a name="l00852"></a>00852 <span class="keywordflow">if</span> (__cur->_M_next) <a name="l00853"></a>00853 this->_M_erase_after(__cur, 0); <a name="l00854"></a>00854 <span class="keywordflow">else</span> <a name="l00855"></a>00855 _M_insert_after_fill(__cur, __len, __x); <a name="l00856"></a>00856 } <a name="l00857"></a>00857 <a name="l00858"></a>00858 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00859"></a>00859 <span class="keywordtype">void</span> <a name="l00860"></a>00860 slist<_Tp, _Alloc>::remove(<span class="keyword">const</span> _Tp& __val) <a name="l00861"></a>00861 { <a name="l00862"></a>00862 _Node_base* __cur = &this->_M_head; <a name="l00863"></a>00863 <span class="keywordflow">while</span> (__cur && __cur->_M_next) <a name="l00864"></a>00864 { <a name="l00865"></a>00865 <span class="keywordflow">if</span> (((_Node*) __cur->_M_next)->_M_data == __val) <a name="l00866"></a>00866 this->_M_erase_after(__cur); <a name="l00867"></a>00867 <span class="keywordflow">else</span> <a name="l00868"></a>00868 __cur = __cur->_M_next; <a name="l00869"></a>00869 } <a name="l00870"></a>00870 } <a name="l00871"></a>00871 <a name="l00872"></a>00872 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00873"></a>00873 <span class="keywordtype">void</span> <a name="l00874"></a>00874 slist<_Tp, _Alloc>::unique() <a name="l00875"></a>00875 { <a name="l00876"></a>00876 _Node_base* __cur = this->_M_head._M_next; <a name="l00877"></a>00877 <span class="keywordflow">if</span> (__cur) <a name="l00878"></a>00878 { <a name="l00879"></a>00879 <span class="keywordflow">while</span> (__cur->_M_next) <a name="l00880"></a>00880 { <a name="l00881"></a>00881 <span class="keywordflow">if</span> (((_Node*)__cur)->_M_data <a name="l00882"></a>00882 == ((_Node*)(__cur->_M_next))->_M_data) <a name="l00883"></a>00883 this->_M_erase_after(__cur); <a name="l00884"></a>00884 <span class="keywordflow">else</span> <a name="l00885"></a>00885 __cur = __cur->_M_next; <a name="l00886"></a>00886 } <a name="l00887"></a>00887 } <a name="l00888"></a>00888 } <a name="l00889"></a>00889 <a name="l00890"></a>00890 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00891"></a>00891 <span class="keywordtype">void</span> <a name="l00892"></a>00892 slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x) <a name="l00893"></a>00893 { <a name="l00894"></a>00894 _Node_base* __n1 = &this->_M_head; <a name="l00895"></a>00895 <span class="keywordflow">while</span> (__n1->_M_next && __x._M_head._M_next) <a name="l00896"></a>00896 { <a name="l00897"></a>00897 <span class="keywordflow">if</span> (((_Node*) __x._M_head._M_next)->_M_data <a name="l00898"></a>00898 < ((_Node*) __n1->_M_next)->_M_data) <a name="l00899"></a>00899 __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); <a name="l00900"></a>00900 __n1 = __n1->_M_next; <a name="l00901"></a>00901 } <a name="l00902"></a>00902 <span class="keywordflow">if</span> (__x._M_head._M_next) <a name="l00903"></a>00903 { <a name="l00904"></a>00904 __n1->_M_next = __x._M_head._M_next; <a name="l00905"></a>00905 __x._M_head._M_next = 0; <a name="l00906"></a>00906 } <a name="l00907"></a>00907 } <a name="l00908"></a>00908 <a name="l00909"></a>00909 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00910"></a>00910 <span class="keywordtype">void</span> <a name="l00911"></a>00911 slist<_Tp, _Alloc>::sort() <a name="l00912"></a>00912 { <a name="l00913"></a>00913 <span class="keywordflow">if</span> (this->_M_head._M_next && this->_M_head._M_next->_M_next) <a name="l00914"></a>00914 { <a name="l00915"></a>00915 slist __carry; <a name="l00916"></a>00916 slist __counter[64]; <a name="l00917"></a>00917 <span class="keywordtype">int</span> __fill = 0; <a name="l00918"></a>00918 <span class="keywordflow">while</span> (!empty()) <a name="l00919"></a>00919 { <a name="l00920"></a>00920 __slist_splice_after(&__carry._M_head, <a name="l00921"></a>00921 &this->_M_head, this->_M_head._M_next); <a name="l00922"></a>00922 <span class="keywordtype">int</span> __i = 0; <a name="l00923"></a>00923 <span class="keywordflow">while</span> (__i < __fill && !__counter[__i].empty()) <a name="l00924"></a>00924 { <a name="l00925"></a>00925 __counter[__i].merge(__carry); <a name="l00926"></a>00926 __carry.swap(__counter[__i]); <a name="l00927"></a>00927 ++__i; <a name="l00928"></a>00928 } <a name="l00929"></a>00929 __carry.swap(__counter[__i]); <a name="l00930"></a>00930 <span class="keywordflow">if</span> (__i == __fill) <a name="l00931"></a>00931 ++__fill; <a name="l00932"></a>00932 } <a name="l00933"></a>00933 <a name="l00934"></a>00934 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> __i = 1; __i < __fill; ++__i) <a name="l00935"></a>00935 __counter[__i].merge(__counter[__i-1]); <a name="l00936"></a>00936 this->swap(__counter[__fill-1]); <a name="l00937"></a>00937 } <a name="l00938"></a>00938 } <a name="l00939"></a>00939 <a name="l00940"></a>00940 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00941"></a>00941 <span class="keyword">template</span> <<span class="keyword">class</span> _Predicate> <a name="l00942"></a>00942 <span class="keywordtype">void</span> slist<_Tp, _Alloc>::remove_if(_Predicate __pred) <a name="l00943"></a>00943 { <a name="l00944"></a>00944 _Node_base* __cur = &this->_M_head; <a name="l00945"></a>00945 <span class="keywordflow">while</span> (__cur->_M_next) <a name="l00946"></a>00946 { <a name="l00947"></a>00947 <span class="keywordflow">if</span> (__pred(((_Node*) __cur->_M_next)->_M_data)) <a name="l00948"></a>00948 this->_M_erase_after(__cur); <a name="l00949"></a>00949 <span class="keywordflow">else</span> <a name="l00950"></a>00950 __cur = __cur->_M_next; <a name="l00951"></a>00951 } <a name="l00952"></a>00952 } <a name="l00953"></a>00953 <a name="l00954"></a>00954 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00955"></a>00955 <span class="keyword">template</span> <<span class="keyword">class</span> _BinaryPredicate> <a name="l00956"></a>00956 <span class="keywordtype">void</span> <a name="l00957"></a>00957 slist<_Tp, _Alloc>::unique(_BinaryPredicate __pred) <a name="l00958"></a>00958 { <a name="l00959"></a>00959 _Node* __cur = (_Node*) this->_M_head._M_next; <a name="l00960"></a>00960 if (__cur) <a name="l00961"></a>00961 { <a name="l00962"></a>00962 <span class="keywordflow">while</span> (__cur->_M_next) <a name="l00963"></a>00963 { <a name="l00964"></a>00964 <span class="keywordflow">if</span> (__pred(((_Node*)__cur)->_M_data, <a name="l00965"></a>00965 ((_Node*)(__cur->_M_next))->_M_data)) <a name="l00966"></a>00966 this->_M_erase_after(__cur); <a name="l00967"></a>00967 <span class="keywordflow">else</span> <a name="l00968"></a>00968 __cur = (_Node*) __cur->_M_next; <a name="l00969"></a>00969 } <a name="l00970"></a>00970 } <a name="l00971"></a>00971 } <a name="l00972"></a>00972 <a name="l00973"></a>00973 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00974"></a>00974 <span class="keyword">template</span> <<span class="keyword">class</span> _StrictWeakOrdering> <a name="l00975"></a>00975 <span class="keywordtype">void</span> <a name="l00976"></a>00976 slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x, <a name="l00977"></a>00977 _StrictWeakOrdering __comp) <a name="l00978"></a>00978 { <a name="l00979"></a>00979 _Node_base* __n1 = &this->_M_head; <a name="l00980"></a>00980 <span class="keywordflow">while</span> (__n1->_M_next && __x._M_head._M_next) <a name="l00981"></a>00981 { <a name="l00982"></a>00982 <span class="keywordflow">if</span> (__comp(((_Node*) __x._M_head._M_next)->_M_data, <a name="l00983"></a>00983 ((_Node*) __n1->_M_next)->_M_data)) <a name="l00984"></a>00984 __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); <a name="l00985"></a>00985 __n1 = __n1->_M_next; <a name="l00986"></a>00986 } <a name="l00987"></a>00987 <span class="keywordflow">if</span> (__x._M_head._M_next) <a name="l00988"></a>00988 { <a name="l00989"></a>00989 __n1->_M_next = __x._M_head._M_next; <a name="l00990"></a>00990 __x._M_head._M_next = 0; <a name="l00991"></a>00991 } <a name="l00992"></a>00992 } <a name="l00993"></a>00993 <a name="l00994"></a>00994 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l00995"></a>00995 <span class="keyword">template</span> <<span class="keyword">class</span> _StrictWeakOrdering> <a name="l00996"></a>00996 <span class="keywordtype">void</span> <a name="l00997"></a>00997 slist<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp) <a name="l00998"></a>00998 { <a name="l00999"></a>00999 <span class="keywordflow">if</span> (this->_M_head._M_next && this->_M_head._M_next->_M_next) <a name="l01000"></a>01000 { <a name="l01001"></a>01001 slist __carry; <a name="l01002"></a>01002 slist __counter[64]; <a name="l01003"></a>01003 <span class="keywordtype">int</span> __fill = 0; <a name="l01004"></a>01004 <span class="keywordflow">while</span> (!empty()) <a name="l01005"></a>01005 { <a name="l01006"></a>01006 __slist_splice_after(&__carry._M_head, <a name="l01007"></a>01007 &this->_M_head, this->_M_head._M_next); <a name="l01008"></a>01008 <span class="keywordtype">int</span> __i = 0; <a name="l01009"></a>01009 <span class="keywordflow">while</span> (__i < __fill && !__counter[__i].empty()) <a name="l01010"></a>01010 { <a name="l01011"></a>01011 __counter[__i].merge(__carry, __comp); <a name="l01012"></a>01012 __carry.swap(__counter[__i]); <a name="l01013"></a>01013 ++__i; <a name="l01014"></a>01014 } <a name="l01015"></a>01015 __carry.swap(__counter[__i]); <a name="l01016"></a>01016 <span class="keywordflow">if</span> (__i == __fill) <a name="l01017"></a>01017 ++__fill; <a name="l01018"></a>01018 } <a name="l01019"></a>01019 <a name="l01020"></a>01020 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> __i = 1; __i < __fill; ++__i) <a name="l01021"></a>01021 __counter[__i].merge(__counter[__i-1], __comp); <a name="l01022"></a>01022 this->swap(__counter[__fill-1]); <a name="l01023"></a>01023 } <a name="l01024"></a>01024 } <a name="l01025"></a>01025 <a name="l01026"></a>01026 _GLIBCXX_END_NAMESPACE_VERSION <a name="l01027"></a>01027 } <span class="comment">// namespace</span> <a name="l01028"></a>01028 <a name="l01029"></a>01029 <span class="keyword">namespace </span>std _GLIBCXX_VISIBILITY(default) <a name="l01030"></a>01030 { <a name="l01031"></a>01031 _GLIBCXX_BEGIN_NAMESPACE_VERSION <a name="l01032"></a>01032 <a name="l01033"></a>01033 <span class="comment">// Specialization of insert_iterator so that insertions will be constant</span> <a name="l01034"></a>01034 <span class="comment">// time rather than linear time.</span> <a name="l01035"></a>01035 <span class="keyword">template</span> <<span class="keyword">class</span> _Tp, <span class="keyword">class</span> _Alloc> <a name="l01036"></a>01036 <span class="keyword">class </span>insert_iterator<__gnu_cxx::slist<_Tp, _Alloc> > <a name="l01037"></a>01037 { <a name="l01038"></a>01038 <span class="keyword">protected</span>: <a name="l01039"></a>01039 <span class="keyword">typedef</span> <a class="code" href="a00067.html">__gnu_cxx::slist<_Tp, _Alloc></a> _Container; <a name="l01040"></a>01040 _Container* container; <a name="l01041"></a>01041 <span class="keyword">typename</span> _Container::iterator iter; <a name="l01042"></a>01042 <a name="l01043"></a>01043 <span class="keyword">public</span>: <a name="l01044"></a>01044 <span class="keyword">typedef</span> _Container <a class="code" href="a00526.html#a81ef704d3e33bcb38d894a8b1e440771" title="A nested typedef for the type of whatever container you used.">container_type</a>; <a name="l01045"></a>01045 <span class="keyword">typedef</span> output_iterator_tag <a class="code" href="a00260.html#a3d32527bfebba5c0459df1390cef50a9" title="One of the tag types.">iterator_category</a>; <a name="l01046"></a>01046 <span class="keyword">typedef</span> <span class="keywordtype">void</span> <a class="code" href="a00260.html#af9f36b7adb257959eef192b9282f1284" title="The type "pointed to" by the iterator.">value_type</a>; <a name="l01047"></a>01047 <span class="keyword">typedef</span> <span class="keywordtype">void</span> <a class="code" href="a00260.html#a7fc5091a6bee76d7bfc6ece04e4050f9" title="Distance between iterators is represented as this type.">difference_type</a>; <a name="l01048"></a>01048 <span class="keyword">typedef</span> <span class="keywordtype">void</span> <a class="code" href="a00260.html#a69bffe0bd881194df5ff48fec79066de" title="This type represents a pointer-to-value_type.">pointer</a>; <a name="l01049"></a>01049 <span class="keyword">typedef</span> <span class="keywordtype">void</span> <a class="code" href="a00260.html#abb17838f15d32971ad823036c6593aef" title="This type represents a reference-to-value_type.">reference</a>; <a name="l01050"></a>01050 <a name="l01051"></a>01051 <a class="code" href="a00526.html#a69916dd7c180bcb5fb6874adaaacc08b">insert_iterator</a>(_Container& __x, <span class="keyword">typename</span> _Container::iterator __i) <a name="l01052"></a>01052 : container(&__x) <a name="l01053"></a>01053 { <a name="l01054"></a>01054 <span class="keywordflow">if</span> (__i == __x.begin()) <a name="l01055"></a>01055 iter = __x.before_begin(); <a name="l01056"></a>01056 <span class="keywordflow">else</span> <a name="l01057"></a>01057 iter = __x.previous(__i); <a name="l01058"></a>01058 } <a name="l01059"></a>01059 <a name="l01060"></a>01060 insert_iterator<_Container>& <a name="l01061"></a>01061 <a class="code" href="a00526.html#a97b27e02a31008441dd0374c6a1021e4">operator=</a>(<span class="keyword">const</span> <span class="keyword">typename</span> _Container::value_type& __value) <a name="l01062"></a>01062 { <a name="l01063"></a>01063 iter = container->insert_after(iter, __value); <a name="l01064"></a>01064 <span class="keywordflow">return</span> *<span class="keyword">this</span>; <a name="l01065"></a>01065 } <a name="l01066"></a>01066 <a name="l01067"></a>01067 insert_iterator<_Container>& <a name="l01068"></a>01068 <a class="code" href="a00526.html#a1a406c868feb4c886b002870abeb8546" title="Simply returns *this.">operator*</a>() <a name="l01069"></a>01069 { <span class="keywordflow">return</span> *<span class="keyword">this</span>; } <a name="l01070"></a>01070 <a name="l01071"></a>01071 insert_iterator<_Container>& <a name="l01072"></a>01072 <a class="code" href="a00526.html#a66d30004d7402c9067fa8faadd7b8861" title="Simply returns *this. (This iterator does not move.)">operator++</a>() <a name="l01073"></a>01073 { <span class="keywordflow">return</span> *<span class="keyword">this</span>; } <a name="l01074"></a>01074 <a name="l01075"></a>01075 insert_iterator<_Container>& <a name="l01076"></a>01076 <a class="code" href="a00526.html#a66d30004d7402c9067fa8faadd7b8861" title="Simply returns *this. (This iterator does not move.)">operator++</a>(<span class="keywordtype">int</span>) <a name="l01077"></a>01077 { <span class="keywordflow">return</span> *<span class="keyword">this</span>; } <a name="l01078"></a>01078 }; <a name="l01079"></a>01079 <a name="l01080"></a>01080 _GLIBCXX_END_NAMESPACE_VERSION <a name="l01081"></a>01081 } <span class="comment">// namespace</span> <a name="l01082"></a>01082 <a name="l01083"></a>01083 <span class="preprocessor">#endif</span> </pre></div></div> </div> <div id="nav-path" class="navpath"> <ul> <li class="navelem"><a class="el" href="a01033.html">slist</a> </li> <li class="footer">Generated by  <a href="http://www.doxygen.org/index.html"> <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.7.4 </li> </ul> </div> </body> </html>