CODEWITHSUNDEEP
c++templatesiterator
Dejan
Dejan

Reputation: 1028

Avoid accumulation of iterator types in template arguments

Following principle: when I want to return a collection from a function I will pass an output iterator and let the caller decide where the output should go.

Consider the class which has n methods and each one returns some collection. This mean that I need to construct class with n template parameters (output iterators). The number of template parameters will start to grow, and I don't know how to handle this problem.

Specific example:

template<class TNode, class TEdge> class AGraph;
template<class TNode, class TEdge, class OutputOfFunc1, class OutputOfFunc2>
class APathCalculation
{
    using TGraph = AGraph<TNode, TEdge>;
public:
    virtual void ReturnShortestPath(size_t source, size_t dest, TGraph& graph, OutputOfFunc1 outPath) = 0;//func1
    virtual void ReturnAllShortestDistances(size_t source, TGraph& graph, OutputOfFunc2 outDistances) = 0;//func2
};

And, I will derive different classes (e.g. Dijkstra, Bellman-Ford) from APathCalculation. But the problem is that I introduce template arguments

...class OutputOfFunc1, class OutputOfFunc2>

which I fell that they should not be in the class definition since they are specific to particular function.

Currently I declare the class like this

// Example of declaration
APathCalculation<
    int,    // type of node
    double, // type of edge
    back_insert_iterator<list<size_t>>,  // return type of shortest path between two nodes
    back_insert_iterator<vector<double>> // return type of shortest distances from source node
> &pathCalculator;

Upvotes: 2

Views: 130

Answers (4)

Kit.
Kit.

Reputation: 2406

A "shallow" answer:

In order to avoid N template parameters in one class, you need to split it into N classes with 1 template parameter each.

A "deep" answer:

You cannot easily combine dynamic (runtime) polymorphism of virtual functions with static (compile-time, template based) polymorphism of its argument types. If users of the APathCalculation interface want to provide their own iterator class, they will need to instantiate all the potentially useful actual implementations of this interface for their iterator class, which makes dynamic polymorphism for APathCalculation a redundant idea.

If you really need dynamic polymorphism, you need a dynamically polymorphous iterator class.

You can actually have both (statically polymorphous template specializations for common algorithms and/or common iterators, backed by a "default" case that is a wrapper to dynamically polymorphous implementations), but that's probably too complicated for your task. Besides, you will still need a way to bind your "default" wrapper to the actual algorithm you want the APathCalculation client to call.

I personally would start with a purely template-based solution, but I could understand someone starting with a purely virtual function based solution.

Upvotes: 0

Klaus
Klaus

Reputation: 25593

You may define all your arguments in a single structure and use them all over your structures like this:

template<class TNode, class TEdge> class AGraph;

template< typename TYPE_DEFS >
class APathCalculation
{
    using TGraph = AGraph<typename TYPE_DEFS::TNode, typename TYPE_DEFS::TEdge>;
public:
    virtual void ReturnShortestPath(size_t source, size_t dest, TGraph& graph, typename TYPE_DEFS::OutputOfFunc1 outPath) = 0;//func1
    virtual void ReturnAllShortestDistances(size_t source, TGraph& graph, typename TYPE_DEFS::OutputOfFunc2 outDistances) = 0;//func2
};


template< typename TYPE_DEFS > 
class Dijkstra: public APathCalculation<TYPE_DEFS>
{
    using TGraph = AGraph<typename TYPE_DEFS::TNode, typename TYPE_DEFS::TEdge>;
public:
    virtual void ReturnShortestPath(size_t source, size_t dest, TGraph& graph, typename TYPE_DEFS::OutputOfFunc1 outPath) override {}
    virtual void ReturnAllShortestDistances(size_t source, TGraph& graph, typename TYPE_DEFS::OutputOfFunc2 outDistances) override {}
};

struct TypeDefs
{
    using TNode = int;
    using TEdge = double;

    using OutputOfFunc1 = std::back_insert_iterator<std::list<size_t>>;
    using OutputOfFunc2 = std::back_insert_iterator<std::vector<double>>;
};

int main()
{
    Dijkstra<TypeDefs> d;
}

All that will not change anything of your binary. It only makes it a bit more convenient. But maybe I have misunderstood your question?

Upvotes: 0

Peter Ruderman
Peter Ruderman

Reputation: 12485

Here are three alternatives to consider:

Option 1: Just pick a type and return it

If you're worried about performance, this likely isn't nearly as bad as you think.

virtual std::vector<TEdge> FindShortestPath(size_t source, size_t dest, TGraph& graph) = 0;

Option 2: Accept a callback

The idea is that the caller will supply a lambda that stores the output in whatever way makes sense.

virtual void TraverseShortestPath(
 size_t source,
 size_t dest,
 TGraph& graph,
 std::function<void(TEdge*)> callback) = 0;

Option 3: Use a function template

It's a little mysterious to me why you want to use polymorphism for this. You could write function templates for different shortest path algorithms (similar to the algorithms style in the STL):

template <class TGraph, class OutIt>
void FindShortestPath(size_t source, size_t dest, TGraph& graph, OutIt output)
{
  // details...
}

There are of course lots of variations you could do on these approaches. I would also caution against the use of output iterators like this. The caller could pass something safe like a back_inserter but could also pass in something dangerous like a raw pointer, which could easily lead to a buffer overrun.

Upvotes: 1

MSalters
MSalters

Reputation: 179779

"Consider the class which has n methods and each one returns some collection. This mean that I need to construct class with n template parameters (output iterators).

No, you don't. You coudd in fact create a class with 0 template parameters. However, each method itself has one template parameter. In your case, you can reduce it to just 2 template parameters for the class:

template<class TNode, class TEdge>
class APathCalculation
{
    using TGraph = AGraph<TNode, TEdge>;
public:
    template<class OutputOfFunc1>
    void ReturnShortestPath(size_t source, size_t dest, TGraph& graph, OutputOfFunc1 outPath);

    template<class OutputOfFunc2>
    void ReturnAllShortestDistances(size_t source, TGraph& graph, OutputOfFunc2 outDistances);
};

Please note that I have made one important change here: this is a class in the OO sense. What you had was an abstract class or interface. Abstract classes are a good way to decouple caller and callee, but here you cannot decouple them: the caller and callee must agree on iterator types.

Upvotes: 2

Related Questions