Visitor class holding large shared state: best way to implement reference semantics?

Question

This question is loosely based on the Boost.Graph library (BGL) that uses a Visitor-like pattern to customize recursive (search) algorithms. The BGL passes visitor objects by value (in analogy with the STL function objects) and the documentation states

Since the visitor parameter is passed by value, if your visitor contains state then any changes to the state during the algorithm will be made to a copy of the visitor object, not the visitor object passed in. Therefore you may want the visitor to hold this state by pointer or reference.

My question: what is the best way to implement the reference semantics of stateful visitor classes? Abstracting from the precise pointer classes (raw vs unique vs shared, const vs non-const), what would be the best place to put the reference: in the parameter passing or in the data member?

Alternative 1: visitor holds state by pointer, and is passed by-value (as in Boost.Graph)

class Visitor
{
public:
    Visitor(): state_(new State()) {}
    void start() { /* bla */ }
    void finish() { /* mwa */ }
private:
    State* state_;
}

template<typename Node, typename Visitor>
int algorithm(Node const& n, Visitor v)
{
    v.start();
    algorithm(next(n), v);
    v.finish();
}

Alternative 2: visitor holds data by-value, and is passed by-pointer

class Visitor
{
public:
    Visitor(): state_() {}
    void start() { /* bla */ } 
    void finish() { /* mwa */ }
private:
    State state_;
}

template<typename Node, typename Visitor>
int algorithm(Node const& n, Visitor* v)
{
    v->start();
    algorithm(next(n), v);
    v->finish();
}

My current inclination: I find Alternative 1 [passing by-value of objects that hold pointers/references] a little uncomfortable because the visitor does not satisfy value semantics, so I would rather make the reference semantics clear in the parameter list [Alternative 2]. Are there any other considerations or alternatives that are relevant here?

Answer 1

I understand your discomfort with Alternative 1, but I think that this is a case of "that bus has left"; in other words, the direction of the C++ standard library (and of Boost, not just BGL) favours the use of the "held reference" pattern.

Consider, for example, the pervasive use of functors which can be implemented with lambda expressions. As far as I know, all standard library (and boost) interfaces pass functor arguments by value, so if the functor holds state, it must hold it by reference. Consequently, we should get used to seeing [&](){} rather than [=](){}. And, by analogy, we should get used to seeing Visitors hold references (or pointers, but I prefer references) to their state.

There is actually a good reason to pass functors (and visitors) by value rather than by reference. If they were passed by reference, they would have to be passed either by const&, which would make state modification impossible, or by &, which would make using temporary values impossible. The only other possibility would be passing an explicit pointer, but that couldn't be used with lambdas or temporary values (unless the temporary values were unnecessarily heap-allocated).