The problem with std::map is that it does not provide constant time access to the vertex index (it is logarithmic). Thus, the graph algorithm will run slower; it won't have the advertised time complexity. Then we'll get bug reports from people that are surprised by how slow the algorithm is.
As a postscript to this issue with graph_copy, I note that the current implementation of the related boost::adjacency_list<> operator= uses a std::map in the core of its implementation (boost 1.33.0 adjacency_list.hpp line 1775). So this objection to std::map was overruled here. However the author has noted the non constant time. (The non existent boost::hash_map would improve matters - yes?) inline void copy_impl(const adj_list_impl& x_) { ... // Would be better to have a constant time way to get from // vertices in x to the corresponding vertices in *this. 1775: std::map<stored_vertex*,stored_vertex*> vertex_map; ... for (tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) { ... vertex_map[(stored_vertex*)*vi] = v; } ... for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) { ... tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s], vertex_map[(stored_vertex*)t], *this); ... } } Tony