Boost 属性映射库

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

属性映射接口的需求源于 Boost 图库 (BGL)，其中包含许多使用属性映射概念来指定其接口的算法示例。例如，请注意ColorMap breadth_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>.

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)