C++ Boost

Boost Property Map Library

The Boost Property Map Library specifies concepts that define an interface for mapping key objects to value objects. Algorithms can take property maps as arguments relying on the concept definition and be ignorant of the underlying data structures. The algorithms can therefore be more generic.

Besides concepts, the Boost Property Map Library also contains adaptors that provide property map interfaces for commonly used data structures that implement a mapping operation, such as build-in arrays (pointers), iterators, and std::map.

Property maps are statically-typed; you can use the dynamic_properties class to access a set of property maps through a dynamically-typed interface (e.g., when you read an unknown set of attributes from a file).

Property Map Concepts

The property map concepts prescribe that get() and put() functions are provided that are used as if they are global functions; i.e, without a namespace qualifier. Furthermore, they prescribe operator[] to access value objects.

The following example from shows the property map functions in use. The templated fix_squares function has a property map as parameter.

#include <iostream>
#include <boost/property_map/property_map.hpp>

template <typename T> void fix_squares(T squares) // assuming that T is a property map
{
  typedef typename boost::property_traits<T>::value_type value_type; 
  
  value_type answer1 = get(squares, 1);  // <- use get() to get a value
  value_type& answer2 = squares[2];      // <- use operator[] to get a reference  
  value_type& answer4 = get(squares, 4); // <- use get() to get a reference  

  if(answer1 == 1) {
    std::cout << "right: 1 X 1 == " << answer1 << std::endl;
} else { std::cout << "wrong: 1 X 1 != " << answer1 << std::endl; put(squares, 1, 1); // <- use put() to set a value }   if( answer2 == 4) { std::cout << "right: 2 X 2 == " << answer2 << std::endl << std::endl; } else { std::cout << "wrong: 2 X 2 != " << answer2 << std::endl<< std::endl; answer2 = 4; // <- answer2 is a reference, hence this works } if( answer4 == 16) { std::cout << "right: 4 X 4 == " << answer4 << std::endl << std::endl; } else { std::cout << "wrong: 4 X 4 != " << answer4 << std::endl<< std::endl; squares[4] = 16;// <- use operator[] to get a reference // get(squares, 4) = 16; // <- this would work, but using put() looks nicer } }

The following example creates a vector_property_map, and passes it to the fix_squares function twice:

#include <boost/property_map/property_map.hpp>

int main()
{
  boost::vector_property_map<int> squares;
 
  squares[1] = 2;
  squares[2] = 4;
  squares[4] = 16;
  
  fix_squares(squares); // first time to verify and fix mistakes
  fix_squares(squares); // second time to verify that all mistakes are fixed
  
  return EXIT_SUCCESS;
}

Whereas this example creates an associative_property_map instead, and passes it to the fix_squares function too:

#include <map>
#include <boost/property_map/property_map.hpp>

int main()
{
  std::map<int, int> squares;
  boost::associative_property_map< std::map<int, int> > squares_adapted(squares);

  squares[1] = 1;
  squares[2] = 3;
  squares[4] = 15;

  fix_squares(squares_adapted); // first time to verify and fix mistakes
  fix_squares(squares_adapted); // second time to verify that all mistakes are fixed
 
  return EXIT_SUCCESS;
}

Each property map object has a set of valid keys for which the mapping to value objects is defined; invalid keys result in undefined behaviour. The property map concepts do not specify the set of valid keys. A function that uses a property map should specify the expected set of valid keys in its preconditions.

There are four property map categories that provide different access capabilities and each has a concept definition:

readable

The associated property data can only be read, using the get() function. It is not prescribed whether the value is returned by reference or as a copy. See documentation of the concept ReadablePropertyMap for details.

writeable

The associated property can only be written to, using the put() function. See documentation of the concept WritablePropertyMap for details.

read/write

The associated property can both be written and read, using the get() and put() functions. See documentation of the concept ReadWritePropertyMap for details.

lvalue

The property map gives access to the value object by reference using operator[] or function get(); put() is also available. See documentation of the concept LvaluePropertyMap for details.

Property Map Category Tags

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 { };

}

Property Map Traits

Tthere 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.

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;
  };

}

Property Map Types

History

The property map interface originated as data accessors in Dietmar Kühl's Masters Thesis on generic graph algorithms. The property map idea also appeared under the guise of decorators 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.

Acknowledgments

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.

Notes to Implementors

Copying a property map should be inexpensive, since they are often passed by value.

Copyright © 2000-2002 Jeremy Siek, Indiana University (jsiek@osl.iu.edu)