ceph/src/boost/libs/multi_index/doc/tutorial/key_extraction.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
   2
   3 <html>
   4 <head>
   5 <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
   6 <title>Boost.MultiIndex Documentation - Tutorial - Key extraction</title>
   7 <link rel="stylesheet" href="../style.css" type="text/css">
   8 <link rel="start" href="../index.html">
   9 <link rel="prev" href="indices.html">
  10 <link rel="up" href="index.html">
  11 <link rel="next" href="creation.html">
  12 </head>
  13
  14 <body>
  15 <h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
  16 "middle" width="277" height="86">Boost.MultiIndex Tutorial: Key extraction</h1>
  17
  18 <div class="prev_link"><a href="indices.html"><img src="../prev.gif" alt="index types" border="0"><br>
  19 Index types
  20 </a></div>
  21 <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
  22 Boost.MultiIndex tutorial
  23 </a></div>
  24 <div class="next_link"><a href="creation.html"><img src="../next.gif" alt="container creation" border="0"><br>
  25 Container creation
  26 </a></div><br clear="all" style="clear: all;">
  27
  28 <hr>
  29
  30 <h2>Contents</h2>
  31
  32 <ul>
  33   <li><a href="#intro">Introduction</a>
  34     <ul>
  35       <li><a href="#read_write_key_extractors">Read/write key extractors</a></li>
  36     </ul>
  37   </li>
  38   <li><a href="#predefined_key_extractors">Predefined key extractors</a>
  39     <ul>
  40       <li><a href="#identity"><code>identity</code></a></li>
  41       <li><a href="#member"><code>member</code></a></li>
  42       <li><a href="#const_mem_fun"><code>const_mem_fun</code>
  43         and <code>mem_fun</code></a></li>
  44       <li><a href="#global_fun"><code>global_fun</code></a></li>
  45     </ul>
  46   </li>
  47   <li><a href="#user_defined_key_extractors">User-defined key extractors</a></li>
  48   <li><a href="#composite_keys">Composite keys</a>
  49     <ul>
  50       <li><a href="#composite_keys_hash">Composite keys and hashed indices</a></li>
  51     </ul>
  52   </li>
  53   <li><a href="#advanced_key_extractors">Advanced features of Boost.MultiIndex key
  54     extractors</a></li>
  55 </ul>
  56
  57 <h2><a name="intro">Introduction</a></h2>
  58
  59 <p>
  60 STL associative containers have a notion of key, albeit in a somewhat incipient
  61 form. So, the keys of such containers are identified by a nested type
  62 <code>key_type</code>; for <code>std::set</code>s and <code>std::multiset</code>s,
  63 <code>key_type</code> coincides with <code>value_type</code>, i.e. the key is the
  64 element itself. <code>std::map</code> and <code>std::multimap</code> manage
  65 elements of type <code>std::pair&lt;const Key,T&gt;</code>, where the first
  66 member is the key. In either case, the process of obtaining the key from a
  67 given element is implicitly fixed and cannot be customized by the user.
  68 </p>
  69
  70 <p>
  71 Fixed key extraction mechanisms like those performed by STL associative
  72 containers do not scale well in the context of Boost.MultiIndex, where
  73 several indices share their <code>value_type</code> definition but
  74 might feature completely different lookup semantics. For this reason,
  75 Boost.MultiIndex formalizes the concept of a
  76 <a href="../reference/key_extraction.html#key_extractors"><code>Key
  77 Extractor</code></a> in order to make it explicit and controllable
  78 in the definition of key-based indices.
  79 </p>
  80
  81 <p>
  82 Intuitively speaking, a key extractor is a function object that accepts
  83 a reference to an element and returns its associated key. The formal
  84 concept also imposes some reasonable constraints about the stability
  85 of the process, in the sense that extractors are assumed to
  86 return the same key when passed the same element: this is in consonance
  87 with the informal understanding that keys are actually some "part"
  88 of the element and do not depend on external data.
  89 </p>
  90
  91 <h3><a name="read_write_key_extractors">Read/write key extractors</a></h3>
  92
  93 <p>
  94 A key extractor is called <i>read/write</i> if it returns a non-constant reference
  95 to the key when passed a non-constant element, and it is called <i>read-only</i>
  96 otherwise. Boost.MultiIndex requires that the key extractor be read/write
  97 when using the <code>modify_key</code> member function of ordered and hashed
  98 indices. In all other situations, read-only extractors suffice.
  99 The section on <a href="#advanced_key_extractors">advanced features
 100 of Boost.MultiIndex key extractors</a> details which of the predefined
 101 key extractors are read/write.
 102 </p>
 103
 104 <h2><a name="predefined_key_extractors">Predefined key extractors</a></h2>
 105
 106 <h3><a name="identity"><code>identity</code></a></h3>
 107
 108 <p>
 109 The <a href="../reference/key_extraction.html#identity"><code>identity</code></a>
 110 key extractor returns the entire base object as the associated key:
 111 </p>
 112
 113 <blockquote><pre>
 114 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index_container</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 115 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>ordered_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 116 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>identity</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 117
 118 <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 119   <span class=keyword>int</span><span class=special>,</span>
 120   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 121     <span class=identifier>ordered_unique</span><span class=special>&lt;</span>
 122       <span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=comment>// the key is the entire element</span>
 123     <span class=special>&gt;</span>
 124   <span class=special>&gt;</span>
 125 <span class=special>&gt;</span> <span class=identifier>cont</span><span class=special>;</span>
 126 </pre></blockquote>
 127
 128 <h3><a name="member"><code>member</code></a></h3>
 129
 130 <p>
 131 <a href="../reference/key_extraction.html#member"><code>member</code></a>
 132 key extractors return a reference to a specified
 133 data field of the base object. For instance, in the following version of our
 134 familiar employee container:
 135 </p>
 136
 137 <blockquote><pre>
 138 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index_container</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 139 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>ordered_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 140 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>identity</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 141 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>member</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 142
 143 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 144   <span class=identifier>employee</span><span class=special>,</span>
 145   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 146     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 147     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 148     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>ssnumber</span><span class=special>&gt;</span> <span class=special>&gt;</span>
 149   <span class=special>&gt;</span>
 150 <span class=special>&gt;</span> <span class=identifier>employee_set</span><span class=special>;</span>
 151 </pre></blockquote>
 152
 153 <p>
 154 the second and third indices use <code>member</code> extractors on
 155 <code>employee::name</code> and <code>employee::ssnumber</code>, respectively.
 156 The specification of an instantiation of <code>member</code> is simple
 157 yet a little contrived:
 158 </p>
 159
 160 <blockquote><pre>
 161 <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier><i>(base type)</i></span><span class=special>,</span><span class=identifier><i>(key type)</i></span><span class=special>,</span><span class=identifier><i>(pointer to member)</i></span><span class=special>&gt;</span>
 162 </pre></blockquote>
 163
 164 <p>
 165 It might seem that the first and second parameters are superfluous,
 166 since the type of the base object and of the associated data field are
 167 already implicit in the pointer to member argument: unfortunately, it is
 168 not possible to extract this information with current C++ mechanisms,
 169 which makes the syntax of <code>member</code> a little too verbose.
 170 </p>
 171
 172 <h3><a name="const_mem_fun"><code>const_mem_fun</code> and <code>mem_fun</code></a></h3>
 173
 174 <p>
 175 Sometimes, the key of an index is not a concrete data member of the element,
 176 but rather it is a value returned by a particular member function.
 177 This resembles the notion of <i>calculated indices</i> supported by some
 178 relational databases. Boost.MultiIndex supports this
 179 kind of key extraction through
 180 <a href="../reference/key_extraction.html#const_mem_fun"><code>const_mem_fun</code></a>.
 181 Consider the following container where sorting on the third index
 182 is based upon the length of the name field:
 183 </p>
 184
 185 <blockquote><pre>
 186 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index_container</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 187 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>ordered_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 188 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>identity</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 189 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>member</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 190 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>mem_fun</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 191
 192 <span class=keyword>struct</span> <span class=identifier>employee</span>
 193 <span class=special>{</span>
 194   <span class=keyword>int</span>         <span class=identifier>id</span><span class=special>;</span>
 195   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span>
 196
 197   <span class=identifier>employee</span><span class=special>(</span><span class=keyword>int</span> <span class=identifier>id</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&amp;</span> <span class=identifier>name</span><span class=special>):</span><span class=identifier>id</span><span class=special>(</span><span class=identifier>id</span><span class=special>),</span><span class=identifier>name</span><span class=special>(</span><span class=identifier>name</span><span class=special>){}</span>
 198
 199   <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>&lt;(</span><span class=keyword>const</span> <span class=identifier>employee</span><span class=special>&amp;</span> <span class=identifier>e</span><span class=special>)</span><span class=keyword>const</span><span class=special>{</span><span class=keyword>return</span> <span class=identifier>id</span><span class=special>&lt;</span><span class=identifier>e</span><span class=special>.</span><span class=identifier>id</span><span class=special>;}</span>
 200
 201   <span class=comment>// returns the length of the name field</span>
 202   <span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span> <span class=identifier>name_length</span><span class=special>()</span><span class=keyword>const</span><span class=special>{</span><span class=keyword>return</span> <span class=identifier>name</span><span class=special>.</span><span class=identifier>size</span><span class=special>();}</span>
 203 <span class=special>};</span>
 204
 205 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 206   <span class=identifier>employee</span><span class=special>,</span>
 207   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 208     <span class=comment>// sort by employee::operator&lt;</span>
 209     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 210
 211     <span class=comment>// sort by less&lt;string&gt; on name</span>
 212     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 213
 214     <span class=comment>// sort by less&lt;int&gt; on name_length()</span>
 215     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span>
 216       <span class=identifier>const_mem_fun</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name_length</span><span class=special>&gt;</span>
 217     <span class=special>&gt;</span>
 218   <span class=special>&gt;</span>
 219 <span class=special>&gt;</span> <span class=identifier>employee_set</span><span class=special>;</span>
 220 </pre></blockquote>
 221
 222 <p>
 223 <code>const_mem_fun</code> usage syntax is similar to that of
 224 <a href="#member"><code>member</code></a>:
 225 </p>
 226
 227 <blockquote><pre>
 228 <span class=identifier>const_mem_fun</span><span class=special>&lt;</span><span class=identifier><i>(base type)</i></span><span class=special>,</span><span class=identifier><i>(key type)</i></span><span class=special>,</span><span class=identifier><i>(pointer to member function)</i></span><span class=special>&gt;</span>
 229 </pre></blockquote>
 230
 231 <p>
 232 The member function referred to must be <code>const</code>, take no arguments and return
 233 a value of the specified key type.
 234 Almost always you will want to use a <code>const</code> member function,
 235 since elements in a <code>multi_index_container</code> are treated as constant, much
 236 as elements of an <code>std::set</code>. However, a
 237 <a href="../reference/key_extraction.html#mem_fun"><code>mem_fun</code></a>
 238 counterpart is provided for use with non-constant member functions, whose
 239 applicability is discussed on the paragraph on
 240 <a href="#advanced_key_extractors">advanced features
 241 of Boost.MultiIndex key extractors</a>.
 242 </p>
 243
 244 <p><a href="../examples.html#example2">Example 2</a> in the examples section
 245 provides a complete program showing how to use <code>const_mem_fun</code>.
 246 <p>
 247
 248 <h3><a name="global_fun"><code>global_fun</code></a></h3>
 249
 250 <p>
 251 Whereas <code>const_mem_fun</code> and <code>mem_fun</code> are based on a
 252 given member function of the base type from where the key is extracted,
 253 <a href="../reference/key_extraction.html#global_fun"><code>global_fun</code></a>
 254 takes a global function (or static member function) accepting the base
 255 type as its parameter and returning the key:
 256 </p>
 257
 258 <blockquote><pre>
 259 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index_container</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 260 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>ordered_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 261 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>global_fun</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 262
 263 <span class=keyword>struct</span> <span class=identifier>rectangle</span>
 264 <span class=special>{</span>
 265   <span class=keyword>int</span> <span class=identifier>x0</span><span class=special>,</span><span class=identifier>y0</span><span class=special>;</span>
 266   <span class=keyword>int</span> <span class=identifier>x1</span><span class=special>,</span><span class=identifier>y1</span><span class=special>;</span>
 267 <span class=special>};</span>
 268
 269 <span class=keyword>unsigned</span> <span class=keyword>long</span> <span class=identifier>area</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>rectangle</span><span class=special>&amp;</span> <span class=identifier>r</span><span class=special>)</span>
 270 <span class=special>{</span>
 271   <span class=keyword>return</span> <span class=special>(</span><span class=keyword>unsigned</span> <span class=keyword>long</span><span class=special>)(</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>x1</span><span class=special>-</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>x0</span><span class=special>)*(</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>x1</span><span class=special>-</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>x0</span><span class=special>)+</span>
 272          <span class=special>(</span><span class=keyword>unsigned</span> <span class=keyword>long</span><span class=special>)(</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>y1</span><span class=special>-</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>y0</span><span class=special>)*(</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>y1</span><span class=special>-</span><span class=identifier>r</span><span class=special>.</span><span class=identifier>y0</span><span class=special>);</span>
 273 <span class=special>}</span>
 274
 275 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 276   <span class=identifier>rectangle</span><span class=special>,</span>
 277   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 278     <span class=comment>// sort by increasing area</span>
 279     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>global_fun</span><span class=special>&lt;</span><span class=keyword>const</span> <span class=identifier>rectangle</span><span class=special>&amp;,</span><span class=keyword>unsigned</span> <span class=keyword>long</span><span class=special>,&amp;</span><span class=identifier>area</span><span class=special>&gt;</span> <span class=special>&gt;</span>
 280   <span class=special>&gt;</span>
 281 <span class=special>&gt;</span> <span class=identifier>rectangle_container</span><span class=special>;</span>
 282 </pre></blockquote>
 283
 284 <p>
 285 The specification of <code>global_fun</code> obeys the following syntax:
 286 </p>
 287
 288 <blockquote><pre>
 289 <span class=identifier>global_fun</span><span class=special>&lt;</span><span class=identifier><i>(argument type)</i></span><span class=special>,</span><span class=identifier><i>(key type)</i></span><span class=special>,</span><span class=identifier><i>(pointer to function)</i></span><span class=special>&gt;</span>
 290 </pre></blockquote>
 291
 292 <p>
 293 where the argument type and key type must match <i>exactly</i> those in the
 294 signature of the function used; for instance, in the example above the argument
 295 type is <code>const rectangle&amp;</code>, without omitting the "<code>const</code>"
 296 and "<code>&amp;</code>" parts. So, although most of the time the base type will be
 297 accepted by constant reference, <code>global_fun</code> is also prepared to take
 298 functions accepting their argument by value or by non-constant reference: this
 299 latter case cannot generally be used directly in the specification of
 300 <code>multi_index_container</code>s as their elements are treated as constant,
 301 but the section on <a href="#advanced_key_extractors">advanced features
 302 of Boost.MultiIndex key extractors</a> describes valid use cases of
 303 key extraction based on such functions with a non-constant reference argument.
 304 </p>
 305
 306 <p><a href="../examples.html#example2">Example 2</a> in the examples section
 307 uses <code>gobal_fun</code>.
 308 <p>
 309
 310 <h2><a name="user_defined_key_extractors">User-defined key extractors</a></h2>
 311
 312 <p>
 313 Although the <a href="#predefined_key_extractors">predefined key extractors</a>
 314 provided by Boost.MultiIndex are intended to serve most cases,
 315 the user can also provide her own key extractors in more exotic situations,
 316 as long as these conform to the
 317 <a href="../reference/key_extraction.html#key_extractors"><code>Key
 318 Extractor</code></a> concept.
 319 </p>
 320
 321 <blockquote><pre>
 322 <span class=comment>// some record class</span>
 323 <span class=keyword>struct</span> <span class=identifier>record</span>
 324 <span class=special>{</span>
 325   <span class=identifier>boost</span><span class=special>::</span><span class=identifier>gregorian</span><span class=special>::</span><span class=identifier>date</span> <span class=identifier>d</span><span class=special>;</span>
 326   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span>            <span class=identifier>str</span><span class=special>;</span>
 327 <span class=special>};</span>
 328
 329 <span class=comment>// extracts a record's year</span>
 330 <span class=keyword>struct</span> <span class=identifier>record_year</span>
 331 <span class=special>{</span>
 332   <span class=comment>// result_type typedef required by Key Extractor concept</span>
 333   <span class=keyword>typedef</span> <span class=identifier>boost</span><span class=special>::</span><span class=identifier>gregorian</span><span class=special>::</span><span class=identifier>greg_year</span> <span class=identifier>result_type</span><span class=special>;</span>
 334
 335   <span class=identifier>result_type</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>const</span> <span class=identifier>record</span><span class=special>&amp;</span> <span class=identifier>r</span><span class=special>)</span><span class=keyword>const</span> <span class=comment>// operator() must be const</span>
 336   <span class=special>{</span>
 337     <span class=keyword>return</span> <span class=identifier>r</span><span class=special>.</span><span class=identifier>d</span><span class=special>.</span><span class=identifier>year</span><span class=special>();</span>
 338   <span class=special>}</span>
 339 <span class=special>};</span>
 340
 341 <span class=comment>// example of use of the previous key extractor</span>
 342 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 343   <span class=identifier>record</span><span class=special>,</span>
 344   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 345     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>record_year</span><span class=special>&gt;</span> <span class=comment>// sorted by record's year</span>
 346   <span class=special>&gt;</span>
 347 <span class=special>&gt;</span> <span class=identifier>record_log</span><span class=special>;</span>
 348 </pre></blockquote>
 349
 350 <p>
 351 <a href="../examples.html#example6">Example 6</a> in the examples section
 352 applies some user-defined key extractors in a complex scenario where
 353 keys are accessed via pointers.
 354 </p>
 355
 356 <h2><a name="composite_keys">Composite keys</a></h2>
 357
 358 <p>
 359 In relational databases, composite keys depend on two or more fields of a given table.
 360 The analogous concept in Boost.MultiIndex is modeled by means of
 361 <a href="../reference/key_extraction.html#composite_key">
 362 <code>composite_key</code></a>, as shown in the example:
 363 </p>
 364
 365 <blockquote><pre>
 366 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index_container</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 367 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>ordered_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 368 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>member</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 369 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>composite_key</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 370
 371 <span class=keyword>struct</span> <span class=identifier>phonebook_entry</span>
 372 <span class=special>{</span>
 373   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>family_name</span><span class=special>;</span>
 374   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>given_name</span><span class=special>;</span>
 375   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>phone_number</span><span class=special>;</span>
 376
 377   <span class=identifier>phonebook_entry</span><span class=special>(</span>
 378     <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>family_name</span><span class=special>,</span>
 379     <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>given_name</span><span class=special>,</span>
 380     <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>phone_number</span><span class=special>):</span>
 381     <span class=identifier>family_name</span><span class=special>(</span><span class=identifier>family_name</span><span class=special>),</span><span class=identifier>given_name</span><span class=special>(</span><span class=identifier>given_name</span><span class=special>),</span><span class=identifier>phone_number</span><span class=special>(</span><span class=identifier>phone_number</span><span class=special>)</span>
 382   <span class=special>{}</span>
 383 <span class=special>};</span>
 384
 385 <span class=comment>// define a multi_index_container with a composite key on
 386 // (family_name,given_name)</span>
 387 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 388   <span class=identifier>phonebook_entry</span><span class=special>,</span>
 389   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 390     <span class=comment>//non-unique as some subscribers might have more than one number</span>
 391     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span>
 392       <span class=identifier>composite_key</span><span class=special>&lt;</span>
 393         <span class=identifier>phonebook_entry</span><span class=special>,</span>
 394         <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>phonebook_entry</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>family_name</span><span class=special>&gt;,</span>
 395         <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>phonebook_entry</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>given_name</span><span class=special>&gt;</span>
 396       <span class=special>&gt;</span>
 397     <span class=special>&gt;,</span>
 398     <span class=identifier>ordered_unique</span><span class=special>&lt;</span> <span class=comment>// unique as numbers belong to only one subscriber</span>
 399       <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>phonebook_entry</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>phone_number</span><span class=special>&gt;</span>
 400     <span class=special>&gt;</span>
 401   <span class=special>&gt;</span>
 402 <span class=special>&gt;</span> <span class=identifier>phonebook</span><span class=special>;</span>
 403 </pre></blockquote>
 404
 405 <p>
 406 <code>composite_key</code> accepts two or more key extractors on the same
 407 value (here, <code>phonebook_entry</code>). Lookup operations on a composite
 408 key are accomplished by passing tuples with the values searched:
 409 </p>
 410
 411 <blockquote><pre>
 412 <span class=identifier>phonebook</span> <span class=identifier>pb</span><span class=special>;</span>
 413 <span class=special>...</span>
 414 <span class=comment>// search for Dorothea White's number</span>
 415 <span class=identifier>phonebook</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>pb</span><span class=special>.</span><span class=identifier>find</span><span class=special>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>make_tuple</span><span class=special>(</span><span class=string>&quot;White&quot;</span><span class=special>,</span><span class=string>&quot;Dorothea&quot;</span><span class=special>));</span>
 416 <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>number</span><span class=special>=</span><span class=identifier>it</span><span class=special>-&gt;</span><span class=identifier>phone_number</span><span class=special>;</span>
 417 </pre></blockquote>
 418
 419 <p>
 420 Composite keys are sorted by lexicographical order, i.e. sorting is performed
 421 by the first key, then the second key if the first one is equal, etc. This
 422 order allows for partial searches where only the first keys are specified:
 423 </p>
 424
 425 <blockquote><pre>
 426 <span class=identifier>phonebook</span> <span class=identifier>pb</span><span class=special>;</span>
 427 <span class=special>...</span>
 428 <span class=comment>// look for all Whites</span>
 429 <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>phonebook</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>phonebook</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>&gt;</span> <span class=identifier>p</span><span class=special>=</span>
 430   <span class=identifier>pb</span><span class=special>.</span><span class=identifier>equal_range</span><span class=special>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>make_tuple</span><span class=special>(</span><span class=string>&quot;White&quot;</span><span class=special>));</span>
 431 </pre></blockquote>
 432
 433 <p>
 434 As a notational convenience, when only the first key is specified it is possible
 435 to pass the argument directly without including it into a tuple:
 436 </p>
 437
 438 <blockquote><pre>
 439 <span class=identifier>phonebook</span> <span class=identifier>pb</span><span class=special>;</span>
 440 <span class=special>...</span>
 441 <span class=comment>// look for all Whites</span>
 442 <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>phonebook</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>phonebook</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>&gt;</span> <span class=identifier>p</span><span class=special>=</span><span class=identifier>pb</span><span class=special>.</span><span class=identifier>equal_range</span><span class=special>(</span><span class=string>&quot;White&quot;</span><span class=special>);</span>
 443 </pre></blockquote>
 444
 445 <p>
 446 On the other hand, partial searches without specifying the first keys are not
 447 allowed.
 448 </p>
 449
 450 <p>
 451 By default, the corresponding <code>std::less</code> predicate is used
 452 for each subkey of a composite key. Alternate comparison predicates can
 453 be specified with <a href="../reference/key_extraction.html#composite_key_compare">
 454 <code>composite_key_compare</code></a>:
 455 </p>
 456
 457 <blockquote><pre>
 458 <span class=comment>// phonebook with given names in reverse order</span>
 459
 460 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 461   <span class=identifier>phonebook_entry</span><span class=special>,</span>
 462   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 463     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span>
 464       <span class=identifier>composite_key</span><span class=special>&lt;</span>
 465         <span class=identifier>phonebook_entry</span><span class=special>,</span>
 466         <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>phonebook_entry</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>family_name</span><span class=special>&gt;,</span>
 467         <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>phonebook_entry</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>given_name</span><span class=special>&gt;</span>
 468       <span class=special>&gt;,</span>
 469       <span class=identifier>composite_key_compare</span><span class=special>&lt;</span>
 470         <span class=identifier>std</span><span class=special>::</span><span class=identifier>less</span><span class=special>&lt;</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&gt;,</span>   <span class=comment>// family names sorted as by default</span>
 471         <span class=identifier>std</span><span class=special>::</span><span class=identifier>greater</span><span class=special>&lt;</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&gt;</span> <span class=comment>// given names reversed</span>
 472       <span class=special>&gt;</span>
 473     <span class=special>&gt;,</span>
 474     <span class=identifier>ordered_unique</span><span class=special>&lt;</span>
 475       <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>phonebook_entry</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>phone_number</span><span class=special>&gt;</span>
 476     <span class=special>&gt;</span>
 477   <span class=special>&gt;</span>
 478 <span class=special>&gt;</span> <span class=identifier>phonebook</span><span class=special>;</span>
 479 </pre></blockquote>
 480
 481 <p>
 482 See <a href="../examples.html#example7">example 7</a> in the examples section
 483 for an application of <code>composite_key</code>.
 484 </p>
 485
 486 <h3><a name="composite_keys_hash">Composite keys and hashed indices</a></h3>
 487
 488 <p>
 489 Composite keys can also be used with hashed indices in a straightforward manner:
 490 </p>
 491
 492 <blockquote><pre>
 493 <span class=keyword>struct</span> <span class=identifier>street_entry</span>
 494 <span class=special>{</span>
 495   <span class=comment>// quadrant coordinates</span>
 496   <span class=keyword>int</span> <span class=identifier>x</span><span class=special>;</span>
 497   <span class=keyword>int</span> <span class=identifier>y</span><span class=special>;</span>
 498
 499   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span>
 500
 501   <span class=identifier>street_entry</span><span class=special>(</span><span class=keyword>int</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>int</span> <span class=identifier>y</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&amp;</span> <span class=identifier>name</span><span class=special>):</span><span class=identifier>x</span><span class=special>(</span><span class=identifier>x</span><span class=special>),</span><span class=identifier>y</span><span class=special>(</span><span class=identifier>y</span><span class=special>),</span><span class=identifier>name</span><span class=special>(</span><span class=identifier>name</span><span class=special>){}</span>
 502 <span class=special>};</span>
 503
 504 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 505   <span class=identifier>street_entry</span><span class=special>,</span>
 506   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 507     <span class=identifier>hashed_non_unique</span><span class=special>&lt;</span> <span class=comment>// indexed by quadrant coordinates</span>
 508       <span class=identifier>composite_key</span><span class=special>&lt;</span>
 509         <span class=identifier>street_entry</span><span class=special>,</span>
 510         <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>street_entry</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&amp;</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>x</span><span class=special>&gt;,</span>
 511         <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>street_entry</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&amp;</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>y</span><span class=special>&gt;</span>
 512       <span class=special>&gt;</span>
 513     <span class=special>&gt;,</span>
 514     <span class=identifier>hashed_non_unique</span><span class=special>&lt;</span> <span class=comment>// indexed by street name</span>
 515       <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>street_entry</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span>
 516     <span class=special>&gt;</span>
 517   <span class=special>&gt;</span>
 518 <span class=special>&gt;</span> <span class=identifier>street_locator</span><span class=special>;</span>
 519
 520 <span class=identifier>street_locator</span> <span class=identifier>sl</span><span class=special>;</span>
 521 <span class=special>...</span>
 522 <span class=keyword>void</span> <span class=identifier>streets_in_quadrant</span><span class=special>(</span><span class=keyword>int</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>int</span> <span class=identifier>y</span><span class=special>)</span>
 523 <span class=special>{</span>
 524   <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>street_locator</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>street_locator</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>&gt;</span> <span class=identifier>p</span><span class=special>=</span>
 525     <span class=identifier>sl</span><span class=special>.</span><span class=identifier>equal_range</span><span class=special>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>make_tuple</span><span class=special>(</span><span class=identifier>x</span><span class=special>,</span><span class=identifier>y</span><span class=special>));</span>
 526
 527   <span class=keyword>while</span><span class=special>(</span><span class=identifier>p</span><span class=special>.</span><span class=identifier>first</span><span class=special>!=</span><span class=identifier>p</span><span class=special>.</span><span class=identifier>second</span><span class=special>){</span>
 528     <span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>&lt;&lt;</span><span class=identifier>p</span><span class=special>.</span><span class=identifier>first</span><span class=special>-&gt;</span><span class=identifier>name</span><span class=special>&lt;&lt;</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>endl</span><span class=special>;</span>
 529     <span class=special>++</span><span class=identifier>p</span><span class=special>.</span><span class=identifier>first</span><span class=special>;</span>
 530   <span class=special>}</span>
 531 <span class=special>}</span>
 532 </pre></blockquote>
 533
 534 <p>
 535 Note that hashing is automatically taken care of: <code>boost::hash</code> is
 536 specialized to hash a composite key as a function of the <code>boost::hash</code>
 537 values of its elements. Should we need to specify different hash functions for the
 538 elements of a composite key, we can explicitly do so by using the
 539 <a href="../reference/key_extraction.html#composite_key_hash"><code>composite_key_hash</code></a>
 540 utility:
 541 </p>
 542
 543 <blockquote><pre>
 544 <span class=keyword>struct</span> <span class=identifier>tuned_int_hash</span>
 545 <span class=special>{</span>
 546   <span class=keyword>int</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>int</span> <span class=identifier>x</span><span class=special>)</span><span class=keyword>const</span>
 547   <span class=special>{</span>
 548     <span class=comment>// specially tuned hash for this application</span>
 549   <span class=special>}</span>
 550 <span class=special>};</span>
 551
 552 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 553   <span class=identifier>street_entry</span><span class=special>,</span>
 554   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 555     <span class=identifier>hashed_non_unique</span><span class=special>&lt;</span> <span class=comment>// indexed by quadrant coordinates</span>
 556       <span class=identifier>composite_key</span><span class=special>&lt;</span>
 557         <span class=identifier>street_entry</span><span class=special>,</span>
 558         <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>street_entry</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&amp;</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>x</span><span class=special>&gt;,</span>
 559         <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>street_entry</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&amp;</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>y</span><span class=special>&gt;</span>
 560       <span class=special>&gt;,</span>
 561       <span class=identifier>composite_key_hash</span><span class=special>&lt;</span>
 562         <span class=identifier>tuned_int_hash</span><span class=special>,</span>
 563         <span class=identifier>tuned_int_hash</span>
 564       <span class=special>&gt;</span>
 565     <span class=special>&gt;,</span>
 566     <span class=identifier>hashed_non_unique</span><span class=special>&lt;</span> <span class=comment>// indexed by street name</span>
 567       <span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>street_entry</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span>
 568     <span class=special>&gt;</span>
 569   <span class=special>&gt;</span>
 570 <span class=special>&gt;</span> <span class=identifier>street_locator</span><span class=special>;</span>
 571 </pre></blockquote>
 572
 573 <p>
 574 Also, equality of composite keys can be tuned with
 575 <a href="../reference/key_extraction.html#composite_key_equal_to"><code>composite_key_equal_to</code></a>,
 576 though in most cases the default equality predicate (relying on
 577 the <code>std::equal_to</code> instantiations for the element types)
 578 will be the right choice.
 579 </p>
 580
 581 <p>
 582 Unlike with ordered indices, we cannot perform partial searches specifying
 583 only the first elements of a composite key:
 584 </p>
 585
 586 <blockquote><pre>
 587 <span class=comment>// try to locate streets in quadrants with x==0
 588 // compile-time error: hashed indices do not allow such operations</span>
 589 <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special>&lt;</span><span class=identifier>street_locator</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>street_locator</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>&gt;</span> <span class=identifier>p</span><span class=special>=</span>
 590   <span class=identifier>sl</span><span class=special>.</span><span class=identifier>equal_range</span><span class=special>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>make_tuple</span><span class=special>(</span><span class=number>0</span><span class=special>));</span>
 591 </pre></blockquote>
 592
 593 <p>
 594 The reason for this limitation is quite logical: as the hash value of a composite
 595 key depends on all of its elements, it is impossible to calculate it from
 596 partial information.
 597 </p>
 598
 599 <h2><a name="advanced_key_extractors">Advanced features of Boost.MultiIndex key
 600 extractors</a></h2>
 601
 602 <p>
 603 The <a href="../reference/key_extraction.html#key_extractors"><code>Key Extractor</code></a>
 604 concept allows the same object to extract keys from several different types,
 605 possibly through suitably defined overloads of <code>operator()</code>:
 606 </p>
 607
 608 <blockquote><pre>
 609 <span class=comment>// example of a name extractor from employee and employee *</span>
 610 <span class=keyword>struct</span> <span class=identifier>name_extractor</span>
 611 <span class=special>{</span>
 612   <span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>result_type</span><span class=special>;</span>
 613
 614   <span class=keyword>const</span> <span class=identifier>result_type</span><span class=special>&amp;</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>const</span> <span class=identifier>employee</span><span class=special>&amp;</span> <span class=identifier>e</span><span class=special>)</span><span class=keyword>const</span><span class=special>{</span><span class=keyword>return</span> <span class=identifier>e</span><span class=special>.</span><span class=identifier>name</span><span class=special>;}</span>
 615   <span class=identifier>result_type</span><span class=special>&amp;</span>       <span class=keyword>operator</span><span class=special>()(</span><span class=identifier>employee</span><span class=special>*</span> <span class=identifier>e</span><span class=special>)</span><span class=keyword>const</span><span class=special>{</span><span class=keyword>return</span> <span class=identifier>e</span><span class=special>-&gt;</span><span class=identifier>name</span><span class=special>;}</span>
 616 <span class=special>};</span>
 617
 618 <span class=comment>// name_extractor can handle elements of type employee...</span>
 619 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 620   <span class=identifier>employee</span><span class=special>,</span>
 621   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 622     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>name_extractor</span><span class=special>&gt;</span>
 623   <span class=special>&gt;</span>
 624 <span class=special>&gt;</span> <span class=identifier>employee_set</span><span class=special>;</span>
 625
 626 <span class=comment>// ...as well as elements of type employee *</span>
 627 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 628   <span class=identifier>employee</span><span class=special>*,</span>
 629   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 630     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>name_extractor</span><span class=special>&gt;</span>
 631   <span class=special>&gt;</span>
 632 <span class=special>&gt;</span> <span class=identifier>employee_ptr_set</span><span class=special>;</span>
 633 </pre></blockquote>
 634
 635 <p>
 636 This possibility is fully exploited by predefined key extractors provided
 637 by Boost.MultiIndex, making it simpler to define <code>multi_index_container</code>s
 638 where elements are pointers or references to the actual objects. The following
 639 specifies a <code>multi_index_container</code> of pointers to employees sorted by their
 640 names.
 641 </p>
 642
 643 <blockquote><pre>
 644 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 645   <span class=identifier>employee</span> <span class=special>*,</span>
 646   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 647     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span> <span class=special>&gt;</span> <span class=special>&gt;</span>
 648 <span class=special>&gt;</span> <span class=identifier>employee_set</span><span class=special>;</span>
 649 </pre></blockquote>
 650
 651 <p>
 652 Note that this is specified in exactly the same manner as a <code>multi_index_container</code>
 653 of actual <code>employee</code> objects: <code>member</code> takes care of the
 654 extra dereferencing needed to gain access to <code>employee::name</code>. A similar
 655 functionality is provided for interoperability with reference wrappers from
 656 <a href="../../../../doc/html/ref.html">Boost.Ref</a>:
 657 </p>
 658
 659 <blockquote><pre>
 660 <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 661   <span class=identifier>boost</span><span class=special>::</span><span class=identifier>reference_wrapper</span><span class=special>&lt;</span><span class=keyword>const</span> <span class=identifier>employee</span><span class=special>&gt;,</span>
 662   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 663     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>member</span><span class=special>&lt;</span><span class=identifier>employee</span><span class=special>,</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&amp;</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;</span> <span class=special>&gt;</span> <span class=special>&gt;</span>
 664 <span class=special>&gt;</span> <span class=identifier>employee_set</span><span class=special>;</span>
 665 </pre></blockquote>
 666
 667 <p>
 668 In fact, support for pointers is further extended to accept what we call
 669 <i>chained pointers</i>. Such a chained pointer is defined by induction as a raw or
 670 smart pointer or iterator to the actual element, to a reference wrapper of the
 671 element or <i>to another chained pointer</i>; that is, chained pointers are arbitrary
 672 compositions of pointer-like types ultimately dereferencing
 673 to the element from where the key is to be extracted. Examples of chained
 674 pointers to <code>employee</code> are:
 675 <ul>
 676   <li><code>employee *</code>,</li>
 677   <li><code>const employee *</code>,</li>
 678   <li><code>std::unique_ptr&lt;employee></code>,</li>
 679   <li><code>std::list&lt;boost::reference_wrapper&lt;employee> >::iterator</code>,</li>
 680   <li><code>employee **</code>,</li>
 681   <li><code>boost::shared_ptr&lt;const employee *></code>.</li>
 682 </ul>
 683 In general, chained pointers with dereferencing distance greater than 1 are not
 684 likely to be used in a normal program, but they can arise in frameworks
 685 which construct "views" as <code>multi_index_container</code>s from preexisting
 686 <code>multi_index_container</code>s.
 687 </p>
 688
 689 <p>
 690 In order to present a short summary of the different usages of Boost.MultiIndex
 691 key extractors in the presence of reference wrappers and pointers, consider the
 692 following final type:
 693 </p>
 694
 695 <blockquote><pre>
 696 <span class=keyword>struct</span> <span class=identifier>T</span>
 697 <span class=special>{</span>
 698   <span class=keyword>int</span>        <span class=identifier>i</span><span class=special>;</span>
 699   <span class=keyword>const</span> <span class=keyword>int</span>  <span class=identifier>j</span><span class=special>;</span>
 700   <span class=keyword>int</span>        <span class=identifier>f</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
 701   <span class=keyword>int</span>        <span class=identifier>g</span><span class=special>();</span>
 702   <span class=keyword>static</span> <span class=keyword>int</span> <span class=identifier>gf</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>T</span><span class=special>&amp;);</span>
 703   <span class=keyword>static</span> <span class=keyword>int</span> <span class=identifier>gg</span><span class=special>(</span><span class=identifier>T</span><span class=special>&amp;);</span>
 704 <span class=special>};</span>
 705 </pre></blockquote>
 706
 707 <p>
 708 The table below lists the appropriate key extractors to be used for
 709 different pointer and reference wrapper types based on <code>T</code>, for
 710 each of its members.
 711 </p>
 712
 713 <p align="center">
 714 <table cellspacing="0">
 715   <caption><b>Use cases for Boost.MultiIndex key extractors.</b></caption>
 716 <tr>
 717   <th>element type</th>
 718   <th>&nbsp;key&nbsp;</th>
 719   <th>key extractor</th>
 720   <th>applicable to<br><code>const</code> elements?</th>
 721   <th>read/write?</th>
 722 </tr>
 723 <tr>
 724   <td align="center" rowspan="6"><code>T</code></td>
 725   <td><code>i</code></td>
 726   <td><code>member&lt;T,int,&amp;T::i></code></td>
 727   <td align="center">yes</td>
 728   <td align="center">yes</td>
 729 </tr>
 730 <tr>
 731   <td><code>j</code></td>
 732   <td><code>member&lt;T,const int,&amp;T::j></code></td>
 733   <td align="center">yes</td>
 734   <td align="center">no</td>
 735 </tr>
 736 <tr>
 737   <td><code>f()</code></td>
 738   <td><code>const_mem_fun&lt;T,int,&amp;T::f></code></td>
 739   <td align="center">yes</td>
 740   <td align="center">no</td>
 741 </tr>
 742 <tr>
 743   <td><code>g()</code></td>
 744   <td><code>mem_fun&lt;T,int,&amp;T::g></code></td>
 745   <td align="center">no</td>
 746   <td align="center">no</td>
 747 </tr>
 748 <tr>
 749   <td><code>gf()</code></td>
 750   <td><code>global_fun&lt;const T&amp;,int,&amp;T::gf></code></td>
 751   <td align="center">yes</td>
 752   <td align="center">no</td>
 753 </tr>
 754 <tr>
 755   <td><code>gg()</code></td>
 756   <td><code>global_fun&lt;T&amp;,int,&amp;T::gg></code></td>
 757   <td align="center">no</td>
 758   <td align="center">no</td>
 759 </tr>
 760
 761 <tr class="odd_tr">
 762   <td align="center" rowspan="6"><code>reference_wrapper&lt;T></code></td>
 763   <td><code>i</code></td>
 764   <td><code>member&lt;T,int,&amp;T::i></code></td>
 765   <td align="center">yes</td>
 766   <td align="center">yes</td>
 767 </tr>
 768 <tr class="odd_tr">
 769   <td><code>j</code></td>
 770   <td><code>member&lt;T,const int,&amp;T::j></code></td>
 771   <td align="center">yes</td>
 772   <td align="center">no</td>
 773 </tr>
 774 <tr class="odd_tr">
 775   <td><code>f()</code></td>
 776   <td><code>const_mem_fun&lt;T,int,&amp;T::f></code></td>
 777   <td align="center">yes</td>
 778   <td align="center">no</td>
 779 </tr>
 780 <tr class="odd_tr">
 781   <td><code>g()</code></td>
 782   <td><code>mem_fun&lt;T,int,&amp;T::g></code></td>
 783   <td align="center">yes</td>
 784   <td align="center">no</td>
 785 </tr>
 786 <tr class="odd_tr">
 787   <td><code>gf()</code></td>
 788   <td><code>global_fun&lt;const T&amp;,int,&amp;T::gf></code></td>
 789   <td align="center">yes</td>
 790   <td align="center">no</td>
 791 </tr>
 792 <tr class="odd_tr">
 793   <td><code>gg()</code></td>
 794   <td><code>global_fun&lt;T&amp;,int,&amp;T::gg></code></td>
 795   <td align="center">yes</td>
 796   <td align="center">no</td>
 797 </tr>
 798
 799 <tr>
 800   <td align="center" rowspan="6"><code>reference_wrapper&lt;const T></code></td>
 801   <td><code>i</code></td>
 802   <td><code>member&lt;T,const int,&amp;T::i></code></td>
 803   <td align="center">yes</td>
 804   <td align="center">no</td>
 805 </tr>
 806 <tr>
 807   <td><code>j</code></td>
 808   <td><code>member&lt;T,const int,&amp;T::j></code></td>
 809   <td align="center">yes</td>
 810   <td align="center">no</td>
 811 </tr>
 812 <tr>
 813   <td><code>f()</code></td>
 814   <td><code>const_mem_fun&lt;T,int,&amp;T::f></code></td>
 815   <td align="center">yes</td>
 816   <td align="center">no</td>
 817 </tr>
 818 <tr>
 819   <td><code>g()</code></td>
 820   <td colspan="3">&nbsp;</td>
 821 </tr>
 822 <tr>
 823   <td><code>gf()</code></td>
 824   <td><code>global_fun&lt;const T&amp;,int,&amp;T::gf></code></td>
 825   <td align="center">yes</td>
 826   <td align="center">no</td>
 827 </tr>
 828 <tr>
 829   <td><code>gg()</code></td>
 830   <td colspan="3">&nbsp;</td>
 831 </tr>
 832
 833 <tr class="odd_tr">
 834   <td align="center" rowspan="6">chained pointer to <code>T</code><br>
 835     or to <code>reference_wrapper&lt;T></code></td>
 836   <td><code>i</code></td>
 837   <td><code>member&lt;T,int,&amp;T::i></code></td>
 838   <td align="center">yes</td>
 839   <td align="center">yes</td>
 840 </tr>
 841 <tr class="odd_tr">
 842   <td><code>j</code></td>
 843   <td><code>member&lt;T,const int,&amp;T::j></code></td>
 844   <td align="center">yes</td>
 845   <td align="center">no</td>
 846 </tr>
 847 <tr class="odd_tr">
 848   <td><code>f()</code></td>
 849   <td><code>const_mem_fun&lt;T,int,&amp;T::f></code></td>
 850   <td align="center">yes</td>
 851   <td align="center">no</td>
 852 </tr>
 853 <tr class="odd_tr">
 854   <td><code>g()</code></td>
 855   <td><code>mem_fun&lt;T,int,&amp;T::g></code></td>
 856   <td align="center">yes</td>
 857   <td align="center">no</td>
 858 </tr>
 859 <tr class="odd_tr">
 860   <td><code>gf()</code></td>
 861   <td><code>global_fun&lt;const T&amp;,int,&amp;T::gf></code></td>
 862   <td align="center">yes</td>
 863   <td align="center">no</td>
 864 </tr>
 865 <tr class="odd_tr">
 866   <td><code>gg()</code></td>
 867   <td><code>global_fun&lt;T&amp;,int,&amp;T::gg></code></td>
 868   <td align="center">yes</td>
 869   <td align="center">no</td>
 870 </tr>
 871
 872 <tr>
 873   <td align="center" rowspan="6">chained pointer to <code>const T</code><br>
 874     or to <code>reference_wrapper&lt;const T></code></td>
 875   <td><code>i</code></td>
 876   <td><code>member&lt;T,const int,&amp;T::i></code></td>
 877   <td align="center">yes</td>
 878   <td align="center">no</td>
 879 </tr>
 880 <tr>
 881   <td><code>j</code></td>
 882   <td><code>member&lt;T,const int,&amp;T::j></code></td>
 883   <td align="center">yes</td>
 884   <td align="center">no</td>
 885 </tr>
 886 <tr>
 887   <td><code>f()</code></td>
 888   <td><code>const_mem_fun&lt;T,int,&amp;T::f></code></td>
 889   <td align="center">yes</td>
 890   <td align="center">no</td>
 891 </tr>
 892 <tr>
 893   <td><code>g()</code></td>
 894   <td colspan="3">&nbsp;</td>
 895 </tr>
 896 <tr>
 897   <td><code>gf()</code></td>
 898   <td><code>global_fun&lt;const T&amp;,int,&amp;T::gf></code></td>
 899   <td align="center">yes</td>
 900   <td align="center">no</td>
 901 </tr>
 902 <tr>
 903   <td><code>gg()</code></td>
 904   <td colspan="3">&nbsp;</td>
 905 </tr>
 906
 907 </table>
 908 </p>
 909
 910 <p>
 911 The column "applicable to <code>const</code> elements?" states whether the
 912 corresponding key extractor can be used when passed constant elements (this
 913 relates to the elements specified in the first column, not the referenced
 914 <code>T</code> objects). The only negative cases are for <code>T::g</code> and
 915 <code>T:gg</code> when the elements are raw <code>T</code> objects, which make sense
 916 as we are dealing with a non-constant member function (<code>T::g</code>)
 917 and a function taking <code>T</code> by
 918 non-constant reference: this also implies that <code>multi_index_container</code>s
 919 of elements of <code>T</code> cannot be sorted by <code>T::g</code> or <code>T::gg</code>, because
 920 elements contained within a <code>multi_index_container</code> are treated as constant.
 921 </p>
 922
 923 <p>
 924 The column "read/write?" shows which combinations yield
 925 <a href="#read_write_key_extractors">read/write key extractors</a>.
 926 </p>
 927
 928 <p>
 929 Some care has to be taken to preserve <code>const</code>-correctness in the
 930 specification of <code>member</code> key extractors: in some sense, the <code>const</code>
 931 qualifier is carried along to the member part, even if that particular
 932 member is not defined as <code>const</code>. For instance, if the elements
 933 are of type <code>const T *</code>, sorting by <code>T::i</code> is <i>not</i>
 934 specified as <code>member&lt;const T,int,&amp;T::i></code>, but rather as
 935 <code>member&lt;T,const int,&amp;T::i></code>.
 936 </p>
 937
 938 <p>
 939 For practical demonstrations of use of these key extractors, refer to
 940 <a href="../examples.html#example2">example 2</a> and
 941 <a href="../examples.html#example6">example 6</a> in the examples section.
 942 </p>
 943
 944 <hr>
 945
 946 <div class="prev_link"><a href="indices.html"><img src="../prev.gif" alt="index types" border="0"><br>
 947 Index types
 948 </a></div>
 949 <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
 950 Boost.MultiIndex tutorial
 951 </a></div>
 952 <div class="next_link"><a href="creation.html"><img src="../next.gif" alt="container creation" border="0"><br>
 953 Container creation
 954 </a></div><br clear="all" style="clear: all;">
 955
 956 <br>
 957
 958 <p>Revised March 25th 2015</p>
 959
 960 <p>&copy; Copyright 2003-2015 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
 961 Distributed under the Boost Software
 962 License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
 963 LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
 964 http://www.boost.org/LICENSE_1_0.txt</a>)
 965 </p>
 966
 967 </body>
 968 </html>