Why can't we directly use lambdas without mentioning its type in some STL containers?

Question

I was working with STL containers, trying to implement custom comparators/predicates, and I realized when giving the predicate as a Functor there seem to be same syntax for all containers, i.e. you just mention the name of the Functor as the respective argument in the template arguments, and bam it works!

Now coming to Lambdas they work fine in containers like in std::vector, but not in std::set the syntax is really weird. Here is some code related to that

For std::vector this works fine

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> a = { 3, 1, 0, 2 };
    sort(a.begin(), a.end(), [](const int& num1, const int& num2) -> bool {
        return num1 < num2;
    });

    for (const int& num : a)
    {
        cout << num << " ";
    }
}

But for std::set this doesn't work

auto PredicateLambda = [](const pair<int, string>& p1, const pair<int, string>& p2) -> bool {
    if (p1.first != p2.first)
        return p1.first < p2.first;
    else
        return p1.second < p2.second;
};

set<pair<int, string>, PredicateLambda> st;

rather, you will have to do

set<pair<int, string>, decltype(PredicateLambda)> st(PredicateLambda);

I find this really weird considering that type is anyway determined during compile time and manually specifying seems unnecessary. I feel like I'm missing something here, really appreciate if someone can fill the gap on why it is done like this?

P.S. One explanation I had in mind is there is some kind of static-time checking of the type of the predicate but, this brings another question to mind how is type checking done in case of Functors which seems to works fine normally(i.e. just specifying the name of the functor)

---

Edit: The intention of the question is not about getting to know the syntax, but rather the reasoning behind the design. The reason is that std::sort() essentially needs just a callable object which can compare two values and uses that to sort in-place, whereas std::set class has to declare the predicate in its class and hence would also need the type of the object too. When we give Functor's name, we are essentially giving the Class Name(which is like a type) but PredicateLambda is an object and hence we use decltype to figure its type.

Answer 1

You have mixed up the function template and the class template. For both cases, for any code to appear, it must be instantiated. Let's look at each case:

The std::sort is a function template which accepts the binary-predicate (i.e. callable compare function/ function objects) as its third parameter.

template< class RandomIt, class Compare >
constexpr void sort( RandomIt first, RandomIt last, Compare comp ); (since C++20)
                                                    ^^^^^^^^^^^^

Here the compiler will try to determine template argument types (i.e. RandomIt and Compare) from the passed function parameters, so-called implicit instantiation will happen automatically if you do not explicitly mention them.

That means, one could also call the std::sort with template parameters (explicit instantiation):

const auto compare = [](const int& num1, const int& num2) { ...
std::sort<std::vector<int>::iterator, decltype(compare)>(a.begin(), a.end(), compare);
//        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

---

Whereas, the std::set is a class template. As long as you do not specify the template parameters here, you will not get a concrete type.

A class template by itself is not a type, or an object, or any other entity. No code is generated from a source file that contains only template definitions. In order for any code to appear, a template must be instantiated: the template arguments must be provided so that the compiler can generate an actual class (or function, from a function template).

template<
    class Key,
    class Compare = std::less<Key>,         // optional
    class Allocator = std::allocator<Key>
> class set;

Here, the Compare is optional but part of the std::set's class template type, which can be replaced with the user defined compare function/ callable. Without providing the type of callable, the compiler can not instantiate the version of std::set you want.

---

Further Reads:

• The std::pair has compare operations defined. Hence, the PredicateLambda is not required in your example code. I hope that it is for demonstration purpose.

• Since c++17 we have deduction guide, for a template class, by which one can simply write:

  #include <set>
  #include <tuple>
  #include <string>
  using namespace std::string_literals;
  
  std::set st{ std::pair{1, "string"s} }; // st uses the 
  
  

  One can also provide own deduction guides

• Since c++20 lambda expression is default constructible. Hence, you may not need to pass the PredicateLambda as argument to the st, in the newer compilers.

  std::set<std::pair<int, std::string>, decltype(PredicateLambda)> st;
  

Answer 2

The type deduction rules for template classes and functions are different.

You are seeing std::sort deduce its arguments, including the predicate, type.

Meanwhile, std::set class template type deduction is blocked because you provided a template argument to it.

In c++17 you can use deduction guides:

std::set s( {{1, "hello"s}}, PredicateLambda );

where the type of PredicateLambda is moved into the set.

Back in c++11 you can use a function pointer

std::set<std::pair<int, std::string>, bool(*)(std::pair<int, std::string> const&)> s(
  {{1, "hello"}}, PredicateLambda );

which relies on the fact that a stateless lambda can be implicitly cast into a function pointer with matching signature.

If your predicate is stateful (ie, captures stuff), you can use std::function<bool(std::pair<int, std::string> const&)> in the type of the std::set to store the predicate and not expose its type.

---

Now, in c++20 we can make your syntax a bit simpler as follows:

#include <set>
#include <string>

auto PredicateLambda = [](auto& p1, auto& p2) -> bool {
    if (p1.first != p2.first)
        return p1.first < p2.first;
    else
        return p1.second < p2.second;
};

template<auto x>
struct call_t {
  decltype(auto) operator()(auto&&...args)const {
    return x(decltype(args)(args)...);
  }
};


int main() {
  std::set<std::pair<int, std::string>, call_t<PredicateLambda>> st;
  st.insert( {0, "hello"} );
}

and now we only mention the template name once, and never use decltype on it.

Live example.