Re: [Boost-Users] Efficient implementation of associative_property_map

From: Douglas Gregor (gregod_at_[hidden])
Date: 2003-03-04 18:07:42

On Tuesday 04 March 2003 02:37 pm, Martin Okrslar wrote:
> In the BGL book on page 103 it is mentioned, that "The choice to use
> std::map to implement the property map is rather inefficient in this
> case...". Since my graph is large I'm a bit worried about this statement.
>
> Could anybody of you please give me a hint, what other datastructure I
> might use here, to make it efficient?

Do you need the data structure to be external to the graph? The fastest 
property map is an internal property map, where the value is stored along 
with the vertex, edge, or graph the property described. Constant lookup time, 
without any hash functions or magic.

        Doug