Linked lists of templated classes vs function ptr

Question

I am designing a library for a hierarchical problem. At each stage of the hierarchy there are several "tools" at hand. If at a state N one tool succeeds, the solution is passed to the next (N+1) state. If all tools of stage N fail, we return to the state N-1 (previous) and let the previous stage handle the problem.

I have two possible ideas how to structure this problem. One uses a linked list of templated classes, the other binds directly to the next stage's run function. My question is, is any of these superior to the other (or are both flawed) and why?

The first solution uses templates to create a linked list of templated classes.

template <typename Input, typename Output>
struct BaseSolver
{
    virtual boost::optional<Output> run(const Input& _input) = 0;
};

template<typename Input>
struct BaseStage
{
    virtual bool runAndRecover(const Input &_input)
    {
        return true;
    }
};

template<typename Input, typename Output>
struct Stage1 : BaseStage<Input>
{
    bool run(const Input& _input)
    {
        for(const auto& solver : solvers_)
        {
            const auto currentResult = solver->run(_input);
            if(currentResult && nextStage->runAndRecover(currentResult.get()))
            {
                return true;
            }
        }
        return false;
    }

    std::vector<boost::shared_ptr<BaseSolver<Input, Output>>> solvers_;

    BaseStage<Output>* nextStage;
};

This is the other solution. It binds only to the run() function of the next stage

template<typename Input, typename Output>
struct Stage2
{
    typedef boost::function<boost::optional<Output> (Input)> SolverFunction;
    typedef boost::function<bool(Output)> NextStage;

    bool run(const Input& _input)
    {
        for(const auto& solver : solverFunctions_)
        {
            const auto solverResult = solver(_input);
            if(solverResult && nextStage_(solverResult.get()))
            {
                return true;
            }
        }
        return false;
    }

    std::vector<SolverFunction> solverFunctions_;
    // will be bind to the next stage::run
    NextStage nextStage_;
};

PS: Both versions compile and run as a prototype.

Answer 1

The second is simpler, neater and avoids virtual functions. Prefer std::function over boost::function unless the latter gives you something extra, which it doesn't here

Answer 2

Your choice here is between the following:

• a functor object, which might hold state between calls, or
• a function pointer, which shouldn't hold state.

I'll assume you're not using static variables in functions, since they are not thread-local and can't be reset between calls.

If none of your solver functions needs to retain any state across successive calls to it (in other words, if it produces output that's entirely determined by its input), then there's no reason not to opt for the shorter, simpler approach.

If you find you're constantly passing "tramp data" along as part of the inputs, then you might want to prefer the functor approach. (If you've not heard the term, "tramp data" refers to parameters that hitch along for the ride - passed through unmodified to another function).