Boost 属性映射库

Boost 属性映射库主要由概念（类似于 STL 中的迭代器概念 [2]）形式的接口规范组成。这些接口规范旨在供通用库的实现者用于向用户传达对模板参数的要求。特别是，Boost 属性映射概念定义了一个通用的接口，用于将键对象映射到相应的值对象，从而隐藏了映射如何从算法中实现这些细节。实现满足属性映射接口的类型由算法的客户端提供。属性映射要求对键和值对象的类型故意含糊不清，以便为通用库的函数模板提供最大的通用性。

属性映射接口的需求源于 Boost 图库 (BGL)，其中包含许多使用属性映射概念来指定其接口的算法示例。例如，请注意ColorMapbreadth_first_search 的模板参数。此外，BGL 还包含许多实现属性映射接口的具体类型示例。adjacency_list 类实现了用于访问附加到图的顶点和边的对象（属性）的属性映射。

Boost 属性映射库还包含一些适配器，它们可以转换常用的数据结构（如内置数组（指针）、迭代器和 std::map）以具有属性映射接口。这些适配器并非旨在满足所有映射需求，而是作为如何实现接口的示例，并涵盖了少数常见情况。有关详细信息，请参阅头文件。

属性映射是静态类型实体。如果您需要在更动态的环境中访问属性映射（例如，因为您正在从文件中读取未知集合的属性），您可以使用 dynamic_properties 类通过动态类型接口访问一组属性映射。

属性映射概念

属性映射接口由一组概念组成（请参阅“概念”的定义 [1] 和 [2]），这些概念定义了将键对象映射到相应值对象的语法。由于属性映射操作是全局函数（实际上它们不必是全局的，但它们总是被无限定地调用，并且可以通过依赖于参数的查找找到），因此可以重载映射函数，使得几乎可以任意使用属性映射类型和键类型。属性映射的接口包含三个函数get(), put()和operator[]。以下来自 example1.cpp 的具体示例显示了如何使用这三个函数来访问与各种人相关联的地址。我们在这里使用一个单独的函数模板来突出显示使用属性映射概念接口的程序部分。在main()函数中，我们使用std::mapandboost::associative_property_map，但使用任何满足属性映射要求的类型（包括您创建的自定义类型）都可以。

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

对于每个属性映射对象，都有一个 *有效键* 集合，用于定义到值对象的映射。在 *无效* 键上调用属性映射函数将导致未定义的行为。属性映射概念不指定如何创建或修改此有效键集。使用属性映射的函数必须在其先决条件中指定预期的有效键集。

属性映射的需求源于 Boost 图库的设计，其算法需要一个接口来访问附加到图的顶点和边上的属性。在这种情况下，顶点和边的描述符是属性映射的键类型。

几类属性映射提供了不同的访问功能

可读

只能读取关联的属性数据。数据按值返回。许多定义问题输入（如边权重）的属性映射可以定义为可读属性映射。

可写

只能写入关联的属性。用于记录广度优先搜索树中路径的父数组是定义为可写属性映射的属性映射的一个示例。

读/写

关联的属性既可以写入也可以读取。Dijkstra 最短路径算法中使用的距离属性需要同时提供读写功能。

左值

关联的属性实际上存储在内存中，并且可以获取其引用。左值类别中的属性映射也支持读/写属性映射的要求。

为四种属性映射类别中的每一种都定义了一个单独的概念。这些属性映射概念列于下文，并附有指向每个概念文档的链接。

• ReadablePropertyMap
• WritablePropertyMap
• ReadWritePropertyMap
• LvaluePropertyMap

属性映射类别标签

在头文件 <boost/property_map/property_map.hpp> 中为每个属性映射类别定义了一个标签结构<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 { };

}

属性映射特征

类似于 STL 的std::iterator_traits类，有一个boost::property_traits类，可用于推导与属性映射类型相关的类型：键和值类型，以及属性映射类别。有一个boost::property_traits的特化，以便指针可以用作属性映射对象。此外，属性映射函数也为指针重载。这些特征类和函数定义在<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::reference reference;
     typedef typename PropertyMap::category category;
  };

}

属性映射类型

• 内置 C++ 指针类型。
  以下对property_traits类的特化和对put()andget()的重载使得可以使用内置 C++ 指针类型作为属性映射。这些定义在boost/property_map/property_map.hpp。更具体地说，这意味着T*是一个 LvaluePropertyMap 的模型，给定一个至少可转换为std::ptrdiff_t.

  namespace boost {
    // specialization for using pointers as property maps
    template <typename T>
    struct property_traits<T*> {
      typedef T value_type;
      typedef T& reference;
      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]; }
  
  }

• identity_property_map 和 typed_identity_property_map
• function_property_map
• iterator_property_map
• shared_array_property_map
• associative_property_map
• const_associative_property_map
• vector_property_map
• ref_property_map
• static_property_map
• transform_value_property_map
• compose_property_map

历史

属性映射接口源自 Dietmar Kühl 的硕士论文中关于通用图算法的*数据访问器*。属性映射的构想也出现在早期版本的通用图组件库 (GGCL) 的*装饰器*名下，该库现在是 Boost 图库 (BGL)。属性映射接口的主要动机是为了支持图的顶点和边关联数据的访问，尽管属性映射的适用性超出了此范围。

致谢

感谢 Dietmar Kühl 提出此机制，并感谢帮助改进和完善属性映射接口的 Boost 成员。感谢 Dave Abrahams 管理了 BGL 的正式审查，该审查包含了属性映射库。

致实现者的说明

复制属性映射应该是廉价的，因为它们经常按值传递。

版权 © 2000-2002

Jeremy Siek, Indiana University (jsiek@osl.iu.edu)