Как я могу использовать параметр шаблона для типов функций?

Question

Я пытаюсь реализовать функцию distance(x,y,f), которая вычисляет, сколько раз вы должны применить f к x, чтобы получить y.

Например, если f = square, то distance(2, 256, square) == 3

Код C ++, который у меня здесь есть, адаптирован из «Элементов программирования» Степанова и МакДжонса:

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;
}

Где Domain(F) и DistanceType(F) равны #define d, чтобы быть int

Я решил использовать функторы для типа функции и создал Square<T> иерархию шаблонов функций:

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; }
};

Когда я пробую функцию distance, она работает:

#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;
}

Полный текст здесь (компилируется с g ++)

Мой вопрос:

Как сделать тип f параметром шаблона?

Я пробовал это:

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;
}

И изменил вызов на это:

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

Однако, когда я компилирую, я получаю эту ошибку:

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;

И я не понимаю ошибки. Почему я не могу использовать Square<int> в качестве параметра шаблона?

Answer 1

Почему бы просто не иметь два параметра шаблона?

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;
}

Это также работает с указателями функций ...

Вариант только принятие функций:

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