c++ - 如何为函数类型使用模板参数？

Question

我正在尝试实现 distance(x,y,f)计算您必须申请的次数的函数f至 x得到y .

例如，如果 f = square然后distance(2, 256, square) == 3

我这里的 C++ 代码改编自 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;
}

在哪里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;
}

Full gist here (compiles with 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));