Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/property_map/property_map.html @ 14

Last change on this file since 14 was 12, checked in by landauf, 17 years ago

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