C++ Boost

Boost Property Map 庫

Boost Property Map 庫主要是以概念(類似於 STL [2] 中的迭代器概念)的方式給出了一些接口的規範。這些接口規範是打算給泛型庫的實現者使用的,用於與庫的使用者進行有關模板參數要求方面的溝通。具體地說,Boost Property Map 概念為鍵對像到相應的值對象的映射定義了一個通用的接口,從而向算法隱藏映射實現的細節。遵循 property map 接口的類型的實現由算法的使用者提供。property map 對於鍵對象與值對象的類型的要求被故意模糊化,以使得泛型庫的函數模板可以獲得最大限度的通用性。

對於 property map 接口的需要來自於 Boost Graph 庫(BGL), 該庫包含了許多算法例子,這些例子都使用了 property map 概念來指明算法的接口。例如,breadth_first_search 中的 ColorMap 模板參數。此外,BGL 還包含了許多實現了 property map 接口的具體類型的例子。adjacency_list 類模板實現了用於訪問附屬於圖的邊和頂點的對象(屬性)的 property map.

Boost Property Map 庫還包含了 少量的適配器,它們將實現映射操作的常用數據結構,如內建數組(指針)、迭代器和 std::map, 轉換為具有 property map 接口。這些適配器並不打算滿足所有映射需要,但可以用作一個實現該接口的例子,同時也可用於一些常見的情況。有關細節請見頭文件。

Property maps 是靜態類型實體。如果你需要在更為動態的設置中訪問 property maps(如,你要從一個文件中讀出一組未知的屬性),你可以使用 dynamic_properties 類來通過動態類型接口訪問一組 property maps.

Property Map 概念

property map 接口包含了一組概念(關於"概念"的定義,請見 [1][2]), 這些概念定義了一種語法,將鍵對像映射到相應的值對象。由於 property map 操作是一些全局函數(實際上它們不一定是全局的,不過他們總是可以被不帶限定符地進行調用,可以通過ADL被查找到),所以重載這些映射函數就可以使用幾 乎是任意的鍵類型和值類型。property map 的接口包括三個函數:get(), put(), 和 operator[]. 以下實際例子來自於 example1.cpp,它示範了如何使用這三個函數來存取不同人員的住址。我們在這裡使用了一個獨立的函數模板,以突出程序中使用了 property map 概念接口的部分。在 main() 函數中,我們使用了 std::mapboost::associative_property_map, 不過使用任意符合 property map 要求的類型(包括你自己創建的定制類型)都是可以的。
#include <iostream>
#include <map>
#include <string>
#include <boost/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;
}

對於每一個 property map 對象,存在一組 有效鍵,有效鍵到值對象的映射是被定義好的。對無效鍵調用 property map 函數將導致未定義行為。property map 概念不規定如何創建和修改這組有效鍵。一個使用 property map 的函數必須將指定有效鍵集合作為其前置條件。

對於 property maps 的需求來自於對 Boost Graph 庫的設計,該庫的算法需要一個接口來訪問附屬於圖的頂點和邊的屬性。在這種上下文中,頂點描述符和邊描述符就是 property map 的鍵類型。

property maps 被分為幾類,它們提供了不同的訪問能力:

可讀的
關聯的屬性數據只能被讀。數據以值的方式返回。多數定義問題輸入(如邊的權重)的 property map 可被定義為可讀 property maps.

可寫的
關聯的屬性數據只能被寫。用於記錄在先寬搜索樹中的路徑的父結點數組就是一個被定義為可寫 property map 的例子。

讀/寫的
關聯的屬性數據即可以讀也可以寫。在 Dijkstra 最短路徑算法中的距離屬性必須提供讀和寫的能力。

左值的
關聯的屬性數據在內存中表示,並可以獲得對該數據的引用。左值類別的 property map 同時也支持讀/寫 property map 的要求。

對於這四個 property map 類別,分別定義了相應的概念。下面列出各個 property map 概念,並分別鏈接到各自的文檔。

Property Map 類別 Tags

每一類 property map 都有一個 tag, 定義於頭文件 <boost/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

類似於 STL 的 std::iterator_traits 類,庫提供了一個 boost::property_traits 類,用於推斷與某個 property map 類型相關聯的類型: 鍵類型和值類型,以及 property map 類別。同時還提供了一個 boost::property_traits 特化類,使得指針也可以用作 property map 對象。另外,property map 函數也針對指針進行了重載。這些 traits 類和函數定義在 <boost/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;
};

}

Property Map 類型

歷史

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.

鳴謝

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.

實現者的注意事項

複製 property map 的代價應該是較低的,因為它們通常會以傳值的方式被傳遞。

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