Can a templated function be a template argument to another function?

Question

I thought I'd benchmark some sorting algorithms, but I must be doing templates incorrectly:

Code

#include <iostream>
#include <vector>

template <typename ForwardIterator>
void dummysort(ForwardIterator begin_it, ForwardIterator end_it)
{
    // pretend to use these and sort stuff
    ++begin_it;
    ++end_it;
}

template<typename SortFunc>
void benchmark(const char* name, SortFunc sort_func, std::vector<int> v)
{
    std::cout << name << std::endl;
    sort_func(v.begin(), v.end());
}

int main()
{
    std::vector<int> first = {3, 2, 1};

    benchmark("bubblesort", dummysort, first);
}

Error

10:48 $ clang -std=c++14 tmp.cpp
tmp.cpp:30:5: error: no matching function for call to 'benchmark'
    benchmark("bubblesort", dummysort, first);
    ^~~~~~~~~
tmp.cpp:20:6: note: candidate template ignored: couldn't infer template argument 'SortFunc'
void benchmark(const char* name, SortFunc sort_func, std::vector<int> v)
     ^
1 error generated.

Compiler Info

10:47 $ clang --version
Apple LLVM version 8.1.0 (clang-802.0.42)
Target: x86_64-apple-darwin16.0.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/

If I "untemplate" dummysort, it works.

void dummysort(std::vector<int>::iterator begin_it, std::vector<int>::iterator end_it)

Question

Is there a way I can make it work generically, or, if not, can someone please give me a good explanation or thought experiment similar to this answer?

Answer 1

As explained by nwp, a template function isn't a function; is only a recipe to construct a function.

So you can't pass the recipe

benchmark("bubblesort", dummysort, first);

but you can do it explicating the type an constructing a function from the recipe; I mean

benchmark("bubblesort", dummysort<std::vector<int>::iterator>, first);

Works but I find it a little ugly.

I propose you another solution: instead of a template function, construct a class (or struct) with a template operator() in it; something like

struct dummySort
 {
   template <typename FI>
   void operator() (FI begin_it, FI end_it)
    {
      ++begin_it;
      ++end_it; 
    }
 };

In this way you can call benchmark() passing an object of this type without explicating the type of the iterator: it's the call to operator inside of benchmark() that select the right type and construct the right operator.

The following is a full compiling example

#include <iostream>
#include <vector>

struct dummySort
 {
   template <typename FI>
   void operator() (FI begin_it, FI end_it)
    { ++begin_it; ++end_it; }
 };

template <typename SortFunc>
void benchmark (char const * name, SortFunc sort_func, std::vector<int> v)
 {
   std::cout << name << std::endl;
   sort_func(v.begin(), v.end());
 }

int main()
 {
   std::vector<int> first = {3, 2, 1};

   benchmark("bubblesort", dummySort{}, first);
 }

Answer 2

There are a few ways around this problem.

1. You could explicitly specify the template arguments for dummysort or you could static_cast it to the appropriate function pointer type. This, to me, is a pretty bad solution as it locks into a specific overload choice rather than relying on the language's overload rules. If you change other arguments or types, you could get (best-case) broken code or (worst-case) code that works but does something unexpected

2. You could lift your function template to be a function object that has a call operator template:

   struct dummysort_t {
       template <typename ForwardIterator>
       void operator()(ForwardIterator begin_it, ForwardIterator end_it) const {
           /* ... */
       }
   } constexpr dummysort{}; // in C++17, also mark inline
   

   This allows you to just directly pass in dummysort to your function templates everywhere with the same expected behavior. The downsides to this solution are if you don't own dummysort, this is of course a non-starter, and if you use dummysort as a customization point, you need to do quite a bit more work to get this to have the expected behavior.

3. You could wrap it in a lambda. Since we're copying iterators, the simple form just works:

   [](auto b, auto e) { dummysort(b, e); }
   

   This delays template instantiation for dummysort until the other function template actually invokes it. This gives you the exact behavior you want, and will work in all situations (and fixes the issues with #2). More generally, this pattern should be used like:

   #define OVERLOADS_OF(name) [&](auto&&... args) -> decltype(name(std::forward<decltype(args)>(args)...)) { return name(std::forward<decltype(args)>(args)...); }
   

   with which you would pass:

   OVERLOADS_OF(dummysort)
   

   which for this particular case is overkill, but is more generally useful.