Swapping two boost::adjacency_list graphs, akin to std::swap

Question

I'm building an application, which contains a class DecoratedGraph (say) making use of a boost::adjacency_list graph as an underlying member.

I have a bunch of other members in DecoratedGraph too, some of them storing std::map and std::vector on vertices of the graph, representing various additional properties. I will refer to these additional properties as decorations.

I have written a custom copy constructor, which would not only copy the graph but make sure that the decorations refer to the vertices on the copied graph, not the original graph.

According to the Rule of 3, alongside the copy constructor, we also need a definition for the copy assignment operator and a destructor - and so I have been implementing these also.

For the copy assignment operator, I've made use of the copy-and-swap idiom, suggested by another stackoverflow answer. To implement a swap function for my class, I would need to swap both the graph and the decorations. For now, I have used std::map::swap and std::vector::swap to swap the decorations, and used std::swap to swap the other members of the two objects, including the graph.

However, when trying to make use of the decorations on my swapped object, I found that the references no longer refer to the vertices on the graph. I'm not certain where I have gone wrong: I believe the problem most likely lies in the swap function not behaving as I had expected. The swaps used on the deocrations are the member methods for std::map and std::vector respectively - I would expect these to function as expected. The one place that I suspect may be a problem is the usage of std::swap on boost::adjacency_list objects, which perhaps will have unexpected behaviour.

I'm wondering if std::swap is the correct way to go about swapping two boost::adjacency_list graphs? If not, what would be the correct approach?

Answer 1

Indeed, std::swap doesn't seem to be what you want. It selects the generic std::swap that moves through a temporary, very simplified implementation:

template <typename T> inline void swap(T& a, T& b) {
    T tmp = std::move(a);
    a = std::move(b);
    b = std::move(tmp);
}

This would seem fine, except that Boost Graph largely predates C++11 so doesn't actuvely use move semantics. This is exemplified by the implementation of adjacency_list<>::swap member:

void swap(adjacency_list& x)
{
    // Is there a more efficient way to do this?
    adjacency_list tmp(x);
    x = *this;
    *this = tmp;
}

They don't even pretend to try to move.

What To Do

Depending on how you catered for your decorations, you might get a free home-run using copy_graph, which will copy internal properties as well as bundled properties and graph properties.

You will want to manually replicate external property maps (or your home-grown equivalent of it).

Out-Of-The Box

The conventional way to make swap both cheap and atomic (think about exception safety!) is to use Pimpl idiom and just swap the implementation pointers.