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> 19Boost Property Map Library 20</H1> 21 22<p>The Boost Property Map Library consists mainly of interface 23specifications in the form of concepts (similar to the iterator 24concepts in the STL <a 25href="http://www.sgi.com/tech/stl/stl_introduction.html">[2]</a>). 26These interface specifications are intended for use by implementors of 27generic libraries in communicating requirements on template parameters 28to their users. In particular, the Boost Property Map concepts define 29a general purpose interface for mapping key objects to corresponding 30value objects, thereby hiding the details of how the mapping is 31implemented from algorithms. The implementation of types fulfilling 32the property map interface is up to the client of the algorithm to 33provide. The property map requirements are purposefully vague on the 34type of the key and value objects to allow for the utmost genericity 35in the function templates of the generic library. 36</p> 37 38<p> 39The need for the property map interface came from the <a 40href="../../graph/doc/index.html">Boost Graph Library</a> (BGL), which 41contains many examples of algorithms that use the property map 42concepts to specify their interface. For an example, note the 43<tt>ColorMap</tt> template parameter of the <a 44href="../../graph/doc/breadth_first_search.html"> 45<tt>breadth_first_search</tt></a>. In addition, the BGL contains many 46examples of concrete types that implement the property map interface. 47The <a href="../../graph/doc/adjacency_list.html"> 48<tt>adjacency_list</tt></a> class implements property maps for 49accessing objects (properties) that are attached to vertices and edges 50of the graph. 51</p> 52 53<p> 54The Boost Property Map Library also contains a <a 55href="#sec:property-map-types"> few adaptors</a> that convert commonly 56used data-structures that implement a mapping operation, such as 57builtin arrays (pointers), iterators, and <a 58href="http://www.sgi.com/tech/stl/Map.html"> <tt>std::map</tt></a>, to 59have the property map interface. These adaptors are not meant to 60fulfill all mapping needs, but are to serve as an example of how to 61implement the interface as well as covering a few common cases. See 62the header files for details. 63</p> 64 65<p>Property maps are statically-typed entities. If you need to access 66property maps in a more dynamic setting (e.g., because you're reading 67an unknown set of attributes from a file), you can use the <a 68href="dynamic_property_map.html"><code>dynamic_properties</code></a> 69class to access a set of property maps through a dynamically-typed 70interface. </p> 71 72<h2><A NAME="sec:property-map-concepts"></A> 73Property Map Concepts 74</h2> 75 76The property map interface consists of a set of concepts (see 77definition of "concept" in <a 78href="../../concept_check/concept_check.htm#introduction">[1]</a> and <a 79href="http://www.sgi.com/tech/stl/stl_introduction.html">[2]</a>) that 80define a syntax for mapping key objects to corresponding value 81objects. Since the property map operations are global functions 82(actually they don't have to be global, but they are always called 83unqualified and may be found via argument dependent lookup), it is 84possible to overload the map functions such that nearly arbitrary 85property map types and key types can be used. The interface for 86property maps consists of three functions: <tt>get()</tt>, 87<tt>put()</tt>, and <tt>operator[]</tt>. The following concrete 88example from <a href="../example/example1.cpp">example1.cpp</a> shows how the 89three functions could be used to access the addresses associated with 90various people. We use a separate function template here to highlight 91the parts of the program that use the property map concept 92interface. In the <tt>main()</tt> function we use <tt>std::map</tt> 93and <tt>boost::associative_property_map</tt>, but it would have been 94OK to use any type (including a custom type that you create) that 95fulfills the property map requirements. 96 97<pre>#include <iostream> 98#include <map> 99#include <string> 100#include <boost/property_map/property_map.hpp> 101 102 103template <typename AddressMap> 104void foo(AddressMap address) 105{ 106 typedef typename boost::property_traits<AddressMap>::value_type value_type; 107 typedef typename boost::property_traits<AddressMap>::key_type key_type; 108 109 value_type old_address, new_address; 110 key_type fred = "Fred"; 111 old_address = get(address, fred); 112 new_address = "384 Fitzpatrick Street"; 113 put(address, fred, new_address); 114 115 key_type joe = "Joe"; 116 value_type& joes_address = address[joe]; 117 joes_address = "325 Cushing Avenue"; 118} 119 120int 121main() 122{ 123 std::map<std::string, std::string> name2address; 124 boost::associative_property_map< std::map<std::string, std::string> > 125 address_map(name2address); 126 127 name2address.insert(make_pair(std::string("Fred"), 128 std::string("710 West 13th Street"))); 129 name2address.insert(make_pair(std::string("Joe"), 130 std::string("710 West 13th Street"))); 131 132 foo(address_map); 133 134 for (std::map<std::string, std::string>::iterator i = name2address.begin(); 135 i != name2address.end(); ++i) 136 std::cout << i->first << ": " << i->second << "\n"; 137 138 return EXIT_SUCCESS; 139}</pre> 140 141<p> 142For each property map object there is a set of <i>valid keys</i> 143for which the mapping to value objects is defined. Invoking a 144property map function on an <i>invalid</i> key results in 145undefined behavior. The property map concepts do not specify how 146this set of valid keys is created or modified. A function that uses a 147property map must specify the expected set of valid keys in its 148preconditions. 149 150<p> 151The need for property maps came out of the design of the Boost 152Graph Library, whose algorithms needed an interface for accessing 153properties attached to vertices and edges in a graph. In this context 154the vertex and edge descriptors are the key type of the property 155maps. 156 157<!-- historical note about Decorators and Data Maps --> 158 159<P> 160Several categories of property maps provide 161different 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> 197There is a separate concept defined for each of the four property 198map categories. These property map concepts are listed 199below, 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> 211There is a tag struct for each of the categories of property 212maps, which is defined in the header 213<tt><boost/property_map/property_map.hpp></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> 233Similar to the <TT>std::iterator_traits</TT> class of the STL, there 234is a <TT>boost::property_traits</TT> class that can be used to deduce 235the types associated with a property map type: the key and value 236types, and the property map category. There is a specialization 237of <TT>boost::property_traits</TT> so that pointers can be used as 238property map objects. In addition, the property map 239functions are overloaded for pointers. These traits classes and 240functions are defined in <tt><boost/property_map/property_map.hpp></tt>. 241 242<PRE>namespace boost { 243 244 template <typename PropertyMap> 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 <typename T> 270 struct property_traits<T*> { 271 typedef T value_type; 272 typedef T& 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<> 279 void put(T* pmap, std::ptrdiff_t k, const T& val) { pmap[k] = val; } 280 281 template<> 282 const T& 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 301The property map interface originated as <i>data accessors</i> in 302Dietmar Kühl's Masters Thesis on generic graph algorithms. The 303property map idea also appeared under the guise of <i>decorators</i> 304in early versions of the Generic Graph Component Library (GGCL), which 305is now the Boost Graph Library (BGL). The main motivation for the 306property map interface was to support the access of data associated 307with vertices and edges in a graph, though the applicability of 308property maps goes beyond this. 309 310<h3>Acknowledgments</h3> 311 312Thanks go to Dietmar Kühl for coming up with this mechanism, and 313thanks go to the Boost members who helped refine and improve the 314property map interface. Thanks to Dave Abrahams for managing the 315formal review of the BGL which included the property map library. 316 317<h3>Notes to Implementors</h3> 318 319Copying a property map should be inexpensive since they are often 320passed by value. 321 322<br> 323<HR> 324<TABLE> 325<TR valign=top> 326<TD nowrap>Copyright © 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 --> 342
