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>Design Notes</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="obtaining_same_type_reducing_space.html" title="Obtaining the same types and reducing symbol length"> 11<link rel="next" href="performance.html" title="Performance"> 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="obtaining_same_type_reducing_space.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="performance.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.design_notes"></a><a class="link" href="design_notes.html" title="Design Notes">Design Notes</a> 29</h2></div></div></div> 30<div class="toc"><dl class="toc"> 31<dt><span class="section"><a href="design_notes.html#intrusive.design_notes.performance_sensitive">Boost.Intrusive 32 in performance sensitive environments</a></span></dt> 33<dt><span class="section"><a href="design_notes.html#intrusive.design_notes.space_constrained">Boost.Intrusive 34 in space constrained environments</a></span></dt> 35<dt><span class="section"><a href="design_notes.html#intrusive.design_notes.basic_building_block">Boost.Intrusive 36 as a basic building block</a></span></dt> 37<dt><span class="section"><a href="design_notes.html#intrusive.design_notes.extending_intrusive">Extending 38 Boost.Intrusive</a></span></dt> 39</dl></div> 40<p> 41 When designing <span class="bold"><strong>Boost.Intrusive</strong></span> the following 42 guidelines have been taken into account: 43 </p> 44<div class="section"> 45<div class="titlepage"><div><div><h3 class="title"> 46<a name="intrusive.design_notes.performance_sensitive"></a><a class="link" href="design_notes.html#intrusive.design_notes.performance_sensitive" title="Boost.Intrusive in performance sensitive environments">Boost.Intrusive 47 in performance sensitive environments</a> 48</h3></div></div></div> 49<p> 50 <span class="bold"><strong>Boost.Intrusive</strong></span> should be a valuable tool 51 in performance sensitive environments, and following this guideline, <span class="bold"><strong>Boost.Intrusive</strong></span> has been designed to offer well known 52 complexity guarantees. Apart from that, some options, like optional constant-time, 53 have been designed to offer faster complexity guarantees in some functions, 54 like <code class="computeroutput"><span class="identifier">slist</span><span class="special">::</span><span class="identifier">splice</span></code>. 55 </p> 56<p> 57 The advanced lookup and insertion functions for associative containers, taking 58 an arbitrary key type and predicates, were designed to avoid unnecessary 59 object constructions. 60 </p> 61</div> 62<div class="section"> 63<div class="titlepage"><div><div><h3 class="title"> 64<a name="intrusive.design_notes.space_constrained"></a><a class="link" href="design_notes.html#intrusive.design_notes.space_constrained" title="Boost.Intrusive in space constrained environments">Boost.Intrusive 65 in space constrained environments</a> 66</h3></div></div></div> 67<p> 68 <span class="bold"><strong>Boost.Intrusive</strong></span> should be useful in space 69 constrained environments, and following this guideline <span class="bold"><strong>Boost.Intrusive</strong></span> 70 separates node algorithms and intrusive containers to avoid instantiating 71 node algorithms for each user type. For example, a single class of red-black 72 algorithms will be instantiated to implement all set and multiset containers 73 using raw pointers. This way, <span class="bold"><strong>Boost.Intrusive</strong></span> 74 seeks to avoid any code size overhead associated with templates. 75 </p> 76<p> 77 Apart from that, <span class="bold"><strong>Boost.Intrusive</strong></span> implements 78 some size improvements: for example, red-black trees embed the color bit 79 in the parent pointer lower bit, if nodes are two-byte aligned. The option 80 to forgo constant-time size operations can reduce container size, and this 81 extra size optimization is noticeable when the container is empty or contains 82 few values. 83 </p> 84</div> 85<div class="section"> 86<div class="titlepage"><div><div><h3 class="title"> 87<a name="intrusive.design_notes.basic_building_block"></a><a class="link" href="design_notes.html#intrusive.design_notes.basic_building_block" title="Boost.Intrusive as a basic building block">Boost.Intrusive 88 as a basic building block</a> 89</h3></div></div></div> 90<p> 91 <span class="bold"><strong>Boost.Intrusive</strong></span> can be a basic building 92 block to build more complex containers and this potential has motivated many 93 design decisions. For example, the ability to have more than one hook per 94 user type opens the opportunity to implement multi-index containers on top 95 of <span class="bold"><strong>Boost.Intrusive</strong></span>. 96 </p> 97<p> 98 <span class="bold"><strong>Boost.Intrusive</strong></span> containers implement advanced 99 functions taking function objects as arguments (<code class="computeroutput"><span class="identifier">clone_from</span></code>, 100 <code class="computeroutput"><span class="identifier">erase_and_dispose</span></code>, <code class="computeroutput"><span class="identifier">insert_check</span></code>, etc.). These functions come 101 in handy when implementing non-intrusive containers (for example, STL-like 102 containers) on top of intrusive containers. 103 </p> 104</div> 105<div class="section"> 106<div class="titlepage"><div><div><h3 class="title"> 107<a name="intrusive.design_notes.extending_intrusive"></a><a class="link" href="design_notes.html#intrusive.design_notes.extending_intrusive" title="Extending Boost.Intrusive">Extending 108 Boost.Intrusive</a> 109</h3></div></div></div> 110<p> 111 <span class="bold"><strong>Boost.Intrusive</strong></span> offers a wide range of containers 112 but also allows the construction of custom containers reusing <span class="bold"><strong>Boost.Intrusive</strong></span> 113 elements. The programmer might want to use node algorithms directly or build 114 special hooks that take advantage of an application environment. 115 </p> 116<p> 117 For example, the programmer can customize parts of <span class="bold"><strong>Boost.Intrusive</strong></span> 118 to manage old data structures whose definition can't be changed. 119 </p> 120</div> 121</div> 122<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 123<td align="left"></td> 124<td align="right"><div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p> 125 Distributed under the Boost Software License, Version 1.0. (See accompanying 126 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>) 127 </p> 128</div></td> 129</tr></table> 130<hr> 131<div class="spirit-nav"> 132<a accesskey="p" href="obtaining_same_type_reducing_space.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="performance.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 133</div> 134</body> 135</html> 136
