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
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Design Notes</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 13. Boost.Intrusive">
<link rel="prev" href="obtaining_same_type_reducing_space.html" title="Obtaining the same types and reducing symbol length">
<link rel="next" href="performance.html" title="Performance">
</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="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>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="intrusive.design_notes"></a><a class="link" href="design_notes.html" title="Design Notes">Design Notes</a>
</h2></div></div></div>
<div class="toc"><dl>
<dt><span class="section"><a href="design_notes.html#intrusive.design_notes.performance_sensitive">Boost.Intrusive
in performance sensitive environments</a></span></dt>
<dt><span class="section"><a href="design_notes.html#intrusive.design_notes.space_constrained">Boost.Intrusive
in space constrained environments</a></span></dt>
<dt><span class="section"><a href="design_notes.html#intrusive.design_notes.basic_building_block">Boost.Intrusive
as a basic building block</a></span></dt>
<dt><span class="section"><a href="design_notes.html#intrusive.design_notes.extending_intrusive">Extending
Boost.Intrusive</a></span></dt>
</dl></div>
<p>
When designing <span class="bold"><strong>Boost.Intrusive</strong></span> the following
guidelines have been taken into account:
</p>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<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
in performance sensitive environments</a>
</h3></div></div></div>
<p>
<span class="bold"><strong>Boost.Intrusive</strong></span> should be a valuable tool
in performance sensitive environments, and following this guideline, <span class="bold"><strong>Boost.Intrusive</strong></span> has been designed to offer well known
complexity guarantees. Apart from that, some options, like optional constant-time,
have been designed to offer faster complexity guarantees in some functions,
like <code class="computeroutput"><span class="identifier">slist</span><span class="special">::</span><span class="identifier">splice</span></code>.
</p>
<p>
The advanced lookup and insertion functions for associative containers, taking
an arbitrary key type and predicates, were designed to avoid unnecessary
object constructions.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<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
in space constrained environments</a>
</h3></div></div></div>
<p>
<span class="bold"><strong>Boost.Intrusive</strong></span> should be useful in space
constrained environments, and following this guideline <span class="bold"><strong>Boost.Intrusive</strong></span>
separates node algorithms and intrusive containers to avoid instantiating
node algorithms for each user type. For example, a single class of red-black
algorithms will be instantiated to implement all set and multiset containers
using raw pointers. This way, <span class="bold"><strong>Boost.Intrusive</strong></span>
seeks to avoid any code size overhead associated with templates.
</p>
<p>
Apart from that, <span class="bold"><strong>Boost.Intrusive</strong></span> implements
some size improvements: for example, red-black trees embed the color bit
in the parent pointer lower bit, if nodes are two-byte aligned. The option
to forgo constant-time size operations can reduce container size, and this
extra size optimization is noticeable when the container is empty or contains
few values.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<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
as a basic building block</a>
</h3></div></div></div>
<p>
<span class="bold"><strong>Boost.Intrusive</strong></span> can be a basic building
block to build more complex containers and this potential has motivated many
design decisions. For example, the ability to have more than one hook per
user type opens the opportunity to implement multi-index containers on top
of <span class="bold"><strong>Boost.Intrusive</strong></span>.
</p>
<p>
<span class="bold"><strong>Boost.Intrusive</strong></span> containers implement advanced
functions taking function objects as arguments (<code class="computeroutput"><span class="identifier">clone_from</span></code>,
<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
in handy when implementing non-intrusive containers (for example, STL-like
containers) on top of intrusive containers.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<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
Boost.Intrusive</a>
</h3></div></div></div>
<p>
<span class="bold"><strong>Boost.Intrusive</strong></span> offers a wide range of containers
but also allows the construction of custom containers reusing <span class="bold"><strong>Boost.Intrusive</strong></span>
elements. The programmer might want to use node algorithms directly or build
special hooks that take advantage of an application environment.
</p>
<p>
For example, the programmer can customize parts of <span class="bold"><strong>Boost.Intrusive</strong></span>
to manage old data structures whose definition can't be changed.
</p>
</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-2011 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="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>
</div>
</body>
</html>
|
