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>When to use?</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="usage.html" title="How to use Boost.Intrusive"> 11<link rel="next" href="concepts_summary.html" title="Concept summary"> 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="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> 25</div> 26<div class="section"> 27<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 28<a name="intrusive.usage_when"></a><a class="link" href="usage_when.html" title="When to use?">When to use?</a> 29</h2></div></div></div> 30<p> 31 Intrusive containers can be used for highly optimized algorithms, where speed 32 is a crucial issue and: 33 </p> 34<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 35<li class="listitem"> 36 additional memory management should be avoided. 37 </li> 38<li class="listitem"> 39 the programmer needs to efficiently track the construction and destruction 40 of objects. 41 </li> 42<li class="listitem"> 43 exception safety, especially the no-throw guarantee, is needed. 44 </li> 45<li class="listitem"> 46 the computation of an iterator to an element from a pointer or reference 47 to that element should be a constant time operation. 48 </li> 49<li class="listitem"> 50 it's important to achieve a well-known worst-time system response. 51 </li> 52<li class="listitem"> 53 localization of data (e.g. for cache hit optimization) leads to measurable 54 effects. 55 </li> 56</ul></div> 57<p> 58 The last point is important if you have a lot of containers over a set of elements. 59 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 60 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>), 61 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: 62 </p> 63<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 64<li class="listitem"> 65 Access from the iterator (usually on the stack) to the list node storing 66 a pointer to <code class="computeroutput"><span class="identifier">Object</span></code>. 67 </li> 68<li class="listitem"> 69 Access from the pointer to <code class="computeroutput"><span class="identifier">Object</span></code> 70 to the Object stored in the vector. 71 </li> 72</ul></div> 73<p> 74 While the objects themselves are tightly packed in the memory of the vector 75 (a vector's memory is guaranteed to be contiguous), and form something like 76 a data block, list nodes may be dispersed in the heap memory. Hence depending 77 on your system you might get a lot of cache misses. The same doesn't hold for 78 an intrusive list. Indeed, dereferencing an iterator from an intrusive list 79 is performed in the same two steps as described above. But the list node is 80 already embedded in the Object, so the memory is directly tracked from the 81 iterator to the Object. 82 </p> 83<p> 84 It's also possible to use intrusive containers when the objects to be stored 85 can have different or unknown size. This allows storing base and derived objects 86 in the same container, as shown in the following example: 87 </p> 88<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> 89 90<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> 91 92<span class="comment">//An abstract class that can be inserted in an intrusive list</span> 93<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> 94<span class="special">{</span> 95 <span class="keyword">public</span><span class="special">:</span> 96 <span class="comment">//This is a container those value is an abstract class: you can't do this with std::list.</span> 97 <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> 98 99 <span class="comment">//A static intrusive list declaration</span> 100 <span class="keyword">static</span> <span class="identifier">win_list</span> <span class="identifier">all_windows</span><span class="special">;</span> 101 102 <span class="comment">//Constructor. Includes this window in the list</span> 103 <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> 104 <span class="comment">//Destructor. Removes this node from the list</span> 105 <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> 106 <span class="comment">//Pure virtual function to be implemented by derived classes</span> 107 <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> 108<span class="special">};</span> 109 110<span class="comment">//The static intrusive list declaration</span> 111<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> 112 113<span class="comment">//Some Window derived classes</span> 114<span class="keyword">class</span> <span class="identifier">FrameWindow</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">Window</span> 115<span class="special">{</span> <span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">(){/**/}</span> <span class="special">};</span> 116 117<span class="keyword">class</span> <span class="identifier">EditWindow</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">Window</span> 118<span class="special">{</span> <span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">(){/**/}</span> <span class="special">};</span> 119 120<span class="keyword">class</span> <span class="identifier">CanvasWindow</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">Window</span> 121<span class="special">{</span> <span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">(){/**/}</span> <span class="special">};</span> 122 123<span class="comment">//A function that prints all windows stored in the intrusive list</span> 124<span class="keyword">void</span> <span class="identifier">paint_all_windows</span><span class="special">()</span> 125<span class="special">{</span> 126 <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> 127 <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> 128 <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> 129 <span class="identifier">i</span><span class="special">-></span><span class="identifier">Paint</span><span class="special">();</span> 130<span class="special">}</span> 131 132<span class="comment">//...</span> 133 134<span class="comment">//A class derived from Window</span> 135<span class="keyword">class</span> <span class="identifier">MainWindow</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">Window</span> 136<span class="special">{</span> 137 <span class="identifier">FrameWindow</span> <span class="identifier">frame_</span><span class="special">;</span> <span class="comment">//these are derived from Window too</span> 138 <span class="identifier">EditWindow</span> <span class="identifier">edit_</span><span class="special">;</span> 139 <span class="identifier">CanvasWindow</span> <span class="identifier">canvas_</span><span class="special">;</span> 140 141 <span class="keyword">public</span><span class="special">:</span> 142 <span class="keyword">void</span> <span class="identifier">Paint</span><span class="special">(){/**/}</span> 143 <span class="comment">//...</span> 144<span class="special">};</span> 145 146<span class="comment">//Main function</span> 147<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 148<span class="special">{</span> 149 <span class="comment">//When a Window class is created, is automatically registered in the global list</span> 150 <span class="identifier">MainWindow</span> <span class="identifier">window</span><span class="special">;</span> 151 152 <span class="comment">//Paint all the windows, sub-windows and so on</span> 153 <span class="identifier">paint_all_windows</span><span class="special">();</span> 154 155 <span class="comment">//All the windows are automatically unregistered in their destructors.</span> 156 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 157<span class="special">}</span> 158</pre> 159<p> 160 Due to certain properties of intrusive containers they are often more difficult 161 to use than their STL-counterparts. That's why you should avoid them in public 162 interfaces of libraries. Classes to be stored in intrusive containers must 163 change their implementation to store the hook and this is not always possible 164 or desirable. 165 </p> 166</div> 167<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 168<td align="left"></td> 169<td align="right"><div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p> 170 Distributed under the Boost Software License, Version 1.0. (See accompanying 171 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>) 172 </p> 173</div></td> 174</tr></table> 175<hr> 176<div class="spirit-nav"> 177<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> 178</div> 179</body> 180</html> 181
