1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>Containers with custom ValueTraits</title> 6<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> 7<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 8<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> 9<link rel="up" href="../intrusive.html" title="Chapter 19. Boost.Intrusive"> 10<link rel="prev" href="node_algorithms.html" title="Node algorithms with custom NodeTraits"> 11<link rel="next" href="thread_safety.html" title="Thread safety guarantees"> 12</head> 13<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 14<table cellpadding="2" width="100%"><tr> 15<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> 16<td align="center"><a href="../../../index.html">Home</a></td> 17<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> 18<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 19<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 20<td align="center"><a href="../../../more/index.htm">More</a></td> 21</tr></table> 22<hr> 23<div class="spirit-nav"> 24<a accesskey="p" href="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> 25</div> 26<div class="section"> 27<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 28<a name="intrusive.value_traits"></a><a class="link" href="value_traits.html" title="Containers with custom ValueTraits">Containers with custom ValueTraits</a> 29</h2></div></div></div> 30<div class="toc"><dl class="toc"> 31<dt><span class="section"><a href="value_traits.html#intrusive.value_traits.value_traits_interface">ValueTraits 32 interface</a></span></dt> 33<dt><span class="section"><a href="value_traits.html#intrusive.value_traits.value_traits_example">Custom ValueTraits 34 example</a></span></dt> 35<dt><span class="section"><a href="value_traits.html#intrusive.value_traits.reusing_node_algorithms">Reusing 36 node algorithms for different values</a></span></dt> 37<dt><span class="section"><a href="value_traits.html#intrusive.value_traits.simplifying_value_traits">Simplifying 38 value traits definition</a></span></dt> 39<dt><span class="section"><a href="value_traits.html#intrusive.value_traits.stateful_value_traits">Stateful 40 value traits</a></span></dt> 41</dl></div> 42<p> 43 As explained in the <a class="link" href="concepts.html" title="Concepts explained">Concepts</a> section, 44 <span class="bold"><strong>Boost.Intrusive</strong></span> containers need a <code class="computeroutput"><span class="identifier">ValueTraits</span></code> class to perform transformations 45 between nodes and user values. <code class="computeroutput"><span class="identifier">ValueTraits</span></code> 46 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 47 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> 48 options). <code class="computeroutput"><span class="identifier">ValueTraits</span></code> contains 49 all the information to glue the <code class="computeroutput"><span class="identifier">value_type</span></code> 50 of the containers and the node to be used in node algorithms, since these types 51 can be different. Apart from this, <code class="computeroutput"><span class="identifier">ValueTraits</span></code> 52 also stores information about the link policy of the values to be inserted. 53 </p> 54<p> 55 Instead of using <span class="bold"><strong>Boost.Intrusive</strong></span> predefined 56 hooks a user might want to develop customized containers, for example, using 57 nodes that are optimized for a specific application or that are compatible 58 with a legacy ABI. A user might want to have only two additional pointers in 59 his class and insert the class in a doubly linked list sometimes and in a singly 60 linked list in other situations. You can't achieve this using <span class="bold"><strong>Boost.Intrusive</strong></span> 61 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 62 <code class="computeroutput"><span class="identifier">value_traits</span><span class="special"><...></span></code> 63 options. Let's see how we can do this: 64 </p> 65<div class="section"> 66<div class="titlepage"><div><div><h3 class="title"> 67<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 68 interface</a> 69</h3></div></div></div> 70<p> 71 <code class="computeroutput"><span class="identifier">ValueTraits</span></code> has the following 72 interface: 73 </p> 74<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">pointer_traits</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 75<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> 76 77<span class="keyword">struct</span> <span class="identifier">my_value_traits</span> 78<span class="special">{</span> 79 <span class="keyword">typedef</span> <span class="identifier">implementation_defined</span> <span class="identifier">node_traits</span><span class="special">;</span> 80 <span class="keyword">typedef</span> <span class="identifier">implementation_defined</span> <span class="identifier">value_type</span><span class="special">;</span> 81 <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> 82 <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> 83 <span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">::</span><span class="identifier">pointer_traits</span><span class="special"><</span><span class="identifier">node_ptr</span><span class="special">>::</span><span class="identifier">rebind_traits</span> 84 <span class="special"><</span><span class="identifier">value_type</span><span class="special">>::</span><span class="identifier">type</span><span class="special">::</span><span class="identifier">pointer</span> <span class="identifier">pointer</span><span class="special">;</span> 85 <span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">::</span><span class="identifier">pointer_traits</span><span class="special"><</span><span class="identifier">node_ptr</span><span class="special">>::</span><span class="identifier">rebind_traits</span> 86 <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="special">::</span><span class="identifier">pointer</span> <span class="identifier">const_pointer</span><span class="special">;</span> 87 88 <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> 89 90 <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> 91 <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> 92 <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> 93 <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> 94<span class="special">};</span> 95</pre> 96<p> 97 Let's explain each type and function: 98 </p> 99<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 100<li class="listitem"> 101 <span class="bold"><strong><span class="emphasis"><em>node_traits</em></span></strong></span>: The 102 node configuration that is needed by node algorithms. These node traits 103 and algorithms are described in the previous chapter: <a class="link" href="node_algorithms.html" title="Node algorithms with custom NodeTraits">Node 104 Algorithms</a>. 105 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "> 106<li class="listitem"> 107 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>, 108 <code class="computeroutput"><span class="identifier">node_traits</span></code> should 109 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>. 110 </li> 111<li class="listitem"> 112 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>, 113 <code class="computeroutput"><span class="identifier">node_traits</span></code> should 114 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>. 115 </li> 116<li class="listitem"> 117 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 118 interface needed by <code class="computeroutput"><a class="link" href="../boost/intrusive/rbtree_algorithms.html" title="Class template rbtree_algorithms">rbtree_algorithms</a></code>. 119 </li> 120<li class="listitem"> 121 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>/ 122 <code class="computeroutput"><a class="link" href="../boost/intrusive/unordered_multiset.html" title="Class template unordered_multiset">unordered_multiset</a></code>, 123 <code class="computeroutput"><span class="identifier">node_traits</span></code> should 124 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>. 125 </li> 126</ul></div> 127 </li> 128<li class="listitem"> 129 <span class="bold"><strong><span class="emphasis"><em>node_ptr</em></span></strong></span>: A typedef 130 for <code class="computeroutput"><span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node_ptr</span></code>. 131 </li> 132<li class="listitem"> 133 <span class="bold"><strong><span class="emphasis"><em>const_node_ptr</em></span></strong></span>: 134 A typedef for <code class="computeroutput"><span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">const_node_ptr</span></code>. 135 </li> 136<li class="listitem"> 137 <span class="bold"><strong><span class="emphasis"><em>value_type</em></span></strong></span>: The 138 type that the user wants to insert in the container. This type can be 139 the same as <code class="computeroutput"><span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node</span></code> 140 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> 141 can be a member type of <code class="computeroutput"><span class="identifier">value_type</span></code>). 142 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> 143 functions are trivial. 144 </li> 145<li class="listitem"> 146 <span class="bold"><strong><span class="emphasis"><em>pointer</em></span></strong></span>: The type 147 of a pointer to a <code class="computeroutput"><span class="identifier">value_type</span></code>. 148 It must be the same pointer type as <code class="computeroutput"><span class="identifier">node_ptr</span></code>: 149 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>, 150 <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>. 151 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>, 152 <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>. 153 This can be generically achieved using <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">::</span><span class="identifier">pointer_traits</span></code> 154 (portable implementation of C++11 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pointer_traits</span></code>). 155 </li> 156<li class="listitem"> 157 <span class="bold"><strong><span class="emphasis"><em>const_pointer</em></span></strong></span>: 158 The type of a pointer to a <code class="computeroutput"><span class="keyword">const</span> 159 <span class="identifier">value_type</span></code>. It must be the 160 same pointer type as <code class="computeroutput"><span class="identifier">node_ptr</span></code>: 161 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>, 162 <code class="computeroutput"><span class="identifier">const_pointer</span></code> must be 163 <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> 164 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>, 165 <code class="computeroutput"><span class="identifier">const_pointer</span></code> must be 166 <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>. 167 </li> 168<li class="listitem"> 169 <span class="bold"><strong><span class="emphasis"><em>link_mode</em></span></strong></span>: Indicates 170 that <code class="computeroutput"><span class="identifier">value_traits</span></code> needs 171 some additional work or checks from the container. The types are enumerations 172 defined in the <code class="computeroutput"><span class="identifier">link_mode</span><span class="special">.</span><span class="identifier">hpp</span></code> 173 header. These are the possible types: 174 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "> 175<li class="listitem"> 176 <span class="bold"><strong><code class="computeroutput"><span class="identifier">normal_link</span></code></strong></span>: 177 If this linking policy is specified in a <code class="computeroutput"><span class="identifier">ValueTraits</span></code> 178 class as the link mode, containers configured with such <code class="computeroutput"><span class="identifier">ValueTraits</span></code> won't set the hooks 179 of the erased values to a default state. Containers also won't 180 check that the hooks of the new values are default initialized. 181 </li> 182<li class="listitem"> 183 <span class="bold"><strong><code class="computeroutput"><span class="identifier">safe_link</span></code></strong></span>: 184 If this linking policy is specified as the link mode in a <code class="computeroutput"><span class="identifier">ValueTraits</span></code> class, containers 185 configured with this <code class="computeroutput"><span class="identifier">ValueTraits</span></code> 186 will set the hooks of the erased values to a default state. Containers 187 also will check that the hooks of the new values are default initialized. 188 </li> 189<li class="listitem"> 190 <span class="bold"><strong><code class="computeroutput"><span class="identifier">auto_unlink</span></code></strong></span>: 191 Same as "safe_link" but containers with constant-time 192 size features won't be compatible with <code class="computeroutput"><span class="identifier">ValueTraits</span></code> 193 configured with this policy. Containers also know that a value 194 can be silently erased from the container without using any function 195 provided by the containers. 196 </li> 197</ul></div> 198 </li> 199<li class="listitem"> 200 <span class="bold"><strong><span class="emphasis"><em>static node_ptr to_node_ptr (value_type 201 &value)</em></span></strong></span> and <span class="bold"><strong><span class="emphasis"><em>static 202 const_node_ptr to_node_ptr (const value_type &value)</em></span></strong></span>: 203 These functions take a reference to a value_type and return a pointer 204 to the node to be used with node algorithms. 205 </li> 206<li class="listitem"> 207 <span class="bold"><strong><span class="emphasis"><em>static pointer to_value_ptr (node_ptr 208 n)</em></span></strong></span> and <span class="bold"><strong><span class="emphasis"><em>static const_pointer 209 to_value_ptr (const_node_ptr n)</em></span></strong></span>: These functions 210 take a pointer to a node and return a pointer to the value that contains 211 the node. 212 </li> 213</ul></div> 214</div> 215<div class="section"> 216<div class="titlepage"><div><div><h3 class="title"> 217<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 218 example</a> 219</h3></div></div></div> 220<p> 221 Let's define our own <code class="computeroutput"><span class="identifier">value_traits</span></code> 222 class to be able to use <span class="bold"><strong>Boost.Intrusive</strong></span> 223 containers with an old C structure whose definition can't be changed. That 224 legacy type has two pointers that can be used to build singly and doubly 225 linked lists: in singly linked lists we only need a pointer, whereas in doubly 226 linked lists, we need two pointers. Since we only have two pointers, we can't 227 insert the object in both a singly and a doubly linked list at the same time. 228 This is the definition of the old node: 229 </p> 230<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> 231<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> 232<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> 233<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">vector</span><span class="special">></span> 234 235<span class="comment">//This node is the legacy type we can't modify and we want to insert in</span> 236<span class="comment">//intrusive list and slist containers using only two pointers, since</span> 237<span class="comment">//we know the object will never be at the same time in both lists.</span> 238<span class="keyword">struct</span> <span class="identifier">legacy_value</span> 239<span class="special">{</span> 240 <span class="identifier">legacy_value</span> <span class="special">*</span><span class="identifier">prev_</span><span class="special">;</span> 241 <span class="identifier">legacy_value</span> <span class="special">*</span><span class="identifier">next_</span><span class="special">;</span> 242 <span class="keyword">int</span> <span class="identifier">id_</span><span class="special">;</span> 243<span class="special">};</span> 244</pre> 245<p> 246 Now we have to define a NodeTraits class that will implement the functions/typedefs 247 that will make the legacy node compatible with <span class="bold"><strong>Boost.Intrusive</strong></span> 248 algorithms. After that, we'll define a ValueTraits class that will configure 249 <span class="bold"><strong>Boost.Intrusive</strong></span> containers: 250 </p> 251<pre class="programlisting"><span class="comment">//Define our own NodeTraits that will configure singly and doubly linked</span> 252<span class="comment">//list algorithms. Note that this node traits is compatible with</span> 253<span class="comment">//circular_slist_algorithms and circular_list_algorithms.</span> 254 255<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> 256 257<span class="keyword">struct</span> <span class="identifier">legacy_node_traits</span> 258<span class="special">{</span> 259 <span class="keyword">typedef</span> <span class="identifier">legacy_value</span> <span class="identifier">node</span><span class="special">;</span> 260 <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> 261 <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> 262 263 <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> 264 <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> 265 <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> 266 <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> 267<span class="special">};</span> 268 269<span class="comment">//This ValueTraits will configure list and slist. In this case,</span> 270<span class="comment">//legacy_node_traits::node is the same as the</span> 271<span class="comment">//legacy_value_traits::value_type so to_node_ptr/to_value_ptr</span> 272<span class="comment">//functions are trivial.</span> 273<span class="keyword">struct</span> <span class="identifier">legacy_value_traits</span> 274<span class="special">{</span> 275 <span class="keyword">typedef</span> <span class="identifier">legacy_node_traits</span> <span class="identifier">node_traits</span><span class="special">;</span> 276 <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> 277 <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> 278 <span class="keyword">typedef</span> <span class="identifier">legacy_value</span> <span class="identifier">value_type</span><span class="special">;</span> 279 <span class="keyword">typedef</span> <span class="identifier">legacy_value</span> <span class="special">*</span> <span class="identifier">pointer</span><span class="special">;</span> 280 <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> 281 <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> 282 <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> 283 <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> 284 <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> 285 <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> 286<span class="special">};</span> 287</pre> 288<p> 289 Defining a value traits class that simply defines <code class="computeroutput"><span class="identifier">value_type</span></code> 290 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 291 customized intrusive containers, so <span class="bold"><strong>Boost.Intrusive</strong></span> 292 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> 293 class that does exactly what we want: 294 </p> 295<pre class="programlisting"><span class="keyword">typedef</span> <span class="identifier">bi</span><span class="special">::</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">bi</span><span class="special">::</span><span class="identifier">normal_link</span><span class="special">></span> <span class="identifier">trivial_legacy_value_traits</span><span class="special">;</span> 296</pre> 297<p> 298 Now we can just define the containers that will store the legacy abi objects 299 and write a little test: 300 </p> 301<pre class="programlisting"><span class="comment">//Now define an intrusive list and slist that will store legacy_value objects</span> 302<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> 303<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">trivial_legacy_value_traits</span><span class="special">></span> <span class="identifier">TrivialValueTraitsOption</span><span class="special">;</span> 304 305<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> 306<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> 307<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">TrivialValueTraitsOption</span><span class="special">></span> <span class="identifier">TrivialLegacyAbiList</span><span class="special">;</span> 308<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">TrivialValueTraitsOption</span><span class="special">></span> <span class="identifier">TrivialLegacyAbiSlist</span><span class="special">;</span> 309 310<span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">List</span><span class="special">></span> 311<span class="keyword">bool</span> <span class="identifier">test_list</span><span class="special">()</span> 312<span class="special">{</span> 313 <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> 314 315 <span class="comment">//Create legacy_value objects, with a different internal number</span> 316 <span class="identifier">Vect</span> <span class="identifier">legacy_vector</span><span class="special">;</span> 317 <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> 318 <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> 319 <span class="special">}</span> 320 321 <span class="comment">//Create the list with the objects</span> 322 <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> 323 324 <span class="comment">//Now test both lists</span> 325 <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> 326 <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> 327 328 <span class="comment">//Test the objects inserted in our list</span> 329 <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> 330 <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> 331 <span class="keyword">return</span> <span class="keyword">true</span><span class="special">;</span> 332<span class="special">}</span> 333 334<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 335<span class="special">{</span> 336 <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> 337 <span class="identifier">test_list</span><span class="special"><</span><span class="identifier">TrivialLegacyAbiList</span><span class="special">>()</span> <span class="special">&&</span> <span class="identifier">test_list</span><span class="special"><</span><span class="identifier">TrivialLegacyAbiSlist</span><span class="special">>()</span> 338 <span class="special">?</span> <span class="number">0</span> <span class="special">:</span> <span class="number">1</span><span class="special">;</span> 339<span class="special">}</span> 340</pre> 341<p> 342 As seen, several key elements of <span class="bold"><strong>Boost.Intrusive</strong></span> 343 can be reused with custom user types, if the user does not want to use the 344 provided <span class="bold"><strong>Boost.Intrusive</strong></span> facilities. 345 </p> 346</div> 347<div class="section"> 348<div class="titlepage"><div><div><h3 class="title"> 349<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 350 node algorithms for different values</a> 351</h3></div></div></div> 352<p> 353 In the previous example, <code class="computeroutput"><span class="identifier">legacy_node_traits</span><span class="special">::</span><span class="identifier">node</span></code> 354 type and <code class="computeroutput"><span class="identifier">legacy_value_traits</span><span class="special">::</span><span class="identifier">value_type</span></code> 355 are the same type, but this is not necessary. It's possible to have several 356 <code class="computeroutput"><span class="identifier">ValueTraits</span></code> defining the 357 same <code class="computeroutput"><span class="identifier">node_traits</span></code> type (and 358 thus, the same <code class="computeroutput"><span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node</span></code>). 359 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> 360 functions need to offer conversions between both types. Let's see a small 361 example: 362 </p> 363<p> 364 First, we'll define the node to be used in the algorithms. For a linked list, 365 we just need a node that stores two pointers: 366 </p> 367<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> 368<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> 369<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">vector</span><span class="special">></span> 370 371<span class="comment">//This is the node that will be used with algorithms.</span> 372<span class="keyword">struct</span> <span class="identifier">simple_node</span> 373<span class="special">{</span> 374 <span class="identifier">simple_node</span> <span class="special">*</span><span class="identifier">prev_</span><span class="special">;</span> 375 <span class="identifier">simple_node</span> <span class="special">*</span><span class="identifier">next_</span><span class="special">;</span> 376<span class="special">};</span> 377</pre> 378<p> 379 Now we'll define two different types that will be inserted in intrusive lists 380 and a templatized <code class="computeroutput"><span class="identifier">ValueTraits</span></code> 381 that will work for both types: 382 </p> 383<pre class="programlisting"><span class="keyword">class</span> <span class="identifier">base_1</span><span class="special">{};</span> 384<span class="keyword">class</span> <span class="identifier">base_2</span><span class="special">{};</span> 385 386<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> 387<span class="special">{</span> <span class="keyword">int</span> <span class="identifier">id_</span><span class="special">;</span> <span class="special">};</span> 388 389<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> 390<span class="special">{</span> <span class="keyword">float</span> <span class="identifier">id_</span><span class="special">;</span> <span class="special">};</span> 391 392<span class="comment">//Define the node traits. A single node_traits will be enough.</span> 393<span class="keyword">struct</span> <span class="identifier">simple_node_traits</span> 394<span class="special">{</span> 395 <span class="keyword">typedef</span> <span class="identifier">simple_node</span> <span class="identifier">node</span><span class="special">;</span> 396 <span class="keyword">typedef</span> <span class="identifier">node</span> <span class="special">*</span> <span class="identifier">node_ptr</span><span class="special">;</span> 397 <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> 398 <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> 399 <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> 400 <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> 401 <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> 402<span class="special">};</span> 403 404<span class="comment">//A templatized value traits for value_1 and value_2</span> 405<span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">ValueType</span><span class="special">></span> 406<span class="keyword">struct</span> <span class="identifier">simple_value_traits</span> 407<span class="special">{</span> 408 <span class="keyword">typedef</span> <span class="identifier">simple_node_traits</span> <span class="identifier">node_traits</span><span class="special">;</span> 409 <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> 410 <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> 411 <span class="keyword">typedef</span> <span class="identifier">ValueType</span> <span class="identifier">value_type</span><span class="special">;</span> 412 <span class="keyword">typedef</span> <span class="identifier">ValueType</span> <span class="special">*</span> <span class="identifier">pointer</span><span class="special">;</span> 413 <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> 414 <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> 415 <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> 416 <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> 417 <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> 418 <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> 419<span class="special">};</span> 420</pre> 421<p> 422 Now define two containers. Both containers will instantiate the same list 423 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 424 used to define the containers provide the same <code class="computeroutput"><span class="identifier">node_traits</span></code> 425 type: 426 </p> 427<pre class="programlisting"><span class="comment">//Now define two intrusive lists. Both lists will use the same algorithms:</span> 428<span class="comment">// circular_list_algorithms<simple_node_traits></span> 429 430<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> 431<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> 432<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> 433</pre> 434<p> 435 All <span class="bold"><strong>Boost.Intrusive</strong></span> containers using predefined 436 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> 437 containers created with predefined hooks that define the same <code class="computeroutput"><span class="identifier">VoidPointer</span></code> type share the same list algorithms. 438 </p> 439</div> 440<div class="section"> 441<div class="titlepage"><div><div><h3 class="title"> 442<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 443 value traits definition</a> 444</h3></div></div></div> 445<p> 446 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> 447 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: 448 </p> 449<pre class="programlisting"><span class="keyword">class</span> <span class="identifier">base_1</span><span class="special">{};</span> 450<span class="keyword">class</span> <span class="identifier">base_2</span><span class="special">{};</span> 451 452<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> 453<span class="special">{</span> 454 <span class="keyword">int</span> <span class="identifier">id_</span><span class="special">;</span> 455 <span class="identifier">simple_node</span> <span class="identifier">node_</span><span class="special">;</span> 456<span class="special">};</span> 457 458<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> 459<span class="special">{</span> 460 <span class="identifier">simple_node</span> <span class="identifier">node_</span><span class="special">;</span> 461 <span class="keyword">float</span> <span class="identifier">id_</span><span class="special">;</span> 462<span class="special">};</span> 463 464<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> 465 466<span class="comment">//Now define the needed value traits using derivation_value_traits</span> 467<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> 468<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> 469 470<span class="comment">//Now define two intrusive lists. Both lists will use the same algorithms:</span> 471<span class="comment">// circular_list_algorithms<simple_node_traits></span> 472<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> 473<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> 474</pre> 475<p> 476 We can even choose to store <code class="computeroutput"><span class="identifier">simple_node</span></code> 477 as a member of <code class="computeroutput"><span class="identifier">value_1</span></code> and 478 <code class="computeroutput"><span class="identifier">value_2</span></code> classes and use 479 <code class="computeroutput"><a class="link" href="../boost/intrusive/member_value_traits.html" title="Struct template member_value_traits">member_value_traits</a></code> 480 to define the needed value traits classes: 481 </p> 482<pre class="programlisting"><span class="keyword">class</span> <span class="identifier">base_1</span><span class="special">{};</span> 483<span class="keyword">class</span> <span class="identifier">base_2</span><span class="special">{};</span> 484 485<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> 486<span class="special">{</span> 487 <span class="keyword">int</span> <span class="identifier">id_</span><span class="special">;</span> 488 <span class="identifier">simple_node</span> <span class="identifier">node_</span><span class="special">;</span> 489<span class="special">};</span> 490 491<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> 492<span class="special">{</span> 493 <span class="identifier">simple_node</span> <span class="identifier">node_</span><span class="special">;</span> 494 <span class="keyword">float</span> <span class="identifier">id_</span><span class="special">;</span> 495<span class="special">};</span> 496 497<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> 498 499<span class="keyword">typedef</span> <span class="identifier">member_value_traits</span> 500 <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> 501<span class="keyword">typedef</span> <span class="identifier">member_value_traits</span> 502<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> 503 504<span class="comment">//Now define two intrusive lists. Both lists will use the same algorithms:</span> 505<span class="comment">// circular_list_algorithms<simple_node_traits></span> 506<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> 507<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> 508</pre> 509</div> 510<div class="section"> 511<div class="titlepage"><div><div><h3 class="title"> 512<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 513 value traits</a> 514</h3></div></div></div> 515<p> 516 Until now all shown custom value traits are stateless, that is, <span class="bold"><strong>the transformation between nodes and values is implemented in 517 terms of static functions</strong></span>. It's possible to use <span class="bold"><strong>stateful</strong></span> 518 value traits so that we can separate nodes and values and <span class="bold"><strong>avoid 519 modifying types to insert nodes</strong></span>. <span class="bold"><strong>Boost.Intrusive</strong></span> 520 differentiates between stateful and stateless value traits by checking if 521 all Node <-> Value transformation functions are static or not (except 522 for Visual 7.1, since overloaded static function detection is not possible, 523 in this case the implementation checks if the class is empty): 524 </p> 525<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 526<li class="listitem"> 527 If all Node <-> Value transformation functions are static , a 528 <span class="bold"><strong>stateless</strong></span> value traits is assumed. transformations 529 must be static functions. 530 </li> 531<li class="listitem"> 532 Otherwise a <span class="bold"><strong>stateful</strong></span> value traits is 533 assumed. 534 </li> 535</ul></div> 536<p> 537 Using stateful value traits it's possible to create containers of non-copyable/movable 538 objects <span class="bold"><strong>without modifying</strong></span> the definition 539 of the class to be inserted. This interesting property is achieved without 540 using global variables (stateless value traits could use global variables 541 to achieve the same goal), so: 542 </p> 543<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 544<li class="listitem"> 545 <span class="bold"><strong>Thread-safety guarantees</strong></span>: Better thread-safety 546 guarantees can be achieved with stateful value traits, since accessing 547 global resources might require synchronization primitives that can be 548 avoided when using internal state. 549 </li> 550<li class="listitem"> 551 <span class="bold"><strong>Flexibility</strong></span>: A stateful value traits 552 type can be configured at run-time. 553 </li> 554<li class="listitem"> 555 <span class="bold"><strong>Run-time polymorphism</strong></span>: A value traits 556 might implement node <-> value transformations as virtual functions. 557 A single container type could be configured at run-time to use different 558 node <-> value relationships. 559 </li> 560</ul></div> 561<p> 562 Stateful value traits have many advantages but also some downsides: 563 </p> 564<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 565<li class="listitem"> 566 <span class="bold"><strong>Performance</strong></span>: Value traits operations 567 should be very efficient since they are basic operations used by containers. 568 <span class="bold"><strong>A heavy node <-> value transformation will 569 hurt intrusive containers' performance</strong></span>. 570 </li> 571<li class="listitem"> 572 <span class="bold"><strong>Exception guarantees</strong></span>: The stateful ValueTraits 573 must maintain no-throw guarantees, otherwise, the container invariants 574 won't be preserved. 575 </li> 576<li class="listitem"> 577 <span class="bold"><strong>Static functions</strong></span>: Some static functions 578 offered by intrusive containers are not available because node <-> 579 value transformations are not static. 580 </li> 581<li class="listitem"> 582 <span class="bold"><strong>Bigger iterators</strong></span>: The size of some iterators 583 is increased because the iterator needs to store a pointer to the stateful 584 value traits to implement node to value transformations (e.g. <code class="computeroutput"><span class="keyword">operator</span><span class="special">*()</span></code> 585 and <code class="computeroutput"><span class="keyword">operator</span><span class="special">->()</span></code>). 586 </li> 587</ul></div> 588<p> 589 An easy and useful example of stateful value traits is when an array of values 590 can be indirectly introduced in a list guaranteeing no additional allocation 591 apart from the initial resource reservation: 592 </p> 593<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> 594 595<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> 596 597<span class="comment">//This type is not modifiable so we can't store hooks or custom nodes</span> 598<span class="keyword">typedef</span> <span class="keyword">int</span> <span class="identifier">identifier_t</span><span class="special">;</span> 599 600<span class="comment">//This value traits will associate elements from an array of identifiers with</span> 601<span class="comment">//elements of an array of nodes. The element i of the value array will use the</span> 602<span class="comment">//node i of the node array:</span> 603<span class="keyword">struct</span> <span class="identifier">stateful_value_traits</span> 604<span class="special">{</span> 605 <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> 606 <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> 607 <span class="keyword">typedef</span> <span class="identifier">node</span> <span class="special">*</span> <span class="identifier">node_ptr</span><span class="special">;</span> 608 <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> 609 <span class="keyword">typedef</span> <span class="identifier">identifier_t</span> <span class="identifier">value_type</span><span class="special">;</span> 610 <span class="keyword">typedef</span> <span class="identifier">identifier_t</span> <span class="special">*</span> <span class="identifier">pointer</span><span class="special">;</span> 611 <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> 612 <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> 613 614 <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> 615 <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> 616 <span class="special">{}</span> 617 618 <span class="comment">///Note: non static functions!</span> 619 <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">const</span> 620 <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> 621 <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> 622 <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> 623 <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">const</span> 624 <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> 625 <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> 626 <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> 627 628 <span class="keyword">private</span><span class="special">:</span> 629 <span class="identifier">pointer</span> <span class="identifier">ids_</span><span class="special">;</span> 630 <span class="identifier">node_ptr</span> <span class="identifier">nodes_</span><span class="special">;</span> 631<span class="special">};</span> 632 633<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 634<span class="special">{</span> 635 <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> 636 637 <span class="comment">//This is an array of ids that we want to "store"</span> 638 <span class="identifier">identifier_t</span> <span class="identifier">ids</span> <span class="special">[</span><span class="identifier">NumElements</span><span class="special">];</span> 639 640 <span class="comment">//This is an array of nodes that is necessary to form the linked list</span> 641 <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> 642 643 <span class="comment">//Initialize id objects, each one with a different number</span> 644 <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> 645 646 <span class="comment">//Define a list that will "link" identifiers using external nodes</span> 647 <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> 648 649 <span class="comment">//This list will store ids without modifying identifier_t instances</span> 650 <span class="comment">//Stateful value traits must be explicitly passed in the constructor.</span> 651 <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> 652 653 <span class="comment">//Insert ids in reverse order in the list</span> 654 <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> 655 <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> 656 657 <span class="comment">//Now test lists</span> 658 <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> 659 <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="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> 660 661 <span class="comment">//Test the objects inserted in the base hook list</span> 662 <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> 663 <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="number">1</span><span class="special">])</span> <span class="keyword">return</span> <span class="number">1</span><span class="special">;</span> 664 665 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 666<span class="special">}</span> 667</pre> 668</div> 669</div> 670<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 671<td align="left"></td> 672<td align="right"><div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p> 673 Distributed under the Boost Software License, Version 1.0. (See accompanying 674 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>) 675 </p> 676</div></td> 677</tr></table> 678<hr> 679<div class="spirit-nav"> 680<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> 681</div> 682</body> 683</html> 684
