boost/property_map
2
0
Fork 0
mirror of https://github.com/boostorg/property_map.git synced 2026-01-31 08:22:17 +00:00
Code Issues Projects Releases Wiki Activity
Files
boost-1.20.0
property_map/property_map.html

218 lines
7.4 KiB
HTML
Raw Permalink Blame History

<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 Concepts</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>
Property Map Concepts
</H1>
The property map interface consists of a set of concepts (see
definition of &quot;concept&quot; 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 &lt;class AddressMap&gt;
void foo(AddressMap address)
{
typedef typename boost::property_traits&lt;AddressMap&gt;::value_type value_type;
typedef typename boost::property_traits&lt;AddressMap&gt;::key_type key_type;
value_type old_address, new_address;
key_type fred = &quot;Fred&quot;;
old_address = get(address, fred);
new_address = &quot;384 Fitzpatrick Street&quot;
put(address, fred, new_address);
key_type joe = &quot;Joe&quot;;
value_type&amp; joes_address = address[joe];
joes_address = &quot;325 Cushing Avenue&quot;;
}</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>
<P>
There is a tag struct for each of the categories of property
maps, which is defined in the header
<tt>&lt;boost/property_map.hpp&gt;</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>
<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>&lt;boost/property_map.hpp&gt;</tt>.
<PRE>namespace boost {
template &lt;class PropertyMap&gt;
struct property_traits {
typedef typename PropertyMap::key_type key_type;
typedef typename PropertyMap::value_type value_type;
typedef typename PropertyMap::category category;
};
// specialization for using pointers as property maps
template &lt;class T&gt;
struct property_traits&lt;T*&gt; {
typedef T value_type;
typedef ptrdiff_t key_type;
typedef random_access_iterator_pa_tag category;
};
// overloads of the property map functions for pointers
template&lt;&gt;
void put(T* pmap, std::ptrdiff_t k, const T&amp; val) { pmap[k] = val; }
template&lt;&gt;
const T&amp; get(const T* pmap, std::ptrdiff_t k) { return pmap[k]; }
}</PRE>
<h3>History</h3>
The property map interface originated as <i>data accessors</i> in
Dietmar K&uuml;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&uuml;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 &copy 2000</TD><TD>
<A HREF=http://www.boost.org/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>
Reference in New Issue View Git Blame Copy Permalink