ceph/src/boost/libs/property_map/doc/property_map.html

   1 <HTML>
   2 <!--
   3      Copyright (c) Jeremy Siek 2000
   4
   5      Distributed under the Boost Software License, Version 1.0.
   6      (See accompanying file LICENSE_1_0.txt or copy at
   7      http://www.boost.org/LICENSE_1_0.txt)
   8   -->
   9 <Head>
  10 <Title>Property Map Library</Title>
  11 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
  12         ALINK="#ff0000">
  13 <IMG SRC="../../../boost.png"
  14      ALT="C++ Boost" width="277" height="86">
  15
  16 <BR Clear>
  17
  18 <H1><A NAME="sec:property-maps"></A>
  19 Boost Property Map Library
  20 </H1>
  21
  22 <p>The Boost Property Map Library consists mainly of interface
  23 specifications in the form of concepts (similar to the iterator
  24 concepts in the STL <a
  25 href="http://www.sgi.com/tech/stl/stl_introduction.html">[2]</a>).
  26 These interface specifications are intended for use by implementors of
  27 generic libraries in communicating requirements on template parameters
  28 to their users.  In particular, the Boost Property Map concepts define
  29 a general purpose interface for mapping key objects to corresponding
  30 value objects, thereby hiding the details of how the mapping is
  31 implemented from algorithms. The implementation of types fulfilling
  32 the property map interface is up to the client of the algorithm to
  33 provide. The property map requirements are purposefully vague on the
  34 type of the key and value objects to allow for the utmost genericity
  35 in the function templates of the generic library.
  36 </p>
  37
  38 <p>
  39 The need for the property map interface came from the <a
  40 href="../../graph/doc/index.html">Boost Graph Library</a> (BGL), which
  41 contains many examples of algorithms that use the property map
  42 concepts to specify their interface. For an example, note the
  43 <tt>ColorMap</tt> template parameter of the <a
  44 href="../../graph/doc/breadth_first_search.html">
  45 <tt>breadth_first_search</tt></a>. In addition, the BGL contains many
  46 examples of concrete types that implement the property map interface.
  47 The <a href="../../graph/doc/adjacency_list.html">
  48 <tt>adjacency_list</tt></a> class implements property maps for
  49 accessing objects (properties) that are attached to vertices and edges
  50 of the graph.
  51 </p>
  52
  53 <p>
  54 The Boost Property Map Library also contains a <a
  55 href="#sec:property-map-types"> few adaptors</a> that convert commonly
  56 used data-structures that implement a mapping operation, such as
  57 builtin arrays (pointers), iterators, and <a
  58 href="http://www.sgi.com/tech/stl/Map.html"> <tt>std::map</tt></a>, to
  59 have the property map interface. These adaptors are not meant to
  60 fulfill all mapping needs, but are to serve as an example of how to
  61 implement the interface as well as covering a few common cases. See
  62 the header files for details.
  63 </p>
  64
  65 <p>Property maps are statically-typed entities. If you need to access
  66 property maps in a more dynamic setting (e.g., because you're reading
  67 an unknown set of attributes from a file), you can use the <a
  68 href="dynamic_property_map.html"><code>dynamic_properties</code></a>
  69 class to access a set of property maps through a dynamically-typed
  70 interface. </p>
  71
  72 <h2><A NAME="sec:property-map-concepts"></A>
  73 Property Map Concepts
  74 </h2>
  75
  76 The property map interface consists of a set of concepts (see
  77 definition of &quot;concept&quot; in <a
  78 href="../../concept_check/concept_check.htm#introduction">[1]</a> and <a
  79 href="http://www.sgi.com/tech/stl/stl_introduction.html">[2]</a>) that
  80 define a syntax for mapping key objects to corresponding value
  81 objects. Since the property map operations are global functions
  82 (actually they don't have to be global, but they are always called
  83 unqualified and may be found via argument dependent lookup), it is
  84 possible to overload the map functions such that nearly arbitrary
  85 property map types and key types can be used. The interface for
  86 property maps consists of three functions: <tt>get()</tt>,
  87 <tt>put()</tt>, and <tt>operator[]</tt>. The following concrete
  88 example from <a href="../example/example1.cpp">example1.cpp</a> shows how the
  89 three functions could be used to access the addresses associated with
  90 various people.  We use a separate function template here to highlight
  91 the parts of the program that use the property map concept
  92 interface. In the <tt>main()</tt> function we use <tt>std::map</tt>
  93 and <tt>boost::associative_property_map</tt>, but it would have been
  94 OK to use any type (including a custom type that you create) that
  95 fulfills the property map requirements.
  96
  97 <pre>#include &lt;iostream&gt;
  98 #include &lt;map&gt;
  99 #include &lt;string&gt;
 100 #include &lt;boost/property_map/property_map.hpp&gt;
 101
 102
 103 template &lt;typename AddressMap&gt;
 104 void foo(AddressMap address)
 105 {
 106   typedef typename boost::property_traits&lt;AddressMap&gt;::value_type value_type;
 107   typedef typename boost::property_traits&lt;AddressMap&gt;::key_type key_type;
 108
 109   value_type old_address, new_address;
 110   key_type fred = &quot;Fred&quot;;
 111   old_address = get(address, fred);
 112   new_address = &quot;384 Fitzpatrick Street&quot;;
 113   put(address, fred, new_address);
 114
 115   key_type joe = &quot;Joe&quot;;
 116   value_type&amp; joes_address = address[joe];
 117   joes_address = &quot;325 Cushing Avenue&quot;;
 118 }
 119
 120 int
 121 main()
 122 {
 123   std::map&lt;std::string, std::string&gt; name2address;
 124   boost::associative_property_map&lt; std::map&lt;std::string, std::string&gt; &gt;
 125     address_map(name2address);
 126
 127   name2address.insert(make_pair(std::string(&quot;Fred&quot;),
 128                                 std::string(&quot;710 West 13th Street&quot;)));
 129   name2address.insert(make_pair(std::string(&quot;Joe&quot;),
 130                                 std::string(&quot;710 West 13th Street&quot;)));
 131
 132   foo(address_map);
 133
 134   for (std::map&lt;std::string, std::string&gt;::iterator i = name2address.begin();
 135        i != name2address.end(); ++i)
 136     std::cout &lt;&lt; i-&gt;first &lt;&lt; &quot;: &quot; &lt;&lt; i-&gt;second &lt;&lt; &quot;\n&quot;;
 137
 138   return EXIT_SUCCESS;
 139 }</pre>
 140
 141 <p>
 142 For each property map object there is a set of <i>valid keys</i>
 143 for which the mapping to value objects is defined.  Invoking a
 144 property map function on an <i>invalid</i> key results in
 145 undefined behavior. The property map concepts do not specify how
 146 this set of valid keys is created or modified. A function that uses a
 147 property map must specify the expected set of valid keys in its
 148 preconditions.
 149
 150 <p>
 151 The need for property maps came out of the design of the Boost
 152 Graph Library, whose algorithms needed an interface for accessing
 153 properties attached to vertices and edges in a graph. In this context
 154 the vertex and edge descriptors are the key type of the property
 155 maps.
 156
 157 <!-- historical note about Decorators and Data Maps -->
 158
 159 <P>
 160 Several categories of property maps provide
 161 different access capabilities:
 162 <DL>
 163 <DT><STRONG>readable</STRONG></DT>
 164 <DD>The associated property data can only be read.
 165   The data is returned by-value. Many property maps defining the
 166   problem input (such as edge weight) can be defined as readable
 167   property maps.
 168
 169 <P>
 170 </DD>
 171 <DT><STRONG>writeable</STRONG></DT>
 172 <DD>The associated property can only be written to.
 173   The parent array used to record the paths in a bread-first search tree
 174   is an example of a property map that would be defined writeable.
 175
 176 <P>
 177 </DD>
 178 <DT><STRONG>read/write</STRONG></DT>
 179 <DD>The associated property can both be written and read.
 180   The distance property use in Dijkstra's shortest paths algorithm
 181   would need to provide both read and write capabilities.
 182
 183 <P>
 184 </DD>
 185 <DT><STRONG>lvalue</STRONG></DT>
 186 <DD>The associated property is actually represented in
 187   memory and it is possible to get a reference to it.
 188   The property maps in the lvalue
 189   category also support the requirements for read/write property
 190   maps.
 191
 192 <P>
 193 </DD>
 194 </DL>
 195
 196 <P>
 197 There is a separate concept defined for each of the four property
 198 map categories.  These property map concepts are listed
 199 below, with links to the documentation for each of them.
 200
 201 <ul>
 202 <li><a href="./ReadablePropertyMap.html">ReadablePropertyMap</a></li>
 203 <li><a href="./WritablePropertyMap.html">WritablePropertyMap</a></li>
 204 <li><a href="./ReadWritePropertyMap.html">ReadWritePropertyMap</a></li>
 205 <li><a href="./LvaluePropertyMap.html">LvaluePropertyMap</a></li>
 206 </ul>
 207
 208 <h2><a name="sec:property-map-tags">Property Map Category Tags</a></h2>
 209
 210 <P>
 211 There is a tag struct for each of the categories of property
 212 maps, which is defined in the header
 213 <tt>&lt;boost/property_map/property_map.hpp&gt;</tt>.
 214
 215 <PRE>namespace boost {
 216
 217   struct readable_property_map_tag { };
 218
 219   struct writable_property_map_tag { };
 220
 221   struct read_write_property_map_tag :
 222     public readable_property_map_tag,
 223     public writable_property_map_tag { };
 224
 225   struct lvalue_property_map_tag :
 226     public read_write_property_map_tag { };
 227
 228 }</PRE>
 229
 230 <h2><a name="sec:property-map-traits">Property Map Traits</a></h2>
 231
 232 <P>
 233 Similar to the <TT>std::iterator_traits</TT> class of the STL, there
 234 is a <TT>boost::property_traits</TT> class that can be used to deduce
 235 the types associated with a property map type: the key and value
 236 types, and the property map category. There is a specialization
 237 of <TT>boost::property_traits</TT> so that pointers can be used as
 238 property map objects. In addition, the property map
 239 functions are overloaded for pointers. These traits classes and
 240 functions are defined in <tt>&lt;boost/property_map/property_map.hpp&gt;</tt>.
 241
 242 <PRE>namespace boost {
 243
 244   template &lt;typename PropertyMap&gt;
 245   struct property_traits {
 246      typedef typename PropertyMap::key_type key_type;
 247      typedef typename PropertyMap::value_type value_type;
 248      typedef typename PropertyMap::reference reference;
 249      typedef typename PropertyMap::category category;
 250   };
 251
 252 }</PRE>
 253
 254 <h2><a name="sec:property-map-types">Property Map Types</a></h2>
 255
 256 <ul>
 257   <li>Builtin C++ pointer types.<br>
 258
 259     The following specialization of the <tt>property_traits</tt> class
 260     and the overloads of <tt>put()</tt> and <tt>get()</tt> make it
 261     possible to use builtin C++ pointer types as property maps. These
 262     are defined in <tt>boost/property_map/property_map.hpp</tt>. More specifically,
 263     it means that <tt>T*</tt> is a model of <a
 264     href="./LvaluePropertyMap.html">LvaluePropertyMap</a>, given a key
 265     type that is at least convertible <tt>std::ptrdiff_t</tt>.
 266
 267 <PRE>namespace boost {
 268   // specialization for using pointers as property maps
 269   template &lt;typename T&gt;
 270   struct property_traits&lt;T*&gt; {
 271     typedef T value_type;
 272     typedef T&amp; reference;
 273     typedef std::ptrdiff_t key_type;
 274     typedef random_access_iterator_pa_tag category;
 275   };
 276
 277   // overloads of the property map functions for pointers
 278   template&lt;&gt;
 279   void put(T* pmap, std::ptrdiff_t k, const T&amp; val) { pmap[k] = val;  }
 280
 281   template&lt;&gt;
 282   const T&amp; get(const T* pmap, std::ptrdiff_t k) { return pmap[k]; }
 283
 284 }</PRE>
 285   </li>
 286   <li><a href="./identity_property_map.html">identity_property_map and typed_identity_property_map</a> </li>
 287   <li><a href="./function_property_map.html">function_property_map</a> </li>
 288   <li><a href="./iterator_property_map.html">iterator_property_map</a></li>
 289   <li><a href="./shared_array_property_map.html">shared_array_property_map</a></li>
 290   <li><a href="./associative_property_map.html">associative_property_map</a></li>
 291   <li><a href="./const_assoc_property_map.html">const_associative_property_map</a></li>
 292   <li><a href="./vector_property_map.html">vector_property_map</a></li>
 293   <li><a href="./ref_property_map.html">ref_property_map</a> </li>
 294   <li><a href="./static_property_map.html">static_property_map</a> </li>
 295   <li><a href="./transform_value_property_map.html">transform_value_property_map</a> </li>
 296   <li><a href="./compose_property_map.html">compose_property_map</a> </li>
 297 </ul>
 298
 299 <h3>History</h3>
 300
 301 The property map interface originated as <i>data accessors</i> in
 302 Dietmar K&uuml;hl's Masters Thesis on generic graph algorithms.  The
 303 property map idea also appeared under the guise of <i>decorators</i>
 304 in early versions of the Generic Graph Component Library (GGCL), which
 305 is now the Boost Graph Library (BGL).  The main motivation for the
 306 property map interface was to support the access of data associated
 307 with vertices and edges in a graph, though the applicability of
 308 property maps goes beyond this.
 309
 310 <h3>Acknowledgments</h3>
 311
 312 Thanks go to Dietmar K&uuml;hl for coming up with this mechanism, and
 313 thanks go to the Boost members who helped refine and improve the
 314 property map interface. Thanks to Dave Abrahams for managing the
 315 formal review of the BGL which included the property map library.
 316
 317 <h3>Notes to Implementors</h3>
 318
 319 Copying a property map should be inexpensive since they are often
 320 passed by value.
 321
 322 <br>
 323 <HR>
 324 <TABLE>
 325 <TR valign=top>
 326 <TD nowrap>Copyright &copy; 2000-2002</TD><TD>
 327 <a HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
 328 </TD></TR></TABLE>
 329
 330 </BODY>
 331 </HTML>
 332 <!--  LocalWords:  ALT STL html genericity BGL ColorMap htm cpp iostream hpp hl
 333  -->
 334 <!--  LocalWords:  typename AddressMap foo fred joe joes int writeable lvalue
 335  -->
 336 <!--  LocalWords:  ReadablePropertyMap WritablePropertyMap ReadWritePropertyMap
 337  -->
 338 <!--  LocalWords:  LvaluePropertyMap struct namespace PropertyMap pmap const
 339  -->
 340 <!--  LocalWords:  val Dietmar hl's GGCL Abrahams
 341  -->