Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

By madhur4127, history, 2 months ago, ,

Hey CodeForces,

TL;DR How to support different callable types as a template argument?

Data structures like segment tree, sparse table, fenwick tree, etc support various operations like max, min, gcd, sum etc. So it would be convenient to write a generic class for the data structure which takes the required operation as an input while constructing the object of the data structure, much in same spirit that std::sort takes various comparators. The binary operation would then be the data member of the data structure's class.

The problem while implementing the operation as a template parameter is that there are many callable types like: lambdas, functors, functions (std::min, std::gcd), function objects(std::less<int>, std::plus<int>), std::function.

One solution would be:

For functions like std::min, std::gcd to work co-exist std::plus, there will a requirement for a functor with operator() implementing desired functionality. Then the functor can be used a template argument and it would be easy. But it certainly is not convenient to wrap the existing functions like std::gcd, std::max, std::min to a class.

Something like this would be ideal:

sparse_table<int, std::plus<int>> st;
sparse_table<int, std::min<int>> st;


Is there a cleaner solution for this?

• +22

 » 2 months ago, # | ← Rev. 4 →   +13 Wow, it just so happens that I wrote a generic sparse table struct yesterday after I encountered a problem on it.It turned out to be not slower than my original code with normal sparse tables.But I have to say, after writing it, it felt too complicated and I will most likely not use it again. Instead I'll have pre-written sparse tables ready; that will be easier. But I guess you're looking for the concept of passing functions so here is how I did it: codetemplate struct SparseT{ int n,lg; vector> arr; T neutral; function Combine; function Nxt; function HasNxt; SparseT(){} SparseT(int _n, T _neutral, function_combine, function_nxt, function _hasNxt){ n = _n; lg = log2(_n); neutral = _neutral; arr.assign(lg+1, vector(n+1, neutral)); Combine = _combine; Nxt = _nxt; HasNxt = _hasNxt; } T& base(int node){ return arr[0][node]; } T get(int node, int len){ T ans = neutral; while(len > 0){ int jump = __builtin_ctz(len); len -= (1< parent, minW;  parent = SparseT(n,0, [&](int old,int cur){return cur;}, [&](int node,int jump){return parent.arr[jump][node];}, [&](int node,int jump){return depth[node] >= (1<(n,INF, [&](int old,int cur){return min(old,cur);}, [&](int node,int jump){return parent.arr[jump][node];}, [&](int node,int jump){return depth[node] >= (1<(n,0, [&](int old,int cur){return old + cur;}, [&](int node,int jump){return node+(1<= sum.n;}); mini = SparseT(n,INF, [&](int old,int cur){return min(old,cur);}, [&](int node,int jump){return node+(1<= mini.n;}); Have fun! :)EDIT: here is the full submission if you want: https://ideone.com/fOwLE0
 » 2 months ago, # |   +3 It is possible to pass your binary operator through a template. Here is my implementation of a disjoint sparse table which accepts an arbitrary type and associative function: codetemplate struct dst { int length; vector> subs; void _fill_subs(int a, int b, int h) { int m = (a+b) >> 1; if (m < length) { T r = subs[h][m] = subs[0][m]; for (int i = m-1; i >= a; i--) subs[h][i] = F(subs[0][i], subs[h][i+1]); } if (m+1 < length) { T r = subs[h][m+1] = subs[0][m+1]; for (int i = m+2; i <= min(b, length-1); i++) subs[h][i] = F(subs[h][i-1], subs[0][i]); } if (h > 1) { _fill_subs(a, m, h-1); _fill_subs(m+1, b, h-1); } } dst(vector& data) { length = data.size(); int exp = 32-__builtin_clz(length-1); subs.assign(exp, vector(length)); for (int i = 0; i < length; i++) subs[0][i] = data[i]; _fill_subs(0, (1<> s) + 1, bs = b >> s; int h = __builtin_ctz(max(as & -as, bs & -bs)) + s; return F(subs[h][a], subs[h][b]); } }; // Sample use int op(int x, int y) { return x+y; } int main() { vector V = {1, 2, 3, 4}; dst table(V); cout << table.query(0, 3) << "\n"; // 10 } So, you have to define the function beforehand and then pass it to the template. A little more cumbersome than using a lambda inline passed to the constructor, but probably faster.
•  » » 2 months ago, # ^ |   0 Thanks for the suggestion but you will still need to create a separate function for every operation you'll use whereas in this case, it would be simpler to use dst> if you'd used class F instead of T F(T,T).
•  » » » 2 months ago, # ^ |   0 Yes, however std::plus and std::min are fundamentally two different types of objects, so you couldn't make a simple template that works for both, as far as I know. My approach gives the user the most freedom over what to choose. e.g., if I want a matrix multiplication function, I can do that easily by just writing the function, rather than having to create my own class to match std::plus. In my experience, it's more convenient despite being more verbose.