projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
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 - Basics</title> | |
| 7 | <link rel="stylesheet" href="../style.css" type="text/css"> | |
| 8 | <link rel="start" href="../index.html"> | |
| 9 | <link rel="prev" href="index.html"> | |
| 10 | <link rel="up" href="index.html"> | |
| 11 | <link rel="next" href="indices.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: Basics</h1> | |
| 17 | ||
| 18 | <div class="prev_link"><a href="index.html"><img src="../prev.gif" alt="Boost.MultiIndex tutorial" border="0"><br> | |
| 19 | Boost.MultiIndex tutorial | |
| 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="indices.html"><img src="../next.gif" alt="index types" border="0"><br> | |
| 25 | Index types | |
| 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="#multiple_sort">Multiple sorts on a single set</a></li> | |
| 36 | <li><a href="#list_fast_lookup">A bidirectional list with fast lookup</a></li> | |
| 37 | </ul> | |
| 38 | </li> | |
| 39 | <li><a href="#index_spec">Index specification</a></li> | |
| 40 | <li><a href="#tagging">Tagging</a></li> | |
| 41 | <li><a href="#iterator_access">Iterator access</a></li> | |
| 42 | <li><a href="#index_types">Index types</a> | |
| 43 | <ul> | |
| 44 | <li><a href="#ord_indices">Ordered indices</a> | |
| 45 | <ul> | |
| 46 | <li><a href="#unique_non_unique">Unique and non-unique variants</a></li> | |
| 47 | <li><a href="#ord_spec">Specification</a></li> | |
| 48 | <li><a href="#key_extraction">Key extraction</a></li> | |
| 49 | <li><a href="#comparison_predicates">Comparison predicates</a></li> | |
| 50 | <li><a href="#special_lookup">Special lookup operations</a></li> | |
| 51 | <li><a href="#range">Retrieval of ranges</a></li> | |
| 52 | <li><a href="#ord_updating">Updating</a></li> | |
| 53 | </ul> | |
| 54 | </li> | |
| 55 | <li><a href="#seq_indices">Sequenced indices</a> | |
| 56 | <ul> | |
| 57 | <li><a href="#seq_spec">Specification</a></li> | |
| 58 | <li><a href="#list_ops">List operations</a></li> | |
| 59 | <li><a href="#seq_updating">Updating</a></li> | |
| 60 | </ul> | |
| 61 | </li> | |
| 62 | </ul> | |
| 63 | </li> | |
| 64 | <li><a href="#projection">Projection of iterators</a></li> | |
| 65 | <li><a href="#complexity">Complexity and exception safety</a></li> | |
| 66 | </ul> | |
| 67 | ||
| 68 | <h2><a name="intro">Introduction</a></h2> | |
| 69 | ||
| 70 | <p> | |
| 71 | We introduce the main concepts of Boost.MultiIndex through the study of | |
| 72 | two typical use cases. | |
| 73 | </p> | |
| 74 | ||
| 75 | <h3><a name="multiple_sort">Multiple sorts on a single set</a></h3> | |
| 76 | ||
| 77 | <p> | |
| 78 | STL sets and multisets are varying-length containers where elements are efficiently | |
| 79 | sorted according to a given comparison predicate. These container classes fall short | |
| 80 | of functionality when the programmer wishes to efficiently sort and look up the elements | |
| 81 | following a different sorting criterion. Consider for instance: | |
| 82 | </p> | |
| 83 | ||
| 84 | <blockquote><pre> | |
| 85 | <span class=keyword>struct</span> <span class=identifier>employee</span> | |
| 86 | <span class=special>{</span> | |
| 87 | <span class=keyword>int</span> <span class=identifier>id</span><span class=special>;</span> | |
| 88 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span> | |
| 89 | ||
| 90 | <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> | |
| 91 | ||
| 92 | <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> | |
| 93 | <span class=special>};</span> | |
| 94 | </pre></blockquote> | |
| 95 | ||
| 96 | <p>The fact that IDs are unique to each employee is reflected by the way | |
| 97 | <code>operator<</code> is defined, so a natural data structure for storing of | |
| 98 | <code>employee</code>s is just a <code>std::set<employee></code>. Now, | |
| 99 | if one wishes to print out a listing of all employees in alphabetical order, available | |
| 100 | solutions may have disadvantages either in terms of storage space, complexity or ease | |
| 101 | of maintenance: | |
| 102 | <ul> | |
| 103 | <li>Copy the employee set into a vector or similar and sort this by a comparison | |
| 104 | functor dependent upon <code>employee::name</code>. | |
| 105 | <li>Keep a secondary data structure of pointers to the elements of the set, appropriately | |
| 106 | sorted by name. | |
| 107 | </ul> | |
| 108 | Of these, probably the second solution will be the one adopted by most programmers | |
| 109 | concerned about efficiency, but it imposes the annoying burden of keeping the two | |
| 110 | structures in sync. If the code is additionally required to be exception-safe, this | |
| 111 | construct easily becomes unmaintainable. | |
| 112 | </p> | |
| 113 | ||
| 114 | <p> | |
| 115 | Boost.MultiIndex features <a href="#ord_indices"><i>ordered indices</i></a>, which | |
| 116 | sort the elements according to a particular key, and are designed to help programmers | |
| 117 | in need of sequences of elements for which <i>more than one</i> sorting criteria are | |
| 118 | relevant. We do so by defining a <code>multi_index_container</code> | |
| 119 | instantiation composed of several ordered indices: each index, viewed in isolation, | |
| 120 | behaves much as an ordered <code>std::set</code> (or <code>std::multiset</code>), whilst | |
| 121 | the overall integrity of the entire data structure is preserved. Our example problem | |
| 122 | thus can be solved with Boost.MultiIndex as follows: | |
| 123 | </p> | |
| 124 | ||
| 125 | <blockquote><pre> | |
| 126 | <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> | |
| 127 | <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> | |
| 128 | <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> | |
| 129 | <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> | |
| 130 | ||
| 131 | <span class=comment>// define a multiply indexed set with indices by id and name</span> | |
| 132 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 133 | <span class=identifier>employee</span><span class=special>,</span> | |
| 134 | <span class=identifier>indexed_by</span><span class=special><</span> | |
| 135 | <span class=comment>// sort by employee::operator<</span> | |
| 136 | <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> | |
| 137 | ||
| 138 | <span class=comment>// sort by less<string> on name</span> | |
| 139 | <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> | |
| 140 | <span class=special>></span> | |
| 141 | <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span> | |
| 142 | ||
| 143 | <span class=keyword>void</span> <span class=identifier>print_out_by_name</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>employee_set</span><span class=special>&</span> <span class=identifier>es</span><span class=special>)</span> | |
| 144 | <span class=special>{</span> | |
| 145 | <span class=comment>// get a view to index #1 (name)</span> | |
| 146 | <span class=keyword>const</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>name_index</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=number>1</span><span class=special>>();</span> | |
| 147 | <span class=comment>// use name_index as a regular std::set</span> | |
| 148 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span> | |
| 149 | <span class=identifier>name_index</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>name_index</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span> | |
| 150 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>ostream_iterator</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>cout</span><span class=special>));</span> | |
| 151 | <span class=special>}</span> | |
| 152 | </pre></blockquote> | |
| 153 | ||
| 154 | <p> | |
| 155 | Instead of a single comparison predicate type, as it happens for STL associative | |
| 156 | containers, <code>multi_index_container</code> is passed a | |
| 157 | <a href="../reference/multi_index_container.html#multi_index_container">list</a> of index | |
| 158 | specifications (<code>indexed_by</code>), each one inducing the corresponding index. | |
| 159 | Indices are accessed via | |
| 160 | <a href="../reference/multi_index_container.html#index_retrieval"><code>get</code></a><code><N>()</code> | |
| 161 | where <i>N</i> ranges between 0 and the number of comparison | |
| 162 | predicates minus one. The functionality of index #0 can be accessed directly from a | |
| 163 | <code>multi_index_container</code> object without using <code>get<0>()</code>: for instance, | |
| 164 | <code>es.begin()</code> is equivalent to <code>es.get<0>().begin()</code>. | |
| 165 | </p> | |
| 166 | ||
| 167 | <p> | |
| 168 | Note that <code>get</code> returns a <i>reference</i> to the index, and not | |
| 169 | an index object. Indices cannot be constructed as separate objects from the | |
| 170 | container they belong to, so the following | |
| 171 | </p> | |
| 172 | ||
| 173 | <blockquote><pre> | |
| 174 | <span class=comment>// Wrong: we forgot the & after employee_set::nth_index<1>::type</span> | |
| 175 | <span class=keyword>const</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>name_index</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=number>1</span><span class=special>>();</span> | |
| 176 | </pre></blockquote> | |
| 177 | ||
| 178 | <p> | |
| 179 | does not compile, since it is trying to construct the index object | |
| 180 | <code>name_index</code>. This is a common source of errors in user code. | |
| 181 | </p> | |
| 182 | ||
| 183 | <h3><a name="list_fast_lookup">A bidirectional list with fast lookup</a></h3> | |
| 184 | ||
| 185 | <p> | |
| 186 | This study case allows us to introduce so-called | |
| 187 | <a href="#seq_indices"><i>sequenced indices</i></a>, and how they | |
| 188 | interact with ordered indices to construct powerful containers. Suppose | |
| 189 | we have a text parsed into words and stored in a list like this: | |
| 190 | </p> | |
| 191 | ||
| 192 | <blockquote><pre> | |
| 193 | <span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>list</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>text_container</span><span class=special>;</span> | |
| 194 | ||
| 195 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>text</span><span class=special>=</span> | |
| 196 | <span class=string>"Alice was beginning to get very tired of sitting by her sister on the "</span> | |
| 197 | <span class=string>"bank, and of having nothing to do: once or twice she had peeped into the "</span> | |
| 198 | <span class=string>"book her sister was reading, but it had no pictures or conversations in "</span> | |
| 199 | <span class=string>"it, 'and what is the use of a book,' thought Alice 'without pictures or "</span> | |
| 200 | <span class=string>"conversation?'"</span><span class=special>;</span> | |
| 201 | ||
| 202 | <span class=comment>// feed the text into the list</span> | |
| 203 | <span class=identifier>text_container</span> <span class=identifier>tc</span><span class=special>;</span> | |
| 204 | <span class=identifier>boost</span><span class=special>::</span><span class=identifier>tokenizer</span><span class=special><</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>char_separator</span><span class=special><</span><span class=keyword>char</span><span class=special>></span> <span class=special>></span> <span class=identifier>tok</span> | |
| 205 | <span class=special>(</span><span class=identifier>text</span><span class=special>,</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>char_separator</span><span class=special><</span><span class=keyword>char</span><span class=special>>(</span><span class=string>" \t\n.,;:!?'\"-"</span><span class=special>));</span> | |
| 206 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span><span class=identifier>tok</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>tok</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>back_inserter</span><span class=special>(</span><span class=identifier>tc</span><span class=special>));</span> | |
| 207 | </pre></blockquote> | |
| 208 | ||
| 209 | <p> | |
| 210 | If we want to count the occurrences of a given word into the text we will resort | |
| 211 | to <code>std::count</code>: | |
| 212 | </p> | |
| 213 | ||
| 214 | <blockquote><pre> | |
| 215 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span> <span class=identifier>occurrences</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>word</span><span class=special>)</span> | |
| 216 | <span class=special>{</span> | |
| 217 | <span class=keyword>return</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>count</span><span class=special>(</span><span class=identifier>tc</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>tc</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>word</span><span class=special>);</span> | |
| 218 | <span class=special>}</span> | |
| 219 | </pre></blockquote> | |
| 220 | ||
| 221 | <p> | |
| 222 | But this implementation of <code>occurrences</code> performs in linear time, which | |
| 223 | could be unacceptable for large quantities of text. Similarly, other operations like | |
| 224 | deletion of selected words are just too costly to carry out on a | |
| 225 | <code>std::list</code>: | |
| 226 | </p> | |
| 227 | ||
| 228 | <blockquote><pre> | |
| 229 | <span class=keyword>void</span> <span class=identifier>delete_word</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>word</span><span class=special>)</span> | |
| 230 | <span class=special>{</span> | |
| 231 | <span class=identifier>tc</span><span class=special>.</span><span class=identifier>remove</span><span class=special>(</span><span class=identifier>word</span><span class=special>);</span> <span class=comment>// scans the entire list looking for word</span> | |
| 232 | <span class=special>}</span> | |
| 233 | </pre></blockquote> | |
| 234 | ||
| 235 | <p> | |
| 236 | When performance is a concern, we will need an additional data structure that indexes | |
| 237 | the elements in <code>tc</code>, presumably in alphabetical order. Boost.MultiIndex | |
| 238 | does precisely this through the combination of sequenced and ordered indices: | |
| 239 | </p> | |
| 240 | ||
| 241 | <blockquote><pre> | |
| 242 | <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> | |
| 243 | <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>sequenced_index</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>></span> | |
| 244 | <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> | |
| 245 | <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> | |
| 246 | ||
| 247 | <span class=comment>// define a multi_index_container with a list-like index and an ordered index</span> | |
| 248 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 249 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,</span> | |
| 250 | <span class=identifier>indexed_by</span><span class=special><</span> | |
| 251 | <span class=identifier>sequenced</span><span class=special><>,</span> <span class=comment>// list-like index</span> | |
| 252 | <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>identity</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=special>></span> <span class=comment>// words by alphabetical order</span> | |
| 253 | <span class=special>></span> | |
| 254 | <span class=special>></span> <span class=identifier>text_container</span><span class=special>;</span> | |
| 255 | ||
| 256 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>text</span><span class=special>=...</span> | |
| 257 | ||
| 258 | <span class=comment>// feed the text into the list</span> | |
| 259 | <span class=identifier>text_container</span> <span class=identifier>tc</span><span class=special>;</span> | |
| 260 | <span class=identifier>boost</span><span class=special>::</span><span class=identifier>tokenizer</span><span class=special><</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>char_separator</span><span class=special><</span><span class=keyword>char</span><span class=special>></span> <span class=special>></span> <span class=identifier>tok</span> | |
| 261 | <span class=special>(</span><span class=identifier>text</span><span class=special>,</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>char_separator</span><span class=special><</span><span class=keyword>char</span><span class=special>>(</span><span class=string>" \t\n.,;:!?'\"-"</span><span class=special>));</span> | |
| 262 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span><span class=identifier>tok</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>tok</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>back_inserter</span><span class=special>(</span><span class=identifier>tc</span><span class=special>));</span> | |
| 263 | </pre></blockquote> | |
| 264 | ||
| 265 | <p> | |
| 266 | So far, the substitution of <code>multi_index_container</code> for <code>std::list</code> | |
| 267 | does not show any advantage. The code for inserting the text into the container | |
| 268 | does not change as sequenced indices provide an interface similar to that of | |
| 269 | <code>std::list</code> (no explicit access to this index through | |
| 270 | <code>get<0>()</code> is needed as <code>multi_index_container</code> inherits the | |
| 271 | functionality of index #0.) But the specification of an additional ordered index | |
| 272 | allows us to implement <code>occurrences</code> and <code>delete_word</code> | |
| 273 | in a much more efficient manner: | |
| 274 | </p> | |
| 275 | ||
| 276 | <blockquote><pre> | |
| 277 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>size_t</span> <span class=identifier>occurrences</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>word</span><span class=special>)</span> | |
| 278 | <span class=special>{</span> | |
| 279 | <span class=comment>// get a view to index #1</span> | |
| 280 | <span class=identifier>text_container</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>sorted_index</span><span class=special>=</span><span class=identifier>tc</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=number>1</span><span class=special>>();</span> | |
| 281 | ||
| 282 | <span class=comment>// use sorted_index as a regular std::set</span> | |
| 283 | <span class=keyword>return</span> <span class=identifier>sorted_index</span><span class=special>.</span><span class=identifier>count</span><span class=special>(</span><span class=identifier>word</span><span class=special>);</span> | |
| 284 | <span class=special>}</span> | |
| 285 | ||
| 286 | <span class=keyword>void</span> <span class=identifier>delete_word</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>word</span><span class=special>)</span> | |
| 287 | <span class=special>{</span> | |
| 288 | <span class=comment>// get a view to index #1</span> | |
| 289 | <span class=identifier>text_container</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>sorted_index</span><span class=special>=</span><span class=identifier>tc</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=number>1</span><span class=special>>();</span> | |
| 290 | ||
| 291 | <span class=comment>// use sorted_index as a regular std::set</span> | |
| 292 | <span class=identifier>sorted_index</span><span class=special>.</span><span class=identifier>erase</span><span class=special>(</span><span class=identifier>word</span><span class=special>);</span> | |
| 293 | <span class=special>}</span> | |
| 294 | </pre></blockquote> | |
| 295 | ||
| 296 | <p> | |
| 297 | Now, <code>occurrences</code> and <code>delete_word</code> have logarithmic | |
| 298 | complexity. The programmer can use index #0 for accessing the text as with | |
| 299 | <code>std::list</code>, and use index #1 when logarithmic lookup is needed. | |
| 300 | </p> | |
| 301 | ||
| 302 | <h2> | |
| 303 | <a name="index_spec">Index specification</a> | |
| 304 | </h2> | |
| 305 | ||
| 306 | <p> | |
| 307 | The indices of a <code>multi_index_container</code> instantiation are specified by | |
| 308 | means of the <a href="../reference/indices.html#indexed_by"> | |
| 309 | <code>indexed_by</code></a> construct. For instance, the instantiation | |
| 310 | </p> | |
| 311 | ||
| 312 | <blockquote><pre> | |
| 313 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 314 | <span class=identifier>employee</span><span class=special>,</span> | |
| 315 | <span class=identifier>indexed_by</span><span class=special><</span> | |
| 316 | <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> | |
| 317 | <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> | |
| 318 | <span class=special>></span> | |
| 319 | <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span> | |
| 320 | </pre></blockquote> | |
| 321 | ||
| 322 | <p> | |
| 323 | is comprised of a <a href="#unique_non_unique">unique ordered index</a> and a | |
| 324 | <a href="#unique_non_unique">non-unique ordered index</a>, while in | |
| 325 | </p> | |
| 326 | ||
| 327 | <blockquote><pre> | |
| 328 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 329 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,</span> | |
| 330 | <span class=identifier>indexed_by</span><span class=special><</span> | |
| 331 | <span class=identifier>sequenced</span><span class=special><>,</span> | |
| 332 | <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>identity</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=special>></span> | |
| 333 | <span class=special>></span> | |
| 334 | <span class=special>></span> <span class=identifier>text_container</span><span class=special>;</span> | |
| 335 | </pre></blockquote> | |
| 336 | ||
| 337 | <p> | |
| 338 | we specifiy two indices, the first of <a href="#seq_indices">sequenced type</a>, | |
| 339 | the second a non-unique <a href="#ord_indices">ordered index</a>. In general, we | |
| 340 | can specify an arbitrary number of indices: each of the arguments of | |
| 341 | <code>indexed_by</code> is called an | |
| 342 | <a href="../reference/indices.html#index_specification"><i>index specifier</i></a>. | |
| 343 | Depending on the type of index being specified, the corresponding specifier | |
| 344 | will need additional information: for instance, the specifiers <code>ordered_unique</code> | |
| 345 | and <code>ordered_non_unique</code> are provided with a | |
| 346 | <a href="#key_extraction">key extractor</a> and an optional | |
| 347 | <a href="#comparison_predicates">comparison predicate</a> which jointly indicate | |
| 348 | how the sorting of elements will be performed. | |
| 349 | </p> | |
| 350 | ||
| 351 | <p> | |
| 352 | A <code>multi_index_container</code> instantiation can be declared without supplying | |
| 353 | the <code>indexed_by</code> part: in this case, default index values are taken | |
| 354 | so that the resulting type is equivalent to a regular <code>std::set</code>. | |
| 355 | Concretely, the instantiation | |
| 356 | </p> | |
| 357 | ||
| 358 | <blockquote><pre> | |
| 359 | <span class=identifier>multi_index_container</span><span class=special><</span><i>(element)</i><span class=special>></span> | |
| 360 | </pre></blockquote> | |
| 361 | ||
| 362 | <p> | |
| 363 | is equivalent to | |
| 364 | </p> | |
| 365 | ||
| 366 | <blockquote><pre> | |
| 367 | <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 368 | <i>(element)</i><span class=special>,</span> | |
| 369 | <span class=identifier>indexed_by</span><span class=special><</span> | |
| 370 | <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><(</span><span class=identifier>element</span><span class=special>)></span> <span class=special>></span> | |
| 371 | <span class=special>></span> | |
| 372 | <span class=special>></span> | |
| 373 | </pre></blockquote> | |
| 374 | ||
| 375 | <h2><a name="tagging">Tagging</a></h2> | |
| 376 | ||
| 377 | <p> | |
| 378 | In order to retrieve (a reference to) an index of a given <code>multi_index_container</code>, | |
| 379 | the programmer must provide its order number, which is cumbersome and not very | |
| 380 | self-descriptive. Optionally, indices can be assigned <i>tags</i> (C++ types) that | |
| 381 | act as more convenient mnemonics. If provided, tags must be passed as the | |
| 382 | first parameter of the corresponding index specifier. The following is a revised version of | |
| 383 | <code>employee_set</code> with inclusion of tags: | |
| 384 | </p> | |
| 385 | ||
| 386 | <blockquote><pre> | |
| 387 | <span class=comment>// tags</span> | |
| 388 | <span class=keyword>struct</span> <span class=identifier>name</span><span class=special>{};</span> | |
| 389 | ||
| 390 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 391 | <span class=identifier>employee</span><span class=special>,</span> | |
| 392 | <span class=identifier>indexed_by</span><span class=special><</span> | |
| 393 | <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> | |
| 394 | <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>tag</span><span class=special><</span><span class=identifier>name</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> | |
| 395 | <span class=special>></span> | |
| 396 | <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span> | |
| 397 | </pre></blockquote> | |
| 398 | ||
| 399 | <p> | |
| 400 | Tags have to be passed inside the <a href="../reference/indices.html#tag"><code>tag</code></a> | |
| 401 | construct. Any type can be used as a tag for an index, although in general one will choose | |
| 402 | names that are descriptive of the index they are associated with. The tagging mechanism allows | |
| 403 | us to write expressions like</p> | |
| 404 | ||
| 405 | <blockquote><pre> | |
| 406 | <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span> | |
| 407 | <span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=identifier>name</span><span class=special>>().</span><span class=identifier>begin</span><span class=special>();</span> | |
| 408 | </pre></blockquote> | |
| 409 | ||
| 410 | <p> | |
| 411 | If no tag is provided for an index (as is the case for index #0 of the previous | |
| 412 | example), access to that index can only be performed by number. Note the existence | |
| 413 | of two different <code>typedef</code>s <code>nth_index</code> and | |
| 414 | <code>index</code> for referring to an index by number and by tag, respectively; | |
| 415 | for instance, | |
| 416 | <ul> | |
| 417 | <li><code>employee_set::nth_index<1>::type</code> is the type of | |
| 418 | index #1,</li> | |
| 419 | <li><code>employee_set::index<name>::type</code> is the type of the index | |
| 420 | tagged with <code>name</code> (the same index #1 in this case.)</li> | |
| 421 | </ul> | |
| 422 | <code>get()</code>, on the other hand, is overloaded to serve both styles of access: | |
| 423 | </p> | |
| 424 | ||
| 425 | <blockquote><pre> | |
| 426 | <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>name_index</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=identifier>name</span><span class=special>>();</span> | |
| 427 | <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>name_index2</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=number>1</span><span class=special>>();</span> <span class=comment>// same index</span> | |
| 428 | </pre></blockquote> | |
| 429 | ||
| 430 | <p> | |
| 431 | Additionally, the <code>tag</code> class template accepts several tags for one | |
| 432 | index, that we can use interchangeably: for instance, the specification of index #1 | |
| 433 | in the previous example can be rewritten to hold two different tags | |
| 434 | <code>name</code> and <code>by_name</code>: | |
| 435 | </p> | |
| 436 | ||
| 437 | <blockquote><pre> | |
| 438 | <span class=comment>// tags</span> | |
| 439 | <span class=keyword>struct</span> <span class=identifier>name</span><span class=special>{};</span> | |
| 440 | <span class=keyword>struct</span> <span class=identifier>by_name</span><span class=special>{};</span> | |
| 441 | ||
| 442 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 443 | <span class=special>...</span> | |
| 444 | <span class=identifier>ordered_non_unique</span><span class=special><</span> | |
| 445 | <span class=identifier>tag</span><span class=special><</span><span class=identifier>name</span><span class=special>,</span><span class=identifier>by_name</span><span class=special>>,</span> | |
| 446 | <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> | |
| 447 | <span class=special>></span> | |
| 448 | <span class=special>...</span> | |
| 449 | <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span> | |
| 450 | </pre></blockquote> | |
| 451 | ||
| 452 | <h2><a name="iterator_access">Iterator access</a></h2> | |
| 453 | ||
| 454 | <p> | |
| 455 | Each index of a <code>multi_index_container</code> uses its own | |
| 456 | iterator types, which are different from those of another indices. As is | |
| 457 | the rule with STL containers, these iterators are defined as nested | |
| 458 | types of the index: | |
| 459 | </p> | |
| 460 | ||
| 461 | <blockquote><pre> | |
| 462 | <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span> | |
| 463 | <span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=number>1</span><span class=special>>().</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Judy Smith"</span><span class=special>);</span> | |
| 464 | </pre></blockquote> | |
| 465 | ||
| 466 | <p> | |
| 467 | This kind of expressions can be rendered more readable by | |
| 468 | means of user-defined <code>typedef</code>s: | |
| 469 | </p> | |
| 470 | ||
| 471 | <blockquote><pre> | |
| 472 | <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span> | |
| 473 | <span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span> | |
| 474 | <span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=number>1</span><span class=special>>().</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Judy Smith"</span><span class=special>);</span> | |
| 475 | </pre></blockquote> | |
| 476 | ||
| 477 | <p> | |
| 478 | The iterators provided by every index are <i>constant</i>, that is, the elements they point to | |
| 479 | cannot be mutated directly. This follows the interface of <code>std::set</code> for ordered | |
| 480 | indices but might come as a surprise for other types such as sequenced indices, which are modeled after | |
| 481 | <code>std::list</code>, where this limitation does not happen. This seemingly odd behavior | |
| 482 | is imposed by the way <code>multi_index_container</code>s work; if elements were | |
| 483 | allowed to be mutated indiscriminately, we could introduce inconsistencies | |
| 484 | in the ordered indices of the <code>multi_index_container</code> without the container | |
| 485 | being notified about it. Element modification is properly done by means of | |
| 486 | <a href="#ord_updating">update operations</a> on any index. | |
| 487 | </p> | |
| 488 | ||
| 489 | <h2> | |
| 490 | <a name="index_types">Index types</a> | |
| 491 | </h2> | |
| 492 | ||
| 493 | <p> | |
| 494 | Currently, Boost.MultiIndex provides the following index types: | |
| 495 | <ul> | |
| 496 | <li>Ordered indices sort the elements like <code>std::set</code>s do and | |
| 497 | provide a similar interface. There are <i>unique</i> and <i>non-unique</i> | |
| 498 | variants: the former do not allow for duplicates, while the latter permit | |
| 499 | them (like <code>std::multiset</code>.)</li> | |
| 500 | <li>Ranked indices are a variation of ordered indices providing extra capabilities | |
| 501 | for querying and accessing elements based on their <i>rank</i> (the numerical position | |
| 502 | they occupy in the index). | |
| 503 | </li> | |
| 504 | <li>Sequenced indices are modeled after the semantics and interface of | |
| 505 | <code>std::list</code>: they arrange the elements as if in a bidirectional | |
| 506 | list.</li> | |
| 507 | <li>Hashed indices provide fast access to the elements through hashing | |
| 508 | techniques, in a similar way as non-standard <code>hash_set</code>s provided | |
| 509 | by some vendors. Recently, <i>unordered associative containers</i> have been | |
| 510 | proposed as part of an extension of the C++ standard library known | |
| 511 | in the standardization commitee as TR1. Hashed indices closely model this | |
| 512 | proposal.</li> | |
| 513 | <li>Random access indices provide an interface similar to that of | |
| 514 | sequenced indices, and additionally feature random access iterators | |
| 515 | and positional access to the elements.</li> | |
| 516 | </ul> | |
| 517 | The examples in the <a href="#intro">introduction</a> exercise ordered and sequenced | |
| 518 | indices, which are the most commonly used; the other kinds of indices are presented | |
| 519 | in the <a href="indices.html">index types</a> section of the tutorial. | |
| 520 | </p> | |
| 521 | ||
| 522 | <h3> | |
| 523 | <a name="ord_indices">Ordered indices</a> | |
| 524 | </h3> | |
| 525 | ||
| 526 | <p> | |
| 527 | Ordered indices sort the elements in a <code>multi_index_container</code> according | |
| 528 | to a specified key and an associated comparison predicate. These indices can | |
| 529 | be viewed as analogues of the standard container <code>std::set</code>, and in fact | |
| 530 | they do replicate its interface, albeit with some minor differences dictated | |
| 531 | by the general constraints of Boost.MultiIndex. | |
| 532 | </p> | |
| 533 | ||
| 534 | <h4> | |
| 535 | <a name="unique_non_unique">Unique and non-unique variants</a> | |
| 536 | </h4> | |
| 537 | ||
| 538 | <p> | |
| 539 | Ordered indices are classified into <i>unique</i>, which prohibit two | |
| 540 | elements to have the same key value, and <i>non-unique</i> indices, | |
| 541 | which allow for duplicates. Consider again the definition | |
| 542 | </p> | |
| 543 | ||
| 544 | <blockquote><pre> | |
| 545 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 546 | <span class=identifier>employee</span><span class=special>,</span> | |
| 547 | <span class=identifier>indexed_by</span><span class=special><</span> | |
| 548 | <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> | |
| 549 | <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> | |
| 550 | <span class=special>></span> | |
| 551 | <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span> | |
| 552 | </pre></blockquote> | |
| 553 | ||
| 554 | <p> | |
| 555 | In this instantiation of <code>multi_index_container</code>, the first index is to be | |
| 556 | treated as unique (since IDs are exclusive to each employee) and thus is declared using | |
| 557 | <code>ordered_unique</code>, whereas the second index is non-unique (as the possibility exists | |
| 558 | that say two John Smiths are hired in the same company), which is specified by the use | |
| 559 | of <code>ordered_non_unique</code>. | |
| 560 | </p> | |
| 561 | ||
| 562 | <p> | |
| 563 | The classification of ordered indices in unique and non-unique has an impact on which | |
| 564 | elements are allowed to be inserted into a given <code>multi_index_container</code>; briefly put, | |
| 565 | unique ordered indices mimic the behavior of <code>std::set</code>s while non-unique | |
| 566 | ordered indices are similar to <code>std::multiset</code>s. For instance, an | |
| 567 | <code>employee_set</code> can hold the objects <code>employee(0,"George Brown")</code> | |
| 568 | and <code>employee(1,"George Brown")</code>, but will not accept the insertion of an | |
| 569 | <code>employee</code> object whose ID coincides with that of some previously inserted | |
| 570 | employee. | |
| 571 | </p> | |
| 572 | ||
| 573 | <p> | |
| 574 | More than one unique index can be specified. For instance, if we augment | |
| 575 | <code>employee</code> to include an additional member for the Social Security number, | |
| 576 | which is reasonably treated as unique, the following captures this design: | |
| 577 | </p> | |
| 578 | ||
| 579 | <blockquote><pre> | |
| 580 | <span class=keyword>struct</span> <span class=identifier>employee</span> | |
| 581 | <span class=special>{</span> | |
| 582 | <span class=keyword>int</span> <span class=identifier>id</span><span class=special>;</span> | |
| 583 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span> | |
| 584 | <span class=keyword>int</span> <span class=identifier>ssnumber</span><span class=special>;</span> | |
| 585 | ||
| 586 | <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=keyword>int</span> <span class=identifier>ssnumber</span><span class=special>):</span> | |
| 587 | <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=identifier>ssnumber</span><span class=special>(</span><span class=identifier>ssnumber</span><span class=special>){}</span> | |
| 588 | ||
| 589 | <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> | |
| 590 | <span class=special>};</span> | |
| 591 | ||
| 592 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 593 | <span class=identifier>employee</span><span class=special>,</span> | |
| 594 | <span class=identifier>indexed_by</span><span class=special><</span> | |
| 595 | <span class=comment>// sort by employee::operator<</span> | |
| 596 | <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> | |
| 597 | ||
| 598 | <span class=comment>// sort by less<string> on name</span> | |
| 599 | <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> | |
| 600 | ||
| 601 | <span class=comment>// sort by less<int> on ssnumber</span> | |
| 602 | <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> | |
| 603 | <span class=special>></span> | |
| 604 | <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span> | |
| 605 | </pre></blockquote> | |
| 606 | ||
| 607 | <h4> | |
| 608 | <a name="ord_spec">Specification</a> | |
| 609 | </h4> | |
| 610 | ||
| 611 | <p> | |
| 612 | Ordered index specifiers in <code>indexed_by</code> must conform to one of the | |
| 613 | following syntaxes: | |
| 614 | </p> | |
| 615 | ||
| 616 | <blockquote><pre> | |
| 617 | <span class=special>(</span><span class=identifier>ordered_unique</span> <span class=special>|</span> <span class=identifier>ordered_non_unique</span><span class=special>) | |
| 618 | </span><span class=special><[</span><i>(tag)</i><span class=special>[,</span><i>(key extractor)</i><span class=special>[,</span><i>(comparison predicate)</i><span class=special>]]]></span> | |
| 619 | ||
| 620 | <span class=special>(</span><span class=identifier>ordered_unique</span> <span class=special>|</span> <span class=identifier>ordered_non_unique</span><span class=special>)</span> | |
| 621 | <span class=special><[</span><i>(key extractor)</i><span class=special>[,</span><i>(comparison predicate)</i><span class=special>]]></span> | |
| 622 | </pre></blockquote> | |
| 623 | ||
| 624 | <p> | |
| 625 | The first optional argument is used if <a href="#tagging">tags</a> are associated | |
| 626 | with the index. We now proceed to briefly discuss the remaining arguments | |
| 627 | of an ordered index specifier. | |
| 628 | </p> | |
| 629 | ||
| 630 | <h4> | |
| 631 | <a name="key_extraction">Key extraction</a> | |
| 632 | </h4> | |
| 633 | ||
| 634 | <p> | |
| 635 | The first template parameter (or the second, if tags are supplied) | |
| 636 | in the specification of an ordered index provides a <i>key extraction</i> predicate. | |
| 637 | This predicate takes a whole element (in our example, a reference to an | |
| 638 | <code>employee</code> object) and returns the piece of information by which | |
| 639 | the sorting is performed. In most cases, one of the following two situations arises: | |
| 640 | <ul> | |
| 641 | <li>The whole element serves as the key, as is the case of the first index | |
| 642 | in <code>employee_set</code>. The predefined | |
| 643 | <a href="key_extraction.html#identity"><code>identity</code></a> predicate | |
| 644 | can be used here as a key extractor; <code>identity</code> returns as the key the | |
| 645 | same object passed as argument.</li> | |
| 646 | <li>The comparison is performed on a particular data member of the element; this | |
| 647 | closely follows the specification of indices on a column of a table in relational | |
| 648 | databases. Boost.MultiIndex provides | |
| 649 | <a href="key_extraction.html#member"><code>member</code></a>, which returns | |
| 650 | as the key a member of the element specified by a given pointer.</li> | |
| 651 | </ul> | |
| 652 | As an example, consider again the definition of <code>employee_set</code>. The | |
| 653 | definition of the first index: | |
| 654 | </p> | |
| 655 | ||
| 656 | <blockquote><pre> | |
| 657 | <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> | |
| 658 | </pre></blockquote> | |
| 659 | ||
| 660 | <p> | |
| 661 | specifies by means of <code>identity</code> that <code>element</code> | |
| 662 | objects themselves serve as key for this index. On the other hand, in the second | |
| 663 | index: | |
| 664 | </p> | |
| 665 | ||
| 666 | <blockquote><pre> | |
| 667 | <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> | |
| 668 | </pre></blockquote> | |
| 669 | ||
| 670 | <p> | |
| 671 | we use <code>member</code> to extract the <code>name</code> part of the | |
| 672 | <code>employee</code> object. The key type of this index is then | |
| 673 | <code>std::string</code>. | |
| 674 | </p> | |
| 675 | ||
| 676 | <p> | |
| 677 | Apart from <code>identity</code> and <code>member</code>, Boost.MultiIndex provides | |
| 678 | several other predefined key extractors and powerful ways to combine them. | |
| 679 | Key extractors can also be defined by the user. | |
| 680 | Consult the <a href="key_extraction.html">key extraction section</a> of | |
| 681 | the tutorial for a more detailed exposition of this topic. | |
| 682 | </p> | |
| 683 | ||
| 684 | <h4><a name="comparison_predicates">Comparison predicates</a></h4> | |
| 685 | ||
| 686 | <p> | |
| 687 | The last part of the specification of an ordered index is the associated | |
| 688 | <i>comparison predicate</i>, which must order the keys in a less-than fashion. | |
| 689 | These comparison predicates are not different from those used by STL containers like | |
| 690 | <code>std::set</code>. By default (i.e. if no comparison predicate is provided), | |
| 691 | an index with keys of type <code>key_type</code> sorts the elements by | |
| 692 | <code>std::less<key_type></code>. Should other comparison criteria be needed, | |
| 693 | they can be specified as an additional parameter in the index declaration: | |
| 694 | </p> | |
| 695 | ||
| 696 | <blockquote><pre> | |
| 697 | <span class=comment>// define a multiply indexed set with indices by id and by name | |
| 698 | // in reverse alphabetical order</span> | |
| 699 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 700 | <span class=identifier>employee</span><span class=special>,</span> | |
| 701 | <span class=identifier>indexed_by</span><span class=special><</span> | |
| 702 | <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>// as usual</span> | |
| 703 | <span class=identifier>ordered_non_unique</span><span class=special><</span> | |
| 704 | <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> | |
| 705 | <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>// default would be std::less<std::string></span> | |
| 706 | <span class=special>></span> | |
| 707 | <span class=special>></span> | |
| 708 | <span class=special>></span> <span class=identifier>employee_set</span><span class=special>;</span> | |
| 709 | </pre></blockquote> | |
| 710 | ||
| 711 | <h4><a name="special_lookup">Special lookup operations</a></h4> | |
| 712 | ||
| 713 | <p> | |
| 714 | A given ordered index allows for lookup based on its key type, rather than the | |
| 715 | whole element. For instance, to find Veronica Cruz in an | |
| 716 | <code>employee_set</code> one would write: | |
| 717 | </p> | |
| 718 | ||
| 719 | <blockquote><pre> | |
| 720 | <span class=identifier>employee_set</span> <span class=identifier>es</span><span class=special>;</span> | |
| 721 | <span class=special>...</span> | |
| 722 | <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span> | |
| 723 | <span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=identifier>name</span><span class=special>>().</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Veronica Cruz"</span><span class=special>);</span> | |
| 724 | </pre></blockquote> | |
| 725 | ||
| 726 | <p>As a plus, Boost.MultiIndex provides lookup operations accepting search keys | |
| 727 | different from the <code>key_type</code> of the index, which is a specially useful | |
| 728 | facility when <code>key_type</code> objects are expensive to create. Ordered STL containers | |
| 729 | fail to provide this functionality, which often leads to inelegant workarounds: consider for | |
| 730 | instance the problem of determining the employees whose IDs fall in the range [0,100]. Given | |
| 731 | that the key of <code>employee_set</code> index #0 | |
| 732 | is <code>employee</code> itself, on a first approach one would write the following: | |
| 733 | </p> | |
| 734 | ||
| 735 | <blockquote><pre> | |
| 736 | <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>p0</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>lower_bound</span><span class=special>(</span><span class=identifier>employee</span><span class=special>(</span><span class=number>0</span><span class=special>,</span><span class=string>""</span><span class=special>));</span> | |
| 737 | <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>p1</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>upper_bound</span><span class=special>(</span><span class=identifier>employee</span><span class=special>(</span><span class=number>100</span><span class=special>,</span><span class=string>""</span><span class=special>));</span> | |
| 738 | </pre></blockquote> | |
| 739 | ||
| 740 | <p> | |
| 741 | Note however that <code>std::less<employee></code> actually only depends | |
| 742 | on the IDs of the employees, so it would be more convenient to avoid | |
| 743 | the creation of entire <code>employee</code> objects just for the sake of | |
| 744 | their IDs. Boost.MultiIndex allows for this: define an appropriate | |
| 745 | comparison predicate | |
| 746 | </p> | |
| 747 | ||
| 748 | <blockquote><pre> | |
| 749 | <span class=keyword>struct</span> <span class=identifier>comp_id</span> | |
| 750 | <span class=special>{</span> | |
| 751 | <span class=comment>// compare an ID and an employee</span> | |
| 752 | <span class=keyword>bool</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=identifier>employee</span><span class=special>&</span> <span class=identifier>e2</span><span class=special>)</span><span class=keyword>const</span><span class=special>{</span><span class=keyword>return</span> <span class=identifier>x</span><span class=special><</span><span class=identifier>e2</span><span class=special>.</span><span class=identifier>id</span><span class=special>;}</span> | |
| 753 | ||
| 754 | <span class=comment>// compare an employee and an ID</span> | |
| 755 | <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>e1</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=keyword>return</span> <span class=identifier>e1</span><span class=special>.</span><span class=identifier>id</span><span class=special><</span><span class=identifier>x</span><span class=special>;}</span> | |
| 756 | <span class=special>};</span> | |
| 757 | </pre></blockquote> | |
| 758 | ||
| 759 | <p>and now write the search as</p> | |
| 760 | ||
| 761 | <blockquote><pre> | |
| 762 | <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>p0</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>lower_bound</span><span class=special>(</span><span class=number>0</span><span class=special>,</span><span class=identifier>comp_id</span><span class=special>());</span> | |
| 763 | <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>p1</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>upper_bound</span><span class=special>(</span><span class=number>100</span><span class=special>,</span><span class=identifier>comp_id</span><span class=special>());</span> | |
| 764 | </pre></blockquote> | |
| 765 | ||
| 766 | <p> | |
| 767 | Here we are not only passing IDs instead of <code>employee</code> objects: | |
| 768 | an alternative comparison predicate is passed as well. In general, lookup operations | |
| 769 | of ordered indices are overloaded to accept | |
| 770 | <a href="../reference/ord_indices.html#set_operations"><i>compatible sorting | |
| 771 | criteria</i></a>. The somewhat cumbersone definition of compatibility in this context | |
| 772 | is given in the reference, but roughly speaking we say that a comparison predicate | |
| 773 | <code>C1</code> is compatible with <code>C2</code> if any sequence sorted by | |
| 774 | <code>C2</code> is also sorted with respect to <code>C1</code>. | |
| 775 | The following shows a more interesting use of compatible predicates: | |
| 776 | </p> | |
| 777 | ||
| 778 | <blockquote><pre> | |
| 779 | <span class=comment>// sorting by name's initial</span> | |
| 780 | <span class=keyword>struct</span> <span class=identifier>comp_initial</span> | |
| 781 | <span class=special>{</span> | |
| 782 | <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>char</span> <span class=identifier>ch</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>s</span><span class=special>)</span><span class=keyword>const</span><span class=special>{</span> | |
| 783 | <span class=keyword>if</span><span class=special>(</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>empty</span><span class=special>())</span><span class=keyword>return</span> <span class=keyword>false</span><span class=special>;</span> | |
| 784 | <span class=keyword>return</span> <span class=identifier>ch</span><span class=special><</span><span class=identifier>s</span><span class=special>[</span><span class=number>0</span><span class=special>];</span> | |
| 785 | <span class=special>}</span> | |
| 786 | ||
| 787 | <span class=keyword>bool</span> <span class=keyword>operator</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>s</span><span class=special>,</span><span class=keyword>char</span> <span class=identifier>ch</span><span class=special>)</span><span class=keyword>const</span><span class=special>{</span> | |
| 788 | <span class=keyword>if</span><span class=special>(</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>empty</span><span class=special>())</span><span class=keyword>return</span> <span class=keyword>true</span><span class=special>;</span> | |
| 789 | <span class=keyword>return</span> <span class=identifier>s</span><span class=special>[</span><span class=number>0</span><span class=special>]<</span><span class=identifier>ch</span><span class=special>;</span> | |
| 790 | <span class=special>}</span> | |
| 791 | <span class=special>};</span> | |
| 792 | ||
| 793 | <span class=comment>// obtain first employee whose name begins with 'J' (ordered by name)</span> | |
| 794 | <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span> | |
| 795 | <span class=identifier>employee_set_by_name</span><span class=special>&</span> <span class=identifier>name_index</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=identifier>name</span><span class=special>>();</span> | |
| 796 | <span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>const_iterator</span> <span class=identifier>it</span><span class=special>=</span> | |
| 797 | <span class=identifier>name_index</span><span class=special>.</span><span class=identifier>lower_bound</span><span class=special>(</span><span class=literal>'J'</span><span class=special>,</span><span class=identifier>comp_initial</span><span class=special>());</span> | |
| 798 | </pre></blockquote> | |
| 799 | ||
| 800 | <h4><a name="range">Retrieval of ranges</a></h4> | |
| 801 | ||
| 802 | <p> | |
| 803 | Range searching, i.e. the lookup of all elements in a given interval, is a very | |
| 804 | frequent operation for which standard <code>lower_bound</code> and | |
| 805 | <code>upper_bound</code> can be resorted to, though in a cumbersome manner. | |
| 806 | For instance, the following code retrieves the elements of an | |
| 807 | <code>multi_index_container<double></code> in the interval [100,200]: | |
| 808 | </p> | |
| 809 | ||
| 810 | <blockquote><pre> | |
| 811 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span><span class=keyword>double</span><span class=special>></span> <span class=identifier>double_set</span><span class=special>;</span> | |
| 812 | <span class=comment>// note: default template parameters resolve to | |
| 813 | // multi_index_container<double,indexed_by<unique<identity<double> > > >.</span> | |
| 814 | ||
| 815 | <span class=identifier>double_set</span> <span class=identifier>s</span><span class=special>;</span> | |
| 816 | <span class=special>...</span> | |
| 817 | <span class=identifier>double_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it0</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>lower_bound</span><span class=special>(</span><span class=number>100.0</span><span class=special>);</span> | |
| 818 | <span class=identifier>double_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it1</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>upper_bound</span><span class=special>(</span><span class=number>200.0</span><span class=special>);</span> | |
| 819 | <span class=comment>// range [it0,it1) contains the elements in [100,200]</span> | |
| 820 | </pre></blockquote> | |
| 821 | ||
| 822 | <p> | |
| 823 | Subtle changes to the code are required when strict inequalities are considered. | |
| 824 | To retrieve the elements <i>greater</i> than 100 and <i>less</i> than 200, the | |
| 825 | code has to be rewritten as | |
| 826 | </p> | |
| 827 | ||
| 828 | <blockquote><pre> | |
| 829 | <span class=identifier>double_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it0</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>upper_bound</span><span class=special>(</span><span class=number>100.0</span><span class=special>);</span> | |
| 830 | <span class=identifier>double_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it1</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>lower_bound</span><span class=special>(</span><span class=number>200.0</span><span class=special>);</span> | |
| 831 | <span class=comment>// range [it0,it1) contains the elements in (100,200)</span> | |
| 832 | </pre></blockquote> | |
| 833 | ||
| 834 | <p> | |
| 835 | To add to this complexity, the careful programmer has to take into account | |
| 836 | that the lower and upper bounds of the interval searched be compatible: for | |
| 837 | instance, if the lower bound is 200 and the upper bound is 100, the iterators | |
| 838 | <code>it0</code> and <code>it1</code> produced by the code above will be in reverse | |
| 839 | order, with possibly catastrophic results if a traversal from <code>it0</code> | |
| 840 | to <code>it1</code> is tried. All these details make range searching a tedious | |
| 841 | and error prone task. | |
| 842 | </p> | |
| 843 | ||
| 844 | <p> | |
| 845 | The <a href="../reference/ord_indices.html#range_operations"><code>range</code></a> | |
| 846 | member function, often in combination with | |
| 847 | <a href="../../../../libs/lambda/index.html">Boost.Lambda</a> expressions, can | |
| 848 | greatly help alleviate this situation: | |
| 849 | </p> | |
| 850 | ||
| 851 | <blockquote><pre> | |
| 852 | <span class=keyword>using</span> <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>::</span><span class=identifier>lambda</span><span class=special>;</span> | |
| 853 | ||
| 854 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span><span class=keyword>double</span><span class=special>></span> <span class=identifier>double_set</span><span class=special>;</span> | |
| 855 | <span class=identifier>double_set</span> <span class=identifier>s</span><span class=special>;</span> | |
| 856 | <span class=special>...</span> | |
| 857 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>pair</span><span class=special><</span><span class=identifier>double_set</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span><span class=identifier>double_set</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>></span> <span class=identifier>p</span><span class=special>=</span> | |
| 858 | <span class=identifier>s</span><span class=special>.</span><span class=identifier>range</span><span class=special>(</span><span class=number>100.0</span><span class=special><=</span><span class=identifier>_1</span><span class=special>,</span><span class=identifier>_1</span><span class=special><=</span><span class=number>200</span><span class=special>);</span> <span class=comment>// 100<= x <=200</span> | |
| 859 | <span class=special>...</span> | |
| 860 | <span class=identifier>p</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>range</span><span class=special>(</span><span class=number>100.0</span><span class=special><</span><span class=identifier>_1</span><span class=special>,</span><span class=identifier>_1</span><span class=special><</span><span class=number>200</span><span class=special>);</span> <span class=comment>// 100< x < 200</span> | |
| 861 | <span class=special>...</span> | |
| 862 | <span class=identifier>p</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>range</span><span class=special>(</span><span class=number>100.0</span><span class=special><=</span><span class=identifier>_1</span><span class=special>,</span><span class=identifier>_1</span><span class=special><</span><span class=number>200</span><span class=special>);</span> <span class=comment>// 100<= x < 200</span> | |
| 863 | </pre></blockquote> | |
| 864 | ||
| 865 | <p> | |
| 866 | <code>range</code> simply accepts predicates specifying the lower and upper bounds | |
| 867 | of the interval searched. Please consult the reference for a detailed explanation | |
| 868 | of the permissible predicates passed to <code>range</code>.</p> | |
| 869 | ||
| 870 | <p> | |
| 871 | One or both bounds can be omitted with the special <code>unbounded</code> marker: | |
| 872 | </p> | |
| 873 | ||
| 874 | <blockquote><pre> | |
| 875 | <span class=identifier>p</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>range</span><span class=special>(</span><span class=number>100.0</span><span class=special><=</span><span class=identifier>_1</span><span class=special>,</span><span class=identifier>unbounded</span><span class=special>);</span> <span class=comment>// 100 <= x</span> | |
| 876 | <span class=identifier>p</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>range</span><span class=special>(</span><span class=identifier>unbounded</span><span class=special>,</span><span class=identifier>_1</span><span class=special><</span><span class=number>200.0</span><span class=special>);</span> <span class=comment>// x < 200</span> | |
| 877 | <span class=identifier>p</span><span class=special>=</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>range</span><span class=special>(</span><span class=identifier>unbounded</span><span class=special>,</span><span class=identifier>unbounded</span><span class=special>);</span> <span class=comment>// equiv. to std::make_pair(s.begin(),s.end())</span> | |
| 878 | </pre></blockquote> | |
| 879 | ||
| 880 | <h4><a name="ord_updating">Updating</a></h4> | |
| 881 | ||
| 882 | <p> | |
| 883 | The <a href="../reference/ord_indices.html#replace"><code>replace</code></a> member function | |
| 884 | performs in-place replacement of a given element as the following example shows: | |
| 885 | </p> | |
| 886 | ||
| 887 | <blockquote><pre> | |
| 888 | <span class=keyword>typedef</span> <span class=identifier>index</span><span class=special><</span><span class=identifier>employee_set</span><span class=special>,</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span> | |
| 889 | <span class=identifier>employee_set_by_name</span><span class=special>&</span> <span class=identifier>name_index</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=identifier>name</span><span class=special>>();</span> | |
| 890 | ||
| 891 | <span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>name_index</span><span class=special>.</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Anna Jones"</span><span class=special>);</span> | |
| 892 | <span class=identifier>employee</span> <span class=identifier>anna</span><span class=special>=*</span><span class=identifier>it</span><span class=special>;</span> | |
| 893 | <span class=identifier>anna</span><span class=special>.</span><span class=identifier>name</span><span class=special>=</span><span class=string>"Anna Smith"</span><span class=special>;</span> <span class=comment>// she just got married to Calvin Smith</span> | |
| 894 | <span class=identifier>name_index</span><span class=special>.</span><span class=identifier>replace</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>anna</span><span class=special>);</span> <span class=comment>// update her record</span> | |
| 895 | </pre></blockquote> | |
| 896 | ||
| 897 | <p> | |
| 898 | <code>replace</code> performs this substitution in such a manner that: | |
| 899 | <ul> | |
| 900 | <li>The complexity is constant time if the changed element retains its original | |
| 901 | order with respect to all indices; it is logarithmic otherwise. | |
| 902 | <li>Iterator and reference validity are preserved. | |
| 903 | <li>The operation is strongly exception-safe, i.e. the <code>multi_index_container</code> | |
| 904 | remains unchanged if some exception (originated by the system or the user's data | |
| 905 | types) is thrown. | |
| 906 | </ul> | |
| 907 | <code>replace</code> is a powerful operation not provided by standard STL | |
| 908 | containers, and one that is specially handy when strong exception-safety is | |
| 909 | required. | |
| 910 | </p> | |
| 911 | ||
| 912 | <p> | |
| 913 | The observant reader might have noticed that the convenience of <code>replace</code> | |
| 914 | comes at a cost: namely the whole element has to be copied <i>twice</i> to do | |
| 915 | the updating (when retrieving it and inside <code>replace</code>). If elements | |
| 916 | are expensive to copy, this may be quite a computational cost for the modification | |
| 917 | of just a tiny part of the object. To cope with this situation, Boost.MultiIndex | |
| 918 | provides an alternative updating mechanism called | |
| 919 | <a href="../reference/ord_indices.html#modify"><code>modify</code></a>: | |
| 920 | </p> | |
| 921 | ||
| 922 | <blockquote><pre> | |
| 923 | <span class=keyword>struct</span> <span class=identifier>change_name</span> | |
| 924 | <span class=special>{</span> | |
| 925 | <span class=identifier>change_name</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>new_name</span><span class=special>):</span><span class=identifier>new_name</span><span class=special>(</span><span class=identifier>new_name</span><span class=special>){}</span> | |
| 926 | ||
| 927 | <span class=keyword>void</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> | |
| 928 | <span class=special>{</span> | |
| 929 | <span class=identifier>e</span><span class=special>.</span><span class=identifier>name</span><span class=special>=</span><span class=identifier>new_name</span><span class=special>;</span> | |
| 930 | <span class=special>}</span> | |
| 931 | ||
| 932 | <span class=keyword>private</span><span class=special>:</span> | |
| 933 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>new_name</span><span class=special>;</span> | |
| 934 | <span class=special>};</span> | |
| 935 | <span class=special>...</span> | |
| 936 | <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span> | |
| 937 | <span class=identifier>employee_set_by_name</span><span class=special>&</span> <span class=identifier>name_index</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=identifier>name</span><span class=special>>();</span> | |
| 938 | ||
| 939 | <span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>name_index</span><span class=special>.</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Anna Jones"</span><span class=special>);</span> | |
| 940 | <span class=identifier>name_index</span><span class=special>.</span><span class=identifier>modify</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>change_name</span><span class=special>(</span><span class=string>"Anna Smith"</span><span class=special>));</span> | |
| 941 | </pre></blockquote> | |
| 942 | ||
| 943 | <p><code>modify</code> accepts a functor (or pointer to function) that is | |
| 944 | passed a reference to the element to be changed, thus eliminating the need | |
| 945 | for spurious copies. Like <code>replace</code>, <code>modify</code> does preserve | |
| 946 | the internal orderings of all the indices of the <code>multi_index_container</code>. | |
| 947 | However, the semantics of <code>modify</code> is not entirely equivalent to | |
| 948 | <code>replace</code>. Consider what happens if a collision occurs as a result | |
| 949 | of modifying the element, i.e. the modified element clashes with another with | |
| 950 | respect to some unique ordered index. In the case of <code>replace</code>, the | |
| 951 | original value is kept and the method returns without altering the container, but | |
| 952 | <code>modify</code> cannot afford such an approach, since the modifying functor | |
| 953 | leaves no trace of the previous value of the element. Integrity constraints | |
| 954 | thus lead to the following policy: when a collision happens in the | |
| 955 | process of calling <code>modify</code>, the element is erased and the method returns | |
| 956 | <code>false</code>. There is a further version of <code>modify</code> which | |
| 957 | accepts a <i>rollback</i> functor to undo the changes in case of collision: | |
| 958 | </p> | |
| 959 | ||
| 960 | <blockquote><pre> | |
| 961 | <span class=keyword>struct</span> <span class=identifier>change_id</span> | |
| 962 | <span class=special>{</span> | |
| 963 | <span class=identifier>change_id</span><span class=special>(</span><span class=keyword>int</span> <span class=identifier>new_id</span><span class=special>):</span><span class=identifier>new_id</span><span class=special>(</span><span class=identifier>new_id</span><span class=special>){}</span> | |
| 964 | ||
| 965 | <span class=keyword>void</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> | |
| 966 | <span class=special>{</span> | |
| 967 | <span class=identifier>e</span><span class=special>.</span><span class=identifier>id</span><span class=special>=</span><span class=identifier>new_id</span><span class=special>;</span> | |
| 968 | <span class=special>}</span> | |
| 969 | ||
| 970 | <span class=keyword>private</span><span class=special>:</span> | |
| 971 | <span class=keyword>int</span> <span class=identifier>new_id</span><span class=special>;</span> | |
| 972 | <span class=special>};</span> | |
| 973 | <span class=special>...</span> | |
| 974 | <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=...</span> | |
| 975 | ||
| 976 | <span class=keyword>int</span> <span class=identifier>old_id</span><span class=special>=</span><span class=identifier>it</span><span class=special>-></span><span class=identifier>id</span><span class=special>;</span> <span class=comment>// keep the original id | |
| 977 | ||
| 978 | // try to modify the id, restore it in case of collisions</span> | |
| 979 | <span class=identifier>es</span><span class=special>.</span><span class=identifier>modify</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>change_id</span><span class=special>(</span><span class=number>321</span><span class=special>),</span><span class=identifier>change_id</span><span class=special>(</span><span class=identifier>old_id</span><span class=special>));</span> | |
| 980 | </pre></blockquote> | |
| 981 | ||
| 982 | <p>In the example, <code>change_id(old_id)</code> is invoked to restore the original | |
| 983 | conditions when the modification results in collisions with some other element. | |
| 984 | The differences in behavior between <code>replace</code>, <code>modify</code> and | |
| 985 | <code>modify</code> with rollback have to be considered by the programmer on a | |
| 986 | case-by-case basis to determine the best updating mechanism. | |
| 987 | </p> | |
| 988 | ||
| 989 | <p align="center"> | |
| 990 | <table cellspacing="0"> | |
| 991 | <caption><b>Behavior of the different updating mechanisms.</b></caption> | |
| 992 | <tr> | |
| 993 | <th align="center">updating function</th> | |
| 994 | <th>If there is a collision...</th> | |
| 995 | </tr> | |
| 996 | <tr> | |
| 997 | <td align="center"><code>replace(it,x)</code></td> | |
| 998 | <td>replacement does not take place.</td> | |
| 999 | </tr> | |
| 1000 | <tr class="odd_tr"> | |
| 1001 | <td align="center"><code>modify(it,mod)</code></td> | |
| 1002 | <td>the element is erased.</td> | |
| 1003 | </tr> | |
| 1004 | <tr> | |
| 1005 | <td align="center"><code>modify(it,mod,back)</code></td> | |
| 1006 | <td><code>back</code> is used to restore the original conditions. | |
| 1007 | (If <code>back</code> throws, the element is erased.) | |
| 1008 | </td> | |
| 1009 | </tr> | |
| 1010 | </table> | |
| 1011 | </p> | |
| 1012 | ||
| 1013 | ||
| 1014 | <p> | |
| 1015 | Key-based versions of <code>modify</code>, named | |
| 1016 | <a href="../reference/ord_indices.html#modify_key"><code>modify_key</code></a>, are | |
| 1017 | provided as well. In this case, the modifying functors are passed a reference to | |
| 1018 | the <code>key_type</code> part of the element instead of the whole object. | |
| 1019 | </p> | |
| 1020 | ||
| 1021 | <blockquote><pre> | |
| 1022 | <span class=keyword>struct</span> <span class=identifier>change_str</span> | |
| 1023 | <span class=special>{</span> | |
| 1024 | <span class=identifier>change_str</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>new_str</span><span class=special>):</span><span class=identifier>new_str</span><span class=special>(</span><span class=identifier>new_str</span><span class=special>){}</span> | |
| 1025 | ||
| 1026 | <span class=comment>// note this is passed a string, not an employee</span> | |
| 1027 | <span class=keyword>void</span> <span class=keyword>operator</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>str</span><span class=special>)</span> | |
| 1028 | <span class=special>{</span> | |
| 1029 | <span class=identifier>str</span><span class=special>=</span><span class=identifier>new_str</span><span class=special>;</span> | |
| 1030 | <span class=special>}</span> | |
| 1031 | ||
| 1032 | <span class=keyword>private</span><span class=special>:</span> | |
| 1033 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>new_str</span><span class=special>;</span> | |
| 1034 | <span class=special>};</span> | |
| 1035 | <span class=special>...</span> | |
| 1036 | <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span> | |
| 1037 | <span class=identifier>employee_set_by_name</span><span class=special>&</span> <span class=identifier>name_index</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=identifier>name</span><span class=special>>();</span> | |
| 1038 | ||
| 1039 | <span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>name_index</span><span class=special>.</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Anna Jones"</span><span class=special>);</span> | |
| 1040 | <span class=identifier>name_index</span><span class=special>.</span><span class=identifier>modify_key</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>change_str</span><span class=special>(</span><span class=string>"Anna Smith"</span><span class=special>));</span> | |
| 1041 | </pre></blockquote> | |
| 1042 | ||
| 1043 | <p> | |
| 1044 | Like <code>modify</code>, there are versions of <code>modify_key</code> with and | |
| 1045 | without rollback. <code>modify</code> and | |
| 1046 | <code>modify_key</code> are particularly well suited to use in conjunction to | |
| 1047 | <a href="../../../../libs/lambda/index.html">Boost.Lambda</a> | |
| 1048 | for defining the modifying functors: | |
| 1049 | </p> | |
| 1050 | ||
| 1051 | <blockquote><pre> | |
| 1052 | <span class=keyword>using</span> <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>::</span><span class=identifier>lambda</span><span class=special>;</span> | |
| 1053 | ||
| 1054 | <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span> | |
| 1055 | <span class=identifier>employee_set_by_name</span><span class=special>&</span> <span class=identifier>name_index</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=identifier>name</span><span class=special>>();</span> | |
| 1056 | ||
| 1057 | <span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>name_index</span><span class=special>.</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Anna Jones"</span><span class=special>);</span> | |
| 1058 | <span class=identifier>name_index</span><span class=special>.</span><span class=identifier>modify_key</span><span class=special>(</span><span class=identifier>it</span><span class=special>,</span><span class=identifier>_1</span><span class=special>=</span><span class=string>"Anna Smith"</span><span class=special>);</span> | |
| 1059 | </pre></blockquote> | |
| 1060 | ||
| 1061 | <p> | |
| 1062 | <code>modify_key</code> requires that the key extractor be of | |
| 1063 | a special type called | |
| 1064 | <a href="key_extraction.html#read_write_key_extractors">read/write</a>: | |
| 1065 | this is usually, but not always, the case. | |
| 1066 | </p> | |
| 1067 | ||
| 1068 | <h3> | |
| 1069 | <a name="seq_indices">Sequenced indices</a> | |
| 1070 | </h3> | |
| 1071 | ||
| 1072 | <p> | |
| 1073 | Unlike ordered indices, sequenced indices do not impose a fixed order on the | |
| 1074 | elements: instead, these can be arranged in any position on the sequence, in the | |
| 1075 | same way as <code>std::list</code> permits. The interface of sequenced indices | |
| 1076 | is thus designed upon that of <code>std::list</code>; nearly every operation | |
| 1077 | provided in the standard container is replicated here, occasionally with changes | |
| 1078 | in the syntax and/or semantics to cope with the constraints imposed by | |
| 1079 | Boost.MultiIndex. An important difference, commented <a href="#iterator_access">above</a>, | |
| 1080 | is the fact that the values pointed to by sequenced index iterators are treated | |
| 1081 | as <i>constant</i>: | |
| 1082 | </p> | |
| 1083 | ||
| 1084 | <blockquote><pre> | |
| 1085 | <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 1086 | <span class=keyword>int</span><span class=special>,</span> | |
| 1087 | <span class=identifier>indexed_by</span><span class=special><</span><span class=identifier>sequenced</span><span class=special><></span> <span class=special>></span> | |
| 1088 | <span class=special>></span> <span class=identifier>s</span><span class=special>;</span> <span class=comment>// list-like container</span> | |
| 1089 | ||
| 1090 | <span class=identifier>s</span><span class=special>.</span><span class=identifier>push_front</span><span class=special>(</span><span class=number>0</span><span class=special>);</span> | |
| 1091 | <span class=special>*(</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>begin</span><span class=special>())=</span><span class=number>1</span><span class=special>;</span> <span class=comment>// ERROR: the element cannot be changed</span> | |
| 1092 | </pre></blockquote> | |
| 1093 | ||
| 1094 | <p> | |
| 1095 | As with any other type of index, element modification | |
| 1096 | can nevertheless be done by means of | |
| 1097 | <a href="#seq_updating">update operations</a>. | |
| 1098 | </p> | |
| 1099 | ||
| 1100 | <p> | |
| 1101 | Consider a <code>multi_index_container</code> with two or more indices, one of them | |
| 1102 | of sequenced type. If an element is inserted through another index, | |
| 1103 | then it will be automatically appended to the end of the sequenced index. | |
| 1104 | An example will help to clarify this: | |
| 1105 | </p> | |
| 1106 | ||
| 1107 | <blockquote><pre> | |
| 1108 | <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 1109 | <span class=keyword>int</span><span class=special>,</span> | |
| 1110 | <span class=identifier>indexed_by</span><span class=special><</span> | |
| 1111 | <span class=identifier>sequenced</span><span class=special><>,</span> <span class=comment>// sequenced type</span> | |
| 1112 | <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=special>></span> <span class=comment>// another index</span> | |
| 1113 | <span class=special>></span> | |
| 1114 | <span class=special>></span> <span class=identifier>s</span><span class=special>;</span> | |
| 1115 | ||
| 1116 | <span class=identifier>s</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=number>1</span><span class=special>>().</span><span class=identifier>insert</span><span class=special>(</span><span class=number>1</span><span class=special>);</span> <span class=comment>// insert 1 through index #1</span> | |
| 1117 | <span class=identifier>s</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=number>1</span><span class=special>>().</span><span class=identifier>insert</span><span class=special>(</span><span class=number>0</span><span class=special>);</span> <span class=comment>// insert 0 through index #1 | |
| 1118 | ||
| 1119 | // list elements through sequenced index #0</span> | |
| 1120 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>s</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>ostream_iterator</span><span class=special><</span><span class=keyword>int</span><span class=special>>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>cout</span><span class=special>));</span> | |
| 1121 | ||
| 1122 | <span class=comment>// result: 1 0</span> | |
| 1123 | </pre></blockquote> | |
| 1124 | ||
| 1125 | <p> | |
| 1126 | Thus the behavior of sequenced indices when insertions are not made through | |
| 1127 | them is to preserve insertion order. | |
| 1128 | </p> | |
| 1129 | ||
| 1130 | <h4><a name="seq_spec">Specification</a></h4> | |
| 1131 | ||
| 1132 | <p> | |
| 1133 | Sequenced indices are specified with the <code>sequenced</code> construct: | |
| 1134 | </p> | |
| 1135 | ||
| 1136 | <blockquote><pre> | |
| 1137 | <span class=identifier>sequenced</span><span class=special><[</span><i>(tag)</i><span class=special>]></span> | |
| 1138 | </pre></blockquote> | |
| 1139 | ||
| 1140 | <p> | |
| 1141 | The <a href="#tagging">tag</a> parameter is optional. | |
| 1142 | </p> | |
| 1143 | ||
| 1144 | <h4><a name="list_ops">List operations</a></h4> | |
| 1145 | ||
| 1146 | <p> | |
| 1147 | As mentioned before, sequenced indices mimic the interface of | |
| 1148 | <code>std::list</code>, and most of the original operations therein are | |
| 1149 | provided as well. The semantics and complexity of these operations, however, | |
| 1150 | do not always coincide with those of the standard container. Differences | |
| 1151 | result mainly from the fact that insertions into a sequenced index are not | |
| 1152 | guaranteed to succeed, due to the possible banning by other indices | |
| 1153 | of the <code>multi_index_container</code>. Consult the | |
| 1154 | <a href="../reference/seq_indices.html">reference</a> for further details. | |
| 1155 | </p> | |
| 1156 | ||
| 1157 | <h4><a name="seq_updating">Updating</a></h4> | |
| 1158 | ||
| 1159 | <p> | |
| 1160 | Like ordered indices, sequenced indices provide | |
| 1161 | <a href="../reference/seq_indices.html#replace"><code>replace</code></a> and | |
| 1162 | <a href="../reference/seq_indices.html#modify"><code>modify</code></a> | |
| 1163 | operations, with identical functionality. There is however no analogous | |
| 1164 | <code>modify_key</code>, since sequenced indices are not key-based. | |
| 1165 | </p> | |
| 1166 | ||
| 1167 | <h2><a name="projection">Projection of iterators</a></h2> | |
| 1168 | ||
| 1169 | <p> | |
| 1170 | Given indices <code>i1</code> and <code>i2</code> on the same <code>multi_index_container</code>, | |
| 1171 | <a href="../reference/multi_index_container.html#projection"><code>project</code></a> can be used to | |
| 1172 | retrieve an <code>i2</code>-iterator from an <code>i1</code>-iterator, both of them | |
| 1173 | pointing to the same element of the container. This functionality allows the programmer to | |
| 1174 | move between different indices of the same <code>multi_index_container</code> when performing | |
| 1175 | elaborate operations: | |
| 1176 | </p> | |
| 1177 | ||
| 1178 | <blockquote><pre> | |
| 1179 | <span class=keyword>typedef</span> <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>index</span><span class=special><</span><span class=identifier>name</span><span class=special>>::</span><span class=identifier>type</span> <span class=identifier>employee_set_by_name</span><span class=special>;</span> | |
| 1180 | <span class=identifier>employee_set_by_name</span><span class=special>&</span> <span class=identifier>name_index</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=identifier>name</span><span class=special>>();</span> | |
| 1181 | ||
| 1182 | <span class=comment>// list employees by ID starting from Robert Brown's ID</span> | |
| 1183 | ||
| 1184 | <span class=identifier>employee_set_by_name</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it1</span><span class=special>=</span><span class=identifier>name_index</span><span class=special>.</span><span class=identifier>find</span><span class=special>(</span><span class=string>"Robert Brown"</span><span class=special>);</span> | |
| 1185 | ||
| 1186 | <span class=comment>// obtain an iterator of index #0 from it1</span> | |
| 1187 | <span class=identifier>employee_set</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it2</span><span class=special>=</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>project</span><span class=special><</span><span class=number>0</span><span class=special>>(</span><span class=identifier>it1</span><span class=special>);</span> | |
| 1188 | ||
| 1189 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>copy</span><span class=special>(</span><span class=identifier>it2</span><span class=special>,</span><span class=identifier>es</span><span class=special>.</span><span class=identifier>end</span><span class=special>(),</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>ostream_iterator</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>cout</span><span class=special>));</span> | |
| 1190 | </pre></blockquote> | |
| 1191 | ||
| 1192 | <p> | |
| 1193 | A slightly more interesting example: | |
| 1194 | </p> | |
| 1195 | ||
| 1196 | <blockquote><pre> | |
| 1197 | <span class=identifier>text_container</span> <span class=identifier>tc</span><span class=special>;</span> | |
| 1198 | ||
| 1199 | <span class=comment>// get a view to index #1 (ordered index on the words)</span> | |
| 1200 | <span class=identifier>text_container</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>sorted_index</span><span class=special>=</span><span class=identifier>tc</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=number>1</span><span class=special>>();</span> | |
| 1201 | ||
| 1202 | <span class=comment>// prepend "older" to all occurrences of "sister"</span> | |
| 1203 | ||
| 1204 | <span class=identifier>text_container</span><span class=special>::</span><span class=identifier>nth_index</span><span class=special><</span><span class=number>1</span><span class=special>>::</span><span class=identifier>type</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it1</span><span class=special>=</span> | |
| 1205 | <span class=identifier>sorted_index</span><span class=special>.</span><span class=identifier>lower_bound</span><span class=special>(</span><span class=string>"sister"</span><span class=special>);</span> | |
| 1206 | ||
| 1207 | <span class=keyword>while</span><span class=special>(</span><span class=identifier>it1</span><span class=special>!=</span><span class=identifier>sorted_index</span><span class=special>.</span><span class=identifier>end</span><span class=special>()&&*</span><span class=identifier>it1</span><span class=special>==</span><span class=string>"sister"</span><span class=special>){</span> | |
| 1208 | <span class=comment>// convert to an iterator to the sequenced index</span> | |
| 1209 | <span class=identifier>text_container</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it2</span><span class=special>=</span><span class=identifier>tc</span><span class=special>.</span><span class=identifier>project</span><span class=special><</span><span class=number>0</span><span class=special>>(</span><span class=identifier>it1</span><span class=special>);</span> | |
| 1210 | ||
| 1211 | <span class=identifier>tc</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=identifier>it2</span><span class=special>,</span><span class=string>"older"</span><span class=special>);</span> | |
| 1212 | <span class=special>++</span><span class=identifier>it1</span><span class=special>;</span> | |
| 1213 | <span class=special>}</span> | |
| 1214 | </pre></blockquote> | |
| 1215 | ||
| 1216 | <p> | |
| 1217 | When provided, <code>project</code> can also be used with | |
| 1218 | <a href="#tagging">tags</a>. | |
| 1219 | </p> | |
| 1220 | ||
| 1221 | <h2><a name="complexity">Complexity and exception safety</a></h2> | |
| 1222 | ||
| 1223 | <p> | |
| 1224 | <code>multi_index_container</code> provides the same complexity and exception safety | |
| 1225 | guarantees as the equivalent STL containers do. Iterator and reference validity | |
| 1226 | is preserved in the face of insertions, even for replace and modify operations. | |
| 1227 | </p> | |
| 1228 | ||
| 1229 | <p> | |
| 1230 | Appropriate instantiations of <code>multi_index_container</code> can in fact simulate | |
| 1231 | <code>std::set</code>, <code>std::multiset</code> and (with more limitations) | |
| 1232 | <code>std::list</code>, as shown in the | |
| 1233 | <a href="techniques.html#emulate_std_containers">techniques</a> | |
| 1234 | section. These simulations are as nearly as efficient as the original STL | |
| 1235 | containers; consult the <a href="../reference/index.html">reference</a> for further | |
| 1236 | information on complexity guarantees and the | |
| 1237 | <a href="../performance.html">performance section</a> for practical measurements of | |
| 1238 | efficiency. | |
| 1239 | </p> | |
| 1240 | ||
| 1241 | <hr> | |
| 1242 | ||
| 1243 | <div class="prev_link"><a href="index.html"><img src="../prev.gif" alt="tutorial" border="0"><br> | |
| 1244 | Boost.MultiIndex Tutorial | |
| 1245 | </a></div> | |
| 1246 | <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex tutorial" border="0"><br> | |
| 1247 | Boost.MultiIndex tutorial | |
| 1248 | </a></div> | |
| 1249 | <div class="next_link"><a href="indices.html"><img src="../next.gif" alt="index types" border="0"><br> | |
| 1250 | Index types | |
| 1251 | </a></div><br clear="all" style="clear: all;"> | |
| 1252 | ||
| 1253 | <br> | |
| 1254 | ||
| 1255 | <p>Revised November 24th 2015</p> | |
| 1256 | ||
| 1257 | <p>© Copyright 2003-2015 Joaquín M López Muñoz. | |
| 1258 | Distributed under the Boost Software | |
| 1259 | License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt"> | |
| 1260 | LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt"> | |
| 1261 | http://www.boost.org/LICENSE_1_0.txt</a>) | |
| 1262 | </p> | |
| 1263 | ||
| 1264 | </body> | |
| 1265 | </html> |