| 1 | <HTML>
|
|---|
| 2 | <!--
|
|---|
| 3 | Copyright (c) Jeremy Siek 2000
|
|---|
| 4 | Copyright (c) Alex Hagen-Zanker 2012
|
|---|
| 5 |
|
|---|
| 6 | Distributed under the Boost Software License, Version 1.0.
|
|---|
| 7 | (See accompanying file LICENSE_1_0.txt or copy at
|
|---|
| 8 | http://www.boost.org/LICENSE_1_0.txt)
|
|---|
| 9 | -->
|
|---|
| 10 | <Head>
|
|---|
| 11 | <Title>Property Map Library</Title>
|
|---|
| 12 | <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
|
|---|
| 13 | ALINK="#ff0000">
|
|---|
| 14 | <IMG SRC="../../../boost.png"
|
|---|
| 15 | ALT="C++ Boost" width="277" height="86">
|
|---|
| 16 |
|
|---|
| 17 | <BR Clear>
|
|---|
| 18 |
|
|---|
| 19 | <H1><A NAME="sec:property-maps"></A>
|
|---|
| 20 | Boost Property Map Library
|
|---|
| 21 | </H1>
|
|---|
| 22 |
|
|---|
| 23 | <p>
|
|---|
| 24 | The Boost Property Map Library specifies concepts that define an
|
|---|
| 25 | interface for mapping key objects to value objects. Algorithms can
|
|---|
| 26 | take property maps as arguments relying on the concept definition
|
|---|
| 27 | and be ignorant of the underlying data structures. The algorithms can
|
|---|
| 28 | therefore be more generic.
|
|---|
| 29 | </p>
|
|---|
| 30 |
|
|---|
| 31 | <p>
|
|---|
| 32 | Besides concepts, the Boost Property Map Library also contains <a
|
|---|
| 33 | href="#sec:property-map-types">adaptors</a> that provide property map
|
|---|
| 34 | interfaces for commonly used data structures that implement a mapping
|
|---|
| 35 | operation, such as built-in arrays (pointers), iterators, and <code>std::map</code>.
|
|---|
| 36 | </p>
|
|---|
| 37 |
|
|---|
| 38 | <p>Property maps are statically-typed; you can use the <a
|
|---|
| 39 | href="dynamic_property_map.html"><code>dynamic_properties</code></a> class
|
|---|
| 40 | to access a set of property maps through a dynamically-typed interface (e.g.,
|
|---|
| 41 | when you read an unknown set of attributes from a file).</p>
|
|---|
| 42 |
|
|---|
| 43 |
|
|---|
| 44 | <h2><A NAME="sec:property-map-concepts"></A>
|
|---|
| 45 | Property Map Concepts
|
|---|
| 46 | </h2>
|
|---|
| 47 | <p>
|
|---|
| 48 | The property map concepts prescribe that <code>get()</code> and <code>put()</code>
|
|---|
| 49 | functions are provided that are used as if they are global functions; i.e,
|
|---|
| 50 | without a namespace qualifier. Furthermore, they prescribe <code>operator[]</code>
|
|---|
| 51 | to access value objects.
|
|---|
| 52 | </p>
|
|---|
| 53 |
|
|---|
| 54 | <p>
|
|---|
| 55 | The following example from shows the property map functions in use. The templated
|
|---|
| 56 | <code>fix_squares</code> function has a property map as parameter.</p>
|
|---|
| 57 |
|
|---|
| 58 | <pre>
|
|---|
| 59 | #include <iostream>
|
|---|
| 60 | #include <boost/property_map/property_map.hpp>
|
|---|
| 61 |
|
|---|
| 62 | template <typename T> void fix_squares(T squares) // assuming that T is a property map
|
|---|
| 63 | {
|
|---|
| 64 | typedef typename boost::property_traits<T>::value_type value_type;
|
|---|
| 65 |
|
|---|
| 66 | value_type answer1 = get(squares, 1); // <- use get() to get a value
|
|---|
| 67 | value_type& answer2 = squares[2]; // <- use operator[] to get a reference
|
|---|
| 68 | value_type& answer4 = get(squares, 4); // <- use get() to get a reference
|
|---|
| 69 |
|
|---|
| 70 | if(answer1 == 1) {
|
|---|
| 71 | std::cout << "right: 1 X 1 == " << answer1 << std::endl;<br> } else {
|
|---|
| 72 | std::cout << "wrong: 1 X 1 != " << answer1 << std::endl;
|
|---|
| 73 |
|
|---|
| 74 | put(squares, 1, 1); // <- use put() to set a value
|
|---|
| 75 | }
|
|---|
| 76 |
|
|---|
| 77 | if( answer2 == 4) {
|
|---|
| 78 | std::cout << "right: 2 X 2 == " << answer2 << std::endl << std::endl;
|
|---|
| 79 | } else {
|
|---|
| 80 | std::cout << "wrong: 2 X 2 != " << answer2 << std::endl<< std::endl;
|
|---|
| 81 |
|
|---|
| 82 | answer2 = 4; // <- answer2 is a reference, hence this works
|
|---|
| 83 | }
|
|---|
| 84 |
|
|---|
| 85 | if( answer4 == 16) {
|
|---|
| 86 | std::cout << "right: 4 X 4 == " << answer4 << std::endl << std::endl;
|
|---|
| 87 | } else {
|
|---|
| 88 | std::cout << "wrong: 4 X 4 != " << answer4 << std::endl<< std::endl;
|
|---|
| 89 |
|
|---|
| 90 | squares[4] = 16; // <- use operator[] to get a reference
|
|---|
| 91 | // get(squares, 4) = 16; // <- this would work, but using put() looks nicer
|
|---|
| 92 | }
|
|---|
| 93 | }</pre>
|
|---|
| 94 |
|
|---|
| 95 | <p>The following example creates a <a href="./vector_property_map.html"><code>vector_property_map</code></a>, and passes it to the <code>fix_squares</code> function twice:
|
|---|
| 96 | </p>
|
|---|
| 97 |
|
|---|
| 98 | <pre>
|
|---|
| 99 | #include <boost/property_map/property_map.hpp>
|
|---|
| 100 |
|
|---|
| 101 | int main()
|
|---|
| 102 | {
|
|---|
| 103 | boost::vector_property_map<int> squares;
|
|---|
| 104 |
|
|---|
| 105 | squares[1] = 2;
|
|---|
| 106 | squares[2] = 4;
|
|---|
| 107 | squares[4] = 16;
|
|---|
| 108 |
|
|---|
| 109 | fix_squares(squares); // first time to verify and fix mistakes
|
|---|
| 110 | fix_squares(squares); // second time to verify that all mistakes are fixed
|
|---|
| 111 |
|
|---|
| 112 | return EXIT_SUCCESS;
|
|---|
| 113 | }
|
|---|
| 114 | </pre>
|
|---|
| 115 |
|
|---|
| 116 | <p>This example creates an <a href="./associative_property_map.html"><code>associative_property_map</code></a> instead, and passes it to the <code>fix_squares</code> function too: </p>
|
|---|
| 117 |
|
|---|
| 118 | <pre>
|
|---|
| 119 | #include <map>
|
|---|
| 120 | #include <boost/property_map/property_map.hpp>
|
|---|
| 121 |
|
|---|
| 122 | int main()
|
|---|
| 123 | {
|
|---|
| 124 | std::map<int, int> squares;
|
|---|
| 125 | boost::associative_property_map< std::map<int, int> > squares_adapted(squares);
|
|---|
| 126 |
|
|---|
| 127 | squares[1] = 1;
|
|---|
| 128 | squares[2] = 3;
|
|---|
| 129 | squares[4] = 15;
|
|---|
| 130 |
|
|---|
| 131 | fix_squares(squares_adapted); // first time to verify and fix mistakes
|
|---|
| 132 | fix_squares(squares_adapted); // second time to verify that all mistakes are fixed
|
|---|
| 133 |
|
|---|
| 134 | return EXIT_SUCCESS;
|
|---|
| 135 | }
|
|---|
| 136 | </pre>
|
|---|
| 137 | <p>Each property map object has a set of <em>valid keys</em> for which the mapping to value objects is defined; <em>invalid</em> keys result in undefined behaviour. The property map concepts do not specify the set of valid keys. A function that uses a property map should specify the expected set of valid keys in its preconditions.</p>
|
|---|
| 138 | <p>
|
|---|
| 139 | There are four property map categories that provide different access capabilities and each has a concept definition:
|
|---|
| 140 | </p>
|
|---|
| 141 |
|
|---|
| 142 | <DL>
|
|---|
| 143 | <DT><STRONG>readable</STRONG></DT>
|
|---|
| 144 | <DD>
|
|---|
| 145 | <p>The associated property data can only be read, using the <code>get()</code> function. It is not prescribed whether the value is returned by reference or as a copy. See documentation of the concept <a href="./ReadablePropertyMap.html">ReadablePropertyMap</a> for details.
|
|---|
| 146 | </P>
|
|---|
| 147 | </DD>
|
|---|
| 148 | <DT><STRONG>writeable</STRONG></DT>
|
|---|
| 149 | <DD>
|
|---|
| 150 | <p>The associated property can only be written to, using the <code>put()</code> function. See documentation of the concept <a href="./WritablePropertyMap.html">WritablePropertyMap</a> for details.
|
|---|
| 151 | </P>
|
|---|
| 152 | </DD>
|
|---|
| 153 | <DT><STRONG>read/write</STRONG></DT>
|
|---|
| 154 | <DD>
|
|---|
| 155 | <p>The associated property can both be read, using the <code>get()</code> function, and written, usign the <code>put()</code> function. See documentation of the concept <a href="./ReadWritePropertyMap.html">ReadWritePropertyMap</a> for details.
|
|---|
| 156 | </P>
|
|---|
| 157 | </DD>
|
|---|
| 158 | <DT><STRONG>lvalue</STRONG></DT>
|
|---|
| 159 | <DD>
|
|---|
| 160 | <p>The property map gives access to the value object by reference using <code>operator[]</code> or the <code>get()</code> function; <code>put()</code> is also available. See documentation of the concept <a href="./LvaluePropertyMap.html">LvaluePropertyMap</a> for details.</P> </DD>
|
|---|
| 161 | </DL>
|
|---|
| 162 |
|
|---|
| 163 | <h2><a name="sec:property-map-tags">Property Map Category Tags</a></h2>
|
|---|
| 164 |
|
|---|
| 165 | <P>
|
|---|
| 166 | There is a tag struct for each of the categories of property
|
|---|
| 167 | maps, which is defined in the header
|
|---|
| 168 | <code><boost/property_map/property_map.hpp></code>.
|
|---|
| 169 |
|
|---|
| 170 | <PRE>namespace boost {
|
|---|
| 171 |
|
|---|
| 172 | struct readable_property_map_tag { };
|
|---|
| 173 |
|
|---|
| 174 | struct writable_property_map_tag { };
|
|---|
| 175 |
|
|---|
| 176 | struct read_write_property_map_tag :
|
|---|
| 177 | public readable_property_map_tag,
|
|---|
| 178 | public writable_property_map_tag { };
|
|---|
| 179 |
|
|---|
| 180 | struct lvalue_property_map_tag :
|
|---|
| 181 | public read_write_property_map_tag { };
|
|---|
| 182 |
|
|---|
| 183 | }</PRE>
|
|---|
| 184 |
|
|---|
| 185 | <h2><a name="sec:property-map-traits">Property Map Traits</a></h2>
|
|---|
| 186 |
|
|---|
| 187 | <P>
|
|---|
| 188 | There
|
|---|
| 189 | is a <code>boost::property_traits</code> class that can be used to deduce
|
|---|
| 190 | the types associated with a property map type: the key and value
|
|---|
| 191 | types, and the property map category.
|
|---|
| 192 |
|
|---|
| 193 | <PRE>namespace boost {
|
|---|
| 194 |
|
|---|
| 195 | template <typename PropertyMap>
|
|---|
| 196 | struct property_traits {
|
|---|
| 197 | typedef typename PropertyMap::key_type key_type;
|
|---|
| 198 | typedef typename PropertyMap::value_type value_type;
|
|---|
| 199 | typedef typename PropertyMap::category category;
|
|---|
| 200 | };
|
|---|
| 201 |
|
|---|
| 202 | }</PRE>
|
|---|
| 203 |
|
|---|
| 204 | <h2><a name="sec:property-map-types">Property Map Types</a></h2>
|
|---|
| 205 |
|
|---|
| 206 | <ul>
|
|---|
| 207 | <li>pointers.<br>
|
|---|
| 208 | Tthe functions <code>get()</code> and <code>put()</code> are overloaded for pointers in the header <code><boost/property_map/property_map.hpp></code>. Furthermore, there is a specialization
|
|---|
| 209 | of <code>boost::property_traits</code> so that pointers can be used as
|
|---|
| 210 | property map objects. Hence, it is
|
|---|
| 211 | possible to use built-in C++ pointer types as property maps;.more specifically,
|
|---|
| 212 | it means that <code>T*</code> is a model of <a
|
|---|
| 213 | href="./LvaluePropertyMap.html">LvaluePropertyMap</a>, of which the key
|
|---|
| 214 | type is <code>std::ptrdiff_t</code>.
|
|---|
| 215 | </li>
|
|---|
| 216 | <li><a href="./identity_property_map.html">identity_property_map</a> </li>
|
|---|
| 217 | <li><a href="./iterator_property_map.html">iterator_property_map</a></li>
|
|---|
| 218 | <li><a href="./shared_array_property_map.html">shared_array_property_map</a></li>
|
|---|
| 219 | <li><a href="./associative_property_map.html">associative_property_map</a></li>
|
|---|
| 220 | <li><a href="./const_assoc_property_map.html">const_associative_property_map</a></li>
|
|---|
| 221 | <li><a href="./vector_property_map.html">vector_property_map</a></li>
|
|---|
| 222 | <li><a href="./ref_property_map.html">ref_property_map</a> </li>
|
|---|
| 223 | </ul>
|
|---|
| 224 |
|
|---|
| 225 | <h3>History</h3>
|
|---|
| 226 |
|
|---|
| 227 | The property map interface originated as <i>data accessors</i> in
|
|---|
| 228 | Dietmar Kühl's Masters Thesis on generic graph algorithms. The
|
|---|
| 229 | property map idea also appeared under the guise of <i>decorators</i>
|
|---|
| 230 | in early versions of the Generic Graph Component Library (GGCL), which
|
|---|
| 231 | is now the Boost Graph Library (BGL). The main motivation for the
|
|---|
| 232 | property map interface was to support the access of data associated
|
|---|
| 233 | with vertices and edges in a graph, though the applicability of
|
|---|
| 234 | property maps goes beyond this.
|
|---|
| 235 |
|
|---|
| 236 | <h3>Acknowledgments</h3>
|
|---|
| 237 |
|
|---|
| 238 | Thanks go to Dietmar Kühl for coming up with this mechanism, and
|
|---|
| 239 | thanks go to the Boost members who helped refine and improve the
|
|---|
| 240 | property map interface. Thanks to Dave Abrahams for managing the
|
|---|
| 241 | formal review of the BGL which included the property map library.
|
|---|
| 242 |
|
|---|
| 243 | <h3>Notes to Implementors</h3>
|
|---|
| 244 |
|
|---|
| 245 | Copying a property map should be inexpensive, since they are often
|
|---|
| 246 | passed by value.
|
|---|
| 247 |
|
|---|
| 248 | <br>
|
|---|
| 249 | <HR>
|
|---|
| 250 | <TABLE>
|
|---|
| 251 | <TR valign=top>
|
|---|
| 252 | <TD width="180" nowrap>Copyright © 2000-2002</TD>
|
|---|
| 253 | <TD width="490">
|
|---|
| 254 | <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>)</TD></TR>
|
|---|
| 255 | <TR valign=top>
|
|---|
| 256 | <TD>Copyright © 2012</TD>
|
|---|
| 257 | <TD>Alex Hagen-Zanker</TD></TR></TABLE>
|
|---|
| 258 | <p> </p>
|
|---|
| 259 | </BODY>
|
|---|
| 260 | </HTML>
|
|---|
| 261 | <!-- LocalWords: ALT STL html genericity BGL ColorMap htm cpp iostream hpp hl
|
|---|
| 262 | -->
|
|---|
| 263 | <!-- LocalWords: typename AddressMap foo fred joe joes int writeable lvalue
|
|---|
| 264 | -->
|
|---|
| 265 | <!-- LocalWords: ReadablePropertyMap WritablePropertyMap ReadWritePropertyMap
|
|---|
| 266 | -->
|
|---|
| 267 | <!-- LocalWords: LvaluePropertyMap struct namespace PropertyMap pmap const
|
|---|
| 268 | -->
|
|---|
| 269 | <!-- LocalWords: val Dietmar hl's GGCL Abrahams
|
|---|
| 270 | -->
|
|---|
