169 lines
12 KiB
HTML
169 lines
12 KiB
HTML
<!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>Presenting Boost.Intrusive containers</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="concepts_summary.html" title="Concept summary">
|
||
<link rel="next" href="safe_hook.html" title="Safe hooks">
|
||
</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="concepts_summary.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="safe_hook.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.presenting_containers"></a><a class="link" href="presenting_containers.html" title="Presenting Boost.Intrusive containers">Presenting Boost.Intrusive
|
||
containers</a>
|
||
</h2></div></div></div>
|
||
<p>
|
||
<span class="bold"><strong>Boost.Intrusive</strong></span> offers a wide range of intrusive
|
||
containers:
|
||
</p>
|
||
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
|
||
<li class="listitem">
|
||
<span class="bold"><strong>slist</strong></span>: An intrusive singly linked list.
|
||
The size overhead is very small for user classes (usually the size of one
|
||
pointer) but many operations have linear time complexity, so the user must
|
||
be careful if he wants to avoid performance problems.
|
||
</li>
|
||
<li class="listitem">
|
||
<span class="bold"><strong>list</strong></span>: A <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span></code>
|
||
like intrusive linked list. The size overhead is quite small for user classes
|
||
(usually the size of two pointers). Many operations have constant time
|
||
complexity.
|
||
</li>
|
||
<li class="listitem">
|
||
<span class="bold"><strong>set/multiset/rbtree</strong></span>: <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code>
|
||
like intrusive associative containers based on red-black trees. The size
|
||
overhead is moderate for user classes (usually the size of three pointers).
|
||
Many operations have logarithmic time complexity.
|
||
</li>
|
||
<li class="listitem">
|
||
<span class="bold"><strong>avl_set/avl_multiset/avltree</strong></span>: A <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> like intrusive associative containers
|
||
based on AVL trees. The size overhead is moderate for user classes (usually
|
||
the size of three pointers). Many operations have logarithmic time complexity.
|
||
</li>
|
||
<li class="listitem">
|
||
<span class="bold"><strong>splay_set/splay_multiset/splaytree</strong></span>: <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> like intrusive associative containers
|
||
based on splay trees. Splay trees have no constant operations, but they
|
||
have some interesting caching properties. The size overhead is moderate
|
||
for user classes (usually the size of three pointers). Many operations
|
||
have logarithmic time complexity.
|
||
</li>
|
||
<li class="listitem">
|
||
<span class="bold"><strong>sg_set/sg_multiset/sgtree</strong></span>: A <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> like intrusive associative containers
|
||
based on scapegoat trees. Scapegoat can be configured with the desired
|
||
balance factor to achieve the desired rebalancing frequency/search time
|
||
compromise. The size overhead is moderate for user classes (usually the
|
||
size of three pointers). Many operations have logarithmic time complexity.
|
||
</li>
|
||
</ul></div>
|
||
<p>
|
||
<span class="bold"><strong>Boost.Intrusive</strong></span> also offers semi-intrusive
|
||
containers:
|
||
</p>
|
||
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem">
|
||
<span class="bold"><strong>unordered_set/unordered_multiset</strong></span>: <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">tr1</span><span class="special">::</span><span class="identifier">unordered_set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">tr1</span><span class="special">::</span><span class="identifier">unordered_multiset</span></code> like intrusive unordered
|
||
associative containers. The size overhead is moderate for user classes
|
||
(an average of two pointers per element). Many operations have amortized
|
||
constant time complexity.
|
||
</li></ul></div>
|
||
<p>
|
||
Most of these intrusive containers can be configured with constant or linear
|
||
time size:
|
||
</p>
|
||
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
|
||
<li class="listitem">
|
||
<span class="bold"><strong>Linear time size</strong></span>: The intrusive container
|
||
doesn't hold a size member that is updated with every insertion/erasure.
|
||
This implies that the <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> function doesn't have constant time complexity.
|
||
On the other hand, the container is smaller, and some operations, like
|
||
<code class="computeroutput"><span class="identifier">splice</span><span class="special">()</span></code>
|
||
taking a range of iterators in linked lists, have constant time complexity
|
||
instead of linear complexity.
|
||
</li>
|
||
<li class="listitem">
|
||
<span class="bold"><strong>Constant time size</strong></span>: The intrusive container
|
||
holds a size member that is updated with every insertion/erasure. This
|
||
implies that the <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>
|
||
function has constant time complexity. On the other hand, increases the
|
||
size of the container, and some operations, like <code class="computeroutput"><span class="identifier">splice</span><span class="special">()</span></code> taking a range of iterators, have linear
|
||
time complexity in linked lists.
|
||
</li>
|
||
</ul></div>
|
||
<p>
|
||
To make user classes compatible with these intrusive containers <span class="bold"><strong>Boost.Intrusive</strong></span>
|
||
offers two types of hooks for each container type:
|
||
</p>
|
||
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
|
||
<li class="listitem">
|
||
<span class="bold"><strong>Base hook</strong></span>: The hook is stored as a public
|
||
base class of the user class.
|
||
</li>
|
||
<li class="listitem">
|
||
<span class="bold"><strong>Member hook</strong></span>: The hook is stored as a public
|
||
member of the user class.
|
||
</li>
|
||
</ul></div>
|
||
<p>
|
||
Apart from that, <span class="bold"><strong>Boost.Intrusive</strong></span> offers additional
|
||
features:
|
||
</p>
|
||
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
|
||
<li class="listitem">
|
||
<span class="bold"><strong>Safe mode hooks</strong></span>: Hook constructor initializes
|
||
the internal <code class="computeroutput"><span class="identifier">node</span></code> to a
|
||
well-known safe state and intrusive containers check that state before
|
||
inserting a value in the container using that hook. When erasing an element
|
||
from the container, the container puts the <code class="computeroutput"><span class="identifier">node</span></code>
|
||
of the hook in the safe state again. This allows a safer use mode and it
|
||
can be used to detect programming errors. It implies a slight performance
|
||
overhead in some operations and can convert some constant time operations
|
||
to linear time operations.
|
||
</li>
|
||
<li class="listitem">
|
||
<span class="bold"><strong>Auto-unlink hooks</strong></span>: The hook destructor
|
||
removes the object from the container automatically and the user can safely
|
||
unlink the object from the container without referring to the container.
|
||
</li>
|
||
<li class="listitem">
|
||
<span class="bold"><strong>Non-raw pointers</strong></span>: If the user wants to
|
||
use smart pointers instead of raw pointers, <span class="bold"><strong>Boost.Intrusive</strong></span>
|
||
hooks can be configured to use any type of pointer. This configuration
|
||
information is also transmitted to the containers, so all the internal
|
||
pointers used by intrusive containers configured with these hooks will
|
||
be smart pointers. As an example, <span class="bold"><strong>Boost.Interprocess</strong></span>
|
||
defines a smart pointer compatible with shared memory, called <code class="computeroutput"><span class="identifier">offset_ptr</span></code>. <span class="bold"><strong>Boost.Intrusive</strong></span>
|
||
can be configured to use this smart pointer to allow shared memory intrusive
|
||
containers.
|
||
</li>
|
||
</ul></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="concepts_summary.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="safe_hook.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
|
||
</div>
|
||
</body>
|
||
</html>
|