Why can not we use `std::multiset` with custom compare lambda as the value of a `std::map`?

Question

This is a follow-up question of asked How to provide custom comparator for `std::multiset` without overloading `operator()`, `std::less`, `std::greater`?

and I have tried to solve by the following manner.

Basic

One can provide custom compare lambda function(since c++11) to the std::multiset of a member of a class as follows:

#include <iostream>
#include <set>

const auto compare = [](int lhs, int rhs) noexcept { return lhs > rhs; };
struct Test
{
    std::multiset<int, decltype(compare)> _set{compare};
    Test() = default;
};

Simple enough.

My Situation

The member of Test class is

std::map<std::string, std::multiset<int, /* custom compare */>> scripts{};

I tried to use the std::multiset with custom

functor Compare (case - 1)
std::greater<> (case - 2)
lambda function (case - 3)

The first two options are a success. But the case of lambda as a custom compare function it did not work. Here is the MCVC:https://godbolt.org/z/mSHi1p

#include <iostream>
#include <functional>
#include <string>
#include <map>
#include <set>

const auto compare = [](int lhs, int rhs) noexcept { return lhs > rhs; };
class Test
{
private:
    struct Compare
    {
        bool operator()(const int lhs, const int rhs) const noexcept { return lhs > rhs; }
    };

private:
    // std::multiset<int, Compare> dummy;                      // works fine
    // std::multiset<int, std::greater<>> dummy;               // works fine
    std::multiset<int, decltype(compare)> dummy{ compare };    // does not work
    using CustomMultiList = decltype(dummy);

public: 
    std::map<std::string, CustomMultiList> scripts{};
};

int main()
{
    Test t{};    
    t.scripts["Linux"].insert(5);
    t.scripts["Linux"].insert(8);
    t.scripts["Linux"].insert(0);

    for (auto a : t.scripts["Linux"]) {
        std::cout << a << '\n';
    }
}

Error message:

error C2280 : '<lambda_778ad726092eb2ad4bce2e3abb93017f>::<lambda_778ad726092eb2ad4bce2e3abb93017f>(void)' : attempting to reference a deleted function
note: see declaration of '<lambda_778ad726092eb2ad4bce2e3abb93017f>::<lambda_778ad726092eb2ad4bce2e3abb93017f>'
note: '<lambda_778ad726092eb2ad4bce2e3abb93017f>::<lambda_778ad726092eb2ad4bce2e3abb93017f>(void)' : function was explicitly deleted
note: while compiling class template member function 'std::multiset<int,const <lambda_778ad726092eb2ad4bce2e3abb93017f>,std::allocator<int>>::multiset(void)'
note: see reference to function template instantiation 'std::multiset<int,const <lambda_778ad726092eb2ad4bce2e3abb93017f>,std::allocator<int>>::multiset(void)' being compiled
note: see reference to class template instantiation 'std::multiset<int,const <lambda_778ad726092eb2ad4bce2e3abb93017f>,std::allocator<int>>' being compiled

It sounds like I tried to default construct the passed lambda, which is not possible until c++20.

If that the case where has it happened? Is it possible to solve this using a lambda compare function within the scope of c++11 till c++17?

score 12 · Accepted Answer · answered Jul 04 '19 at 18:35

It sounds like I tried to default construct the passed lambda, which is not possible until c++20. If that the case where has it happened?

Yes. That exactly what happened here and due to the call of std::map::operator[] at the line(s)

t.scripts["Linux"].insert(5);
//       ^^^^^^^^^

Let's look into detail. The above call will result in a call of the following overload as the key being temporary std::string constructed from const char*.

T& operator[]( Key&& key );

Since C++17 this is equivalent to:

return this->try_emplace(
    std::move(key)).first  ->  second;
//               key_type    mapped_type
//               ^^^^^^^^    ^^^^^^^^^^^
//                  |           |
//                  |           |
//             (std::string)  (std::multiset<int, decltype(compare)>)
//                  |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//                  |           |                               (default-construction meaning)
//                  |       default-construction -->   std::multiset<int, decltype(compare)>{}
//               move-construction                                                          ^^

where the key_type(i.e. temporarly constructed std::string from const char*) should be move constructible, which happends fine.

The mapped_type(i.e. std::multiset<int, decltype(compare)>) should be default construct ed first and that requires the compare lambda should be also default constructed. From cppreference.com:

ClosureType::ClosureType()
ClosureType() = delete;   (until C++14)
ClosureType() = default;  (since C++20)(only if no captures are specified)
Closure types are not DefaultConstructible. Closure types have a deleted (until C++14)no (since C++14) default constructor. (until C++20)

If no captures are specified, the closure type has a defaulted default constructor. Otherwise, it has no default constructor (this includes the case when there is a capture-default, even if it does not actually capture anything). (since C++20)

That means, default construction of lambda closure type not available in C++17(that is what the compiler error is complaining about).

On the other hand, there is no captures are specified(i.e. stateless lambdas) in the compare lambda there and hence it can be explicitly defaulted by the compilers which support C++20 standard.

Is it possible to solve this using a lambda compare function within the scope of c++11 till c++17?

Not by using std::map::operator[](as for the reason explained above), but Yes, the way what @JohnZwinck's has mentioned in his answer. I would like to explain, how that works.

One of the constructors¹ of std::multiset provides the possibility to pass the comparator object.

template< class InputIt >
multiset( InputIt first, InputIt last,
          const Compare& comp = Compare(),
//        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 
          const Allocator& alloc = Allocator() );

The same time, the copy constructor and the move constructor for the lambda closure type have been defaulted since C++14. That means, if we have a possibility to provide the lambda as the first argument²(either by copying or by moving it), it would be the Basic case, what showed in the question.

std::multiset<int, decltype(compare)> dummy{ compare };            // copying
std::multiset<int, decltype(compare)> dummy{ std::move(compare) }; // moving

Luckily, C++17 introduced the member function std::map::try_emplace

template <class... Args>
pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);

by which one can pass the lambda to the above-mentioned constructors¹ of std::multiset as the first argument² like shown above. If we warp this into the member function of the Test class, elements could be inserted to the CustomMultiList (i.e. values) of the scripts map.

The solution would look like(same as the linked post, because I wrote that answer after I asking this question!)

(See Live)

#include <iostream>
#include <string>
#include <map>
#include <set>

// provide a lambda compare
const auto compare = [](int lhs, int rhs) noexcept { return lhs > rhs; };

class Test
{
private:
    // make a std::multi set with custom compare function  
    std::multiset<int, decltype(compare)> dummy{ compare };
    using CustomMultiList = decltype(dummy); // use the type for values of the map 
public:
    std::map<std::string, CustomMultiList> scripts{};
    // warper method to insert the `std::multilist` entries to the corresponding keys
    void emplace(const std::string& key, const int listEntry)
    {
        scripts.try_emplace(key, compare).first->second.emplace(listEntry);
    }
    // getter function for custom `std::multilist`
    const CustomMultiList& getValueOf(const std::string& key) const noexcept
    {
        static CustomMultiList defaultEmptyList{ compare };
        const auto iter = scripts.find(key);
        return iter != scripts.cend() ? iter->second : defaultEmptyList;
    }
};

int main()
{
    Test t{};
    // 1: insert using using wrapper emplace method
    t.emplace(std::string{ "Linux" }, 5);
    t.emplace(std::string{ "Linux" }, 8);
    t.emplace(std::string{ "Linux" }, 0);


    for (const auto a : t.getValueOf(std::string{ "Linux" }))
    {
        std::cout << a << '\n';
    }
    // 2: insert the `CustomMultiList` directly using `std::map::emplace`
    std::multiset<int, decltype(compare)> valueSet{ compare };
    valueSet.insert(1);
    valueSet.insert(8);
    valueSet.insert(5);
    t.scripts.emplace(std::string{ "key2" }, valueSet);

    // 3: since C++20 : use with std::map::operator[]
    // latest version of GCC has already included this change
    //t.scripts["Linux"].insert(5);
    //t.scripts["Linux"].insert(8);
    //t.scripts["Linux"].insert(0);

    return 0;
}

score 4 · Answer 2 · answered Jun 01 '19 at 22:54

4

To do it in one line, you need something like this:

t.scripts.try_emplace("Linux", compare).first->second.insert(5);

This is because the lambda compare has to be passed to the constructor of your multiset. Otherwise there's no comparison object and the multiset cannot be constructed.

Demo: https://godbolt.org/z/rVb3-D

answered Jun 01 '19 at 22:54

John Zwinck

239,568
38
324
436

@JeJo: No, the comparator is required to construct the `multiset`. If you don't like this, simply create a wrapper class `my_multiset` whose default constructor constructs `multiset` with `compare`. – John Zwinck Jun 02 '19 at 03:49

Why can not we use `std::multiset` with custom compare lambda as the value of a `std::map`?

Basic

My Situation

2 Answers2

(See Live)