use lambda in function template, can't deduce type, makeSet() use case

Question

What I want to achieve is a makeSet() function accepting three arguments, a pair of iterator, and a function that transforms the value.

One use case could be creating a set from a sequence of values and do transformation, eg, convert a std::map<K,V> to std::set<std::pair<V,K>>.

The client code may look like

auto s = makeSet(hash.begin(), hash.end(),
    [](std::pair<int,int> x) { return std::make_pair(x.second, x.first); });

my current attempt is as follow,

// (commented code are some other *failed* attempt).
template <typename Iterator,
        typename T = typename std::iterator_traits<Iterator>::value_type,
        template<typename ... > class Monad, typename R >
        // typename R, typename Monad = std::function<R(T)> >
std::set<R> makeSet(Iterator first, Iterator last, Monad<R,T> f) {
    std::set<R> res;
    for (; first != last; ++first) res.insert(f(*first));
    return res;
}

but unfortunately does not work. The problem looks like failing to deduce R.

Is there any solution or workaround? I will be very grateful if you can tell me the right way to do it.

Answer 1

The type of a lambda expression is a unnamed class type (its closure type), not std::function. You cannot therefore deduce std::function or Monad from it.

Your best bet would be to do what the standard library does, and simply accept anything as the predicate:

template <
  class Iterator,
  class UnaryFunction
>
auto makeSet(Iterator first, Iterator last, UnaryFunction f) -> std::set<decltype(f(*first))>
{
  std::set<decltype(f(*first))> res;
  for (; first != last; ++first) res.insert(f(*first));
  return res;
}

Note that you may have to wrap the decltype in std::remove_reference and/or std::remove_cv to cover all corner cases (or, as suggested by @Yakk, std::decay).

Also, to avoid re-inventing the wheel, you might want to take a look at the Boost.Range library.