12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139 |
- <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
- <html>
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
- <title>Boost.MultiIndex Documentation - Tutorial - Key extraction</title>
- <link rel="stylesheet" href="../style.css" type="text/css">
- <link rel="start" href="../index.html">
- <link rel="prev" href="indices.html">
- <link rel="up" href="index.html">
- <link rel="next" href="creation.html">
- </head>
- <body>
- <h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
- "middle" width="277" height="86">Boost.MultiIndex Tutorial: Key extraction</h1>
- <div class="prev_link"><a href="indices.html"><img src="../prev.gif" alt="index types" border="0"><br>
- Index types
- </a></div>
- <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
- Boost.MultiIndex tutorial
- </a></div>
- <div class="next_link"><a href="creation.html"><img src="../next.gif" alt="container creation" border="0"><br>
- Container creation
- </a></div><br clear="all" style="clear: all;">
- <hr>
- <h2>Contents</h2>
- <ul>
- <li><a href="#intro">Introduction</a>
- <ul>
- <li><a href="#read_write_key_extractors">Read/write key extractors</a></li>
- </ul>
- </li>
- <li><a href="#predefined_key_extractors">Predefined key extractors</a>
- <ul>
- <li><a href="#identity"><code>identity</code></a></li>
- <li><a href="#member"><code>member</code></a></li>
- <li><a href="#const_mem_fun"><code>const_mem_fun</code> and <code>mem_fun</code></a>
- <ul>
- <li><a href="#x_mem_fun">Variants for other types of member functions</a></li>
- </ul>
- </li>
- <li><a href="#global_fun"><code>global_fun</code></a></li>
- </ul>
- </li>
- <li><a href="#user_defined_key_extractors">User-defined key extractors</a></li>
- <li><a href="#composite_keys">Composite keys</a>
- <ul>
- <li><a href="#composite_keys_hash">Composite keys and hashed indices</a></li>
- </ul>
- </li>
- <li><a href="#key">C++17 terse key specification syntax</a></li>
- <li><a href="#advanced_key_extractors">Advanced features of Boost.MultiIndex key
- extractors</a></li>
- </ul>
- <h2><a name="intro">Introduction</a></h2>
- <p>
- STL associative containers have a notion of key, albeit in a somewhat incipient
- form. So, the keys of such containers are identified by a nested type
- <code>key_type</code>; for <code>std::set</code>s and <code>std::multiset</code>s,
- <code>key_type</code> coincides with <code>value_type</code>, i.e. the key is the
- element itself. <code>std::map</code> and <code>std::multimap</code> manage
- elements of type <code>std::pair<const Key,T></code>, where the first
- member is the key. In either case, the process of obtaining the key from a
- given element is implicitly fixed and cannot be customized by the user.
- </p>
- <p>
- Fixed key extraction mechanisms like those performed by STL associative
- containers do not scale well in the context of Boost.MultiIndex, where
- several indices share their <code>value_type</code> definition but
- might feature completely different lookup semantics. For this reason,
- Boost.MultiIndex formalizes the concept of a
- <a href="../reference/key_extraction.html#key_extractors"><code>Key
- Extractor</code></a> in order to make it explicit and controllable
- in the definition of key-based indices.
- </p>
- <p>
- Intuitively speaking, a key extractor is a function object that accepts
- a reference to an element and returns its associated key. The formal
- concept also imposes some reasonable constraints about the stability
- of the process, in the sense that extractors are assumed to
- return the same key when passed the same element: this is in consonance
- with the informal understanding that keys are actually some "part"
- of the element and do not depend on external data.
- </p>
- <h3><a name="read_write_key_extractors">Read/write key extractors</a></h3>
- <p>
- A key extractor is called <i>read/write</i> if it returns a non-constant reference
- to the key when passed a non-constant element, and it is called <i>read-only</i>
- otherwise. Boost.MultiIndex requires that the key extractor be read/write
- when using the <code>modify_key</code> member function of ordered and hashed
- indices. In all other situations, read-only extractors suffice.
- The section on <a href="#advanced_key_extractors">advanced features
- of Boost.MultiIndex key extractors</a> details which of the predefined
- key extractors are read/write.
- </p>
- <h2><a name="predefined_key_extractors">Predefined key extractors</a></h2>
- <h3><a name="identity"><code>identity</code></a></h3>
- <p>
- The <a href="../reference/key_extraction.html#identity"><code>identity</code></a>
- key extractor returns the entire base object as the associated key:
- </p>
- <blockquote><pre>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=keyword>int</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=identifier>ordered_unique</span><span class=special><</span>
- <span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=comment>// the key is the entire element</span>
- <span class=special>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>cont</span><span class=special>;</span>
- </pre></blockquote>
- <h3><a name="member"><code>member</code></a></h3>
- <p>
- <a href="../reference/key_extraction.html#member"><code>member</code></a>
- key extractors return a reference to a specified
- data field of the base object. For instance, in the following version of our
- familiar employee container:
- </p>
- <blockquote><pre>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>employee</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=identifier>employee</span><span class=special>></span> <span class=special>>,</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>></span> <span class=special>>,</span>
- <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>member</span><span class=special><</span><span class=identifier>employee</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>ssnumber</span><span class=special>></span> <span class=special>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- the second and third indices use <code>member</code> extractors on
- <code>employee::name</code> and <code>employee::ssnumber</code>, respectively.
- The specification of an instantiation of <code>member</code> is simple
- yet a little contrived:
- </p>
- <blockquote><pre>
- <span class=identifier>member</span><span class=special><</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>></span>
- </pre></blockquote>
- <p>
- It might seem that the first and second parameters are superfluous,
- since the type of the base object and of the associated data field are
- already implicit in the pointer to member argument: unfortunately, it is
- not possible to extract this information with current C++ mechanisms,
- which makes the syntax of <code>member</code> a little too verbose.
- </p>
- <h3><a name="const_mem_fun"><code>const_mem_fun</code> and <code>mem_fun</code></a></h3>
- <p>
- Sometimes, the key of an index is not a concrete data member of the element,
- but rather it is a value returned by a particular member function.
- This resembles the notion of <i>calculated indices</i> supported by some
- relational databases. Boost.MultiIndex supports this
- kind of key extraction through
- <a href="../reference/key_extraction.html#const_mem_fun"><code>const_mem_fun</code></a>.
- Consider the following container where sorting on the third index
- is based upon the length of the name field:
- </p>
- <blockquote><pre>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=keyword>struct</span> <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=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span>
- <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>&</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>
- <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special><(</span><span class=keyword>const</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>id</span><span class=special><</span><span class=identifier>e</span><span class=special>.</span><span class=identifier>id</span><span class=special>;}</span>
- <span class=comment>// returns the length of the name field</span>
- <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>
- <span class=special>};</span>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>employee</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=comment>// sort by employee::operator<</span>
- <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=identifier>employee</span><span class=special>></span> <span class=special>>,</span>
-
- <span class=comment>// sort by less<string> on name</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>></span> <span class=special>>,</span>
-
- <span class=comment>// sort by less<int> on name_length()</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span>
- <span class=identifier>const_mem_fun</span><span class=special><</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>,&</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name_length</span><span class=special>></span>
- <span class=special>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- <code>const_mem_fun</code> usage syntax is similar to that of
- <a href="#member"><code>member</code></a>:
- </p>
- <blockquote><pre>
- <span class=identifier>const_mem_fun</span><span class=special><</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>></span>
- </pre></blockquote>
- <p>
- The member function referred to must be <code>const</code>, take no arguments and return
- a value of the specified key type.
- Almost always you will want to use a <code>const</code> member function,
- since elements in a <code>multi_index_container</code> are treated as constant, much
- as elements of an <code>std::set</code>. However, a
- <a href="../reference/key_extraction.html#mem_fun"><code>mem_fun</code></a>
- counterpart is provided for use with non-constant member functions, whose
- applicability is discussed on the paragraph on
- <a href="#advanced_key_extractors">advanced features
- of Boost.MultiIndex key extractors</a>.
- </p>
- <p><a href="../examples.html#example2">Example 2</a> in the examples section
- provides a complete program showing how to use <code>const_mem_fun</code>.
- <p>
- <h4><a name="x_mem_fun">Variants for other types of member functions</a></h4>
- <p>
- Consider the following, non-compiling code:
- </p>
- <blockquote><pre>
- <span class=keyword>struct</span> <span class=identifier>employee</span>
- <span class=special>{</span>
- <span class=special>...</span>
- <span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span> <span class=identifier>salary</span><span class=special>()</span><span class=keyword>const</span><span class=special><b>&</b>;</span> <span class=comment>// note the &</span>
- <span class=special>};</span>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>employee</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=special>...</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span>
- <span class=comment>// compiler error: can't convert &employee::salary to
- // std::size_t (employee::*)() const</span>
- <span class=identifier><b>const_mem_fun</b></span><span class=special><</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>,&</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>salary</span><span class=special>></span>
- <span class=special>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- The problem here is that the type of <code>&employee::salary</code>, which is
- <a href="https://en.cppreference.com/w/cpp/language/member_functions#const-.2C_volatile-.2C_and_ref-qualified_member_functions">ref-qualified</a>,
- does not match exactly what <code>const_mem_fun</code> expects. Fortunately, Boost.MultiIndex
- provides a variant to fit:
- </p>
- <blockquote><pre>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>employee</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=special>...</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span>
- <span class=identifier><b>cref_mem_fun</b></span><span class=special><</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>,&</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>salary</span><span class=special>></span>
- <span class=special>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- This is the list of all available variants of <code>const_mem_fun</code> and
- <code>mem_fun</code>:
- </p>
- <p align="center">
- <table cellspacing="0">
- <caption><b>Variants of <code>const_mem_fun</code> and <code>mem_fun</code>.</b></caption>
- <tr>
- <th> Member function example </th>
- <th>Suitable extractor</th>
- <th>Behaves as</th>
- </tr>
- <tr>
- <td><code>int f()const volatile</code></td>
- <td><a href="../reference/key_extraction.html#cv_mem_fun"><code>cv_mem_fun</code></a><code><int,X,&X::f></code></td>
- <td align="center" rowspan="3"> <code>const_mem_fun</code> </td>
- </tr>
- <tr>
- <td><code>int f()const&</code></td>
- <td><a href="../reference/key_extraction.html#cv_mem_fun"><code>cref_mem_fun</code></a><code><int,X,&X::f></code></td>
- </tr>
- <tr>
- <td><code>int f()const volatile&</code></td>
- <td><a href="../reference/key_extraction.html#cv_mem_fun"><code>cvref_mem_fun</code></a><code><int,X,&X::f></code></td>
- </tr>
- <tr>
- <td><code>int f()volatile</code></td>
- <td><a href="../reference/key_extraction.html#volatile_mem_fun"><code>volatile_mem_fun</code></a><code><int,X,&X::f></code></td>
- <td align="center" rowspan="3"><code>mem_fun</code></td>
- </tr>
- <tr>
- <td><code>int f()&</code></td>
- <td><a href="../reference/key_extraction.html#volatile_mem_fun"><code>ref_mem_fun</code></a><code><int,X,&X::f></code></td>
- </tr>
- <tr>
- <td><code>int f()volatile&</code></td>
- <td><a href="../reference/key_extraction.html#volatile_mem_fun"><code>vref_mem_fun</code></a><code><int,X,&X::f></code></td>
- </tr>
- </table>
- </p>
- <h3><a name="global_fun"><code>global_fun</code></a></h3>
- <p>
- Whereas <code>const_mem_fun</code> and its variants are based on a
- given member function of the base type from where the key is extracted,
- <a href="../reference/key_extraction.html#global_fun"><code>global_fun</code></a>
- takes a global function (or static member function) accepting the base
- type as its parameter and returning the key:
- </p>
- <blockquote><pre>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=keyword>struct</span> <span class=identifier>rectangle</span>
- <span class=special>{</span>
- <span class=keyword>int</span> <span class=identifier>x0</span><span class=special>,</span><span class=identifier>y0</span><span class=special>;</span>
- <span class=keyword>int</span> <span class=identifier>x1</span><span class=special>,</span><span class=identifier>y1</span><span class=special>;</span>
- <span class=special>};</span>
- <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>&</span> <span class=identifier>r</span><span class=special>)</span>
- <span class=special>{</span>
- <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>
- <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>
- <span class=special>}</span>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>rectangle</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=comment>// sort by increasing area</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>global_fun</span><span class=special><</span><span class=keyword>const</span> <span class=identifier>rectangle</span><span class=special>&,</span><span class=keyword>unsigned</span> <span class=keyword>long</span><span class=special>,&</span><span class=identifier>area</span><span class=special>></span> <span class=special>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>rectangle_container</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- The specification of <code>global_fun</code> obeys the following syntax:
- </p>
- <blockquote><pre>
- <span class=identifier>global_fun</span><span class=special><</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>></span>
- </pre></blockquote>
- <p>
- where the argument type and key type must match <i>exactly</i> those in the
- signature of the function used; for instance, in the example above the argument
- type is <code>const rectangle&</code>, without omitting the "<code>const</code>"
- and "<code>&</code>" parts. So, although most of the time the base type will be
- accepted by constant reference, <code>global_fun</code> is also prepared to take
- functions accepting their argument by value or by non-constant reference: this
- latter case cannot generally be used directly in the specification of
- <code>multi_index_container</code>s as their elements are treated as constant,
- but the section on <a href="#advanced_key_extractors">advanced features
- of Boost.MultiIndex key extractors</a> describes valid use cases of
- key extraction based on such functions with a non-constant reference argument.
- </p>
- <p><a href="../examples.html#example2">Example 2</a> in the examples section
- uses <code>gobal_fun</code>.
- <p>
- <h2><a name="user_defined_key_extractors">User-defined key extractors</a></h2>
- <p>
- Although the <a href="#predefined_key_extractors">predefined key extractors</a>
- provided by Boost.MultiIndex are intended to serve most cases,
- the user can also provide her own key extractors in more exotic situations,
- as long as these conform to the
- <a href="../reference/key_extraction.html#key_extractors"><code>Key
- Extractor</code></a> concept.
- </p>
- <blockquote><pre>
- <span class=comment>// some record class</span>
- <span class=keyword>struct</span> <span class=identifier>record</span>
- <span class=special>{</span>
- <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>
- <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>str</span><span class=special>;</span>
- <span class=special>};</span>
- <span class=comment>// extracts a record's year</span>
- <span class=keyword>struct</span> <span class=identifier>record_year</span>
- <span class=special>{</span>
- <span class=comment>// result_type typedef required by Key Extractor concept</span>
- <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>
-
- <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>&</span> <span class=identifier>r</span><span class=special>)</span><span class=keyword>const</span> <span class=comment>// operator() must be const</span>
- <span class=special>{</span>
- <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>
- <span class=special>}</span>
- <span class=special>};</span>
- <span class=comment>// example of use of the previous key extractor</span>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>record</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>record_year</span><span class=special>></span> <span class=comment>// sorted by record's year</span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>record_log</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- <a href="../examples.html#example6">Example 6</a> in the examples section
- applies some user-defined key extractors in a complex scenario where
- keys are accessed via pointers.
- </p>
- <h2><a name="composite_keys">Composite keys</a></h2>
- <p>
- In relational databases, composite keys depend on two or more fields of a given table.
- The analogous concept in Boost.MultiIndex is modeled by means of
- <a href="../reference/key_extraction.html#composite_key">
- <code>composite_key</code></a>, as shown in the example:
- </p>
- <blockquote><pre>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=preprocessor>#include</span> <span class=special><</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>></span>
- <span class=keyword>struct</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=identifier>family_name</span><span class=special>;</span>
- <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>given_name</span><span class=special>;</span>
- <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>phone_number</span><span class=special>;</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=identifier>family_name</span><span class=special>,</span>
- <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>given_name</span><span class=special>,</span>
- <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>phone_number</span><span class=special>):</span>
- <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>
- <span class=special>{}</span>
- <span class=special>};</span>
- <span class=comment>// define a multi_index_container with a composite key on
- // (family_name,given_name)</span>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>phonebook_entry</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=comment>// non-unique as some subscribers might have more than one number</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span>
- <span class=identifier>composite_key</span><span class=special><</span>
- <span class=identifier>phonebook_entry</span><span class=special>,</span>
- <span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>family_name</span><span class=special>>,</span>
- <span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>given_name</span><span class=special>></span>
- <span class=special>></span>
- <span class=special>>,</span>
- <span class=identifier>ordered_unique</span><span class=special><</span> <span class=comment>// unique as numbers belong to only one subscriber</span>
- <span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>phone_number</span><span class=special>></span>
- <span class=special>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>phonebook</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- <code>composite_key</code> accepts two or more key extractors on the same
- value (here, <code>phonebook_entry</code>). Lookup operations on a composite
- key are accomplished by passing tuples with the values searched:
- </p>
- <blockquote><pre>
- <span class=identifier>phonebook</span> <span class=identifier>pb</span><span class=special>;</span>
- <span class=special>...</span>
- <span class=comment>// search for Dorothea White's number</span>
- <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>"White"</span><span class=special>,</span><span class=string>"Dorothea"</span><span class=special>));</span>
- <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>-></span><span class=identifier>phone_number</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- Composite keys are sorted by lexicographical order, i.e. sorting is performed
- by the first key, then the second key if the first one is equal, etc. This
- order allows for partial searches where only the first keys are specified:
- </p>
- <blockquote><pre>
- <span class=identifier>phonebook</span> <span class=identifier>pb</span><span class=special>;</span>
- <span class=special>...</span>
- <span class=comment>// look for all Whites</span>
- <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special><</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>></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=identifier>std</span><span class=special>::</span><span class=identifier>make_tuple</span><span class=special>(</span><span class=string>"White"</span><span class=special>));</span>
- </pre></blockquote>
- <p>
- As a notational convenience, when only the first key is specified it is possible
- to pass the argument directly without including it into a tuple:
- </p>
- <blockquote><pre>
- <span class=identifier>phonebook</span> <span class=identifier>pb</span><span class=special>;</span>
- <span class=special>...</span>
- <span class=comment>// look for all Whites</span>
- <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special><</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>></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>"White"</span><span class=special>);</span>
- </pre></blockquote>
- <p>
- On the other hand, partial searches without specifying the first keys are not
- allowed.
- </p>
- <p>
- By default, the corresponding <code>std::less</code> predicate is used
- for each subkey of a composite key. Alternate comparison predicates can
- be specified with <a href="../reference/key_extraction.html#composite_key_compare">
- <code>composite_key_compare</code></a>:
- </p>
- <blockquote><pre>
- <span class=comment>// phonebook with given names in reverse order</span>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>phonebook_entry</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span>
- <span class=identifier>composite_key</span><span class=special><</span>
- <span class=identifier>phonebook_entry</span><span class=special>,</span>
- <span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>family_name</span><span class=special>>,</span>
- <span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>given_name</span><span class=special>></span>
- <span class=special>>,</span>
- <span class=identifier>composite_key_compare</span><span class=special><</span>
- <span class=identifier>std</span><span class=special>::</span><span class=identifier>less</span><span class=special><</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>>,</span> <span class=comment>// family names sorted as by default</span>
- <span class=identifier>std</span><span class=special>::</span><span class=identifier>greater</span><span class=special><</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>></span> <span class=comment>// given names reversed</span>
- <span class=special>></span>
- <span class=special>>,</span>
- <span class=identifier>ordered_unique</span><span class=special><</span>
- <span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>phone_number</span><span class=special>></span>
- <span class=special>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>phonebook</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- See <a href="../examples.html#example7">example 7</a> in the examples section
- for an application of <code>composite_key</code>.
- </p>
- <h3><a name="composite_keys_hash">Composite keys and hashed indices</a></h3>
- <p>
- Composite keys can also be used with hashed indices in a straightforward manner:
- </p>
- <blockquote><pre>
- <span class=keyword>struct</span> <span class=identifier>street_entry</span>
- <span class=special>{</span>
- <span class=comment>// quadrant coordinates</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=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span>
- <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>&</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>
- <span class=special>};</span>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>street_entry</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=identifier>hashed_non_unique</span><span class=special><</span> <span class=comment>// indexed by quadrant coordinates</span>
- <span class=identifier>composite_key</span><span class=special><</span>
- <span class=identifier>street_entry</span><span class=special>,</span>
- <span class=identifier>member</span><span class=special><</span><span class=identifier>street_entry</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>x</span><span class=special>>,</span>
- <span class=identifier>member</span><span class=special><</span><span class=identifier>street_entry</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>y</span><span class=special>></span>
- <span class=special>></span>
- <span class=special>>,</span>
- <span class=identifier>hashed_non_unique</span><span class=special><</span> <span class=comment>// indexed by street name</span>
- <span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>name</span><span class=special>></span>
- <span class=special>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>street_locator</span><span class=special>;</span>
- <span class=identifier>street_locator</span> <span class=identifier>sl</span><span class=special>;</span>
- <span class=special>...</span>
- <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>
- <span class=special>{</span>
- <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special><</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>></span> <span class=identifier>p</span><span class=special>=</span>
- <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>
- <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>
- <span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</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>name</span><span class=special><<</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>endl</span><span class=special>;</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=special>}</span>
- <span class=special>}</span>
- </pre></blockquote>
- <p>
- Note that hashing is automatically taken care of: <code>boost::hash</code> is
- specialized to hash a composite key as a function of the <code>boost::hash</code>
- values of its elements. Should we need to specify different hash functions for the
- elements of a composite key, we can explicitly do so by using the
- <a href="../reference/key_extraction.html#composite_key_hash"><code>composite_key_hash</code></a>
- utility:
- </p>
- <blockquote><pre>
- <span class=keyword>struct</span> <span class=identifier>tuned_int_hash</span>
- <span class=special>{</span>
- <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>
- <span class=special>{</span>
- <span class=comment>// specially tuned hash for this application</span>
- <span class=special>}</span>
- <span class=special>};</span>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>street_entry</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=identifier>hashed_non_unique</span><span class=special><</span> <span class=comment>// indexed by quadrant coordinates</span>
- <span class=identifier>composite_key</span><span class=special><</span>
- <span class=identifier>street_entry</span><span class=special>,</span>
- <span class=identifier>member</span><span class=special><</span><span class=identifier>street_entry</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>x</span><span class=special>>,</span>
- <span class=identifier>member</span><span class=special><</span><span class=identifier>street_entry</span><span class=special>,</span><span class=keyword>int</span><span class=special>,&</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>y</span><span class=special>></span>
- <span class=special>>,</span>
- <span class=identifier>composite_key_hash</span><span class=special><</span>
- <span class=identifier>tuned_int_hash</span><span class=special>,</span>
- <span class=identifier>tuned_int_hash</span>
- <span class=special>></span>
- <span class=special>>,</span>
- <span class=identifier>hashed_non_unique</span><span class=special><</span> <span class=comment>// indexed by street name</span>
- <span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>street_entry</span><span class=special>::</span><span class=identifier>name</span><span class=special>></span>
- <span class=special>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>street_locator</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- Also, equality of composite keys can be tuned with
- <a href="../reference/key_extraction.html#composite_key_equal_to"><code>composite_key_equal_to</code></a>,
- though in most cases the default equality predicate (relying on
- the <code>std::equal_to</code> instantiations for the element types)
- will be the right choice.
- </p>
- <p>
- Unlike with ordered indices, we cannot perform partial searches specifying
- only the first elements of a composite key:
- </p>
- <blockquote><pre>
- <span class=comment>// try to locate streets in quadrants with x==0
- // compile-time error: hashed indices do not allow such operations</span>
- <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special><</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>></span> <span class=identifier>p</span><span class=special>=</span>
- <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>
- </pre></blockquote>
- <p>
- The reason for this limitation is quite logical: as the hash value of a composite
- key depends on all of its elements, it is impossible to calculate it from
- partial information.
- </p>
- <h2><a name="key">C++17 terse key specification syntax</a></h2>
- <p>
- C++17 introduces the declaration of <code>auto</code> template parameters, which can be
- taken advantage of to eliminate some redundancy in the specification of Boost.MultiIndex
- predefined key extractors. For instance, instead of the classical:
- </p>
- <blockquote><pre>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>employee</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=identifier>employee</span><span class=special>></span> <span class=special>>,</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>></span> <span class=special>>,</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span>
- <span class=identifier>const_mem_fun</span><span class=special><</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>,&</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name_length</span><span class=special>></span>
- <span class=special>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
- </pre></blockquote>
- one can now write:
- <blockquote><pre>
- <span class=preprocessor>#include</span> <span class=special><</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>multi_index</span><span class=special>/</span><span class=identifier>key</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>></span>
- <span class=special>...</span>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>employee</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=identifier>employee</span><span class=special>>>,</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier><b>key</b></span><span class=special><b><&</b></span><span class=identifier><b>employee</b></span><span class=special><b>::</b></span><span class=identifier><b>name</b></span><span class=special><b>></b>>,</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier><b>key</b></span><span class=special><b><&</b></span><span class=identifier><b>employee</b></span><span class=special><b>::</b></span><span class=identifier><b>name_length</b></span><span class=special><b>></b>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- which results in the exact same defined type, as
- <a href="../reference/key_extraction.html#key"><code>key</code></a> constructs are mere
- aliases for the old syntax. <code>key</code> can be used to shorten the specification of
- <a href="../reference/key_extraction.html#member"><code>member</code></a>,
- <a href="../reference/key_extraction.html#const_mem_fun"><code>const_mem_fun</code></a>
- (and <a href="../reference/key_extraction.html#cv_mem_fun">variants</a>),
- <a href="../reference/key_extraction.html#mem_fun"><code>mem_fun</code></a>
- (and <a href="../reference/key_extraction.html#volatile_mem_fun">variants</a>),
- <a href="../reference/key_extraction.html#global_fun"><code>global_fun</code></a>
- and, with additional terseness benefits,
- <a href="../reference/key_extraction.html#composite_key"><code>composite_key</code></a>:
- </p>
- <blockquote><pre>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>phonebook_entry</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=comment>// composite key on family name and given name</span>
- <span class=identifier>ordered_non_unique</span><span class=special><
- </span><span class=identifier><b>key</b></span><span class=special><b><&</b></span><span class=identifier><b>phonebook_entry</b></span><span class=special><b>::</b></span><span class=identifier><b>family_name</b></span><span class=special><b>,&</b></span><span class=identifier><b>phonebook_entry</b></span><span class=special><b>::</b></span><span class=identifier><b>given_name</b></span><span class=special><b>></b></span>
- <span class=special>>,</span>
- <span class=comment>// unique index on phone number</span>
- <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>key</span><span class=special><&</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>phone_number</span><span class=special>>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>phonebook</span><span class=special>;</span>
- </pre></blockquote>
- In this example, the first usage of <code>key</code> substitutes for the
- decidedly more cumbersome:
- <blockquote><pre>
- <span class=identifier>composite_key</span><span class=special><</span>
- <span class=identifier>phonebook_entry</span><span class=special>,</span>
- <span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>family_name</span><span class=special>>,</span>
- <span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>phonebook_entry</span><span class=special>::</span><span class=identifier>given_name</span><span class=special>></span>
- <span class=special>></span>
- </pre></blockquote>
- Note that we did not even have to specify the first <code>phonebook_entry</code>
- argument: the internal machinery of <code>key</code> automatically deduces it for
- us. Check the <a href="../reference/key_extraction.html#key_synopsis">reference</a>
- for technical details.
- <h2><a name="advanced_key_extractors">Advanced features of Boost.MultiIndex key
- extractors</a></h2>
- <p>
- The <a href="../reference/key_extraction.html#key_extractors"><code>Key Extractor</code></a>
- concept allows the same object to extract keys from several different types,
- possibly through suitably defined overloads of <code>operator()</code>:
- </p>
- <blockquote><pre>
- <span class=comment>// example of a name extractor from employee and employee *</span>
- <span class=keyword>struct</span> <span class=identifier>name_extractor</span>
- <span class=special>{</span>
- <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>
- <span class=keyword>const</span> <span class=identifier>result_type</span><span class=special>&</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>const</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>.</span><span class=identifier>name</span><span class=special>;}</span>
- <span class=identifier>result_type</span><span class=special>&</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>-></span><span class=identifier>name</span><span class=special>;}</span>
- <span class=special>};</span>
- <span class=comment>// name_extractor can handle elements of type employee...</span>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>employee</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>name_extractor</span><span class=special>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
- <span class=comment>// ...as well as elements of type employee *</span>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>employee</span><span class=special>*,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>name_extractor</span><span class=special>></span>
- <span class=special>></span>
- <span class=special>></span> <span class=identifier>employee_ptr_set</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- This possibility is fully exploited by predefined key extractors provided
- by Boost.MultiIndex, making it simpler to define <code>multi_index_container</code>s
- where elements are pointers or references to the actual objects. The following
- specifies a <code>multi_index_container</code> of pointers to employees sorted by their
- names.
- </p>
- <blockquote><pre>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>employee</span> <span class=special>*,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>></span> <span class=special>></span> <span class=special>></span>
- <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- Note that this is specified in exactly the same manner as a <code>multi_index_container</code>
- of actual <code>employee</code> objects: <code>member</code> takes care of the
- extra dereferencing needed to gain access to <code>employee::name</code>. A similar
- functionality is provided for interoperability with reference wrappers from
- <a href="../../../../doc/html/ref.html">Boost.Ref</a>:
- </p>
- <blockquote><pre>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=identifier>boost</span><span class=special>::</span><span class=identifier>reference_wrapper</span><span class=special><</span><span class=keyword>const</span> <span class=identifier>employee</span><span class=special>>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>member</span><span class=special><</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>,&</span><span class=identifier>employee</span><span class=special>::</span><span class=identifier>name</span><span class=special>></span> <span class=special>></span> <span class=special>></span>
- <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- In fact, support for pointers is further extended to accept what we call
- <i>chained pointers</i>. Such a chained pointer is defined by induction as a raw or
- smart pointer or iterator to the actual element, to a reference wrapper of the
- element or <i>to another chained pointer</i>; that is, chained pointers are arbitrary
- compositions of pointer-like types ultimately dereferencing
- to the element from where the key is to be extracted. Examples of chained
- pointers to <code>employee</code> are:
- <ul>
- <li><code>employee *</code>,</li>
- <li><code>const employee *</code>,</li>
- <li><code>std::unique_ptr<employee></code>,</li>
- <li><code>std::list<boost::reference_wrapper<employee> >::iterator</code>,</li>
- <li><code>employee **</code>,</li>
- <li><code>boost::shared_ptr<const employee *></code>.</li>
- </ul>
- In general, chained pointers with dereferencing distance greater than 1 are not
- likely to be used in a normal program, but they can arise in frameworks
- which construct "views" as <code>multi_index_container</code>s from preexisting
- <code>multi_index_container</code>s.
- </p>
- <p>
- In order to present a short summary of the different usages of Boost.MultiIndex
- key extractors in the presence of reference wrappers and pointers, consider the
- following final type:
- </p>
- <blockquote><pre>
- <span class=keyword>struct</span> <span class=identifier>T</span>
- <span class=special>{</span>
- <span class=keyword>int</span> <span class=identifier>i</span><span class=special>;</span>
- <span class=keyword>const</span> <span class=keyword>int</span> <span class=identifier>j</span><span class=special>;</span>
- <span class=keyword>int</span> <span class=identifier>f</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=keyword>int</span> <span class=identifier>g</span><span class=special>();</span>
- <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>&);</span>
- <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>&);</span>
- <span class=special>};</span>
- </pre></blockquote>
- <p>
- The table below lists the appropriate key extractors to be used for
- different pointer and reference wrapper types based on <code>T</code>, for
- each of its members.
- </p>
- <p align="center">
- <table cellspacing="0">
- <caption><b>Use cases for Boost.MultiIndex key extractors.</b></caption>
- <tr>
- <th>element type</th>
- <th> key </th>
- <th>key extractor</th>
- <th>applicable to<br><code>const</code> elements?</th>
- <th>read/write?</th>
- </tr>
- <tr>
- <td align="center" rowspan="6"><code>T</code></td>
- <td><code>i</code></td>
- <td><code>member<T,int,&T::i></code></td>
- <td align="center">yes</td>
- <td align="center">yes</td>
- </tr>
- <tr>
- <td><code>j</code></td>
- <td><code>member<T,const int,&T::j></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td><code>f()</code></td>
- <td><code>const_mem_fun<T,int,&T::f></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td><code>g()</code></td>
- <td><code>mem_fun<T,int,&T::g></code></td>
- <td align="center">no</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td><code>gf()</code></td>
- <td><code>global_fun<const T&,int,&T::gf></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td><code>gg()</code></td>
- <td><code>global_fun<T&,int,&T::gg></code></td>
- <td align="center">no</td>
- <td align="center">no</td>
- </tr>
- <tr class="odd_tr">
- <td align="center" rowspan="6"><code>reference_wrapper<T></code></td>
- <td><code>i</code></td>
- <td><code>member<T,int,&T::i></code></td>
- <td align="center">yes</td>
- <td align="center">yes</td>
- </tr>
- <tr class="odd_tr">
- <td><code>j</code></td>
- <td><code>member<T,const int,&T::j></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr class="odd_tr">
- <td><code>f()</code></td>
- <td><code>const_mem_fun<T,int,&T::f></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr class="odd_tr">
- <td><code>g()</code></td>
- <td><code>mem_fun<T,int,&T::g></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr class="odd_tr">
- <td><code>gf()</code></td>
- <td><code>global_fun<const T&,int,&T::gf></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr class="odd_tr">
- <td><code>gg()</code></td>
- <td><code>global_fun<T&,int,&T::gg></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td align="center" rowspan="6"><code>reference_wrapper<const T></code></td>
- <td><code>i</code></td>
- <td><code>member<T,const int,&T::i></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td><code>j</code></td>
- <td><code>member<T,const int,&T::j></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td><code>f()</code></td>
- <td><code>const_mem_fun<T,int,&T::f></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td><code>g()</code></td>
- <td colspan="3"> </td>
- </tr>
- <tr>
- <td><code>gf()</code></td>
- <td><code>global_fun<const T&,int,&T::gf></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td><code>gg()</code></td>
- <td colspan="3"> </td>
- </tr>
- <tr class="odd_tr">
- <td align="center" rowspan="6">chained pointer to <code>T</code><br>
- or to <code>reference_wrapper<T></code></td>
- <td><code>i</code></td>
- <td><code>member<T,int,&T::i></code></td>
- <td align="center">yes</td>
- <td align="center">yes</td>
- </tr>
- <tr class="odd_tr">
- <td><code>j</code></td>
- <td><code>member<T,const int,&T::j></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr class="odd_tr">
- <td><code>f()</code></td>
- <td><code>const_mem_fun<T,int,&T::f></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr class="odd_tr">
- <td><code>g()</code></td>
- <td><code>mem_fun<T,int,&T::g></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr class="odd_tr">
- <td><code>gf()</code></td>
- <td><code>global_fun<const T&,int,&T::gf></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr class="odd_tr">
- <td><code>gg()</code></td>
- <td><code>global_fun<T&,int,&T::gg></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td align="center" rowspan="6">chained pointer to <code>const T</code><br>
- or to <code>reference_wrapper<const T></code></td>
- <td><code>i</code></td>
- <td><code>member<T,const int,&T::i></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td><code>j</code></td>
- <td><code>member<T,const int,&T::j></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td><code>f()</code></td>
- <td><code>const_mem_fun<T,int,&T::f></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td><code>g()</code></td>
- <td colspan="3"> </td>
- </tr>
- <tr>
- <td><code>gf()</code></td>
- <td><code>global_fun<const T&,int,&T::gf></code></td>
- <td align="center">yes</td>
- <td align="center">no</td>
- </tr>
- <tr>
- <td><code>gg()</code></td>
- <td colspan="3"> </td>
- </tr>
- </table>
- </p>
- <p>
- The column "applicable to <code>const</code> elements?" states whether the
- corresponding key extractor can be used when passed constant elements (this
- relates to the elements specified in the first column, not the referenced
- <code>T</code> objects). The only negative cases are for <code>T::g</code> and
- <code>T:gg</code> when the elements are raw <code>T</code> objects, which make sense
- as we are dealing with a non-constant member function (<code>T::g</code>)
- and a function taking <code>T</code> by
- non-constant reference: this also implies that <code>multi_index_container</code>s
- of elements of <code>T</code> cannot be sorted by <code>T::g</code> or <code>T::gg</code>, because
- elements contained within a <code>multi_index_container</code> are treated as constant.
- </p>
- <p>
- The column "read/write?" shows which combinations yield
- <a href="#read_write_key_extractors">read/write key extractors</a>.
- </p>
- <p>
- Some care has to be taken to preserve <code>const</code>-correctness in the
- specification of <code>member</code> key extractors: in some sense, the <code>const</code>
- qualifier is carried along to the member part, even if that particular
- member is not defined as <code>const</code>. For instance, if the elements
- are of type <code>const T *</code>, sorting by <code>T::i</code> is <i>not</i>
- specified as <code>member<const T,int,&T::i></code>, but rather as
- <code>member<T,const int,&T::i></code>.
- </p>
- <p>
- For practical demonstrations of use of these key extractors, refer to
- <a href="../examples.html#example2">example 2</a> and
- <a href="../examples.html#example6">example 6</a> in the examples section.
- </p>
- <hr>
- <div class="prev_link"><a href="indices.html"><img src="../prev.gif" alt="index types" border="0"><br>
- Index types
- </a></div>
- <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex tutorial" border="0"><br>
- Boost.MultiIndex tutorial
- </a></div>
- <div class="next_link"><a href="creation.html"><img src="../next.gif" alt="container creation" border="0"><br>
- Container creation
- </a></div><br clear="all" style="clear: all;">
- <br>
- <p>Revised June 11th 2019</p>
- <p>© Copyright 2003-2019 Joaquín M López Muñoz.
- Distributed under the Boost Software
- License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
- LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
- http://www.boost.org/LICENSE_1_0.txt</a>)
- </p>
- </body>
- </html>
|