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

Revision en1, by madhur4127, 2020-03-28 13:56:07

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English madhur4127 2020-03-28 13:56:07 1413 Initial revision (published)