Templates with Function Type Parameter Cause Compiler Error

Question

I have defined the following function in C++:

template<class Type> Type GetMedian(const vector<Type>& items, function<bool(Type, Type)> comp) {
  vector<Type> copied_items(items);
  std::nth_element(copied_items.begin(), copied_items.begin() + copied_items.size()/2, copied_items.end(), comp);
  return copied_items[copied_items.size()/2];
}

However, when I try to call it as GetMedian(v, greater<uint32_t>()), my compiler (clang) complains:

error: no
      matching function for call to 'GetMedian'
  GetMedian(v, greater<uint32_t>());
  ^~~~~~~~~
note: 
      candidate template ignored: could not match 'function' against 'greater'
template<class Type> Type  GetMedian(const vector<Type>& items, function...

However, I do not see this error, whenever I change to not use templates, as:

uint32_t GetMedian(const vector<uint32_t>& items, function<bool(uint32_t, uint32_t)> comp) {
  vector<uint32_t> copied_items(items);
  std::nth_element(copied_items.begin(), copied_items.begin() + copied_items.size()/2, copied_items.end(), comp);
  return copied_items[copied_items.size()/2];
}

Is there any way to make my function as flexible as I am trying to?

Answer 1

The type Type is deduced in two spots here:

template<class Type> 
Type GetMedian(const vector<Type>& items, function<bool(Type, Type)> comp);
                            ^^^^                        ^^^^^^^^^^

When you call it with GetMedian(v, greater<uint32_t>()), it'll deduce Type as uint32_t for v, but then it needs to deduce function<bool(Type, Type)> against greater<uin32_t>. But the latter is not of type function, so the deduction fails. It's convertible to function<bool(uint32_t, uint32_t)>, but conversions don't happen during the template deduction process.

Thankfully, you don't actually need a std::function here. It's actually worse to have it - you're giving yourself the overhead of type erasure for no reason. Just have the comparator be a separate template type:

template <class Type, class Comp>
Type GetMedian(const vector<Type>& items, Comp comp);

---

Alternatively, if you really really really want a std::function, you could wrap the Type in a non-deduced context via something like:

template <class T> struct non_deduced { using type = T; };
template <class T> using non_deduced_t = typename non_deduced<T>::type;

template <class T>
T median(const std::vector<T>&, std::function<bool(non_deduced_t<T>, non_deduced_t<T>)>)

Now, the conversion from std::greater<uint32_t> to std::function<bool(uint32_t, uint32_t)> is allowed to happen because it's only the vector<T> that is a deduced context, so the compiler deduces T to uint32_t and then checks if the second argument conversion works.