C++的std ::加爲模板參數

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，目前我無法證實，因爲失敗的第一步，也許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等）上參數化。這裏你試圖參數化一個不是整數類型的實例化值。也就是說，在這種情況下，您實際上並不需要參數化一個值。

由於您的構造函數不接受參數來初始化op成員變量，也不能通過接口訪問它，所以我認爲可以安全地假設運算符在編譯時是已知的，保證不可變，並且默認可構造。

因此，我宣稱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模板來這裏默認情況下，第三個參數。現在看來，在實例化過程中，你幾乎總是要定義所有三個參數。