1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
<!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=US-ASCII">
<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.76.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../intrusive.html" title="Chapter 16. 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" 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" 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" 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" 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" 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>
|
