How can I use a template parameter for function types?

Question

I am trying to implement a distance(x,y,f) function that computes the number of times you have to apply f to x to get y.

For example, if f = square then distance(2, 256, square) == 3

The C++ code I have here is adapted from Elements of Programming by Stepanov & McJones:

DistanceType(F) distance(Domain(F) x, Domain(F) y, Square<int> f) {
    typedef DistanceType(F) N;
    // Precondition: y is reachable from x under f
    N n(0);
    while(x != y) {
        x = f(x);
        n += 1;
    }
    return n;
}

Where Domain(F) and DistanceType(F) is #defined to be int

I decided to use functors for the function type, and made this Square<T> function template hierarchy:

template<typename T>
class Transformation {
    public:
        Transformation() {};
        virtual T operator() (T x) = 0;
};

template<typename T>
class Square : public Transformation<T> {
    public:
        virtual T operator() (T x) { return x * x; }
};

When I try the distance function out, it works:

#include <iostream>
using namespace std;
int main() {
    int x = 2;
    int y = 256;
    Square<int> f = Square<int>();
    int d = distance(x, y, f);
    cout << "the distance between " << x << " and " 
        << y << " is " << d << endl;

    return 0;
}

Full gist here (compiles with g++)

My question:

How can I make the type of f a template parameter?

I've tried this:

template<typename F>
DistanceType(F) distance(Domain(F) x, Domain(F) y, F f) {
    typedef DistanceType(F) N;
    // Precondition: y is reachable from x under f
    N n(0);
    while(x != y) {
        x = f(x);
        n += 1;
    }
    return n;
}

And changed the call to this:

typedef Square<int> F;
int d = distance<F>(x, y, f);

However, when I compile, I get this error:

In file included from /usr/include/c++/5/bits/stl_algobase.h:65:0,
                from /usr/include/c++/5/bits/char_traits.h:39,
                from /usr/include/c++/5/ios:40,
                from /usr/include/c++/5/ostream:38,
                from /usr/include/c++/5/iostream:39,
                from transformations.cpp:35:
/usr/include/c++/5/bits/stl_iterator_base_types.h: In instantiation of ‘struct std::iterator_traits<Square<int> >’:
/usr/include/c++/5/bits/stl_iterator_base_funcs.h:114:5:   required by substitution of ‘template<class _InputIterator> typename std::iterator_traits<_Iterator>::difference_type std::distance(_InputIterator, _InputIterator) [with _InputIterator = Square<int>]’
transformations.cpp:42:32:   required from here
/usr/include/c++/5/bits/stl_iterator_base_types.h:168:53: error: no type named ‘iterator_category’ in ‘class Square<int>’
    typedef typename _Iterator::iterator_category iterator_category;
                                                    ^
/usr/include/c++/5/bits/stl_iterator_base_types.h:169:53: error: no type named ‘value_type’ in ‘class Square<int>’
    typedef typename _Iterator::value_type        value_type;
                                                    ^
/usr/include/c++/5/bits/stl_iterator_base_types.h:170:53: error: no type named ‘difference_type’ in ‘class Square<int>’
    typedef typename _Iterator::difference_type   difference_type;
                                                    ^
/usr/include/c++/5/bits/stl_iterator_base_types.h:171:53: error: no type named ‘pointer’ in ‘class Square<int>’
    typedef typename _Iterator::pointer           pointer;
                                                    ^
/usr/include/c++/5/bits/stl_iterator_base_types.h:172:53: error: no type named ‘reference’ in ‘class Square<int>’
    typedef typename _Iterator::reference         reference;

And I don't understand the error. Why can't I use Square<int> as a template parameter?

Please show your Minimal, Complete, and Verifiable Example in the question body. Questions should be self-contained. — Some programmer dude
– Some programmer dude, Commented Sep 11, 2018 at 4:36

Aconcagua · Accepted Answer · 2018-09-11 05:15:06Z

2

Why not just have two template parameters?

template <typename T, typename F>
unsigned long distance(T x, T y, F f)
{
    unsigned long n = 0;
    while(x != y)
    {
        x = f(x);
        ++n;
    }
    return n;
}

This works with function pointers as well...

A variant only accepting functions:

template <typename T>
unsigned long distance(T x, T y, T (f)(T));

edited Sep 11, 2018 at 5:15

answered Sep 11, 2018 at 4:45

Aconcagua

25.6k4 gold badges37 silver badges66 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

tlehman Over a year ago

That variant only accepting functions, T (f)(T) is only going to work for a function pointer correct?

tlehman Over a year ago

Okay, I think functors will be a better choice for this book, since the Arity(F) macros can be more easily defined in terms of methods on functors. I like the elegance of your approach though, thanks for answering!

Aconcagua Over a year ago

That's up to you... First variant works with both, so you'll be fine. You can can use mismatching types with as well, as long as these are implicitly convertible one into the other; e. g. having T as int, but passing std::exp operating on doubles (OK, that one is overloaded, but that's another matter...). If that's now an advantage or rather disadvantage - well, I won't judge.

Collectives™ on Stack Overflow

How can I use a template parameter for function types?

My question:

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

My question:

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related