136 lines
8.6 KiB
HTML
136 lines
8.6 KiB
HTML
<!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=UTF-8">
|
||
<title>Design Notes</title>
|
||
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
|
||
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
|
||
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
|
||
<link rel="up" href="../intrusive.html" title="Chapter 19. 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 class="toc">
|
||
<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-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="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>
|