1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>Intrusive singly linked list: slist</title> 6<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> 7<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 8<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> 9<link rel="up" href="../intrusive.html" title="Chapter 19. Boost.Intrusive"> 10<link rel="prev" href="auto_unlink_hooks.html" title="Auto-unlink hooks"> 11<link rel="next" href="list.html" title="Intrusive doubly linked list: list"> 12</head> 13<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 14<table cellpadding="2" width="100%"><tr> 15<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> 16<td align="center"><a href="../../../index.html">Home</a></td> 17<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> 18<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 19<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 20<td align="center"><a href="../../../more/index.htm">More</a></td> 21</tr></table> 22<hr> 23<div class="spirit-nav"> 24<a accesskey="p" href="auto_unlink_hooks.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="list.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 25</div> 26<div class="section"> 27<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 28<a name="intrusive.slist"></a><a class="link" href="slist.html" title="Intrusive singly linked list: slist">Intrusive singly linked list: slist</a> 29</h2></div></div></div> 30<div class="toc"><dl class="toc"> 31<dt><span class="section"><a href="slist.html#intrusive.slist.slist_hooks">slist hooks</a></span></dt> 32<dt><span class="section"><a href="slist.html#intrusive.slist.slist_container">slist container</a></span></dt> 33<dt><span class="section"><a href="slist.html#intrusive.slist.slist_example">Example</a></span></dt> 34</dl></div> 35<p> 36 <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> is the simplest 37 intrusive container of <span class="bold"><strong>Boost.Intrusive</strong></span>: a 38 singly linked list. The memory overhead it imposes is 1 pointer per node. The 39 size of an empty, non constant-time size <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> 40 is the size of 1 pointer. This lightweight memory overhead comes with drawbacks, 41 though: many operations have linear time complexity, even some that usually 42 are constant time, like <code class="computeroutput">swap</code>. 43 <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> only provides forward 44 iterators. 45 </p> 46<p> 47 For most cases, a doubly linked list is preferable because it offers more constant-time 48 functions with a slightly bigger size overhead. However, for some applications 49 like constructing more elaborate containers, singly linked lists are essential 50 because of their low size overhead. 51 </p> 52<div class="section"> 53<div class="titlepage"><div><div><h3 class="title"> 54<a name="intrusive.slist.slist_hooks"></a><a class="link" href="slist.html#intrusive.slist.slist_hooks" title="slist hooks">slist hooks</a> 55</h3></div></div></div> 56<p> 57 Like the rest of <span class="bold"><strong>Boost.Intrusive</strong></span> containers, 58 <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> has two hook types: 59 </p> 60<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span><span class="keyword">class</span> <span class="special">...</span><span class="identifier">Options</span><span class="special">></span> 61<span class="keyword">class</span> <span class="identifier">slist_base_hook</span><span class="special">;</span> 62</pre> 63<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"> 64 <code class="computeroutput"><a class="link" href="../boost/intrusive/slist_base_hook.html" title="Class template slist_base_hook">slist_base_hook</a></code>: 65 the user class derives publicly from <code class="computeroutput"><a class="link" href="../boost/intrusive/slist_base_hook.html" title="Class template slist_base_hook">slist_base_hook</a></code> 66 to make it <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code>-compatible. 67 </li></ul></div> 68<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span><span class="keyword">class</span> <span class="special">...</span><span class="identifier">Options</span><span class="special">></span> 69<span class="keyword">class</span> <span class="identifier">slist_member_hook</span><span class="special">;</span> 70</pre> 71<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"> 72 <code class="computeroutput"><a class="link" href="../boost/intrusive/slist_member_hook.html" title="Class template slist_member_hook">slist_member_hook</a></code>: 73 the user class contains a public <code class="computeroutput"><a class="link" href="../boost/intrusive/slist_member_hook.html" title="Class template slist_member_hook">slist_member_hook</a></code> 74 to make it <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code>-compatible. 75 </li></ul></div> 76<p> 77 <code class="computeroutput"><a class="link" href="../boost/intrusive/slist_base_hook.html" title="Class template slist_base_hook">slist_base_hook</a></code> 78 and <code class="computeroutput"><a class="link" href="../boost/intrusive/slist_member_hook.html" title="Class template slist_member_hook">slist_member_hook</a></code> 79 receive the same options explained in the section <a class="link" href="usage.html" title="How to use Boost.Intrusive">How 80 to use Boost.Intrusive</a>: 81 </p> 82<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 83<li class="listitem"> 84 <span class="bold"><strong><code class="computeroutput"><span class="identifier">tag</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">Tag</span><span class="special">></span></code></strong></span> 85 (for base hooks only): This argument serves as a tag, so you can derive 86 from more than one slist hook. Default: <code class="computeroutput"><span class="identifier">tag</span><span class="special"><</span><span class="identifier">default_tag</span><span class="special">></span></code>. 87 </li> 88<li class="listitem"> 89 <span class="bold"><strong><code class="computeroutput"><span class="identifier">link_mode</span><span class="special"><</span><span class="identifier">link_mode_type</span> 90 <span class="identifier">LinkMode</span><span class="special">></span></code></strong></span>: 91 The linking policy. Default: <code class="computeroutput"><span class="identifier">link_mode</span><span class="special"><</span><span class="identifier">safe_link</span><span class="special">></span></code>. 92 </li> 93<li class="listitem"> 94 <span class="bold"><strong><code class="computeroutput"><span class="identifier">void_pointer</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">VoidPointer</span><span class="special">></span></code></strong></span>: 95 The pointer type to be used internally in the hook and propagated to 96 the container. Default: <code class="computeroutput"><span class="identifier">void_pointer</span><span class="special"><</span><span class="keyword">void</span><span class="special">*></span></code>. 97 </li> 98</ul></div> 99</div> 100<div class="section"> 101<div class="titlepage"><div><div><h3 class="title"> 102<a name="intrusive.slist.slist_container"></a><a class="link" href="slist.html#intrusive.slist.slist_container" title="slist container">slist container</a> 103</h3></div></div></div> 104<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="special">...</span><span class="identifier">Options</span><span class="special">></span> 105<span class="keyword">class</span> <span class="identifier">slist</span><span class="special">;</span> 106</pre> 107<p> 108 <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> receives the options 109 explained in the section <a class="link" href="usage.html" title="How to use Boost.Intrusive">How to use Boost.Intrusive</a>: 110 </p> 111<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 112<li class="listitem"> 113 <span class="bold"><strong><code class="computeroutput"><span class="identifier">base_hook</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">Hook</span><span class="special">></span></code></strong></span> 114 / <span class="bold"><strong><code class="computeroutput"><span class="identifier">member_hook</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Hook</span><span class="special">,</span> <span class="identifier">Hook</span> <span class="identifier">T</span><span class="special">::*</span> <span class="identifier">PtrToMember</span><span class="special">></span></code></strong></span> 115 / <span class="bold"><strong><code class="computeroutput"><span class="identifier">value_traits</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">ValueTraits</span><span class="special">></span></code></strong></span>: 116 To specify the hook type or value traits used to configure the container. 117 (To learn about value traits go to the section <a class="link" href="value_traits.html" title="Containers with custom ValueTraits">Containers 118 with custom ValueTraits</a>.) 119 </li> 120<li class="listitem"> 121 <span class="bold"><strong><code class="computeroutput"><span class="identifier">constant_time_size</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">Enabled</span><span class="special">></span></code></strong></span>: 122 To activate the constant-time <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> operation. Default: <code class="computeroutput"><span class="identifier">constant_time_size</span><span class="special"><</span><span class="keyword">true</span><span class="special">></span></code> 123 </li> 124<li class="listitem"> 125 <span class="bold"><strong><code class="computeroutput"><span class="identifier">size_type</span><span class="special"><</span><span class="keyword">typename</span> 126 <span class="identifier">SizeType</span><span class="special">></span></code></strong></span>: 127 To specify the type that will be used to store the size of the container. 128 Default: <code class="computeroutput"><span class="identifier">size_type</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span><span class="special">></span></code>. 129 </li> 130</ul></div> 131<p> 132 <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> can receive additional 133 options: 134 </p> 135<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 136<li class="listitem"> 137 <span class="bold"><strong><code class="computeroutput"><span class="identifier">linear</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">Enable</span><span class="special">></span></code></strong></span>: 138 the singly linked list is implemented as a null-terminated list instead 139 of a circular list. This allows <code class="computeroutput"><span class="identifier">O</span><span class="special">(</span><span class="number">1</span><span class="special">)</span></code> 140 swap, but losses some operations like <code class="computeroutput"><span class="identifier">container_from_end_iterator</span></code>. 141 </li> 142<li class="listitem"> 143 <span class="bold"><strong><code class="computeroutput"><span class="identifier">cache_last</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">Enable</span><span class="special">></span></code></strong></span>: 144 <code class="computeroutput"><span class="identifier">slist</span></code> also stores a pointer 145 to the last element of the singly linked list. This allows <code class="computeroutput"><span class="identifier">O</span><span class="special">(</span><span class="number">1</span><span class="special">)</span></code> swap, 146 <code class="computeroutput"><span class="identifier">splice_after</span><span class="special">(</span><span class="identifier">iterator</span><span class="special">,</span> 147 <span class="identifier">slist</span> <span class="special">&)</span></code> 148 and makes the list offer new functions like <code class="computeroutput"><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">reference</span><span class="special">)</span></code> and <code class="computeroutput"><span class="identifier">back</span><span class="special">()</span></code>. Logically, the size an empty list 149 is increased in <code class="computeroutput"><span class="keyword">sizeof</span><span class="special">(</span><span class="identifier">void_pointer</span><span class="special">)</span></code> 150 and the cached last node pointer must be updated in every operation, 151 and that might incur in a slight performance impact. 152 </li> 153</ul></div> 154<p> 155 <code class="computeroutput"><span class="identifier">auto_unlink</span></code> hooks are not 156 usable if <code class="computeroutput"><span class="identifier">linear</span><span class="special"><</span><span class="keyword">true</span><span class="special">></span></code> and/or 157 <code class="computeroutput"><span class="identifier">cache_last</span><span class="special"><</span><span class="keyword">true</span><span class="special">></span></code> options 158 are used. If <code class="computeroutput"><span class="identifier">auto_unlink</span></code> 159 hooks are used and those options are specified, a static assertion will be 160 raised. 161 </p> 162</div> 163<div class="section"> 164<div class="titlepage"><div><div><h3 class="title"> 165<a name="intrusive.slist.slist_example"></a><a class="link" href="slist.html#intrusive.slist.slist_example" title="Example">Example</a> 166</h3></div></div></div> 167<p> 168 Now let's see a small example using both hooks: 169 </p> 170<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">slist</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 171<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">vector</span><span class="special">></span> 172 173<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">;</span> 174 175 <span class="comment">//This is a base hook</span> 176<span class="keyword">class</span> <span class="identifier">MyClass</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">slist_base_hook</span><span class="special"><></span> 177<span class="special">{</span> 178 <span class="keyword">int</span> <span class="identifier">int_</span><span class="special">;</span> 179 180 <span class="keyword">public</span><span class="special">:</span> 181 <span class="comment">//This is a member hook</span> 182 <span class="identifier">slist_member_hook</span><span class="special"><></span> <span class="identifier">member_hook_</span><span class="special">;</span> 183 184 <span class="identifier">MyClass</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">)</span> 185 <span class="special">:</span> <span class="identifier">int_</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> 186 <span class="special">{}</span> 187<span class="special">};</span> 188 189<span class="comment">//Define an slist that will store MyClass using the public base hook</span> 190<span class="keyword">typedef</span> <span class="identifier">slist</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">></span> <span class="identifier">BaseList</span><span class="special">;</span> 191 192<span class="comment">//Define an slist that will store MyClass using the public member hook</span> 193<span class="keyword">typedef</span> <span class="identifier">member_hook</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">slist_member_hook</span><span class="special"><>,</span> <span class="special">&</span><span class="identifier">MyClass</span><span class="special">::</span><span class="identifier">member_hook_</span><span class="special">></span> <span class="identifier">MemberOption</span><span class="special">;</span> 194<span class="keyword">typedef</span> <span class="identifier">slist</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">MemberOption</span><span class="special">></span> <span class="identifier">MemberList</span><span class="special">;</span> 195 196<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 197<span class="special">{</span> 198 <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">>::</span><span class="identifier">iterator</span> <span class="identifier">VectIt</span><span class="special">;</span> 199 <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">>::</span><span class="identifier">reverse_iterator</span> <span class="identifier">VectRit</span><span class="special">;</span> 200 201 <span class="comment">//Create several MyClass objects, each one with a different value</span> 202 <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">></span> <span class="identifier">values</span><span class="special">;</span> 203 <span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special"><</span> <span class="number">100</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span> <span class="identifier">values</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">MyClass</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span> 204 205 <span class="identifier">BaseList</span> <span class="identifier">baselist</span><span class="special">;</span> 206 <span class="identifier">MemberList</span> <span class="identifier">memberlist</span><span class="special">;</span> 207 208 <span class="comment">//Now insert them in the reverse order in the base hook list</span> 209 <span class="keyword">for</span><span class="special">(</span><span class="identifier">VectIt</span> <span class="identifier">it</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()),</span> <span class="identifier">itend</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">itend</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">)</span> 210 <span class="identifier">baselist</span><span class="special">.</span><span class="identifier">push_front</span><span class="special">(*</span><span class="identifier">it</span><span class="special">);</span> 211 212 <span class="comment">//Now insert them in the same order as in vector in the member hook list</span> 213 <span class="keyword">for</span><span class="special">(</span><span class="identifier">BaseList</span><span class="special">::</span><span class="identifier">iterator</span> <span class="identifier">it</span><span class="special">(</span><span class="identifier">baselist</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()),</span> <span class="identifier">itend</span><span class="special">(</span><span class="identifier">baselist</span><span class="special">.</span><span class="identifier">end</span><span class="special">())</span> 214 <span class="special">;</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">itend</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">){</span> 215 <span class="identifier">memberlist</span><span class="special">.</span><span class="identifier">push_front</span><span class="special">(*</span><span class="identifier">it</span><span class="special">);</span> 216 <span class="special">}</span> 217 218 <span class="comment">//Now test lists</span> 219 <span class="special">{</span> 220 <span class="identifier">BaseList</span><span class="special">::</span><span class="identifier">iterator</span> <span class="identifier">bit</span><span class="special">(</span><span class="identifier">baselist</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());</span> 221 <span class="identifier">MemberList</span><span class="special">::</span><span class="identifier">iterator</span> <span class="identifier">mit</span><span class="special">(</span><span class="identifier">memberlist</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());</span> 222 <span class="identifier">VectRit</span> <span class="identifier">rit</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">rbegin</span><span class="special">()),</span> <span class="identifier">ritend</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">rend</span><span class="special">());</span> 223 <span class="identifier">VectIt</span> <span class="identifier">it</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()),</span> <span class="identifier">itend</span><span class="special">(</span><span class="identifier">values</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> 224 225 <span class="comment">//Test the objects inserted in the base hook list</span> 226 <span class="keyword">for</span><span class="special">(;</span> <span class="identifier">rit</span> <span class="special">!=</span> <span class="identifier">ritend</span><span class="special">;</span> <span class="special">++</span><span class="identifier">rit</span><span class="special">,</span> <span class="special">++</span><span class="identifier">bit</span><span class="special">)</span> 227 <span class="keyword">if</span><span class="special">(&*</span><span class="identifier">bit</span> <span class="special">!=</span> <span class="special">&*</span><span class="identifier">rit</span><span class="special">)</span> <span class="keyword">return</span> <span class="number">1</span><span class="special">;</span> 228 229 <span class="comment">//Test the objects inserted in the member hook list</span> 230 <span class="keyword">for</span><span class="special">(;</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">itend</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">,</span> <span class="special">++</span><span class="identifier">mit</span><span class="special">)</span> 231 <span class="keyword">if</span><span class="special">(&*</span><span class="identifier">mit</span> <span class="special">!=</span> <span class="special">&*</span><span class="identifier">it</span><span class="special">)</span> <span class="keyword">return</span> <span class="number">1</span><span class="special">;</span> 232 <span class="special">}</span> 233 234 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 235<span class="special">}</span> 236</pre> 237</div> 238</div> 239<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 240<td align="left"></td> 241<td align="right"><div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p> 242 Distributed under the Boost Software License, Version 1.0. (See accompanying 243 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 244 </p> 245</div></td> 246</tr></table> 247<hr> 248<div class="spirit-nav"> 249<a accesskey="p" href="auto_unlink_hooks.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="list.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 250</div> 251</body> 252</html> 253
