<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Containers with custom ValueTraits</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="node_algorithms.html" title="Node algorithms with custom NodeTraits">
<link rel="next" href="thread_safety.html" title="Thread safety guarantees">
</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="node_algorithms.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="thread_safety.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.value_traits"></a><a class="link" href="value_traits.html" title="Containers with custom ValueTraits"> Containers with custom ValueTraits</a>
</h2></div></div></div>
<div class="toc"><dl>
<dt><span class="section"><a href="value_traits.html#intrusive.value_traits.value_traits_interface"> ValueTraits
interface</a></span></dt>
<dt><span class="section"><a href="value_traits.html#intrusive.value_traits.value_traits_example"> Custom
ValueTraits example</a></span></dt>
<dt><span class="section"><a href="value_traits.html#intrusive.value_traits.reusing_node_algorithms"> Reusing
node algorithms for different values</a></span></dt>
<dt><span class="section"><a href="value_traits.html#intrusive.value_traits.simplifying_value_traits"> Simplifying
value traits definition</a></span></dt>
<dt><span class="section"><a href="value_traits.html#intrusive.value_traits.stateful_value_traits"> Stateful
value traits</a></span></dt>
</dl></div>
<p>
As explained in the <a class="link" href="concepts.html" title="Concepts explained">Concepts</a> section,
<span class="bold"><strong>Boost.Intrusive</strong></span> containers need a <code class="computeroutput"><span class="identifier">ValueTraits</span></code> class to perform transformations
between nodes and user values. <code class="computeroutput"><span class="identifier">ValueTraits</span></code>
can be explicitly configured (using the <code class="computeroutput"><span class="identifier">value_traits</span><span class="special"><></span></code> option) or implicitly configured (using
hooks and their <code class="computeroutput"><span class="identifier">base_hook</span><span class="special"><></span></code>/<code class="computeroutput"><span class="identifier">member_hook</span><span class="special"><></span></code>
options). <code class="computeroutput"><span class="identifier">ValueTraits</span></code> contains
all the information to glue the <code class="computeroutput"><span class="identifier">value_type</span></code>
of the containers and the node to be used in node algorithms, since these types
can be different. Apart from this, <code class="computeroutput"><span class="identifier">ValueTraits</span></code>
also stores information about the link policy of the values to be inserted.
</p>
<p>
Instead of using <span class="bold"><strong>Boost.Intrusive</strong></span> predefined
hooks a user might want to develop customized containers, for example, using
nodes that are optimized for a specific application or that are compatible
with a legacy ABI. A user might want to have only two additional pointers in
his class and insert the class in a doubly linked list sometimes and in a singly
linked list in other situations. You can't achieve this using <span class="bold"><strong>Boost.Intrusive</strong></span>
predefined hooks. Now, instead of using <code class="computeroutput"><span class="identifier">base_hook</span><span class="special"><...></span></code> or <code class="computeroutput"><span class="identifier">member_hook</span><span class="special"><...></span></code> options the user will specify the
<code class="computeroutput"><span class="identifier">value_traits</span><span class="special"><...></span></code>
options. Let's see how we can do this:
</p>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.value_traits.value_traits_interface"></a><a class="link" href="value_traits.html#intrusive.value_traits.value_traits_interface" title="ValueTraits interface"> ValueTraits
interface</a>
</h3></div></div></div>
<p>
<code class="computeroutput"><span class="identifier">ValueTraits</span></code> has the following
interface:
</p>
<p>
</p>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">pointer_to_other</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<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">link_mode</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<span class="keyword">struct</span> <span class="identifier">my_value_traits</span>
<span class="special">{</span>
<span class="keyword">typedef</span> <span class="identifier">implementation_defined</span> <span class="identifier">node_traits</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">implementation_defined</span> <span class="identifier">value_type</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node_ptr</span> <span class="identifier">node_ptr</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">const_node_ptr</span> <span class="identifier">const_node_ptr</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">pointer_to_other</span><span class="special"><</span><span class="identifier">node_ptr</span><span class="special">,</span> <span class="identifier">value_type</span><span class="special">>::</span><span class="identifier">type</span> <span class="identifier">pointer</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">pointer_to_other</span><span class="special"><</span><span class="identifier">node_ptr</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">value_type</span><span class="special">>::</span><span class="identifier">type</span> <span class="identifier">const_pointer</span><span class="special">;</span>
<span class="keyword">static</span> <span class="keyword">const</span> <span class="identifier">link_mode_type</span> <span class="identifier">link_mode</span> <span class="special">=</span> <span class="identifier">some_linking_policy</span><span class="special">;</span>
<span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">to_node_ptr</span> <span class="special">(</span><span class="identifier">value_type</span> <span class="special">&</span><span class="identifier">value</span><span class="special">);</span>
<span class="keyword">static</span> <span class="identifier">const_node_ptr</span> <span class="identifier">to_node_ptr</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">value_type</span> <span class="special">&</span><span class="identifier">value</span><span class="special">);</span>
<span class="keyword">static</span> <span class="identifier">pointer</span> <span class="identifier">to_value_ptr</span> <span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">);</span>
<span class="keyword">static</span> <span class="identifier">const_pointer</span> <span class="identifier">to_value_ptr</span> <span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">);</span>
<span class="special">};</span>
</pre>
<p>
Let's explain each type and function:
</p>
<div class="itemizedlist"><ul class="itemizedlist" type="disc">
<li class="listitem">
<span class="bold"><strong><span class="emphasis"><em>node_traits</em></span></strong></span>: The
node configuration that is needed by node algorithms. These node traits
and algorithms are described in the previous chapter: <a class="link" href="node_algorithms.html" title="Node algorithms with custom NodeTraits">Node
Algorithms</a>.
<div class="itemizedlist"><ul class="itemizedlist" type="circle">
<li class="listitem">
If my_value_traits is meant to be used with <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code>,
<code class="computeroutput"><span class="identifier">node_traits</span></code> should
follow the interface needed by <code class="computeroutput"><a class="link" href="../boost/intrusive/circular_slist_algorithms.html" title="Class template circular_slist_algorithms">circular_slist_algorithms</a></code>.
</li>
<li class="listitem">
If my_value_traits is meant to be used with <code class="computeroutput"><a class="link" href="../boost/intrusive/list.html" title="Class template list">list</a></code>,
<code class="computeroutput"><span class="identifier">node_traits</span></code> should
follow the interface needed by <code class="computeroutput"><a class="link" href="../boost/intrusive/circular_list_algorithms.html" title="Class template circular_list_algorithms">circular_list_algorithms</a></code>.
</li>
<li class="listitem">
If my_value_traits is meant to be used with <code class="computeroutput"><a class="link" href="../boost/intrusive/set.html" title="Class template set">set</a></code>/<code class="computeroutput"><a class="link" href="../boost/intrusive/multiset.html" title="Class template multiset">multiset</a></code>, <code class="computeroutput"><span class="identifier">node_traits</span></code> should follow the
interface needed by <code class="computeroutput"><a class="link" href="../boost/intrusive/rbtree_algorithms.html" title="Class template rbtree_algorithms">rbtree_algorithms</a></code>.
</li>
<li class="listitem">
If my_value_traits is meant to be used with <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_set.html" title="Class template unordered_set">unordered_set</a></code>/
<code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_multiset.html" title="Class template unordered_multiset">unordered_multiset</a></code>,
<code class="computeroutput"><span class="identifier">node_traits</span></code> should
follow the interface needed by <code class="computeroutput"><a class="link" href="../boost/intrusive/circular_slist_algorithms.html" title="Class template circular_slist_algorithms">circular_slist_algorithms</a></code>.
</li>
</ul></div>
</li>
<li class="listitem">
<span class="bold"><strong><span class="emphasis"><em>node_ptr</em></span></strong></span>: A typedef
for <code class="computeroutput"><span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node_ptr</span></code>.
</li>
<li class="listitem">
<span class="bold"><strong><span class="emphasis"><em>const_node_ptr</em></span></strong></span>:
A typedef for <code class="computeroutput"><span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">const_node_ptr</span></code>.
</li>
<li class="listitem">
<span class="bold"><strong><span class="emphasis"><em>value_type</em></span></strong></span>: The
type that the user wants to insert in the container. This type can be
the same as <code class="computeroutput"><span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node</span></code>
but it can be different (for example, <code class="computeroutput"><span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node</span></code>
can be a member type of <code class="computeroutput"><span class="identifier">value_type</span></code>).
If <code class="computeroutput"><span class="identifier">value_type</span></code> and <code class="computeroutput"><span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node</span></code> are the same type, the <code class="computeroutput"><span class="identifier">to_node_ptr</span></code> and <code class="computeroutput"><span class="identifier">to_value_ptr</span></code>
functions are trivial.
</li>
<li class="listitem">
<span class="bold"><strong><span class="emphasis"><em>pointer</em></span></strong></span>: The type
of a pointer to a <code class="computeroutput"><span class="identifier">value_type</span></code>.
It must be the same pointer type as <code class="computeroutput"><span class="identifier">node_ptr</span></code>:
If <code class="computeroutput"><span class="identifier">node_ptr</span></code> is <code class="computeroutput"><span class="identifier">node</span><span class="special">*</span></code>,
<code class="computeroutput"><span class="identifier">pointer</span></code> must be <code class="computeroutput"><span class="identifier">value_type</span><span class="special">*</span></code>.
If <code class="computeroutput"><span class="identifier">node_ptr</span></code> is <code class="computeroutput"><span class="identifier">smart_ptr</span><span class="special"><</span><span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node</span><span class="special">></span></code>,
<code class="computeroutput"><span class="identifier">pointer</span></code> must be <code class="computeroutput"><span class="identifier">smart_ptr</span><span class="special"><</span><span class="identifier">value_type</span><span class="special">></span></code>.
This can be generically achieved using <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">pointer_to_other</span></code>
utility from <span class="bold"><strong>Boost SmartPointers</strong></span> defined
in <code class="computeroutput"><span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">pointer_to_other</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span></code>.
</li>
<li class="listitem">
<span class="bold"><strong><span class="emphasis"><em>const_pointer</em></span></strong></span>:
The type of a pointer to a <code class="computeroutput"><span class="keyword">const</span>
<span class="identifier">value_type</span></code>. It must be the
same pointer type as <code class="computeroutput"><span class="identifier">node_ptr</span></code>:
If <code class="computeroutput"><span class="identifier">node_ptr</span></code> is <code class="computeroutput"><span class="identifier">node</span><span class="special">*</span></code>,
<code class="computeroutput"><span class="identifier">const_pointer</span></code> must be
<code class="computeroutput"><span class="keyword">const</span> <span class="identifier">value_type</span><span class="special">*</span></code>. If <code class="computeroutput"><span class="identifier">node_ptr</span></code>
is <code class="computeroutput"><span class="identifier">smart_ptr</span><span class="special"><</span><span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node</span><span class="special">></span></code>,
<code class="computeroutput"><span class="identifier">const_pointer</span></code> must be
<code class="computeroutput"><span class="identifier">smart_ptr</span><span class="special"><</span><span class="keyword">const</span> <span class="identifier">value_type</span><span class="special">></span></code> This can be generically achieved
using <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">pointer_to_other</span></code> utility from <span class="bold"><strong>Boost SmartPointers</strong></span> defined in <code class="computeroutput"><span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">pointer_to_other</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span></code>.
</li>
<li class="listitem">
<span class="bold"><strong><span class="emphasis"><em>link_mode</em></span></strong></span>: Indicates
that <code class="computeroutput"><span class="identifier">value_traits</span></code> needs
some additional work or checks from the container. The types are enumerations
defined in the <code class="computeroutput"><span class="identifier">link_mode</span><span class="special">.</span><span class="identifier">hpp</span></code>
header. These are the possible types:
<div class="itemizedlist"><ul class="itemizedlist" type="circle">
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">normal_link</span></code></strong></span>:
If this linking policy is specified in a <code class="computeroutput"><span class="identifier">ValueTraits</span></code>
class as the link mode, containers configured with such <code class="computeroutput"><span class="identifier">ValueTraits</span></code> won't set the hooks
of the erased values to a default state. Containers also won't
check that the hooks of the new values are default initialized.
</li>
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">safe_link</span></code></strong></span>:
If this linking policy is specified as the link mode in a <code class="computeroutput"><span class="identifier">ValueTraits</span></code> class, containers
configured with this <code class="computeroutput"><span class="identifier">ValueTraits</span></code>
will set the hooks of the erased values to a default state. Containers
also will check that the hooks of the new values are default initialized.
</li>
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">auto_unlink</span></code></strong></span>:
Same as "safe_link" but containers with constant-time
size features won't be compatible with <code class="computeroutput"><span class="identifier">ValueTraits</span></code>
configured with this policy. Containers also know that a value
can be silently erased from the container without using any function
provided by the containers.
</li>
</ul></div>
</li>
<li class="listitem">
<span class="bold"><strong><span class="emphasis"><em>static node_ptr to_node_ptr (value_type
&value)</em></span></strong></span> and <span class="bold"><strong><span class="emphasis"><em>static
const_node_ptr to_node_ptr (const value_type &value)</em></span></strong></span>:
These functions take a reference to a value_type and return a pointer
to the node to be used with node algorithms.
</li>
<li class="listitem">
<span class="bold"><strong><span class="emphasis"><em>static pointer to_value_ptr (node_ptr
n)</em></span></strong></span> and <span class="bold"><strong><span class="emphasis"><em>static const_pointer
to_value_ptr (const_node_ptr n)</em></span></strong></span>: These functions
take a pointer to a node and return a pointer to the value that contains
the node.
</li>
</ul></div>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.value_traits.value_traits_example"></a><a class="link" href="value_traits.html#intrusive.value_traits.value_traits_example" title="Custom ValueTraits example"> Custom
ValueTraits example</a>
</h3></div></div></div>
<p>
Let's define our own <code class="computeroutput"><span class="identifier">value_traits</span></code>
class to be able to use <span class="bold"><strong>Boost.Intrusive</strong></span>
containers with an old C structure whose definition can't be changed. That
legacy type has two pointers that can be used to build singly and doubly
linked lists: in singly linked lists we only need a pointer, whereas in doubly
linked lists, we need two pointers. Since we only have two pointers, we can't
insert the object in both a singly and a doubly linked list at the same time.
This is the definition of the old node:
</p>
<p>
</p>
<p>
</p>
<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">link_mode</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<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>
<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">slist</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">vector</span><span class="special">></span>
<span class="comment">//This node is the legacy type we can't modify and we want to insert in
</span><span class="comment">//intrusive list and slist containers using only two pointers, since
</span><span class="comment">//we know the object will never be at the same time in both lists.
</span><span class="keyword">struct</span> <span class="identifier">legacy_value</span>
<span class="special">{</span>
<span class="identifier">legacy_value</span> <span class="special">*</span><span class="identifier">prev_</span><span class="special">;</span>
<span class="identifier">legacy_value</span> <span class="special">*</span><span class="identifier">next_</span><span class="special">;</span>
<span class="keyword">int</span> <span class="identifier">id_</span><span class="special">;</span>
<span class="special">};</span>
</pre>
<p>
</p>
<p>
</p>
<p>
Now we have to define a NodeTraits class that will implement the functions/typedefs
that will make the legacy node compatible with <span class="bold"><strong>Boost.Intrusive</strong></span>
algorithms. After that, we'll define a ValueTraits class that will configure
<span class="bold"><strong>Boost.Intrusive</strong></span> containers:
</p>
<p>
</p>
<p>
</p>
<pre class="programlisting"><span class="comment">//Define our own NodeTraits that will configure singly and doubly linked
</span><span class="comment">//list algorithms. Note that this node traits is compatible with
</span><span class="comment">//circular_slist_algorithms and circular_list_algorithms.
</span>
<span class="keyword">namespace</span> <span class="identifier">bi</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="keyword">struct</span> <span class="identifier">legacy_node_traits</span>
<span class="special">{</span>
<span class="keyword">typedef</span> <span class="identifier">legacy_value</span> <span class="identifier">node</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">legacy_value</span> <span class="special">*</span> <span class="identifier">node_ptr</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="keyword">const</span> <span class="identifier">legacy_value</span> <span class="special">*</span> <span class="identifier">const_node_ptr</span><span class="special">;</span>
<span class="keyword">static</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">get_next</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">next_</span><span class="special">;</span> <span class="special">}</span>
<span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_next</span><span class="special">(</span><span class="identifier">node</span> <span class="special">*</span><span class="identifier">n</span><span class="special">,</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">next</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">next_</span> <span class="special">=</span> <span class="identifier">next</span><span class="special">;</span> <span class="special">}</span>
<span class="keyword">static</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">get_previous</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">prev_</span><span class="special">;</span> <span class="special">}</span>
<span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_previous</span><span class="special">(</span><span class="identifier">node</span> <span class="special">*</span><span class="identifier">n</span><span class="special">,</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">prev</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">prev_</span> <span class="special">=</span> <span class="identifier">prev</span><span class="special">;</span> <span class="special">}</span>
<span class="special">};</span>
<span class="comment">//This ValueTraits will configure list and slist. In this case,
</span><span class="comment">//legacy_node_traits::node is the same as the
</span><span class="comment">//legacy_value_traits::value_type so to_node_ptr/to_value_ptr
</span><span class="comment">//functions are trivial.
</span><span class="keyword">struct</span> <span class="identifier">legacy_value_traits</span>
<span class="special">{</span>
<span class="keyword">typedef</span> <span class="identifier">legacy_node_traits</span> <span class="identifier">node_traits</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node_ptr</span> <span class="identifier">node_ptr</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">const_node_ptr</span> <span class="identifier">const_node_ptr</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">legacy_value</span> <span class="identifier">value_type</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">legacy_value</span> <span class="special">*</span> <span class="identifier">pointer</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="keyword">const</span> <span class="identifier">legacy_value</span> <span class="special">*</span> <span class="identifier">const_pointer</span><span class="special">;</span>
<span class="keyword">static</span> <span class="keyword">const</span> <span class="identifier">bi</span><span class="special">::</span><span class="identifier">link_mode_type</span> <span class="identifier">link_mode</span> <span class="special">=</span> <span class="identifier">bi</span><span class="special">::</span><span class="identifier">normal_link</span><span class="special">;</span>
<span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">to_node_ptr</span> <span class="special">(</span><span class="identifier">value_type</span> <span class="special">&</span><span class="identifier">value</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">node_ptr</span><span class="special">(&</span><span class="identifier">value</span><span class="special">);</span> <span class="special">}</span>
<span class="keyword">static</span> <span class="identifier">const_node_ptr</span> <span class="identifier">to_node_ptr</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">value_type</span> <span class="special">&</span><span class="identifier">value</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">const_node_ptr</span><span class="special">(&</span><span class="identifier">value</span><span class="special">);</span> <span class="special">}</span>
<span class="keyword">static</span> <span class="identifier">pointer</span> <span class="identifier">to_value_ptr</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">pointer</span><span class="special">(</span><span class="identifier">n</span><span class="special">);</span> <span class="special">}</span>
<span class="keyword">static</span> <span class="identifier">const_pointer</span> <span class="identifier">to_value_ptr</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">const_pointer</span><span class="special">(</span><span class="identifier">n</span><span class="special">);</span> <span class="special">}</span>
<span class="special">};</span>
</pre>
<p>
</p>
<p>
</p>
<p>
Defining a value traits class that simply defines <code class="computeroutput"><span class="identifier">value_type</span></code>
as <code class="computeroutput"><span class="identifier">legacy_node_traits</span><span class="special">::</span><span class="identifier">node</span></code> is a common approach when defining
customized intrusive containers, so <span class="bold"><strong>Boost.Intrusive</strong></span>
offers a templatized <code class="computeroutput"><a class="link" href="../boost/intrusive/trivial_value_traits.html" title="Struct template trivial_value_traits">trivial_value_traits</a></code>
class that does exactly what we want:
</p>
<p>
</p>
<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">trivial_value_traits</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<span class="comment">//Now we can define legacy_value_traits just with a single line
</span><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>
<span class="keyword">typedef</span> <span class="identifier">trivial_value_traits</span><span class="special"><</span><span class="identifier">legacy_node_traits</span><span class="special">,</span> <span class="identifier">normal_link</span><span class="special">></span> <span class="identifier">legacy_value_traits</span><span class="special">;</span>
</pre>
<p>
Now we can just define the containers that will store the legacy abi objects
and write a little test:
</p>
<p>
</p>
<p>
</p>
<pre class="programlisting"><span class="comment">//Now define an intrusive list and slist that will store legacy_value objects
</span><span class="keyword">typedef</span> <span class="identifier">bi</span><span class="special">::</span><span class="identifier">value_traits</span><span class="special"><</span><span class="identifier">legacy_value_traits</span><span class="special">></span> <span class="identifier">ValueTraitsOption</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">bi</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">legacy_value</span><span class="special">,</span> <span class="identifier">ValueTraitsOption</span><span class="special">></span> <span class="identifier">LegacyAbiList</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">bi</span><span class="special">::</span><span class="identifier">slist</span><span class="special"><</span><span class="identifier">legacy_value</span><span class="special">,</span> <span class="identifier">ValueTraitsOption</span><span class="special">></span> <span class="identifier">LegacyAbiSlist</span><span class="special">;</span>
<span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">List</span><span class="special">></span>
<span class="keyword">bool</span> <span class="identifier">test_list</span><span class="special">()</span>
<span class="special">{</span>
<span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">legacy_value</span><span class="special">></span> <span class="identifier">Vect</span><span class="special">;</span>
<span class="comment">//Create legacy_value objects, with a different internal number
</span> <span class="identifier">Vect</span> <span class="identifier">legacy_vector</span><span class="special">;</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special"><</span> <span class="number">100</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">){</span>
<span class="identifier">legacy_value</span> <span class="identifier">value</span><span class="special">;</span> <span class="identifier">value</span><span class="special">.</span><span class="identifier">id_</span> <span class="special">=</span> <span class="identifier">i</span><span class="special">;</span> <span class="identifier">legacy_vector</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">value</span><span class="special">);</span>
<span class="special">}</span>
<span class="comment">//Create the list with the objects
</span> <span class="identifier">List</span> <span class="identifier">mylist</span><span class="special">(</span><span class="identifier">legacy_vector</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">legacy_vector</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
<span class="comment">//Now test both lists
</span> <span class="keyword">typename</span> <span class="identifier">List</span><span class="special">::</span><span class="identifier">const_iterator</span> <span class="identifier">bit</span><span class="special">(</span><span class="identifier">mylist</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()),</span> <span class="identifier">bitend</span><span class="special">(</span><span class="identifier">mylist</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
<span class="keyword">typename</span> <span class="identifier">Vect</span><span class="special">::</span><span class="identifier">const_iterator</span> <span class="identifier">it</span><span class="special">(</span><span class="identifier">legacy_vector</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()),</span> <span class="identifier">itend</span><span class="special">(</span><span class="identifier">legacy_vector</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
<span class="comment">//Test the objects inserted in our list
</span> <span class="keyword">for</span><span class="special">(;</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">itend</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">,</span> <span class="special">++</span><span class="identifier">bit</span><span class="special">)</span>
<span class="keyword">if</span><span class="special">(&*</span><span class="identifier">bit</span> <span class="special">!=</span> <span class="special">&*</span><span class="identifier">it</span><span class="special">)</span> <span class="keyword">return</span> <span class="keyword">false</span><span class="special">;</span>
<span class="keyword">return</span> <span class="keyword">true</span><span class="special">;</span>
<span class="special">}</span>
<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span>
<span class="special">{</span>
<span class="keyword">return</span> <span class="identifier">test_list</span><span class="special"><</span><span class="identifier">LegacyAbiList</span><span class="special">>()</span> <span class="special">&&</span> <span class="identifier">test_list</span><span class="special"><</span><span class="identifier">LegacyAbiSlist</span><span class="special">>()</span> <span class="special">?</span> <span class="number">0</span> <span class="special">:</span> <span class="number">1</span><span class="special">;</span>
<span class="special">}</span>
</pre>
<p>
</p>
<p>
</p>
<p>
As seen, several key elements of <span class="bold"><strong>Boost.Intrusive</strong></span>
can be reused with custom user types, if the user does not want to use the
provided <span class="bold"><strong>Boost.Intrusive</strong></span> facilities.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.value_traits.reusing_node_algorithms"></a><a class="link" href="value_traits.html#intrusive.value_traits.reusing_node_algorithms" title="Reusing node algorithms for different values"> Reusing
node algorithms for different values</a>
</h3></div></div></div>
<p>
In the previous example, <code class="computeroutput"><span class="identifier">legacy_node_traits</span><span class="special">::</span><span class="identifier">node</span></code>
type and <code class="computeroutput"><span class="identifier">legacy_value_traits</span><span class="special">::</span><span class="identifier">value_type</span></code>
are the same type, but this is not necessary. It's possible to have several
<code class="computeroutput"><span class="identifier">ValueTraits</span></code> defining the
same <code class="computeroutput"><span class="identifier">node_traits</span></code> type (and
thus, the same <code class="computeroutput"><span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node</span></code>).
This reduces the number of node algorithm instantiations, but now <code class="computeroutput"><span class="identifier">ValueTraits</span><span class="special">::</span><span class="identifier">to_node_ptr</span></code> and <code class="computeroutput"><span class="identifier">ValueTraits</span><span class="special">::</span><span class="identifier">to_value_ptr</span></code>
functions need to offer conversions between both types. Let's see a small
example:
</p>
<p>
First, we'll define the node to be used in the algorithms. For a linked list,
we just need a node that stores two pointers:
</p>
<p>
</p>
<p>
</p>
<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">link_mode</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<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>
<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">vector</span><span class="special">></span>
<span class="comment">//This is the node that will be used with algorithms.
</span><span class="keyword">struct</span> <span class="identifier">simple_node</span>
<span class="special">{</span>
<span class="identifier">simple_node</span> <span class="special">*</span><span class="identifier">prev_</span><span class="special">;</span>
<span class="identifier">simple_node</span> <span class="special">*</span><span class="identifier">next_</span><span class="special">;</span>
<span class="special">};</span>
</pre>
<p>
</p>
<p>
</p>
<p>
Now we'll define two different types that will be inserted in intrusive lists
and a templatized <code class="computeroutput"><span class="identifier">ValueTraits</span></code>
that will work for both types:
</p>
<p>
</p>
<p>
</p>
<pre class="programlisting"><span class="keyword">class</span> <span class="identifier">base_1</span><span class="special">{};</span>
<span class="keyword">class</span> <span class="identifier">base_2</span><span class="special">{};</span>
<span class="keyword">struct</span> <span class="identifier">value_1</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">base_1</span><span class="special">,</span> <span class="keyword">public</span> <span class="identifier">simple_node</span>
<span class="special">{</span> <span class="keyword">int</span> <span class="identifier">id_</span><span class="special">;</span> <span class="special">};</span>
<span class="keyword">struct</span> <span class="identifier">value_2</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">base_1</span><span class="special">,</span> <span class="keyword">public</span> <span class="identifier">base_2</span><span class="special">,</span> <span class="keyword">public</span> <span class="identifier">simple_node</span>
<span class="special">{</span> <span class="keyword">float</span> <span class="identifier">id_</span><span class="special">;</span> <span class="special">};</span>
<span class="comment">//Define the node traits. A single node_traits will be enough.
</span><span class="keyword">struct</span> <span class="identifier">simple_node_traits</span>
<span class="special">{</span>
<span class="keyword">typedef</span> <span class="identifier">simple_node</span> <span class="identifier">node</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">node</span> <span class="special">*</span> <span class="identifier">node_ptr</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="keyword">const</span> <span class="identifier">node</span> <span class="special">*</span> <span class="identifier">const_node_ptr</span><span class="special">;</span>
<span class="keyword">static</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">get_next</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">next_</span><span class="special">;</span> <span class="special">}</span>
<span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_next</span><span class="special">(</span><span class="identifier">node</span> <span class="special">*</span><span class="identifier">n</span><span class="special">,</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">next</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">next_</span> <span class="special">=</span> <span class="identifier">next</span><span class="special">;</span> <span class="special">}</span>
<span class="keyword">static</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">get_previous</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">prev_</span><span class="special">;</span> <span class="special">}</span>
<span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_previous</span><span class="special">(</span><span class="identifier">node</span> <span class="special">*</span><span class="identifier">n</span><span class="special">,</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">prev</span><span class="special">)</span> <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">prev_</span> <span class="special">=</span> <span class="identifier">prev</span><span class="special">;</span> <span class="special">}</span>
<span class="special">};</span>
<span class="comment">//A templatized value traits for value_1 and value_2
</span><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">ValueType</span><span class="special">></span>
<span class="keyword">struct</span> <span class="identifier">simple_value_traits</span>
<span class="special">{</span>
<span class="keyword">typedef</span> <span class="identifier">simple_node_traits</span> <span class="identifier">node_traits</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node_ptr</span> <span class="identifier">node_ptr</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">const_node_ptr</span> <span class="identifier">const_node_ptr</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">ValueType</span> <span class="identifier">value_type</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">ValueType</span> <span class="special">*</span> <span class="identifier">pointer</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="keyword">const</span> <span class="identifier">ValueType</span> <span class="special">*</span> <span class="identifier">const_pointer</span><span class="special">;</span>
<span class="keyword">static</span> <span class="keyword">const</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">::</span><span class="identifier">link_mode_type</span> <span class="identifier">link_mode</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">normal_link</span><span class="special">;</span>
<span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">to_node_ptr</span> <span class="special">(</span><span class="identifier">value_type</span> <span class="special">&</span><span class="identifier">value</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">node_ptr</span><span class="special">(&</span><span class="identifier">value</span><span class="special">);</span> <span class="special">}</span>
<span class="keyword">static</span> <span class="identifier">const_node_ptr</span> <span class="identifier">to_node_ptr</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">value_type</span> <span class="special">&</span><span class="identifier">value</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">const_node_ptr</span><span class="special">(&</span><span class="identifier">value</span><span class="special">);</span> <span class="special">}</span>
<span class="keyword">static</span> <span class="identifier">pointer</span> <span class="identifier">to_value_ptr</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="keyword">static_cast</span><span class="special"><</span><span class="identifier">value_type</span><span class="special">*>(</span><span class="identifier">n</span><span class="special">);</span> <span class="special">}</span>
<span class="keyword">static</span> <span class="identifier">const_pointer</span> <span class="identifier">to_value_ptr</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="keyword">static_cast</span><span class="special"><</span><span class="keyword">const</span> <span class="identifier">value_type</span><span class="special">*>(</span><span class="identifier">n</span><span class="special">);</span> <span class="special">}</span>
<span class="special">};</span>
</pre>
<p>
</p>
<p>
</p>
<p>
Now define two containers. Both containers will instantiate the same list
algorithms (<code class="computeroutput"><span class="identifier">circular_list_algorithms</span><span class="special"><</span><span class="identifier">simple_node_traits</span><span class="special">></span></code>), due to the fact that the value traits
used to define the containers provide the same <code class="computeroutput"><span class="identifier">node_traits</span></code>
type:
</p>
<p>
</p>
<p>
</p>
<pre class="programlisting"><span class="comment">//Now define two intrusive lists. Both lists will use the same algorithms:
</span><span class="comment">// circular_list_algorithms<simple_node_traits>
</span>
<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>
<span class="keyword">typedef</span> <span class="identifier">list</span> <span class="special"><</span><span class="identifier">value_1</span><span class="special">,</span> <span class="identifier">value_traits</span><span class="special"><</span><span class="identifier">simple_value_traits</span><span class="special"><</span><span class="identifier">value_1</span><span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="identifier">Value1List</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">list</span> <span class="special"><</span><span class="identifier">value_2</span><span class="special">,</span> <span class="identifier">value_traits</span><span class="special"><</span><span class="identifier">simple_value_traits</span><span class="special"><</span><span class="identifier">value_2</span><span class="special">></span> <span class="special">></span> <span class="special">></span> <span class="identifier">Value2List</span><span class="special">;</span>
</pre>
<p>
</p>
<p>
</p>
<p>
All <span class="bold"><strong>Boost.Intrusive</strong></span> containers using predefined
hooks use this technique to minimize code size: all possible <code class="computeroutput"><a class="link" href="../boost/intrusive/list.html" title="Class template list">list</a></code>
containers created with predefined hooks that define the same <code class="computeroutput"><span class="identifier">VoidPointer</span></code> type share the same list algorithms.
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.value_traits.simplifying_value_traits"></a><a class="link" href="value_traits.html#intrusive.value_traits.simplifying_value_traits" title="Simplifying value traits definition"> Simplifying
value traits definition</a>
</h3></div></div></div>
<p>
The previous example can be further simplified using the <code class="computeroutput"><a class="link" href="../boost/intrusive/derivation_value_traits.html" title="Struct template derivation_value_traits">derivation_value_traits</a></code>
class to define a value traits class with a value that stores the <code class="computeroutput"><span class="identifier">simple_node</span></code> as a base class:
</p>
<p>
</p>
<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">derivation_value_traits</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<span class="comment">//value_1, value_2, simple_node and simple_node_traits are defined
</span><span class="comment">//as in the previous example...
</span><span class="comment">//...
</span>
<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>
<span class="comment">//Now define the needed value traits using
</span><span class="keyword">typedef</span> <span class="identifier">derivation_value_traits</span><span class="special"><</span><span class="identifier">value_1</span><span class="special">,</span> <span class="identifier">simple_node_traits</span><span class="special">,</span> <span class="identifier">normal_link</span><span class="special">></span> <span class="identifier">ValueTraits1</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">derivation_value_traits</span><span class="special"><</span><span class="identifier">value_2</span><span class="special">,</span> <span class="identifier">simple_node_traits</span><span class="special">,</span> <span class="identifier">normal_link</span><span class="special">></span> <span class="identifier">ValueTraits2</span><span class="special">;</span>
<span class="comment">//Now define the containers
</span><span class="keyword">typedef</span> <span class="identifier">list</span> <span class="special"><</span><span class="identifier">value1</span><span class="special">,</span> <span class="identifier">value_traits</span><span class="special"><</span><span class="identifier">ValueTraits1</span><span class="special">></span> <span class="special">></span> <span class="identifier">Value1List</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">list</span> <span class="special"><</span><span class="identifier">value2</span><span class="special">,</span> <span class="identifier">value_traits</span><span class="special"><</span><span class="identifier">ValueTraits2</span><span class="special">></span> <span class="special">></span> <span class="identifier">Value2List</span><span class="special">;</span>
</pre>
<p>
We can even choose to store <code class="computeroutput"><span class="identifier">simple_node</span></code>
as a member of <code class="computeroutput"><span class="identifier">value_1</span></code> and
<code class="computeroutput"><span class="identifier">value_2</span></code> classes and use
<code class="computeroutput"><a class="link" href="../boost/intrusive/member_value_traits.html" title="Struct template member_value_traits">member_value_traits</a></code>
to define the needed value traits classes:
</p>
<p>
</p>
<p>
</p>
<pre class="programlisting"><span class="keyword">class</span> <span class="identifier">base_1</span><span class="special">{};</span>
<span class="keyword">class</span> <span class="identifier">base_2</span><span class="special">{};</span>
<span class="keyword">struct</span> <span class="identifier">value_1</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">base_1</span><span class="special">,</span> <span class="keyword">public</span> <span class="identifier">simple_node</span>
<span class="special">{</span>
<span class="keyword">int</span> <span class="identifier">id_</span><span class="special">;</span>
<span class="identifier">simple_node</span> <span class="identifier">node_</span><span class="special">;</span>
<span class="special">};</span>
<span class="keyword">struct</span> <span class="identifier">value_2</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">base_1</span><span class="special">,</span> <span class="keyword">public</span> <span class="identifier">base_2</span><span class="special">,</span> <span class="keyword">public</span> <span class="identifier">simple_node</span>
<span class="special">{</span>
<span class="identifier">simple_node</span> <span class="identifier">node_</span><span class="special">;</span>
<span class="keyword">float</span> <span class="identifier">id_</span><span class="special">;</span>
<span class="special">};</span>
<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>
<span class="keyword">typedef</span> <span class="identifier">member_value_traits</span>
<span class="special"><</span><span class="identifier">value_1</span><span class="special">,</span> <span class="identifier">simple_node_traits</span><span class="special">,</span> <span class="special">&</span><span class="identifier">value_1</span><span class="special">::</span><span class="identifier">node_</span><span class="special">,</span> <span class="identifier">normal_link</span><span class="special">></span> <span class="identifier">ValueTraits1</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">member_value_traits</span>
<span class="special"><</span><span class="identifier">value_2</span><span class="special">,</span> <span class="identifier">simple_node_traits</span><span class="special">,</span> <span class="special">&</span><span class="identifier">value_2</span><span class="special">::</span><span class="identifier">node_</span><span class="special">,</span> <span class="identifier">normal_link</span><span class="special">></span> <span class="identifier">ValueTraits2</span><span class="special">;</span>
<span class="comment">//Now define two intrusive lists. Both lists will use the same algorithms:
</span><span class="comment">// circular_list_algorithms<simple_node_traits>
</span><span class="keyword">typedef</span> <span class="identifier">list</span> <span class="special"><</span><span class="identifier">value_1</span><span class="special">,</span> <span class="identifier">value_traits</span><span class="special"><</span><span class="identifier">ValueTraits1</span><span class="special">></span> <span class="special">></span> <span class="identifier">Value1List</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">list</span> <span class="special"><</span><span class="identifier">value_2</span><span class="special">,</span> <span class="identifier">value_traits</span><span class="special"><</span><span class="identifier">ValueTraits2</span><span class="special">></span> <span class="special">></span> <span class="identifier">Value2List</span><span class="special">;</span>
</pre>
<p>
</p>
<p>
</p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.value_traits.stateful_value_traits"></a><a class="link" href="value_traits.html#intrusive.value_traits.stateful_value_traits" title="Stateful value traits"> Stateful
value traits</a>
</h3></div></div></div>
<p>
Until now all shown custom value traits are stateless, that is, <span class="bold"><strong>the transformation between nodes and values is implemented in
terms of static functions</strong></span>. It's possible to use <span class="bold"><strong>stateful</strong></span>
value traits so that we can separate nodes and values and <span class="bold"><strong>avoid
modifying types to insert nodes</strong></span>. <span class="bold"><strong>Boost.Intrusive</strong></span>
differentiates between stateful and stateless value traits by checking if
all Node <-> Value transformation functions are static or not (except
for Visual 7.1, since overloaded static function detection is not possible,
in this case the implementation checks if the class is empty):
</p>
<div class="itemizedlist"><ul class="itemizedlist" type="disc">
<li class="listitem">
If all Node <-> Value transformation functions are static , a
<span class="bold"><strong>stateless</strong></span> value traits is assumed. transformations
must be static functions.
</li>
<li class="listitem">
Otherwise a <span class="bold"><strong>stateful</strong></span> value traits is
assumed.
</li>
</ul></div>
<p>
Using stateful value traits it's possible to create containers of non-copyable/movable
objects <span class="bold"><strong>without modifying</strong></span> the definition
of the class to be inserted. This interesting property is achieved without
using global variables (stateless value traits could use global variables
to achieve the same goal), so:
</p>
<div class="itemizedlist"><ul class="itemizedlist" type="disc">
<li class="listitem">
<span class="bold"><strong>Thread-safety guarantees</strong></span>: Better thread-safety
guarantees can be achieved with stateful value traits, since accessing
global resources might require synchronization primitives that can be
avoided when using internal state.
</li>
<li class="listitem">
<span class="bold"><strong>Flexibility</strong></span>: A stateful value traits
type can be configured at run-time.
</li>
<li class="listitem">
<span class="bold"><strong>Run-time polymorphism</strong></span>: A value traits
might implement node <-> value transformations as virtual functions.
A single container type could be configured at run-time to use different
node <-> value relationships.
</li>
</ul></div>
<p>
Stateful value traits have many advantages but also some downsides:
</p>
<div class="itemizedlist"><ul class="itemizedlist" type="disc">
<li class="listitem">
<span class="bold"><strong>Performance</strong></span>: Value traits operations
should be very efficient since they are basic operations used by containers.
<span class="bold"><strong>A heavy node <-> value transformation will
hurt intrusive containers' performance</strong></span>.
</li>
<li class="listitem">
<span class="bold"><strong>Exception guarantees</strong></span>: The stateful ValueTraits
must maintain no-throw guarantees, otherwise, the container invariants
won't be preserved.
</li>
<li class="listitem">
<span class="bold"><strong>Static functions</strong></span>: Some static functions
offered by intrusive containers are not available because node <->
value transformations are not static.
</li>
<li class="listitem">
<span class="bold"><strong>Bigger iterators</strong></span>: The size of some iterators
is increased because the iterator needs to store a pointer to the stateful
value traits to implement node to value transformations (e.g. <code class="computeroutput"><span class="keyword">operator</span><span class="special">*()</span></code>
and <code class="computeroutput"><span class="keyword">operator</span><span class="special">->()</span></code>).
</li>
</ul></div>
<p>
An easy and useful example of stateful value traits is when an array of values
can be indirectly introduced in a list guaranteeing no additional allocation
apart from the initial resource reservation:
</p>
<p>
</p>
<p>
</p>
<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>
<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>
<span class="comment">//This type is not modifiable so we can't store hooks or custom nodes
</span><span class="keyword">typedef</span> <span class="keyword">int</span> <span class="identifier">identifier_t</span><span class="special">;</span>
<span class="comment">//This value traits will associate elements from an array of identifiers with
</span><span class="comment">//elements of an array of nodes. The element i of the value array will use the
</span><span class="comment">//node i of the node array:
</span><span class="keyword">struct</span> <span class="identifier">stateful_value_traits</span>
<span class="special">{</span>
<span class="keyword">typedef</span> <span class="identifier">list_node_traits</span><span class="special"><</span><span class="keyword">void</span><span class="special">*></span> <span class="identifier">node_traits</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node</span> <span class="identifier">node</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">node</span> <span class="special">*</span> <span class="identifier">node_ptr</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="keyword">const</span> <span class="identifier">node</span> <span class="special">*</span> <span class="identifier">const_node_ptr</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">identifier_t</span> <span class="identifier">value_type</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">identifier_t</span> <span class="special">*</span> <span class="identifier">pointer</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="keyword">const</span> <span class="identifier">identifier_t</span> <span class="special">*</span> <span class="identifier">const_pointer</span><span class="special">;</span>
<span class="keyword">static</span> <span class="keyword">const</span> <span class="identifier">link_mode_type</span> <span class="identifier">link_mode</span> <span class="special">=</span> <span class="identifier">normal_link</span><span class="special">;</span>
<span class="identifier">stateful_value_traits</span><span class="special">(</span><span class="identifier">pointer</span> <span class="identifier">ids</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">node_array</span><span class="special">)</span>
<span class="special">:</span> <span class="identifier">ids_</span><span class="special">(</span><span class="identifier">ids</span><span class="special">),</span> <span class="identifier">nodes_</span><span class="special">(</span><span class="identifier">node_array</span><span class="special">)</span>
<span class="special">{}</span>
<span class="comment">///Note: non static functions!
</span> <span class="identifier">node_ptr</span> <span class="identifier">to_node_ptr</span> <span class="special">(</span><span class="identifier">value_type</span> <span class="special">&</span><span class="identifier">value</span><span class="special">)</span>
<span class="special">{</span> <span class="keyword">return</span> <span class="keyword">this</span><span class="special">-></span><span class="identifier">nodes_</span> <span class="special">+</span> <span class="special">(&</span><span class="identifier">value</span> <span class="special">-</span> <span class="keyword">this</span><span class="special">-></span><span class="identifier">ids_</span><span class="special">);</span> <span class="special">}</span>
<span class="identifier">const_node_ptr</span> <span class="identifier">to_node_ptr</span> <span class="special">(</span><span class="keyword">const</span> <span class="identifier">value_type</span> <span class="special">&</span><span class="identifier">value</span><span class="special">)</span> <span class="keyword">const</span>
<span class="special">{</span> <span class="keyword">return</span> <span class="keyword">this</span><span class="special">-></span><span class="identifier">nodes_</span> <span class="special">+</span> <span class="special">(&</span><span class="identifier">value</span> <span class="special">-</span> <span class="keyword">this</span><span class="special">-></span><span class="identifier">ids_</span><span class="special">);</span> <span class="special">}</span>
<span class="identifier">pointer</span> <span class="identifier">to_value_ptr</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">)</span>
<span class="special">{</span> <span class="keyword">return</span> <span class="keyword">this</span><span class="special">-></span><span class="identifier">ids_</span> <span class="special">+</span> <span class="special">(</span><span class="identifier">n</span> <span class="special">-</span> <span class="keyword">this</span><span class="special">-></span><span class="identifier">nodes_</span><span class="special">);</span> <span class="special">}</span>
<span class="identifier">const_pointer</span> <span class="identifier">to_value_ptr</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> <span class="keyword">const</span>
<span class="special">{</span> <span class="keyword">return</span> <span class="keyword">this</span><span class="special">-></span><span class="identifier">ids_</span> <span class="special">+</span> <span class="special">(</span><span class="identifier">n</span> <span class="special">-</span> <span class="keyword">this</span><span class="special">-></span><span class="identifier">nodes_</span><span class="special">);</span> <span class="special">}</span>
<span class="keyword">private</span><span class="special">:</span>
<span class="identifier">pointer</span> <span class="identifier">ids_</span><span class="special">;</span>
<span class="identifier">node_ptr</span> <span class="identifier">nodes_</span><span class="special">;</span>
<span class="special">};</span>
<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span>
<span class="special">{</span>
<span class="keyword">const</span> <span class="keyword">int</span> <span class="identifier">NumElements</span> <span class="special">=</span> <span class="number">100</span><span class="special">;</span>
<span class="comment">//This is an array of ids that we want to "store"
</span> <span class="identifier">identifier_t</span> <span class="identifier">ids</span> <span class="special">[</span><span class="identifier">NumElements</span><span class="special">];</span>
<span class="comment">//This is an array of nodes that is necessary to form the linked list
</span> <span class="identifier">list_node_traits</span><span class="special"><</span><span class="keyword">void</span><span class="special">*>::</span><span class="identifier">node</span> <span class="identifier">nodes</span> <span class="special">[</span><span class="identifier">NumElements</span><span class="special">];</span>
<span class="comment">//Initialize id objects, each one with a different number
</span> <span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special">!=</span> <span class="identifier">NumElements</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span> <span class="identifier">ids</span><span class="special">[</span><span class="identifier">i</span><span class="special">]</span> <span class="special">=</span> <span class="identifier">i</span><span class="special">;</span>
<span class="comment">//Define a list that will "link" identifiers using external nodes
</span> <span class="keyword">typedef</span> <span class="identifier">list</span><span class="special"><</span><span class="identifier">identifier_t</span><span class="special">,</span> <span class="identifier">value_traits</span><span class="special"><</span><span class="identifier">stateful_value_traits</span><span class="special">></span> <span class="special">></span> <span class="identifier">List</span><span class="special">;</span>
<span class="comment">//This list will store ids without modifying identifier_t instances
</span> <span class="comment">//Stateful value traits must be explicitly passed in the constructor.
</span> <span class="identifier">List</span> <span class="identifier">my_list</span> <span class="special">(</span><span class="identifier">stateful_value_traits</span> <span class="special">(</span><span class="identifier">ids</span><span class="special">,</span> <span class="identifier">nodes</span><span class="special">));</span>
<span class="comment">//Insert ids in reverse order in the list
</span> <span class="keyword">for</span><span class="special">(</span><span class="identifier">identifier_t</span> <span class="special">*</span> <span class="identifier">it</span><span class="special">(&</span><span class="identifier">ids</span><span class="special">[</span><span class="number">0</span><span class="special">]),</span> <span class="special">*</span><span class="identifier">itend</span><span class="special">(&</span><span class="identifier">ids</span><span class="special">[</span><span class="identifier">NumElements</span><span class="special">]);</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">itend</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">)</span>
<span class="identifier">my_list</span><span class="special">.</span><span class="identifier">push_front</span><span class="special">(*</span><span class="identifier">it</span><span class="special">);</span>
<span class="comment">//Now test lists
</span> <span class="identifier">List</span><span class="special">::</span><span class="identifier">const_iterator</span> <span class="identifier">list_it</span> <span class="special">(</span><span class="identifier">my_list</span><span class="special">.</span><span class="identifier">cbegin</span><span class="special">());</span>
<span class="identifier">identifier_t</span> <span class="special">*</span><span class="identifier">it_val</span><span class="special">(&</span><span class="identifier">ids</span><span class="special">[</span><span class="identifier">NumElements</span><span class="special">-</span><span class="number">1</span><span class="special">]),</span> <span class="special">*</span><span class="identifier">it_rbeg_val</span><span class="special">(&</span><span class="identifier">ids</span><span class="special">[</span><span class="number">0</span><span class="special">]-</span><span class="number">1</span><span class="special">);</span>
<span class="comment">//Test the objects inserted in the base hook list
</span> <span class="keyword">for</span><span class="special">(;</span> <span class="identifier">it_val</span> <span class="special">!=</span> <span class="identifier">it_rbeg_val</span><span class="special">;</span> <span class="special">--</span><span class="identifier">it_val</span><span class="special">,</span> <span class="special">++</span><span class="identifier">list_it</span><span class="special">)</span>
<span class="keyword">if</span><span class="special">(&*</span><span class="identifier">list_it</span> <span class="special">!=</span> <span class="special">&*</span><span class="identifier">it_val</span><span class="special">)</span> <span class="keyword">return</span> <span class="number">1</span><span class="special">;</span>
<span class="keyword">return</span> <span class="number">0</span><span class="special">;</span>
<span class="special">}</span>
</pre>
<p>
</p>
<p>
</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, 2006-2009 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="node_algorithms.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="thread_safety.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
