是boost :: property_map運算符[] O（1）在這段代碼中的時間複雜度？

我是新的提升和圖形庫。任何人都可以解釋一下property_map背後的實現是什麼，下面的代碼中operator []的時間複雜度是多少？是boost :: property_map運算符[] O（1）在這段代碼中的時間複雜度？

謝謝！

#include <string> 
#include <boost/graph/adjacency_list.hpp> 
int main() 
{ 
    using namespace boost; 
    typedef adjacency_list<listS, listS, directedS, 
    property<vertex_name_t, std::string> > graph_t; 
    graph_t g; 
    graph_traits<graph_t>::vertex_descriptor u = add_vertex(g); 
    property_map<graph_t, vertex_name_t>::type name_map = get(vertex_name, g); 
    name_map[i] = "Joe"; 
    return EXIT_SUCCESS; 
}

來源

2013-05-29 xiao 嘯

您可以通過給std::map創建一個房產地圖。所以時間和空間的複雜性可能與底層std::map相同。您可能想深入瞭解Sorted Associative Container的STL文檔。

來源

2013-09-20 06:44:14 chaero

我很想知道這一點，並發現boost :: graph文檔沒有明確說明這一點，因爲這樣的問題與性能關鍵算法/應用程序高度相關。

總之我相信答案是肯定的，它是O（1）的時間複雜度。我的推理如下。

由於property map concepts只是概念，它不能保證複雜性。所以我們必須看看adjacency_list的一個屬性映射的實現來了解它的複雜性。我相信相關的代碼在boost/graph/detail/adjacency_list.hpp;搜索「頂點屬性地圖」。

template <class Graph, class ValueType, class Reference, class Tag> 
struct adj_list_vertex_property_map 
    : public boost::put_get_helper< 
     Reference, 
     adj_list_vertex_property_map<Graph, ValueType, Reference, Tag> 
    > 
{ 
    typedef typename Graph::stored_vertex StoredVertex; 
    typedef ValueType value_type; 
    typedef Reference reference; 
    typedef typename Graph::vertex_descriptor key_type; 
    typedef boost::lvalue_property_map_tag category; 
    inline adj_list_vertex_property_map(const Graph* = 0, Tag tag = Tag()): m_tag(tag) { } 
    inline Reference operator[](key_type v) const { 
    StoredVertex* sv = (StoredVertex*)v; 
    return get_property_value(sv->m_property, m_tag); 
    } 
    inline Reference operator()(key_type v) const { 
    return this->operator[](v); 
    } 
    Tag m_tag; 
};

我相信這是用於對被實例化一個列表VertexList時，類型，在你的例子一個內部的adjacency_list性能屬性映射。你可以看到operator []接受一個Graph :: vertex_descriptor，它似乎是一些句柄，也許是一個迭代器，並且直接訪問屬性結構而不用查找，即sv->m_property，因此是恆定時間。對於get_property_value()的調用似乎是在您有多個與每個頂點關聯的屬性時用於屬性標記解析;在你的情況下，你只有一個。標籤查找通常也是恆定時間。

使用VecS VertexList類型實例化具有屬性的adjacency_list，在屬性映射查找中也顯示出O（1）時間複雜性。在那裏使用的類型似乎是vec_adj_list_vertex_property_map，操作符[]使用Graph :: vector_descriptor來顯示每個頂點屬性向量的索引，因此O（1）。

回想起來，我想我會期待這樣的，因爲庫的工作原理非常高效，它可以確保這也是高性能的。

來源

2014-11-07 17:54:58 kalaxy

是boost :: property_map運算符[] O（1）在這段代碼中的時間複雜度？

回答

相關問題