...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
The Boost Property Map Library consists mainly of interface specifications in the form of concepts (similar to the iterator concepts in the STL [2]). These interface specifications are intended for use by implementors of generic libraries in communicating requirements on template parameters to their users. In particular, the Boost Property Map concepts define a general purpose interface for mapping key objects to corresponding value objects, thereby hiding the details of how the mapping is implemented from algorithms. The implementation of types fulfilling the property map interface is up to the client of the algorithm to provide. The property map requirements are purposefully vague on the type of the key and value objects to allow for the utmost genericity in the function templates of the generic library.
The need for the property map interface came from the Boost Graph Library (BGL), which contains many examples of algorithms that use the property map concepts to specify their interface. For an example, note the ColorMap template parameter of the breadth_first_search. In addition, the BGL contains many examples of concrete types that implement the property map interface. The adjacency_list class implements property maps for accessing objects (properties) that are attached to vertices and edges of the graph.
The Boost Property Map Library also contains a few adaptors that convert commonly used data-structures that implement a mapping operation, such as builtin arrays (pointers), iterators, and std::map, to have the property map interface. These adaptors are not meant to fulfill all mapping needs, but are to serve as an example of how to implement the interface as well as covering a few common cases. See the header files for details.
Property maps are statically-typed entities. If you need to access
property maps in a more dynamic setting (e.g., because you're reading
an unknown set of attributes from a file), you can use the dynamic_properties
class to access a set of property maps through a dynamically-typed
interface.
#include <iostream> #include <map> #include <string> #include <boost/property_map/property_map.hpp> template <typename 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"; } int main() { std::map<std::string, std::string> name2address; boost::associative_property_map< std::map<std::string, std::string> > address_map(name2address); name2address.insert(make_pair(std::string("Fred"), std::string("710 West 13th Street"))); name2address.insert(make_pair(std::string("Joe"), std::string("710 West 13th Street"))); foo(address_map); for (std::map<std::string, std::string>::iterator i = name2address.begin(); i != name2address.end(); ++i) std::cout << i->first << ": " << i->second << "\n"; return EXIT_SUCCESS; }
For each property map object there is a set of valid keys for which the mapping to value objects is defined. Invoking a property map function on an invalid 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.
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.
Several categories of property maps provide different access capabilities:
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.
There is a tag struct for each of the categories of property maps, which is defined in the header <boost/property_map/property_map.hpp>.
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 { }; }
Similar to the std::iterator_traits class of the STL, there is a boost::property_traits 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 boost::property_traits 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 <boost/property_map/property_map.hpp>.
namespace boost { template <typename PropertyMap> struct property_traits { typedef typename PropertyMap::key_type key_type; typedef typename PropertyMap::value_type value_type; typedef typename PropertyMap::category category; }; }
namespace boost { // specialization for using pointers as property maps template <typename 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]; } }
Copyright © 2000-2002 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) |