Блог пользователя aldol_reaction

How can I pass std function as a function's parameter?
Автор aldol_reaction, история, 3 года назад, По-английски 
#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;
}
  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

you can use this template

code
→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Almost correct

Check first line

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    sincere thanks!I know my error.

    → Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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;
}
    → Ответить
    • »
      »
      »
      6 месяцев назад, # ^ |
      ← Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

      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
      → Ответить
    • »
      »
      »
      6 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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).

      → Ответить