generic-library/boost
1
0
Fork 0
Code Issues Pull Requests Releases Wiki Activity
boost/doc/html/intrusive/slist.html
Edouard DUPIN d0115b733d [DEV] add v1.76.0
2021-10-05 21:37:46 +02:00

253 lines
28 KiB
HTML
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Intrusive singly linked list: slist</title>
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../intrusive.html" title="Chapter 19. Boost.Intrusive">
<link rel="prev" href="auto_unlink_hooks.html" title="Auto-unlink hooks">
<link rel="next" href="list.html" title="Intrusive doubly linked list: list">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
<td align="center"><a href="../../../index.html">Home</a></td>
<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<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>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="intrusive.slist"></a><a class="link" href="slist.html" title="Intrusive singly linked list: slist">Intrusive singly linked list: slist</a>
</h2></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="slist.html#intrusive.slist.slist_hooks">slist hooks</a></span></dt>
<dt><span class="section"><a href="slist.html#intrusive.slist.slist_container">slist container</a></span></dt>
<dt><span class="section"><a href="slist.html#intrusive.slist.slist_example">Example</a></span></dt>
</dl></div>
<p>
<code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> is the simplest
intrusive container of <span class="bold"><strong>Boost.Intrusive</strong></span>: a
singly linked list. The memory overhead it imposes is 1 pointer per node. The
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>
is the size of 1 pointer. This lightweight memory overhead comes with drawbacks,
though: many operations have linear time complexity, even some that usually
are constant time, like <code class="computeroutput">swap</code>.
<code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> only provides forward
iterators.
</p>
<p>
For most cases, a doubly linked list is preferable because it offers more constant-time
functions with a slightly bigger size overhead. However, for some applications
like constructing more elaborate containers, singly linked lists are essential
because of their low size overhead.
</p>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.slist.slist_hooks"></a><a class="link" href="slist.html#intrusive.slist.slist_hooks" title="slist hooks">slist hooks</a>
</h3></div></div></div>
<p>
Like the rest of <span class="bold"><strong>Boost.Intrusive</strong></span> containers,
<code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> has two hook types:
</p>
<pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="special">...</span><span class="identifier">Options</span><span class="special">&gt;</span>
<span class="keyword">class</span> <span class="identifier">slist_base_hook</span><span class="special">;</span>
</pre>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem">
<code class="computeroutput"><a class="link" href="../boost/intrusive/slist_base_hook.html" title="Class template slist_base_hook">slist_base_hook</a></code>:
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>
to make it <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code>-compatible.
</li></ul></div>
<pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="special">...</span><span class="identifier">Options</span><span class="special">&gt;</span>
<span class="keyword">class</span> <span class="identifier">slist_member_hook</span><span class="special">;</span>
</pre>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem">
<code class="computeroutput"><a class="link" href="../boost/intrusive/slist_member_hook.html" title="Class template slist_member_hook">slist_member_hook</a></code>:
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>
to make it <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code>-compatible.
</li></ul></div>
<p>
<code class="computeroutput"><a class="link" href="../boost/intrusive/slist_base_hook.html" title="Class template slist_base_hook">slist_base_hook</a></code>
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>
receive the same options explained in the section <a class="link" href="usage.html" title="How to use Boost.Intrusive">How
to use Boost.Intrusive</a>:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">tag</span><span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Tag</span><span class="special">&gt;</span></code></strong></span>
(for base hooks only): This argument serves as a tag, so you can derive
from more than one slist hook. Default: <code class="computeroutput"><span class="identifier">tag</span><span class="special">&lt;</span><span class="identifier">default_tag</span><span class="special">&gt;</span></code>.
</li>
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">link_mode</span><span class="special">&lt;</span><span class="identifier">link_mode_type</span>
<span class="identifier">LinkMode</span><span class="special">&gt;</span></code></strong></span>:
The linking policy. Default: <code class="computeroutput"><span class="identifier">link_mode</span><span class="special">&lt;</span><span class="identifier">safe_link</span><span class="special">&gt;</span></code>.
</li>
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">void_pointer</span><span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">VoidPointer</span><span class="special">&gt;</span></code></strong></span>:
The pointer type to be used internally in the hook and propagated to
the container. Default: <code class="computeroutput"><span class="identifier">void_pointer</span><span class="special">&lt;</span><span class="keyword">void</span><span class="special">*&gt;</span></code>.
</li>
</ul></div>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.slist.slist_container"></a><a class="link" href="slist.html#intrusive.slist.slist_container" title="slist container">slist container</a>
</h3></div></div></div>
<pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</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">&gt;</span>
<span class="keyword">class</span> <span class="identifier">slist</span><span class="special">;</span>
</pre>
<p>
<code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> receives the options
explained in the section <a class="link" href="usage.html" title="How to use Boost.Intrusive">How to use Boost.Intrusive</a>:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">base_hook</span><span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Hook</span><span class="special">&gt;</span></code></strong></span>
/ <span class="bold"><strong><code class="computeroutput"><span class="identifier">member_hook</span><span class="special">&lt;</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">&gt;</span></code></strong></span>
/ <span class="bold"><strong><code class="computeroutput"><span class="identifier">value_traits</span><span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">ValueTraits</span><span class="special">&gt;</span></code></strong></span>:
To specify the hook type or value traits used to configure the container.
(To learn about value traits go to the section <a class="link" href="value_traits.html" title="Containers with custom ValueTraits">Containers
with custom ValueTraits</a>.)
</li>
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">constant_time_size</span><span class="special">&lt;</span><span class="keyword">bool</span> <span class="identifier">Enabled</span><span class="special">&gt;</span></code></strong></span>:
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">&lt;</span><span class="keyword">true</span><span class="special">&gt;</span></code>
</li>
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">size_type</span><span class="special">&lt;</span><span class="keyword">typename</span>
<span class="identifier">SizeType</span><span class="special">&gt;</span></code></strong></span>:
To specify the type that will be used to store the size of the container.
Default: <code class="computeroutput"><span class="identifier">size_type</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span><span class="special">&gt;</span></code>.
</li>
</ul></div>
<p>
<code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> can receive additional
options:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">linear</span><span class="special">&lt;</span><span class="keyword">bool</span> <span class="identifier">Enable</span><span class="special">&gt;</span></code></strong></span>:
the singly linked list is implemented as a null-terminated list instead
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>
swap, but losses some operations like <code class="computeroutput"><span class="identifier">container_from_end_iterator</span></code>.
</li>
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">cache_last</span><span class="special">&lt;</span><span class="keyword">bool</span> <span class="identifier">Enable</span><span class="special">&gt;</span></code></strong></span>:
<code class="computeroutput"><span class="identifier">slist</span></code> also stores a pointer
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,
<code class="computeroutput"><span class="identifier">splice_after</span><span class="special">(</span><span class="identifier">iterator</span><span class="special">,</span>
<span class="identifier">slist</span> <span class="special">&amp;)</span></code>
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
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>
and the cached last node pointer must be updated in every operation,
and that might incur in a slight performance impact.
</li>
</ul></div>
<p>
<code class="computeroutput"><span class="identifier">auto_unlink</span></code> hooks are not
usable if <code class="computeroutput"><span class="identifier">linear</span><span class="special">&lt;</span><span class="keyword">true</span><span class="special">&gt;</span></code> and/or
<code class="computeroutput"><span class="identifier">cache_last</span><span class="special">&lt;</span><span class="keyword">true</span><span class="special">&gt;</span></code> options
are used. If <code class="computeroutput"><span class="identifier">auto_unlink</span></code>
hooks are used and those options are specified, a static assertion will be
raised.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.slist.slist_example"></a><a class="link" href="slist.html#intrusive.slist.slist_example" title="Example">Example</a>
</h3></div></div></div>
<p>
Now let's see a small example using both hooks:
</p>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</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">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">vector</span><span class="special">&gt;</span>
<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>
<span class="comment">//This is a base hook</span>
<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">&lt;&gt;</span>
<span class="special">{</span>
<span class="keyword">int</span> <span class="identifier">int_</span><span class="special">;</span>
<span class="keyword">public</span><span class="special">:</span>
<span class="comment">//This is a member hook</span>
<span class="identifier">slist_member_hook</span><span class="special">&lt;&gt;</span> <span class="identifier">member_hook_</span><span class="special">;</span>
<span class="identifier">MyClass</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">)</span>
<span class="special">:</span> <span class="identifier">int_</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span>
<span class="special">{}</span>
<span class="special">};</span>
<span class="comment">//Define an slist that will store MyClass using the public base hook</span>
<span class="keyword">typedef</span> <span class="identifier">slist</span><span class="special">&lt;</span><span class="identifier">MyClass</span><span class="special">&gt;</span> <span class="identifier">BaseList</span><span class="special">;</span>
<span class="comment">//Define an slist that will store MyClass using the public member hook</span>
<span class="keyword">typedef</span> <span class="identifier">member_hook</span><span class="special">&lt;</span><span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">slist_member_hook</span><span class="special">&lt;&gt;,</span> <span class="special">&amp;</span><span class="identifier">MyClass</span><span class="special">::</span><span class="identifier">member_hook_</span><span class="special">&gt;</span> <span class="identifier">MemberOption</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">slist</span><span class="special">&lt;</span><span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">MemberOption</span><span class="special">&gt;</span> <span class="identifier">MemberList</span><span class="special">;</span>
<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span>
<span class="special">{</span>
<span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">MyClass</span><span class="special">&gt;::</span><span class="identifier">iterator</span> <span class="identifier">VectIt</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">MyClass</span><span class="special">&gt;::</span><span class="identifier">reverse_iterator</span> <span class="identifier">VectRit</span><span class="special">;</span>
<span class="comment">//Create several MyClass objects, each one with a different value</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">MyClass</span><span class="special">&gt;</span> <span class="identifier">values</span><span class="special">;</span>
<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">&lt;</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>
<span class="identifier">BaseList</span> <span class="identifier">baselist</span><span class="special">;</span>
<span class="identifier">MemberList</span> <span class="identifier">memberlist</span><span class="special">;</span>
<span class="comment">//Now insert them in the reverse order in the base hook list</span>
<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>
<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>
<span class="comment">//Now insert them in the same order as in vector in the member hook list</span>
<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>
<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="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>
<span class="special">}</span>
<span class="comment">//Now test lists</span>
<span class="special">{</span>
<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>
<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>
<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>
<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="comment">//Test the objects inserted in the base hook list</span>
<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>
<span class="keyword">if</span><span class="special">(&amp;*</span><span class="identifier">bit</span> <span class="special">!=</span> <span class="special">&amp;*</span><span class="identifier">rit</span><span class="special">)</span> <span class="keyword">return</span> <span class="number">1</span><span class="special">;</span>
<span class="comment">//Test the objects inserted in the member hook list</span>
<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>
<span class="keyword">if</span><span class="special">(&amp;*</span><span class="identifier">mit</span> <span class="special">!=</span> <span class="special">&amp;*</span><span class="identifier">it</span><span class="special">)</span> <span class="keyword">return</span> <span class="number">1</span><span class="special">;</span>
<span class="special">}</span>
<span class="keyword">return</span> <span class="number">0</span><span class="special">;</span>
<span class="special">}</span>
</pre>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
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>)
</p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<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>
</div>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink