Using reference-to-lambda as comparator in a map (the right way?)

Question

I want to use a lambda as a custom comparator in a std::map but unfortunately Visual Studio 2013 compiler does not allow using a simple code like that:

auto cmp = [](int l, int r) { return l < r; };
std::map<int, int, decltype(cmp)> myMap(cmp);
myMap[1] = 1;

and fails with

error C3497: you cannot construct an instance of a lambda

Seems that this code works fine in GCC 5.1 and Visual Studio 2015 (checked using ideone and VC++ online compiler). But for VS2013, one of the solutions would be to use a reference as proposed here (note auto&):

auto& cmp = [](int l, int r) { return l < r; };
std::map<int, int, decltype(cmp)> myMap(cmp);
myMap[1] = 1;

Clearly, GCC doesn't compile this due to binding a non-const reference to a temporary, while VS2015 issues a warning about the use of a non-standard extension. One could also use a const reference instead, but then the following code will not compile (note mutable - I'm stretching it a little by having a stateful comparator):

int compCounter = 0;
const auto& cmp = [&compCounter](int l, int r) mutable { ++compCounter; return l < r; };
std::map<int, int, decltype(cmp)> myMap(cmp);
myMap[1] = 1;

So, I see two ways of getting around this, while at the same time having the code compatible with VS2013. First,

int compCounter = 0;
auto cmp = [&compCounter](int l, int r) mutable { ++compCounter; return l < r; };
std::map<int, int, decltype(cmp)&> myMap(cmp);
myMap[1] = 1;

But this makes me think about Stephan T. Lavavej's talk on how passing raw references as explicit template parameters might be wrong if internally it is used in a template type deduction context - he talks about this at exactly this point in his presentation.

The other approach is to use a std::reference_wrapper:

int compCounter = 0;
auto cmp = [&compCounter](int l, int r) mutable { ++compCounter; return l < r; };
std::map<int, int, std::reference_wrapper<decltype(cmp)>> myMap(cmp);
myMap[1] = 1;

So my question finally is: is it guaranteed by any means that passing a raw reference type as comparator is safe? Or it depends on the STL implementers and it might break in some case and, therefore, using reference_wrapper is the way to go?

One final note: I think that passing a reference (in any form) might be useful outside of VS2013 world in case for some reason one doesn't want the comparator to be copied.

Cheers, Rostislav.

Edit: One more difference:

int compCounter = 0;
auto cmp = [&compCounter](int l, int r) mutable { ++compCounter; return l < r; };

//using cmpT = decltype(cmp)&;
using cmpT = std::reference_wrapper<decltype(cmp)>;

std::map<int, int, cmpT> myMap(cmp); 
myMap[1] = 1;

// Will work in both cases of cmpT
std::map<int, int, cmpT> m2(myMap);

// Will work only for reference_wrapper
std::map<int, int, cmpT> m2(cmp);
m2 = myMap;

Answer 1

The error message cannot construct an instance of a lambda is in fact an optimization bug in the STL. It is stated that this only happens with lambdas that do not capture anything, so the proposed workaround is to capture a dummy variable. (I did not actually test this; I could not find an old enough online compiler for Visual C++.)

Using a reference to to lambda instead of the lambda itself also avoids this optimization, so const auto& cmp = ... works, too. Const reference fails for mutable lambdas, because decltype(cmp) carries that const qualifier over into the map, as opposed to map(cmp) receiving a const reference and then creating a non-const copy. The code in Dietmar Kühl's answer creates a non-const reference and thus works.

Using references as template arguments

I am not really an expert here, but I will try anyway.

As Dietmar has stated in his answer, the comparator has to be CopyConstructible. The obvious explanation is that the container constructor receives it as const reference and then creates an internal copy.

When you use CompareClass & as template argument, it does not matter if CompareClass is itself CopyConstructible, because references always are. However, in this case map will hold a copy of the reference and not a copy of the object itself.

The obvious consequence is that you will have to make sure that the referenced object is not freed prematurely. Also, all copies will reference the same object instead of each having its own copy. Except that, nothing bad should happen.

So if you can keep track of references and are sure that they all will die before the object itself, I'd say it is safe. On the other side, it might not be transparent enough, and someone might misunderstand your code and break it. Also, note that after auto &a = ..., decltype(a) will be reference type too, which is even more obscure.

Note on stateful map comparator

In case of Visual Studio, map internally calls the comparator from a const-qualified method. This means that the comparator's operator() should also be const-qualified. That is, a stateful comparator will have to "pretend" to be stateless, e.g. store the state in mutable fields or in other objects stored by reference. Storing the comparator as reference type works, too.

Answer 2

First, note that the lambda expression is a temporary, not a const object. It is possible to bind it to an rvalue reference just fine:

int compCounter = 0;
auto&& tmp = [compCounter](int l, int r) mutable { ++compCounter; return l < r; };
auto&  cmp = tmp;
std::map<int, int, decltype(cmp)> myMap(cmp);
myMap[1] = 1;

This code first binds the lambda object to an rvalue reference. Since an rvalue reference is an lvalue, the name can be bound to an lvalue reference. The lvalue reference can then be used with the std::map<...>.

Aside from being able to compare key types, the only requirement I can find on the comparison object is that it is CopyConstructible (in Table 102 "Associative container requirements"). Base on std::is_copy_constructible<decltype(cmp)>::value it is CopyConstructible.

That code certainly compiles with gcc and clang. I don't have MSVC++ accessible to check if it also compiles with MSVC++.