madhur4127's blog

[C++] Supporting different operations in Generic Data Structures

By madhur4127, history, 4 years ago, In English

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?

  • Vote: I like it
  • +22
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 4   Vote: I like it +13 Vote: I do not like it

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:

code

I needed a parent(on tree) sparse table for computing LCA. I also needed a minimum weight over path(on tree also) which uses the parent sparse table. Here is how I instantiated them:

code

As I said, I would rather keep instances of the different possible types of sparse tables instead of this. By that I mean there are ones based on trees, and ones on arrays. You can see the resemblance between parent and minW above since they are both based on trees. Look at these two simple sum and minimum on array sparse tables to see how they resemble as well:

code

Have fun! :)

EDIT: here is the full submission if you want: https://ideone.com/fOwLE0

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

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:

code

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.

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

    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<int, std::plus<int>> if you'd used class F instead of T F(T,T).

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

      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.

      → Reply