1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
|
<HTML>
<!--
-- Copyright (c) Jeremy Siek 2000
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. Silicon Graphics makes no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
-->
<Head>
<Title>Property Map Library</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="../../c++boost.gif"
ALT="C++ Boost" width="277" height="86">
<BR Clear>
<H1><A NAME="sec:property-maps"></A>
Boost Property Map Library
</H1>
The Boost Property Map Library is a small library that addresses the
need to provide a generic interface for mapping between objects. Most
of the library is the interface definition, captured as a <a
href="#sec:property-map-concepts">set of concepts</a>. In addition
there are supporting <a href="#sec:property-map-tags">category
tags</a> and a <a href="#sec:property-map-traits">traits class</a>, as
well as <a href="#sec:property-map-types">some types</a> that
implement the property map interface. These classes are not meant to
fulfill all mapping needs, but more to serve as an example of how to
implement the interface as well as covering a few common cases.
<h2><A NAME="sec:property-map-concepts"></A>
Property Map Concepts
</h2>
The property map interface consists of a set of concepts (see
definition of "concept" in <a
href="../concept_check/concept_check.htm#introduction">[1]</a> and <a
href="http://www.sgi.com/Technology/STL/stl_introduction.html">[2]</a>)
that define a general purpose mechanism for mapping key objects to
corresponding value objects, thereby hiding the details of how the
mapping is implemented from algorithms that use property maps. The
property map requirements are purposefully vague on the type of the
key and value objects to allow for the utmost flexibility. Since the
property map operations are global functions, it is possible to
overload the map functions such that nearly arbitrary property map
types and key types can be used. The interface for property maps
consists of three functions: <tt>get()</tt>, <tt>put()</tt>, and
<tt>operator[]</tt>. The following concrete example shows how the
three functions could be used to access the addresses associated with
various people.
<pre>template <class AddressMap>
void foo(AddressMap address)
{
typedef typename boost::property_traits<AddressMap>::value_type value_type;
typedef typename boost::property_traits<AddressMap>::key_type key_type;
value_type old_address, new_address;
key_type fred = "Fred";
old_address = get(address, fred);
new_address = "384 Fitzpatrick Street"
put(address, fred, new_address);
key_type joe = "Joe";
value_type& joes_address = address[joe];
joes_address = "325 Cushing Avenue";
}</pre>
<p>
For each property map object there is a set of <i>valid keys</i>
for which the mapping to value objects is defined. Invoking a
property map function on an <i>invalid</i> key results in
undefined behavior. The property map concepts do not specify how
this set of valid keys is created or modified. A function that uses a
property map must specify the expected set of valid keys in its
preconditions.
<p>
The need for property maps came out of the design of the Boost
Graph Library, whose algorithms needed an interface for accessing
properties attached to vertices and edges in a graph. In this context
the vertex and edge descriptors are the key type of the property
maps.
<!-- historical note about Decorators and Data Maps -->
<P>
Several categories of property maps provide
different access capabilities:
<DL>
<DT><STRONG>readable</STRONG></DT>
<DD>The associated property data can only be read.
The data is returned by-value. Many property maps defining the
problem input (such as edge weight) can be defined as readable
property maps.
<P>
</DD>
<DT><STRONG>writeable</STRONG></DT>
<DD>The associated property can only be written to.
The parent array used to record the paths in a bread-first search tree
is an example of a property map that would be defined writeable.
<P>
</DD>
<DT><STRONG>read/write</STRONG></DT>
<DD>The associated property can both be written and read.
The distance property use in Dijkstra's shortest paths algorithm
would need to provide both read and write capabilities.
<P>
</DD>
<DT><STRONG>lvalue</STRONG></DT>
<DD>The associated property is actually represented in
memory and it is possible to get a reference to it.
The property maps in the lvalue
category also support the requirements for read/write property
maps.
<P>
</DD>
</DL>
<P>
There is a separate concept defined for each of the four property
map categories. These property map concepts are listed
below, with links to the documentation for each of them.
<ul>
<li><a href="./ReadablePropertyMap.html">ReadablePropertyMap</a></li>
<li><a href="./WritablePropertyMap.html">WritablePropertyMap</a></li>
<li><a href="./ReadWritePropertyMap.html">ReadWritePropertyMap</a></li>
<li><a href="./LvaluePropertyMap.html">LvaluePropertyMap</a></li>
</ul>
<h2><a name="sec:property-map-tags">Property Map Category Tags</a></h2>
<P>
There is a tag struct for each of the categories of property
maps, which is defined in the header
<tt><boost/property_map.hpp></tt>.
<PRE>namespace boost {
struct readable_property_map_tag { };
struct writable_property_map_tag { };
struct read_write_property_map_tag :
public readable_property_map_tag,
public writable_property_map_tag { };
struct lvalue_property_map_tag :
public read_write_property_map_tag { };
}</PRE>
<h2><a name="sec:property-map-traits">Property Map Traits</a></h2>
<P>
Similar to the <TT>std::iterator_traits</TT> class of the STL, there
is a <TT>boost::property_traits</TT> class that can be used to deduce
the types associated with a property map type: the key and value
types, and the property map category. There is a specialization
of <TT>boost::property_traits</TT> so that pointers can be used as
property map objects. In addition, the property map
functions are overloaded for pointers. These traits classes and
functions are defined in <tt><boost/property_map.hpp></tt>.
<PRE>namespace boost {
template <class PropertyMap>
struct property_traits {
typedef typename PropertyMap::key_type key_type;
typedef typename PropertyMap::value_type value_type;
typedef typename PropertyMap::category category;
};
}</PRE>
<h2><a name="sec:property-map-types">Property Map Types</a></h2>
<ul>
<li>Builtin C++ pointer types.<br>
The following specialization of the <tt>property_traits</tt> class
and the overloads of <tt>put()</tt> and <tt>get()</tt> make it
possible to use builtin C++ pointer types as property maps. These
are defined in <tt>boost/property_map.hpp</tt>. More specifically,
it means that <tt>T*</tt> is a model of <a
href="./LvaluePropertyMap.html">LvaluePropertyMap</a>, given a key
type that is at least convertible <tt>std::ptrdiff_t</tt>.
<PRE>namespace boost {
// specialization for using pointers as property maps
template <class T>
struct property_traits<T*> {
typedef T value_type;
typedef std::ptrdiff_t key_type;
typedef random_access_iterator_pa_tag category;
};
// overloads of the property map functions for pointers
template<>
void put(T* pmap, std::ptrdiff_t k, const T& val) { pmap[k] = val; }
template<>
const T& get(const T* pmap, std::ptrdiff_t k) { return pmap[k]; }
}</PRE>
</li>
<li><a href="./identity_property_map.html">identity_property_map</a> </li>
<li><a href="./iterator_property_map.html">iterator_property_map</a></li>
</ul>
<h3>History</h3>
The property map interface originated as <i>data accessors</i> in
Dietmar Kühl's Masters Thesis on generic graph algorithms. The
property map idea also appeared under the guise of <i>decorators</i>
in early versions of the Generic Graph Component Library (GGCL), which
is now the Boost Graph Library (BGL). The main motivation for the
property map interface was to support the access of data associated
with vertices and edges in a graph, though the applicability of
property maps goes beyond this.
<h3>Acknowledgments</h3>
Thanks go to Dietmar Kühl for coming up with this mechanism, and
thanks go to the Boost members who helped refine and improve the
property map interface. Thanks to Dave Abrahams for managing the
formal review of the BGL which included the property map library.
<h3>Notes to Implementors</h3>
Copying a property map should be inexpensive since they are often
passed by value.
<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright © 2000</TD><TD>
<a HREF="../../people/jeremy_siek.htm">Jeremy Siek</a>, Univ.of Notre Dame (<A HREF="mailto:jsiek@lsc.nd.edu">jsiek@lsc.nd.edu</A>)
</TD></TR></TABLE>
</BODY>
</HTML>
|
