mirror of
https://github.com/boostorg/property_map.git
synced 2026-01-31 08:22:17 +00:00
255 lines
9.1 KiB
HTML
255 lines
9.1 KiB
HTML
<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">random_access_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=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>
|