aldol_reaction's blog

How can I pass std function as a function's parameter?
By aldol_reaction, history, 3 years ago, In English 
#include <bits/stdc++.h>
using namespace std;
int Min(int a, int b) {return a < b ? a : b;}

template<class T,int N,T (*fun)(T,T)> struct SparseTable{
    int lg[N+10],n;
    T f[21][N+10];
    int pw(int x){return 1<<x;}
    SparseTable():n(0){lg[0]=-1;}
    void insert(T x){
        f[0][++n]=x,lg[n]=lg[n>>1]+1;
        for(int t=1;pw(t)<=n;t++){
            int i=n-pw(t)+1;
            f[t][i]=fun(f[t-1][i],f[t-1][i+pw(t-1)]);
        }
    }
    T query(int l,int r){
        int len=lg[r-l+1];
        return fun(f[len][l],f[len][r-pw(len)+1]);
    }
};

int main() {
    SparseTable<int,100010, Min> t;//compile succussfully
    // SparseTable<int,100010, min> t;//compile failed
    return 0;
}
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

you can use this template

code
→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Almost correct

Check first line

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sincere thanks!I know my error.

    → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dang I really wanted this to work. But your template only works for passing in std::min, std::max. You can't pass in some arbitrary function like bitwise and/or etc because of some weird pointer/reference error:

    #include <bits/stdc++.h>
using namespace std;

const int& f1(const int& x, const int& y) {
    return x < y ? x : y;
}

const int& f2(const int& x, const int& y) {
    return (x & y);
}

int main() {
    cout << f1(1, 2) << endl; //works
    //cout << f2(1, 2) << endl; //RTE
    return 0;
}
    → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 4   Vote: I like it +5 Vote: I do not like it

      In my code library, I prefer the following design for customization points when they need to be function-like:

      Code

      The good thing about lambdas is that they're just objects, and function well with the rest of the language. Starting from C++20, the C++ STL has been moving towards making new functions niebloids (using mechanisms that disable ADL, and currently they seem to be only implemented as function objects) starting from range algorithms, so as I showed in the last example, it is possible to pass those as objects too. The one drawback is that you'd need std::ranges::min instead of std::min which may or may not be extra typing, depending on whether you have a namespace alias for std::ranges.

      Nitpick

      There's also a way to do this using an auto non-type template parameter for the lambda, but it doesn't work with lambdas that can't be called in a constexpr context (for example, lambdas that capture something).

      Code
      → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Actually the error is quite normal, if you turn on the compiler error it shows 

      ...: warning: returning reference to temporary [-Wreturn-local-addr]
   27 |     return (x & y);

      f2 is returning a reference, meanwhile (x & y) is returning a temporary variable, so by the time f2 ends, the reference becomes dangling and pointing to some already gone variable.

      To pass some arbitrary function, you could change the template parameter to template<class T, auto f = std::min<T> >, and modify the parentheses operator to const T operator()(size_t l, size_t r) const {, and f2 to const int f2(const int& x, const int& y), so it return by value. Of course, it might not be very optimal when T is a large object (but if your arbitrary function will create temporary its gonna be it anyway).

      → Reply