template argument type deduction from std::function return type with lambda

Question

First of, I'm using C++11 (and my topic sucks).

What I'm trying to do is write a generic template function that implements something usually called sort_by in other programming languages. It involves calculating an arbitrary criterion for each member of a range exactly once and then sorting that range according to those criteria. Such a criterion doesn't have to be a POD, all it has to be is less-than-comparable. For things for which std::less doesn't work the caller should be able to provide her own comparison functor.

I've successfully written said function which uses the following signature:

template<  typename Tcriterion
         , typename Titer
         , typename Tcompare = std::less<Tcriterion>
         >
void
sort_by(Titer first, Titer last,
        std::function<Tcriterion(typename std::iterator_traits<Titer>::value_type const &)> criterion_maker,
        Tcompare comparator = Tcompare()) {
}

It can be used e.g. like this:

struct S { int a; std::string b; double c; };
std::vector<S> s_vec{
  { 42, "hello", 0.5 },
  { 42, "moo!",  1.2 },
  { 23, "fubar", 0.2 },
};

sort_by1< std::pair<int, double> >(
  s_vec.begin(), s_vec.end(),
  [](S const &one_s) { return std::make_pair(one_s.a, one_s.c); }
);

What I don't like about this approach is that I have to provide the Tcriterion argument myself because the compiler cannot deduce that type from the lambda expression. Therefore this does not work:

sort_by1(s_vec.begin(), s_vec.end(), [](S const &one_s) { return std::make_pair(one_s.a, one_s.c); });

clang 3.1 and gcc 4.7.1 both bark on this (gcc 4.7.1 even barks on the code above, so I guess I'm really doing something wrong here).

However, if I assign the lambda to a std::function first then at least clang 3.1 can deduce the argument, meaning this works:

typedef std::pair<int, double> criterion_type;
std::function<criterion_type(S const &)> criterion_maker = [](S const &one_s) {
  return std::make_pair(one_s.a, one_s.c);
};
sort_by1(s_vec.begin(), s_vec.end(), criterion_maker);

So my questions are: How do I have to change my function signature so that I don't need to specify that one argument? And (probably related) how would I fix my example to have it working with gcc?

Answer 1

Don't use std::function in tandem with template argument deduction. In fact, there's very likely no reason to use std::function in a function or function template argument list. More often than not, you should not use std::function; it is a very specialized tool that is very good at solving one particular problem. The rest of the time, you can dispense with it altogether.

In your case you don't need template argument deduction if you use a polymorphic functor to order things:

struct less {
    template<typename T, typename U>
    auto operator()(T&& t, U&& u) const
    -> decltype( std::declval<T>() < std::declval<U>() )
    { return std::forward<T>(t) < std::forward<U>(u); }

    // operator< is not appropriate for pointers however
    // the Standard defines a 'composite pointer type' that
    // would be very helpful here, left as an exercise to implement
    template<typename T, typename U>
    bool operator()(T* t, U* u) const
    { return std::less<typename std::common_type<T*, U*>::type> {}(t, u); }
};

You can then declare:

template<typename Iter, typename Criterion, typename Comparator = less>
void sort_by(Iter first, Iter last, Criterion crit, Comparator comp = less {});

and comp(*ita, *itb) will do the right thing, as well as comp(crit(*ita), crit(*itb)) or anything else as long as it makes sense.

Answer 2

How about something like this:

template<  typename Titer
         , typename Tmaker
         , typename Tcompare
         >
void
sort_by(Titer first, Titer last,
        Tmaker criterion_maker,
        Tcompare comparator)
{
  typedef decltype(criterion_maker(*first)) Tcriterion;
  /*
    Now that you know the actual type of your criterion,
    you can do the real work here
  */
}

The problem is that you can obviously not use a default for the comparator with this, but you can easily overcome that by providing an overload that doesn't take a comparator and fills in std::less internally.

To do it like you originally suggested, the compiler would have to be able to "invert" the template instantiation process. I.e. for a given std::function<> instantiation, what parameter do I have to supply as the result to get it. This "looks" easy, but it is not!