ceph/src/boost/libs/flyweight/doc/tutorial/key_value.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
   2
   3 <html>
   4 <head>
   5 <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
   6 <title>Boost.Flyweight Documentation - Tutorial - Key-value flyweights</title>
   7 <link rel="stylesheet" href="../style.css" type="text/css">
   8 <link rel="start" href="../index.html">
   9 <link rel="prev" href="basics.html">
  10 <link rel="up" href="index.html">
  11 <link rel="next" href="configuration.html">
  12 </head>
  13
  14 <body>
  15 <h1><img src="../../../../boost.png" alt="Boost logo" align=
  16 "middle" width="277" height="86">Boost.Flyweight Tutorial: Key-value flyweights</h1>
  17
  18 <div class="prev_link"><a href="basics.html"><img src="../prev.gif" alt="basics" border="0"><br>
  19 Basics
  20 </a></div>
  21 <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.Flyweight tutorial" border="0"><br>
  22 Boost.Flyweight tutorial
  23 </a></div>
  24 <div class="next_link"><a href="configuration.html"><img src="../next.gif" alt="configuring Boost.Flyweight" border="0"><br>
  25 Configuring Boost.Flyweight
  26 </a></div><br clear="all" style="clear: all;">
  27
  28 <hr>
  29
  30 <h2>Contents</h2>
  31
  32 <ul>
  33   <li><a href="#key_value">Key-value flyweights</a>
  34     <ul>
  35       <li><a href="#key_extractor">Key extractors</a></li>
  36       <li><a href="#requirements">Type requirements</a></li>
  37     </ul>
  38   </li>
  39 </ul>
  40
  41 <h2><a name="key_value">Key-value flyweights</a></h2>
  42
  43 <p>
  44 Continuing with our online game example, suppose we have a huge class for
  45 handling rendering textures:
  46 </p>
  47
  48 <blockquote><pre>
  49 <span class=keyword>class</span> <span class=identifier>texture</span>
  50 <span class=special>{</span>
  51 <span class=keyword>public</span><span class=special>:</span>
  52   <span class=identifier>texture</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&amp;</span> <span class=identifier>filename</span><span class=special>){/*</span> <span class=identifier>loads</span> <span class=identifier>texture</span> <span class=identifier>file</span> <span class=special>*/}</span>
  53
  54   <span class=keyword>const</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&amp;</span> <span class=identifier>get_filename</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
  55
  56   <span class=comment>// rest of the interface</span>
  57 <span class=special>};</span>
  58 </pre></blockquote>
  59
  60 <p>
  61 and we decide to use <code>flyweight&lt;texture&gt;</code> to ease the
  62 manipulation of these objects. Now consider this seemingly innocent
  63 expression:
  64 </p>
  65
  66 <blockquote><pre>
  67 <span class=identifier>flyweight</span><span class=special>&lt;</span><span class=identifier>texture</span><span class=special>&gt;</span> <span class=identifier>fw</span><span class=special>(</span><span class=string>&quot;grass.texture&quot;</span><span class=special>);</span>
  68 </pre></blockquote>
  69
  70 <p>
  71 Note that in order to construct <code>fw</code> we are implicitly
  72 constructing a full grass texture object. The expression is mostly
  73 equivalent to
  74 </p>
  75
  76 <blockquote><pre>
  77 <span class=identifier>flyweight</span><span class=special>&lt;</span><span class=identifier>texture</span><span class=special>&gt;</span> <span class=identifier>fw</span><span class=special>(</span><span class=identifier>texture</span><span class=special>(</span><span class=string>&quot;grass.texture&quot;</span><span class=special>));</span>
  78 </pre></blockquote>
  79
  80 <p>
  81 This is unnaceptably costly: we are constructing a massive temporary
  82 object just to throw it away in most cases, since Boost.Flyweight most
  83 likely already has an internal equivalent object to which <code>fw</code>
  84 will be bound --value sharing is the key feature behind the flyweight
  85 pattern after all. In this particular example, texture filenames act
  86 as a <i>key</i> to the actual texture objects: two texture objects
  87 constructed from the same filename are equivalent. So, we would like
  88 for filenames to be used for texture lookup and somehow be sure that
  89 the costly texture construction is only performed when no equivalent
  90 value has been found.
  91 </p>
  92
  93 <p>
  94 <code>flyweight&lt;T&gt;</code> makes this distinction between key and value
  95 blurry because it uses <code>T</code> both as the key type and
  96 its associated value type. When this is inefficient, as in our texture
  97 example, we can explicity specify both types using the
  98 <a href="../reference/key_value.html#key_value_construct"><code>key_value</code></a>
  99 construct:
 100 </p>
 101
 102 <blockquote><pre>
 103 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>flyweight</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 104 <span class=preprocessor>#include</span> <span class=special>&lt;</span><span class=identifier>boost</span><span class=special>/</span><span class=identifier>flyweight</span><span class=special>/</span><span class=identifier>key_value</span><span class=special>.</span><span class=identifier>hpp</span><span class=special>&gt;</span>
 105 <span class=special>...</span>
 106 <span class=identifier>flyweight</span><span class=special>&lt;</span><span class=identifier>key_value</span><span class=special>&lt;</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,</span><span class=identifier>texture</span><span class=special>&gt;</span> <span class=special>&gt;</span> <span class=identifier>fw</span><span class=special>(</span><span class=string>&quot;grass.texture&quot;</span><span class=special>);</span>
 107 </pre></blockquote>
 108
 109 <p>
 110 So called <i>key-value flyweights</i> have then the form
 111 <code>flyweight&lt;key_value&lt;K,T&gt; &gt;</code>: the key type <code>K</code> is
 112 used to do the internal lookup for the associated values of type <code>T</code>. Key-value
 113 flyweights guarantee that <code>T</code> values are not constructed except when
 114 no other equivalent value exists; such construction is done from the associated
 115 <code>K</code> value.
 116 </p>
 117
 118 <h3><a name="key_extractor">Key extractors</a></h3>
 119
 120 <p>
 121 Besides the key-based semantics on construction time, key-value flyweights
 122 behave much the same as regular flyweights, although some differences persist.
 123 Consider the following code, which poses no problems with regular
 124 flyweights:
 125 </p>
 126
 127 <blockquote><pre>
 128 <span class=keyword>const</span> <span class=identifier>texture</span><span class=special>&amp;</span> <span class=identifier>get_texture</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>object</span><span class=special>&amp;);</span>
 129 <span class=special>...</span>
 130 <span class=identifier>flyweight</span><span class=special>&lt;</span><span class=identifier>key_value</span><span class=special>&lt;</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,</span><span class=identifier>texture</span><span class=special>&gt;</span> <span class=special>&gt;</span> <span class=identifier>fw</span><span class=special>;</span>
 131 <span class=special>...</span>
 132 <span class=identifier>fw</span><span class=special>=</span><span class=identifier>get_texture</span><span class=special>(</span><span class=identifier>obj</span><span class=special>);</span>
 133 </pre></blockquote>
 134
 135 <p>
 136 The assignment cannot possibly work, because a key of type <code>std::string</code>
 137 is needed to do the internal lookup whereas we are passing a full texture object.
 138 Indeed, the code produces a compilation error similar to this:
 139 </p>
 140
 141 <blockquote><pre>
 142 error: 'boost::mpl::assertion_failed' : cannot convert parameter 1 from
 143 'boost::mpl::failed ************(__thiscall boost::flyweights::detail::
 144 regular_key_value&lt;Key,Value&gt;::rep_type::no_key_from_value_failure::
 145 <b>NO_KEY_FROM_VALUE_CONVERSION_PROVIDED</b>::* ***********)(std::string,texture)'
 146 to 'boost::mpl::assert&lt;false&gt;::type'...
 147 </pre></blockquote>
 148
 149 <p>
 150 It turns out that we can make the assignment work if only we provide a means
 151 to retrieve the key from the value. This is not always possible, but in
 152 our particular example the texture class does store the filename used for
 153 construction, as indicated by the <code>texture::get_filename</code>
 154 member function. We take advantage of this by specifying a
 155 suitable <a href="../reference/key_value.html#key_extractor"><i>key
 156 extractor</i></a> as part of the flyweight type definition:
 157 </p>
 158
 159 <blockquote><pre>
 160 <span class=keyword>struct</span> <span class=identifier>texture_filename_extractor</span>
 161 <span class=special>{</span>
 162   <span class=keyword>const</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>&amp;</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>const</span> <span class=identifier>texture</span><span class=special>&amp;</span> <span class=identifier>x</span><span class=special>)</span><span class=keyword>const</span>
 163   <span class=special>{</span>
 164     <span class=keyword>return</span> <span class=identifier>x</span><span class=special>.</span><span class=identifier>get_filename</span><span class=special>();</span>
 165   <span class=special>}</span>
 166 <span class=special>};</span>
 167
 168 <span class=identifier>flyweight</span><span class=special>&lt;</span><span class=identifier>key_value</span><span class=special>&lt;</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,</span><span class=identifier>texture</span><span class=special>,</span><span class=identifier>texture_filename_extractor</span><span class=special>&gt;</span> <span class=special>&gt;</span> <span class=identifier>fw</span><span class=special>;</span>
 169 <span class=special>...</span>
 170 <span class=identifier>fw</span><span class=special>=</span><span class=identifier>get_texture</span><span class=special>(</span><span class=identifier>obj</span><span class=special>);</span> <span class=comment>// OK now</span>
 171 </pre></blockquote>
 172
 173 <p>
 174 The specification of a key extractor in the
 175 definition of a key-value flyweight results in internal space optimizations,
 176 as the keys need not be stored along the values but are retrieved from
 177 them instead. So, it is always a good idea to provide a key extractor when
 178 possible even if your program does not contain assignment statements like
 179 the one above.
 180 </p>
 181
 182 <p>
 183 Examples <a href="../examples.html#example2">2</a> and
 184 <a href="../examples.html#example5">5</a>
 185 of the examples section make use of key-value flyweights.
 186 </p>
 187
 188 <h3><a name="requirements">Type requirements</a></h3>
 189
 190 <p>
 191 Many of the requirements imposed on <code>T</code> for
 192 <a href="basics.html#requirements">regular flyweights</a> move to the key
 193 type in the case of a key-value <code>flyweight&lt;key_value&lt;K,T&gt; &gt;</code>.
 194 Now it is <code>K</code> that must be
 195 <a href="http://www.sgi.com/tech/stl/Assignable.html"><code>Assignable</code></a>,
 196 <a href="http://www.sgi.com/tech/stl/EqualityComparable.html"><code>Equality
 197 Comparable</code></a> and interoperate with
 198 <a href="../../../functional/hash/index.html">Boost.Hash</a>, where equality and
 199 hash compatibility are requirements imposed by the default internal factory of
 200 Boost.Flyweight and can change if this factory is further configured or replaced
 201 by the user. The only requisite retained on <code>T</code> is that it must be
 202 constructible from <code>K</code>; only in the case that a flyweight is directly
 203 assigned a <code>T</code> object is also <code>T</code> required to be
 204 <a href="http://www.sgi.com/tech/stl/Assignable.html"><code>Assignable</code></a>.
 205 To serialize objects of type <code>flyweight&lt;key_value&lt;K,T&gt; &gt;</code>
 206 only <code>K</code> needs to be serializable.
 207 </p>
 208
 209 <hr>
 210
 211 <div class="prev_link"><a href="basics.html"><img src="../prev.gif" alt="basics" border="0"><br>
 212 Basics
 213 </a></div>
 214 <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.Flyweight tutorial" border="0"><br>
 215 Boost.Flyweight tutorial
 216 </a></div>
 217 <div class="next_link"><a href="configuration.html"><img src="../next.gif" alt="configuring Boost.Flyweight" border="0"><br>
 218 Configuring Boost.Flyweight
 219 </a></div><br clear="all" style="clear: all;">
 220
 221 <br>
 222
 223 <p>Revised September 1st 2014</p>
 224
 225 <p>&copy; Copyright 2006-2014 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
 226 Distributed under the Boost Software
 227 License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
 228 LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
 229 http://www.boost.org/LICENSE_1_0.txt</a>)
 230 </p>
 231
 232 </body>
 233 </html>