C++ std::plus 作为模板参数

Question

我想为 binary indexed array 写一个类,

使用两个非类型默认模板参数，op和 identity .

并且需要检查 op(identity,identity) == identity 的约束.

我的问题是，

1. 我不知道如何指定 op ，我当前的解决方案无法编译。 ‘class std::function<T(T, T)>’ is not a valid type for a template non-type parameter
2. 如何检查op(identity,identity) == identity ，目前我无法验证，因为第1步失败，可能是static_assert ？

所以目前我使用以下解决方法，但我无法指定 op ，例如 std::multiplies<int> .谁能告诉我如何实现目标？

#include <vector>
#include <functional>

// template <typename T = int, std::function<T(T,T)> op = std::plus<T>(), const T identity = T()>
template <typename T = int, const T identity = T()>     // currently workaround
class BIT { // binary indexed array
    const std::function<T(T,T)> op = std::plus<T>();    // currently workaround
public:
    BIT(std::vector<T> value) : value(value), prefixSum(value.size() + 1, identity) {
        for (size_t i = 1; i < prefixSum.size(); ++i) {
            incrementNodeByValue(i, value[i-1]);
        }
        // print(prefixSum,"prefixSum");
    }
    T getSum(size_t i) {
        auto sum = identity;
        while (i) {
            sum = op(sum, prefixSum(i));
            i = firstSmallerAncestor(i);
        }
        return sum;
    }
    void incrementNodeByValue(size_t i, T x) {
        while (i < prefixSum.size()) {
            prefixSum[i] = op(prefixSum[i], x);
            i = firstLargerAncestor(i);
        }
    }
private:
    inline size_t firstLargerAncestor(size_t node) { return node + (node & -node); }
    inline size_t firstSmallerAncestor(size_t node) { return node & (node - 1); }
    std::vector<T> value;
    std::vector<T> prefixSum;
};

int main() {
    auto vec = std::vector<int> {5,1,15,11,52,28,0};
    auto bit = BIT<>(vec);
}

Answer 1

std::function 的使用是一种浪费，似乎是您混淆的根源。

请注意，模板只能在整数类型(char、int、long 等)的类型名称和值上进行参数化。在这里，您试图对 std::function 实例化的值进行参数化，这不是整数类型。也就是说，在这种情况下，您实际上不需要对值进行参数化。

因为你的构造函数不接受初始化 op 成员变量的参数，也不能通过接口(interface)访问它，所以我认为可以安全地假设运算符在编译时已知，是有保证的不可变且默认可构造。

因此，我将 op 成员声明为名为 operation 的参数类型。

#include <functional>
#include <vector>

template< typename T = int,
          typename operation = std::plus<T>, 
          const T identity = T() >
class BIT { 
    const operation op = operation();

    static_assert( operation()(identity, identity) == identity );

    std::vector<T> value;
    std::vector<T> prefixSum;

    inline size_t firstLargerAncestor(size_t node) { return node + (node & -node); }
    inline size_t firstSmallerAncestor(size_t node) { return node & (node - 1); }

 public:
    BIT(std::vector<T> value) : 
        value(value), 
        prefixSum(value.size() + 1, identity) {
        for (size_t i = 1; i < prefixSum.size(); ++i) {
            incrementNodeByValue(i, value[i-1]);
        }
    }

    T getSum(size_t i) {
        auto sum = identity;
        while (i) {
            sum = op(sum, prefixSum(i));
            i = firstSmallerAncestor(i);
        }
        return sum;
    }
    void incrementNodeByValue(size_t i, T x) {
        while (i < prefixSum.size()) {
            prefixSum[i] = op(prefixSum[i], x);
            i = firstLargerAncestor(i);
        }
    }
};

live example

请注意，您可能希望在别处定义一个 identity 模板以对操作和值类型进行参数化以在此处默认第三个参数。实际上，您似乎总是在实例化期间定义所有三个参数。