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 - Future work</title> | |
| 7 | <link rel="stylesheet" href="style.css" type="text/css"> | |
| 8 | <link rel="start" href="index.html"> | |
| 9 | <link rel="prev" href="tests.html"> | |
| 10 | <link rel="up" href="index.html"> | |
| 11 | <link rel="next" href="release_notes.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 Future work</h1> | |
| 17 | ||
| 18 | <div class="prev_link"><a href="tests.html"><img src="prev.gif" alt="tests" border="0"><br> | |
| 19 | Tests | |
| 20 | </a></div> | |
| 21 | <div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br> | |
| 22 | Index | |
| 23 | </a></div> | |
| 24 | <div class="next_link"><a href="release_notes.html"><img src="next.gif" alt="release notes" border="0"><br> | |
| 25 | Release notes | |
| 26 | </a></div><br clear="all" style="clear: all;"> | |
| 27 | ||
| 28 | <hr> | |
| 29 | ||
| 30 | <p> | |
| 31 | A number of new functionalities are considered for inclusion into | |
| 32 | future releases of Boost.MultiIndex. Some of them depend on the | |
| 33 | potential for extensibility of the library, which has been a guiding | |
| 34 | principle driving the current internal design of <code>multi_index_container</code>. | |
| 35 | </p> | |
| 36 | ||
| 37 | <h2>Contents</h2> | |
| 38 | ||
| 39 | <ul> | |
| 40 | <li><a href="#notifying">Notifying indices</a></li> | |
| 41 | <li><a href="#constraints">Constraints</a></li> | |
| 42 | <li><a href="#user_defined_indices">User-defined indices</a></li> | |
| 43 | <li><a href="#indexed_maps">Indexed maps</a></li> | |
| 44 | </ul> | |
| 45 | ||
| 46 | <h2><a name="notifying">Notifying indices</a></h2> | |
| 47 | ||
| 48 | <p> | |
| 49 | <i>Notifying indices</i> can be implemented as decorators over | |
| 50 | preexistent index types, with the added functionality that internal | |
| 51 | events of the index (insertion, erasing, modifying of elements) are | |
| 52 | signalled to an external entity --for instance, by means of the | |
| 53 | <a href="../../../doc/html/signals.html">Boost.Signals</a> | |
| 54 | library. This functionality can have applications for: | |
| 55 | <ol> | |
| 56 | <li>Logging,</li> | |
| 57 | <li>interfacing to GUI-based applications,</li> | |
| 58 | <li>synchronization between separate data structures.</li> | |
| 59 | </ol> | |
| 60 | </p> | |
| 61 | ||
| 62 | <p> | |
| 63 | The following is a sketch of a possible realization of notifying | |
| 64 | indices: | |
| 65 | </p> | |
| 66 | ||
| 67 | <blockquote><pre> | |
| 68 | <span class=keyword>struct</span> <span class=identifier>insert_log</span> | |
| 69 | <span class=special>{</span> | |
| 70 | <span class=keyword>void</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>int</span> <span class=identifier>x</span><span class=special>)</span> | |
| 71 | <span class=special>{</span> | |
| 72 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>clog</span><span class=special><<</span><span class=string>"insert: "</span><span class=special><<</span><span class=identifier>x</span><span class=special><<</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>endl</span><span class=special>;</span> | |
| 73 | <span class=special>}</span> | |
| 74 | <span class=special>};</span> | |
| 75 | ||
| 76 | <span class=keyword>int</span> <span class=identifier>main</span><span class=special>()</span> | |
| 77 | <span class=special>{</span> | |
| 78 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 79 | <span class=keyword>int</span><span class=special>,</span> | |
| 80 | <span class=identifier>indexed_by</span><span class=special><</span> | |
| 81 | <span class=identifier>notifying</span><span class=special><</span><span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>></span> <span class=special>>,</span> <span class=comment>// notifying index</span> | |
| 82 | <span class=identifier>ordered_non_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> | |
| 83 | <span class=special>></span> | |
| 84 | <span class=special>></span> <span class=identifier>indexed_t</span><span class=special>;</span> | |
| 85 | ||
| 86 | <span class=identifier>indexed_t</span> <span class=identifier>t</span><span class=special>;</span> | |
| 87 | ||
| 88 | <span class=comment>// on_insert is the signal associated to insertions</span> | |
| 89 | <span class=identifier>t</span><span class=special>.</span><span class=identifier>on_insert</span><span class=special>.</span><span class=identifier>connect</span><span class=special>(</span><span class=identifier>insert_log</span><span class=special>());</span> | |
| 90 | ||
| 91 | <span class=identifier>t</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=number>0</span><span class=special>);</span> | |
| 92 | <span class=identifier>t</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=number>1</span><span class=special>);</span> | |
| 93 | ||
| 94 | <span class=keyword>return</span> <span class=number>0</span><span class=special>;</span> | |
| 95 | <span class=special>}</span> | |
| 96 | ||
| 97 | <span class=comment>// output: | |
| 98 | // insert: 0 | |
| 99 | // insert: 1</span> | |
| 100 | </pre></blockquote> | |
| 101 | ||
| 102 | <h2><a name="constraints">Constraints</a></h2> | |
| 103 | ||
| 104 | <p> | |
| 105 | The notifying indices functionality described above exploits a powerful | |
| 106 | design pattern based on <i>index adaptors</i>, decorators over preexistent | |
| 107 | indices which add some functionality or somehow change the semantics of | |
| 108 | the underlying index. This pattern can be used for the implementation | |
| 109 | of <i>constraints</i>, adaptors that restrict the elements accepted by an | |
| 110 | index according to some validation predicate. The following is a possible | |
| 111 | realization of how constraints syntax may look like: | |
| 112 | </p> | |
| 113 | ||
| 114 | <blockquote><pre> | |
| 115 | <span class=keyword>struct</span> <span class=identifier>is_even</span> | |
| 116 | <span class=special>{</span> | |
| 117 | <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=special>{</span><span class=keyword>return</span> <span class=identifier>x</span><span class=special>%</span><span class=number>2</span><span class=special>==</span><span class=number>0</span><span class=special>;}</span> | |
| 118 | <span class=special>};</span> | |
| 119 | ||
| 120 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 121 | <span class=keyword>int</span><span class=special>,</span> | |
| 122 | <span class=identifier>indexed_by</span><span class=special><</span> | |
| 123 | <span class=identifier>constrained</span><span class=special><</span><span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>>,</span><span class=identifier>is_even</span><span class=special>></span> | |
| 124 | <span class=special>></span> | |
| 125 | <span class=special>></span> <span class=identifier>indexed_t</span><span class=special>;</span> | |
| 126 | </pre></blockquote> | |
| 127 | ||
| 128 | <h2><a name="user_defined_indices">User-defined indices</a></h2> | |
| 129 | ||
| 130 | <p> | |
| 131 | The mechanisms by which Boost.MultiIndex orchestrates the | |
| 132 | operations of the indices held by a <code>multi_index_container</code> are | |
| 133 | simple enough to make them worth documenting so that the (bold) | |
| 134 | user can write implementations for her own indices. | |
| 135 | </p> | |
| 136 | ||
| 137 | <h2><a name="indexed_maps">Indexed maps</a></h2> | |
| 138 | ||
| 139 | <p> | |
| 140 | <code>multi_index_container</code> is rich enough to provide the basis | |
| 141 | for implementation of <i>indexed maps</i>, i.e. maps which | |
| 142 | can be looked upon several different keys. The motivation for having | |
| 143 | such a container is mainly aesthetic convenience, since it | |
| 144 | would not provide any additional feature to similar constructs | |
| 145 | based directly on <code>multi_index_container</code>. | |
| 146 | </p> | |
| 147 | ||
| 148 | <p> | |
| 149 | The main challenge in writing an indexed map lies in the design of a | |
| 150 | reasonable interface that resembles that of <code>std::map</code> as | |
| 151 | much as possible. There seem to be fundamental difficulties in extending | |
| 152 | the syntax of a <code>std::map</code> to multiple keys. For one example, | |
| 153 | consider the situation: | |
| 154 | </p> | |
| 155 | ||
| 156 | <blockquote><pre> | |
| 157 | <span class=identifier>indexed_map</span><span class=special><</span><span class=keyword>int</span><span class=special>,</span><span class=identifier>string</span><span class=special>,</span><span class=keyword>double</span><span class=special>></span> <span class=identifier>m</span><span class=special>;</span> | |
| 158 | <span class=comment>// keys are int and string, double is the mapped to value</span> | |
| 159 | ||
| 160 | <span class=special>...</span> | |
| 161 | ||
| 162 | <span class=identifier>cout</span><span class=special><<</span><span class=identifier>m</span><span class=special>[</span><span class=number>0</span><span class=special>]<<</span><span class=identifier>endl</span><span class=special>;</span> <span class=comment>// OK</span> | |
| 163 | <span class=identifier>cout</span><span class=special><<</span><span class=identifier>m</span><span class=special>[</span><span class=string>"zero"</span><span class=special>]<<</span><span class=identifier>endl</span><span class=special>;</span> <span class=comment>// OK</span> | |
| 164 | <span class=identifier>m</span><span class=special>[</span><span class=number>1</span><span class=special>]=</span><span class=number>1.0</span><span class=special>;</span> <span class=comment>// !!</span> | |
| 165 | </pre></blockquote> | |
| 166 | ||
| 167 | <p> | |
| 168 | In the last sentence of the example, the user has no way of | |
| 169 | providing the <code>string</code> key mapping to the same value | |
| 170 | as <code>m[1]</code>. This and similar problems have to be devoted | |
| 171 | a careful study when designing the interface of a potential | |
| 172 | indexed map. | |
| 173 | </p> | |
| 174 | ||
| 175 | <hr> | |
| 176 | ||
| 177 | <div class="prev_link"><a href="tests.html"><img src="prev.gif" alt="tests" border="0"><br> | |
| 178 | Tests | |
| 179 | </a></div> | |
| 180 | <div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br> | |
| 181 | Index | |
| 182 | </a></div> | |
| 183 | <div class="next_link"><a href="release_notes.html"><img src="next.gif" alt="release notes" border="0"><br> | |
| 184 | Release notes | |
| 185 | </a></div><br clear="all" style="clear: all;"> | |
| 186 | ||
| 187 | <br> | |
| 188 | ||
| 189 | <p>Revised April 19th 2015</p> | |
| 190 | ||
| 191 | <p>© Copyright 2003-2015 Joaquín M López Muñoz. | |
| 192 | Distributed under the Boost Software | |
| 193 | License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt"> | |
| 194 | LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt"> | |
| 195 | http://www.boost.org/LICENSE_1_0.txt</a>) | |
| 196 | </p> | |
| 197 | ||
| 198 | </body> | |
| 199 | </html> |