| <html> |
| <head> |
| <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> |
| <title>Presenting Boost.Intrusive containers</title> |
| <link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> |
| <meta name="generator" content="DocBook XSL Stylesheets V1.75.2"> |
| <link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> |
| <link rel="up" href="../intrusive.html" title="Chapter 10. Boost.Intrusive"> |
| <link rel="prev" href="concepts_summary.html" title="Concept summary"> |
| <link rel="next" href="safe_hook.html" title="Safe hooks"> |
| </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="concepts_summary.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="safe_hook.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.presenting_containers"></a><a class="link" href="presenting_containers.html" title="Presenting Boost.Intrusive containers">Presenting Boost.Intrusive |
| containers</a> |
| </h2></div></div></div> |
| <p> |
| <span class="bold"><strong>Boost.Intrusive</strong></span> offers a wide range of intrusive |
| containers: |
| </p> |
| <div class="itemizedlist"><ul class="itemizedlist" type="disc"> |
| <li class="listitem"> |
| <span class="bold"><strong>slist</strong></span>: An intrusive singly linked list. |
| The size overhead is very small for user classes (usually the size of one |
| pointer) but many operations have linear time complexity, so the user must |
| be careful if he wants to avoid performance problems. |
| </li> |
| <li class="listitem"> |
| <span class="bold"><strong>list</strong></span>: A <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span></code> |
| like intrusive linked list. The size overhead is quite small for user classes |
| (usually the size of two pointers). Many operations have constant time |
| complexity. |
| </li> |
| <li class="listitem"> |
| <span class="bold"><strong>set/multiset/rbtree</strong></span>: <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> |
| like intrusive associative containers based on red-black trees. The size |
| overhead is moderate for user classes (usually the size of three pointers). |
| Many operations have logarithmic time complexity. |
| </li> |
| <li class="listitem"> |
| <span class="bold"><strong>avl_set/avl_multiset/avltree</strong></span>: A <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> like intrusive associative containers |
| based on AVL trees. The size overhead is moderate for user classes (usually |
| the size of three pointers). Many operations have logarithmic time complexity. |
| </li> |
| <li class="listitem"> |
| <span class="bold"><strong>splay_set/splay_multiset/splaytree</strong></span>: <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> like intrusive associative containers |
| based on splay trees. Splay trees have no constant operations, but they |
| have some interesting caching properties. The size overhead is moderate |
| for user classes (usually the size of three pointers). Many operations |
| have logarithmic time complexity. |
| </li> |
| <li class="listitem"> |
| <span class="bold"><strong>sg_set/sg_multiset/sgtree</strong></span>: A <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> like intrusive associative containers |
| based on scapegoat trees. Scapegoat can be configured with the desired |
| balance factor to achieve the desired rebalancing frequency/search time |
| compromise. The size overhead is moderate for user classes (usually the |
| size of three pointers). Many operations have logarithmic time complexity. |
| </li> |
| </ul></div> |
| <p> |
| <span class="bold"><strong>Boost.Intrusive</strong></span> also offers semi-intrusive |
| containers: |
| </p> |
| <div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"> |
| <span class="bold"><strong>unordered_set/unordered_multiset</strong></span>: <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">tr1</span><span class="special">::</span><span class="identifier">unordered_set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">tr1</span><span class="special">::</span><span class="identifier">unordered_multiset</span></code> like intrusive unordered |
| associative containers. The size overhead is moderate for user classes |
| (an average of two pointers per element). Many operations have amortized |
| constant time complexity. |
| </li></ul></div> |
| <p> |
| Most of these intrusive containers can be configured with constant or linear |
| time size: |
| </p> |
| <div class="itemizedlist"><ul class="itemizedlist" type="disc"> |
| <li class="listitem"> |
| <span class="bold"><strong>Linear time size</strong></span>: The intrusive container |
| doesn't hold a size member that is updated with every insertion/erasure. |
| This implies that the <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> function doesn't have constant time complexity. |
| On the other hand, the container is smaller, and some operations, like |
| <code class="computeroutput"><span class="identifier">splice</span><span class="special">()</span></code> |
| taking a range of iterators in linked lists, have constant time complexity |
| instead of linear complexity. |
| </li> |
| <li class="listitem"> |
| <span class="bold"><strong>Constant time size</strong></span>: The intrusive container |
| holds a size member that is updated with every insertion/erasure. This |
| implies that the <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> |
| function has constant time complexity. On the other hand, increases the |
| size of the container, and some operations, like <code class="computeroutput"><span class="identifier">splice</span><span class="special">()</span></code> taking a range of iterators, have linear |
| time complexity in linked lists. |
| </li> |
| </ul></div> |
| <p> |
| To make user classes compatible with these intrusive containers <span class="bold"><strong>Boost.Intrusive</strong></span> |
| offers two types of hooks for each container type: |
| </p> |
| <div class="itemizedlist"><ul class="itemizedlist" type="disc"> |
| <li class="listitem"> |
| <span class="bold"><strong>Base hook</strong></span>: The hook is stored as a public |
| base class of the user class. |
| </li> |
| <li class="listitem"> |
| <span class="bold"><strong>Member hook</strong></span>: The hook is stored as a public |
| member of the user class. |
| </li> |
| </ul></div> |
| <p> |
| Apart from that, <span class="bold"><strong>Boost.Intrusive</strong></span> offers additional |
| features: |
| </p> |
| <div class="itemizedlist"><ul class="itemizedlist" type="disc"> |
| <li class="listitem"> |
| <span class="bold"><strong>Safe mode hooks</strong></span>: Hook constructor initializes |
| the internal data to a well-known safe state and intrusive containers check |
| that state before inserting a value in the container. When erasing an element |
| from the container, the container puts the hook in the safe state again. |
| This allows a safer use mode and it can be used to detect programming errors. |
| It implies a slight performance overhead in some operations and can convert |
| some constant time operations to linear time operations. |
| </li> |
| <li class="listitem"> |
| <span class="bold"><strong>Auto-unlink hooks</strong></span>: The hook destructor |
| removes the object from the container automatically and the user can safely |
| unlink the object from the container without referring to the container. |
| </li> |
| <li class="listitem"> |
| <span class="bold"><strong>Non-raw pointers</strong></span>: If the user wants to |
| use smart pointers instead of raw pointers, <span class="bold"><strong>Boost.Intrusive</strong></span> |
| hooks can be configured to use any type of pointer. This configuration |
| information is also transmitted to the containers, so all the internal |
| pointers used by intrusive containers configured with these hooks will |
| be smart pointers. As an example, <span class="bold"><strong>Boost.Interprocess</strong></span> |
| defines a smart pointer compatible with shared memory, called <code class="computeroutput"><span class="identifier">offset_ptr</span></code>. <span class="bold"><strong>Boost.Intrusive</strong></span> |
| can be configured to use this smart pointer to allow shared memory intrusive |
| containers. |
| </li> |
| </ul></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, 2006-2010 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="concepts_summary.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="safe_hook.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> |
| </div> |
| </body> |
| </html> |
