使用可变参数模板在C++中实现划分差异

Question

我正在尝试实现C++此处显示的除法差公式。

到目前为止，我已经有了这个

template<typename F, typename T>
T divdiff(F f, T t1, T t2) {
  return (f(t1) - f(t2)) / (t1 - t2);
};
template<typename F, typename T, typename... Args>
T divdiff(F f, T tstart, Args... t, T tend) {
  return (divdiff(f, tstart, t...) - divdiff(f, t..., tend))/ (tstart - tend);
};

它

编译得很好，但是当它尝试使用它时，例如这样

 double r = divdiff([](double x) { return 2 * x; }, 1.0, 2.0, 3.0);

我收到以下错误

note: candidate function not viable: requires 3 arguments, but 4 were provided
T divdiff(F f, T tstart, Args... t, T tend) {``

我的编译器是 gcc

配置：--prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/usr/include/c++/4.2.1 Apple LLVM 版本 8.0.0 （clang-800.0.42.1） 目标： x86_64-苹果-达尔文15.4.0 线程模型： posix 已安装目录：/Library/Developer/CommandLineTools/usr/bin

有谁知道为什么它不起作用以及如何解决它

Answer 1

template<typename F, typename T, typename... Args>
T divdiff(F f, T tstart, Args... t, T tend)

由于Args... t不在参数列表的末尾，因此不会被推导。不允许这种推论，部分是为了简化语言规则，部分是为了帮助保持程序简单（并防止搬起石头砸自己的脚）。你可以像divdiff<F, double, double>一样显式指定Args ...，但是对于递归调用，很难删除最后一个double。

在任何情况下，可变参数模板方法都会遭受模板膨胀和效率低下的影响，因为每个函数调用都可能复制参数列表。由于序列的元素应全部为同一类型，因此请考虑改用迭代器。然后，您可以使用基于数组的可迭代序列的std::initializer_list添加方便的重载。

template< typename F, typename bidirectional_iterator >
typename std::iterator_traits< bidirectional_iterator >::value_type
divdiff( F f, bidirectional_iterator first, bidirectional_iterator last ) {
    bidirectional_iterator next = std::next( first );
    bidirectional_iterator prev = std::prev( last );
    auto diff = next == prev?
        f( * first ) - f( * prev )
      : divdiff( f, first, prev ) - divdiff( f, next, last );
    return diff / ( * first - * prev );
}
template< typename F, typename T >
T divdiff( F f, std::initializer_list< T > il )
    { return divdiff( f, il.begin(), il.end() ); }

演示。

Answer 2

这是标准的元组解包递归解决方案。我更改了您的lambda，因为线性函数在这里有点无聊。

#include <iostream>
#include <utility>
#include <tuple>
// The base version of divdiff, ends recursion
template<typename F, typename T>
T divdiff(F f, T t0, T t1) {
    return (f(t0) - f(t1)) / (t0 - t1);
}
// This divdiff overload takes a tuple and an index sequence
// The index sequence specifies which elements from the tuple will
// be unpacked as arguments for a divdiff call
template <typename F, typename T, std::size_t... Is>
auto divdiff(F f, T arg_tuple, std::index_sequence<Is...>) {
    return divdiff(f, std::get<Is>(arg_tuple)...);
}
template<typename F, typename T, typename ...Ts>
T divdiff(F f, T t0, Ts ...right_args) {
    // pack all arguments into a tuple
    auto arg_tuple = std::make_tuple(t0, right_args...);
    // make an index sequence whose size is one less than the
    // current recursion's argument count
    using next_index_sequence = std::make_index_sequence<sizeof...(Ts)>;
    // get the value of the final argument in tn
    auto tn = std::get<sizeof...(Ts)>(arg_tuple);
    // Call divdiff, first using the tuple/sequence overload for the left
    // side arguments.
    // Then call it with the easily-obtained right side arguments.
    return (divdiff(f, arg_tuple, next_index_sequence{})
        - divdiff(f, right_args...)) / (t0 - tn);
}
int main() {
    double r = divdiff([](double x) { return x * x * x; }, 1.0, 2.0, 3.0);
    std::cout << r << 'n';
}