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