title: template argument type deduction from std::function return type with lambda
body: <p>First of, I'm using C++11 (and my topic sucks).</p>
  
  <p>What I'm trying to do is write a generic template function that implements something usually called <code>sort_by</code> 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 <code>std::less</code> doesn't work the caller should be able to provide her own comparison functor.</p>
  
  <p>I've successfully written said function which uses the following signature:</p>
  
  <pre><code>template&lt;  typename Tcriterion
           , typename Titer
           , typename Tcompare = std::less&lt;Tcriterion&gt;
           &gt;
  void
  sort_by(Titer first, Titer last,
          std::function&lt;Tcriterion(typename std::iterator_traits&lt;Titer&gt;::value_type const &amp;)&gt; criterion_maker,
          Tcompare comparator = Tcompare()) {
  }
  </code></pre>
  
  <p>It can be used e.g. like this:</p>
  
  <pre><code>struct S { int a; std::string b; double c; };
  std::vector&lt;S&gt; s_vec{
    { 42, "hello", 0.5 },
    { 42, "moo!",  1.2 },
    { 23, "fubar", 0.2 },
  };
  
  sort_by1&lt; std::pair&lt;int, double&gt; &gt;(
    s_vec.begin(), s_vec.end(),
    [](S const &amp;one_s) { return std::make_pair(one_s.a, one_s.c); }
  );
  </code></pre>
  
  <p>What I don't like about this approach is that I have to provide the <code>Tcriterion</code> argument myself because the compiler cannot deduce that type from the lambda expression. Therefore this does not work:</p>
  
  <pre><code>sort_by1(s_vec.begin(), s_vec.end(), [](S const &amp;one_s) { return std::make_pair(one_s.a, one_s.c); });
  </code></pre>
  
  <p>clang 3.1 and gcc 4.7.1 both bark on this (gcc 4.7.1 even <a href="http://pastebin.com/BzMPDiGt" rel="noreferrer">barks on the code above</a>, so I guess I'm really doing something wrong here).</p>
  
  <p>However, if I assign the lambda to a <code>std::function</code> first then at least clang 3.1 can deduce the argument, meaning this works:</p>
  
  <pre><code>typedef std::pair&lt;int, double&gt; criterion_type;
  std::function&lt;criterion_type(S const &amp;)&gt; criterion_maker = [](S const &amp;one_s) {
    return std::make_pair(one_s.a, one_s.c);
  };
  sort_by1(s_vec.begin(), s_vec.end(), criterion_maker);
  </code></pre>
  
  <p>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?</p>