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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>When to use?</title>
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.78.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../intrusive.html" title="Chapter 15. Boost.Intrusive">
<link rel="prev" href="usage.html" title="How to use Boost.Intrusive">
<link rel="next" href="concepts_summary.html" title="Concept summary">
</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="usage.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="concepts_summary.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.usage_when"></a><a class="link" href="usage_when.html" title="When to use?">When to use?</a>
</h2></div></div></div>
<p>
Intrusive containers can be used for highly optimized algorithms, where speed
is a crucial issue and:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
additional memory management should be avoided.
</li>
<li class="listitem">
the programmer needs to efficiently track the construction and destruction
of objects.
</li>
<li class="listitem">
exception safety, especially the no-throw guarantee, is needed.
</li>
<li class="listitem">
the computation of an iterator to an element from a pointer or reference
to that element should be a constant time operation.
</li>
<li class="listitem">
it's important to achieve a well-known worst-time system response.
</li>
<li class="listitem">
localization of data (e.g. for cache hit optimization) leads to measurable
effects.
</li>
</ul></div>
<p>
The last point is important if you have a lot of containers over a set of elements.
E.g. if you have a vector of objects (say, <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">Object</span><span class="special">></span></code>), and you also have a list storing a subset
of those objects (<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">Object</span><span class="special">*></span></code>),
then operating on an Object from the list iterator (<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">Object</span><span class="special">*>::</span><span class="identifier">iterator</span></code>) requires two steps:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
Access from the iterator (usually on the stack) to the list node storing
a pointer to <code class="computeroutput"><span class="identifier">Object</span></code>.
</li>
<li class="listitem">
Access from the pointer to <code class="computeroutput"><span class="identifier">Object</span></code>
to the Object stored in the vector.
</li>
</ul></div>
<p>
While the objects themselves are tightly packed in the memory of the vector
(a vector's memory is guaranteed to be contiguous), and form something like
a data block, list nodes may be dispersed in the heap memory. Hence depending
on your system you might get a lot of cache misses. The same doesn't hold for
an intrusive list. Indeed, dereferencing an iterator from an intrusive list
is performed in the same two steps as described above. But the list node is
already embedded in the Object, so the memory is directly tracked from the
iterator to the Object.
</p>
<p>
It's also possible to use intrusive containers when the objects to be stored
can have different or unknown size. This allows storing base and derived objects
in the same container, as shown in the following example:
</p>
<p>
</p>
<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">list</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></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">//An abstract class that can be inserted in an intrusive list</span>
<span class="keyword">class</span> <span class="identifier">Window</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">list_base_hook</span><span class="special"><></span>
<span class="special">{</span>
<span class="keyword">public</span><span class="special">:</span>
<span class="comment">//This is a container those value is an abstract class: you can't do this with std::list.</span>
<span class="keyword">typedef</span> <span class="identifier">list</span><span class="special"><</span><span class="identifier">Window</span><span class="special">></span> <span class="identifier">win_list</span><span class="special">;</span>
<span class="comment">//A static intrusive list declaration</span>
<span class="keyword">static</span> <span class="identifier">win_list</span> <span class="identifier">all_windows</span><span class="special">;</span>
<span class="comment">//Constructor. Includes this window in the list</span>
<span class="identifier">Window</span><span class="special">()</span> <span class="special">{</span> <span class="identifier">all_windows</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(*</span><span class="keyword">this</span><span class="special">);</span> <span class="special">}</span>
<span class="comment">//Destructor. Removes this node from the list</span>
<span class="keyword">virtual</span> <span class="special">~</span><span class="identifier">Window</span><span class="special">()</span> <span class="special">{</span> <span class="identifier">all_windows</span><span class="special">.</span><span class="identifier">erase</span><span class="special">(</span><span class="identifier">win_list</span><span class="special">::</span><span class="identifier">s_iterator_to</span><span class="special">(*</span><span class="keyword">this</span><span class="special">));</span> <span class="special">}</span>
<span class="comment">//Pure virtual function to be implemented by derived classes</span>
<span class="keyword">virtual</span> <span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">()</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span>
<span class="special">};</span>
<span class="comment">//The static intrusive list declaration</span>
<span class="identifier">Window</span><span class="special">::</span><span class="identifier">win_list</span> <span class="identifier">Window</span><span class="special">::</span><span class="identifier">all_windows</span><span class="special">;</span>
<span class="comment">//Some Window derived classes</span>
<span class="keyword">class</span> <span class="identifier">FrameWindow</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">Window</span>
<span class="special">{</span> <span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">(){/**/}</span> <span class="special">};</span>
<span class="keyword">class</span> <span class="identifier">EditWindow</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">Window</span>
<span class="special">{</span> <span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">(){/**/}</span> <span class="special">};</span>
<span class="keyword">class</span> <span class="identifier">CanvasWindow</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">Window</span>
<span class="special">{</span> <span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">(){/**/}</span> <span class="special">};</span>
<span class="comment">//A function that prints all windows stored in the intrusive list</span>
<span class="keyword">void</span> <span class="identifier">paint_all_windows</span><span class="special">()</span>
<span class="special">{</span>
<span class="keyword">for</span><span class="special">(</span><span class="identifier">Window</span><span class="special">::</span><span class="identifier">win_list</span><span class="special">::</span><span class="identifier">iterator</span> <span class="identifier">i</span><span class="special">(</span><span class="identifier">Window</span><span class="special">::</span><span class="identifier">all_windows</span><span class="special">.</span><span class="identifier">begin</span><span class="special">())</span>
<span class="special">,</span> <span class="identifier">e</span><span class="special">(</span><span class="identifier">Window</span><span class="special">::</span><span class="identifier">all_windows</span><span class="special">.</span><span class="identifier">end</span><span class="special">())</span>
<span class="special">;</span> <span class="identifier">i</span> <span class="special">!=</span> <span class="identifier">e</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span>
<span class="identifier">i</span><span class="special">-></span><span class="identifier">Paint</span><span class="special">();</span>
<span class="special">}</span>
<span class="comment">//...</span>
<span class="comment">//A class derived from Window</span>
<span class="keyword">class</span> <span class="identifier">MainWindow</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">Window</span>
<span class="special">{</span>
<span class="identifier">FrameWindow</span> <span class="identifier">frame_</span><span class="special">;</span> <span class="comment">//these are derived from Window too</span>
<span class="identifier">EditWindow</span> <span class="identifier">edit_</span><span class="special">;</span>
<span class="identifier">CanvasWindow</span> <span class="identifier">canvas_</span><span class="special">;</span>
<span class="keyword">public</span><span class="special">:</span>
<span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">(){/**/}</span>
<span class="comment">//...</span>
<span class="special">};</span>
<span class="comment">//Main function</span>
<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span>
<span class="special">{</span>
<span class="comment">//When a Window class is created, is automatically registered in the global list</span>
<span class="identifier">MainWindow</span> <span class="identifier">window</span><span class="special">;</span>
<span class="comment">//Paint all the windows, sub-windows and so on</span>
<span class="identifier">paint_all_windows</span><span class="special">();</span>
<span class="comment">//All the windows are automatically unregistered in their destructors.</span>
<span class="keyword">return</span> <span class="number">0</span><span class="special">;</span>
<span class="special">}</span>
</pre>
<p>
</p>
<p>
Due to certain properties of intrusive containers they are often more difficult
to use than their STL-counterparts. That's why you should avoid them in public
interfaces of libraries. Classes to be stored in intrusive containers must
change their implementation to store the hook and this is not always possible
or desirable.
</p>
</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-2013 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="usage.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="concepts_summary.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
|
