Ticket #6538: property_map.3.html

File property_map.3.html, 15.1 KB (added by Alex Hagen-Zanker <ahh34@…>, 7 years ago)

a more rigorous rewrite

Line 
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>
20Boost Property Map Library
21</H1>
22
23<p>
24The Boost Property Map Library specifies concepts that define an
25interface for mapping key objects to value objects. Algorithms can
26take property maps as arguments relying on the concept definition
27and be ignorant of the underlying data structures. The algorithms can
28therefore be more generic. The property map concepts offer <code>get()</code> and <code>put()</code> functions  that are used as if they are global functions; i.e,
29without a namespace qualifier. Furthermore, they can offer <code>operator[]</code> to access value objects. </p>
30
31<p>
32Besides concepts, the Boost Property Map Library also contains  <a
33href="#sec:property-map-types">property map types</a> that provide property map
34interfaces for commonly used data structures, such as arrays, iterators, and associative maps.
35</p>
36
37<p>Property maps are statically-typed; you can use the <a
38href="dynamic_property_map.html"><code>dynamic_properties</code></a> class
39to access a set of property maps through a dynamically-typed interface (e.g.,
40when you read an unknown set of attributes from a file).</p>
41
42
43<h2><A NAME="sec:example"></A> Example </h2>
44<p>The following example from shows the property map functions in use. The templated <code>fix_squares</code> function has a property map as parameter. </p>
45<pre>
46#include &lt;iostream&gt;
47#include &lt;boost/property_map/property_map.hpp&gt;
48
49template &lt;typename T&gt; void fix_squares(T squares) // assuming that T is a property map
50{
51  typedef typename boost::property_traits&lt;T&gt;::value_type value_type;
52 
53  value_type answer1 = get(squares, 1);    // &lt;- use get() to get a value
54  value_type&amp; answer2 = squares[2];        // &lt;- use operator[] to get a reference 
55  //value_type&amp; answer2 = get(squares, 2); // &lt;- this would work too 
56
57  bool all_correct = true;
58  if(answer1 != 1) {
59    all_correct = false;
60    put(squares, 1, 1);                    // &lt;- use put() to set a value
61  }
62 
63  if( answer2 != 4) {
64    all_correct = false;         
65    answer2 = 4;                           // &lt;- answer2 is a reference, hence this works
66    // squares[2] = 4;                     // &lt;- this would work too
67    // get(squares, 2) = 4;                // &lt;- this would work too
68  }
69
70  std::cout &lt;&lt; all_correct ? &quot;yes, all correct&quot; : &quot;no, something was wrong&quot; &lt;&lt; std::endl;
71
72}</pre>
73<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: </p>
74<pre>
75int main()
76{
77  boost::vector_property_map&lt;int&gt; squares;
78 
79  squares[1] = 2;
80  squares[2] = 4;
81 
82  fix_squares(squares); // first time to verify and fix mistakes
83  fix_squares(squares); // second time to verify that all mistakes are fixed
84 
85  return EXIT_SUCCESS;
86}
87</pre>
88<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>
89<pre>
90#include &lt;map&gt;
91
92int main()
93{
94  std::map&lt;int, int&gt; squares;
95  boost::associative_property_map&lt; std::map&lt;int, int&gt; &gt; squares_adapted(squares);
96
97  squares[1] = 1;
98  squares[2] = 3;
99
100  fix_squares(squares_adapted); // first time to verify and fix mistakes
101  fix_squares(squares_adapted); // second time to verify that all mistakes are fixed
102 
103  return EXIT_SUCCESS;
104}</pre>
105<h2><A NAME="sec:property-map-concepts"></A>
106        Property Map Concepts
107</h2>
108<p>
109        To differentiate between different forms of access, there are four property map concepts.
110The following table gives an overview of the property map concepts and the forms
111of access that they must offer:</p>
112
113<table width="782" height="258" border="1">
114        <tr>
115                <td width="452">&nbsp;</td>
116                <td width="80"><code>Readable..</code></td>
117                <td width="80"><code>Writable..</code></td>
118                <td width="80"><code>ReadWrite..</code></td>
119                <td width="64"><code>Lvalue..</code></td>
120                <td width="72"><code>Mutable..</code></td>
121        </tr>
122        <tr>
123                <td><code>value_type v = get(pmap, key);</code></td>
124                <td><p align="center">X</p></td>
125                <td>&nbsp;</td>
126                <td><p align="center">X</p></td>
127                <td><p align="center">X</p></td>
128                <td><p align="center">X</p></td>
129        </tr>
130        <tr>
131                <td><code>value_type&amp; v = get(pmap, key); </code></td>
132                <td>&nbsp;</td>
133                <td>&nbsp;</td>
134                <td>&nbsp;</td>
135                <td><p align="center"></p></td>
136                <td><p align="center">X</p></td>
137        </tr>
138        <tr>
139                <td><code>value_type&amp; v = pmap[key];</code></td>
140                <td>&nbsp;</td>
141                <td><p align="center"></p></td>
142                <td><p align="center"></p></td>
143                <td><p align="center"></p></td>
144                <td><p align="center">X</p></td>
145        </tr>
146        <tr>
147                <td><code>const value_type&amp; v = get(pmap, key); </code></td>
148                <td><p align="center"></p></td>
149                <td><p align="center"></p></td>
150                <td><p align="center"></p></td>
151                <td><p align="center">X</p></td>
152                <td><p align="center">X</p></td>
153        </tr>
154        <tr>
155                <td><code>const value_type&amp; v = pmap[key];</code></td>
156                <td><p align="center"></p></td>
157                <td><p align="center"></p></td>
158                <td><p align="center"></p></td>
159                <td><p align="center">X</p></td>
160                <td><p align="center">X</p></td>
161        </tr>
162        <tr>
163                <td><code>put(pmap, key, value);</code></td>
164                <td><p align="center"></p></td>
165                <td><p align="center">X</p></td>
166                <td><p align="center">X</p></td>
167                <td><p align="center"></p></td>
168                <td><p align="center">X</p></td>
169        </tr>
170</table>
171<p>Where <code>pmap</code> is a property map object, <code>key</code> is a <code>key_type</code> object
172and <code>value</code> is a <code>value_type</code> object; all parameters are passed as const reference;
173and the following abbreviations are used to indicate property map concepts:</p>
174<table width="623" border="1">
175        <tr>
176                <td width="80">Abbrevation</td>
177                <td width="256">Full concept name</td>
178                <td width="265">Further details</td>
179        </tr>
180        <tr>
181                <td><code>Readable..</code></td>
182                <td><code>ReadablePropertyMapConcept</code></td>
183                <td><a href="./ReadablePropertyMap.html">readable property map concept</a></td>
184        </tr>
185        <tr>
186                <td><code>Writable..</code></td>
187                <td><code>WriteablePropertyMapConcept</code></td>
188                <td><a href="./WritablePropertyMap.html">writable property map concept</a></td>
189        </tr>
190        <tr>
191                <td><code>ReadWrite..</code></td>
192                <td><code>ReadWritePropertyMapConcept</code></td>
193                <td><a href="./ReadWritePropertyMap.html">read- and writable property map concept</a></td>
194        </tr>
195        <tr>
196                <td><code>LValue..</code></td>
197                <td><code>LvaluePropertyMapConcept</code></td>
198                <td><a href="./LvaluePropertyMap.html">lvalue property map concepts</code></a></td>
199        </tr>
200        <tr>
201                <td><code>Mutable..</code></td>
202                <td><code>Mutable_LvaluePropertyMapConcept</code></td>
203                <td><a href="./LvaluePropertyMap.html">lvalue property map concepts</code></a></td>
204        </tr>
205</table>
206<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>
207<h2><a name="sec:property-map-traits">Property Map Traits</a></h2>
208<P> There is a <code>boost::property_traits</code> class that can be used to deduce the types associated with a property map type. The following table gives an overview and the requirements on the trait types:
209<table width="968" height="359" border="1">
210        <tr>
211                <td width="320">&nbsp;</td>
212                <td width="208">Purpose</td>
213                <td width="418">Restrictions</td>
214        </tr>
215        <tr>
216                <td><p align="left"><code>boost::property_traits&lt;PMap&gt;::value_type</code></p></td>
217                <td><p align="left">the value type of the map</p></td>
218                <td><p align="left">any type</p></td>
219        </tr>
220        <tr>
221                <td><p align="left"><code>boost::property_traits&lt;PMap&gt;::key_type</code></p></td>
222                <td><p align="left">the key type of the map</p></td>
223                <td><p align="left">any type</p></td>
224        </tr>
225        <tr>
226                <td><p align="left"><code>boost::property_traits&lt;PMap&gt;::category</code></p></td>
227                <td><p align="left">the tag for the type of access by the map. See the next section for definitions of category tags.</p></td>
228                <td>
229                        <table width="200" border="1">
230                                <tr>
231                                        <td>Concept...</td>
232                                        <td>requires type convertible to:</td>
233                                </tr>
234                                <tr>
235                                        <td><code>Readable..</code></td>
236                                        <td><code>readable_property_map_tag</code></td>
237                                </tr>
238                                <tr>
239                                        <td><code>Writable..</code></td>
240                                        <td><code>writable_property_map_tag</code></td>
241                                </tr>
242                                <tr>
243                                        <td><code>ReadWrite..</code></td>
244                                        <td><code>read_write_property_map_tag</code></td>
245                                </tr>
246                                <tr>
247                                        <td><code>LValue..</code></td>
248                                        <td><code>lvalue_property_map_tag</code></td>
249                                </tr>
250                                <tr>
251                                        <td><code>Mutable..</code></td>
252                                        <td><code>lvalue_property_map_tag</code></td>
253                                </tr>
254                        </table>
255                </td>
256        </tr>
257        <tr>
258                <td height="143"><div align="left"><code>boost::property_traits&lt;PMap&gt;::reference</code></div></td>
259                <td>the return type of <code>get()</code> and <code>operator[]</code></td>
260                <td>
261                        <table width="397" border="1">
262                                <tr>
263                                        <td>Concept...</td>
264                                        <td>requires</td>
265                                </tr>
266                                <tr>
267                                        <td width="80"><code>Readable..</code></td>
268                                        <td width="301">assignable to <code>value_type</code></td>
269                                        </tr>
270                                <tr>
271                                        <td><code>Writable..</code></td>
272                                        <td>does not require this trait</td>
273                                        </tr>
274                                <tr>
275                                        <td><code>ReadWrite..</code></td>
276                                        <td>assignable to <code>value_type</code></td>
277                                        </tr>
278                                <tr>
279                                        <td><code>LValue..</code></td>
280                                        <td><code>const value_type&amp;</code> or <code>value_type&amp;</code></td>
281                                        </tr>
282                                <tr>
283                                        <td><code>Mutable..</code></td>
284                                        <td><code>value_type&amp;</code></td>
285                                        </tr>
286                        </table>
287                </td>
288        </tr>
289</table>
290<p><em>Note:</em>There is no separate property tag for <code>Mutable_LvaluePropertyMapConcept</code>. And, even though <code>lvalue_property_map_tag</code> is convertible to <code>writable_property_map_tag</code> it does not necessarily indicate that a map of this category complies to <code>WriteablePropertyMapConcept</code>.</p>
291<h2><a name="sec:property-map-tags">Property Map Category Tags</a></h2>
292<P> There is a tag struct for each of the categories of property
293        maps, which is defined in the header <code>&lt;boost/property_map/property_map.hpp&gt;</code>.
294       
295<PRE>
296namespace boost {
297
298  struct readable_property_map_tag { };
299
300  struct writable_property_map_tag { };
301
302  struct read_write_property_map_tag :
303    public readable_property_map_tag,
304    public writable_property_map_tag { };
305
306  struct lvalue_property_map_tag :
307    public read_write_property_map_tag { };
308
309}</PRE>
310<h2><a name="sec:property-map-types">Property Map Types</a></h2>
311<p>The property map library provides several specific property map types that are listed in the table below. Furthermore, the header <code>&lt;boost/property_map/property_map.hpp&gt;</code> for pointers and provides the <code>boost::property_trait</code> and<code>get()</code> and <code>put()</code> functions for built-in C++ pointers, which means that <code>T*</code> is a model of Mutable_LvaluePropertyMapConcept, with  key
312        type <code>std::ptrdiff_t.</code></p>
313<table width="695" border="1">
314        <tr>
315                <td width="199">Property map </td>
316                <td width="480">Summary</td>
317        </tr>
318        <tr>
319                <td><a href="./identity_property_map.html">identity_property_map</a></td>
320                <td>returns a copy of the key as value.</td>
321        </tr>
322        <tr>
323                <td><a href="./iterator_property_map.html">iterator_property_map</a></td>
324                <td>converts any random access  iterator into a lvalue property map</td>
325        </tr>
326        <tr>
327                <td><a href="./vector_property_map.html">vector_property_map</a></td>
328                <td>keeps its data in a dynamically resized vector</td>
329        </tr>
330        <tr>
331                <td><a href="./shared_array_property_map.html">shared_array_property_map</a></td>
332                <td> keeps its data in a fixed-size <a href="file:///C:/Users/ahh34/Development/Third_party/boost-svn/property_map/smart_ptr/shared_array.htm">boost::shared_array</a></td>
333        </tr>
334        <tr>
335                <td><a href="./associative_property_map.html">associative_property_map</a></td>
336                <td>wraps around a <a href="http://www.sgi.com/tech/stl/PairAssociativeContainer.html">Pair  Associative Container</a> or <a href="http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html">Unique  Associative Container</a> such as <a href="http://www.sgi.com/tech/stl/Map.html">std::map</a></td>
337        </tr>
338        <tr>
339                <td><a href="./const_assoc_property_map.html">const_associative_property_map</a></td>
340                <td>as above but non-mutable</td>
341        </tr>
342        <tr>
343                <td><a href="./ref_property_map.html">ref_property_map</a></td>
344                <td>wraps a reference to one particular object, and  returns that reference whenever a key object is input.</td>
345        </tr>
346</table>
347<h3>History</h3>
348
349The property map interface originated as <i>data accessors</i> in
350Dietmar K&uuml;hl's Masters Thesis on generic graph algorithms.  The
351property map idea also appeared under the guise of <i>decorators</i>
352in early versions of the Generic Graph Component Library (GGCL), which
353is now the Boost Graph Library (BGL).  The main motivation for the
354property map interface was to support the access of data associated
355with vertices and edges in a graph, though the applicability of
356property maps goes beyond this.
357
358<h3>Acknowledgments</h3>
359
360Thanks go to Dietmar K&uuml;hl for coming up with this mechanism, and
361thanks go to the Boost members who helped refine and improve the
362property map interface. Thanks to Dave Abrahams for managing the
363formal review of the BGL which included the property map library.
364
365<h3>Notes to Implementors</h3>
366
367Copying a property map should be inexpensive, since they are often
368passed by value.
369<br>
370<HR>
371<TABLE>
372<TR valign=top>
373<TD width="180" nowrap>Copyright &copy 2000-2002</TD>
374<TD width="490">
375<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>
376<TR valign=top>
377<TD>Copyright &copy 2012</TD>
378<TD>Alex Hagen-Zanker</TD></TR></TABLE>
379<p>&nbsp;</p>
380</BODY>
381</HTML> 
382<!--  LocalWords:  ALT STL html genericity BGL ColorMap htm cpp iostream hpp hl
383 -->
384<!--  LocalWords:  typename AddressMap foo fred joe joes int writeable lvalue
385 -->
386<!--  LocalWords:  ReadablePropertyMap WritablePropertyMap ReadWritePropertyMap
387 -->
388<!--  LocalWords:  LvaluePropertyMap struct namespace PropertyMap pmap const
389 -->
390<!--  LocalWords:  val Dietmar hl's GGCL Abrahams
391 -->