C++中如何正确使用带自定义比较器的set的unordered_map？

我想使用一个存储set的unordered_map，其中set使用自定义比较器，代码如下：

using item = pair<string, int>;
auto comp = [](item const& p1, item const& p2) {return p1.second < p2.second;};

class TimeMap {
    unordered_map<string, decltype(set<item, decltype(comp)>(comp))> data;
    
public:
    TimeMap() {
        data.clear();
    }
    
    void set(string key, string value, int timestamp) {
        data[key].insert({value, timestamp});
    }
};

编译时出现错误：

In file included from prog_joined.cpp:1:
In file included from ./precompiled/headers.h:50:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/map:60:
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_tree.h:149:9: error: no matching constructor for initialization of '(lambda at prog_joined.cpp:7:13)'
      : _M_key_compare()
        ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_tree.h:680:4: note: in instantiation of member function 'std::_Rb_tree_key_compare<(lambda at prog_joined.cpp:7:13)>::_Rb_tree_key_compare' requested here
          _Rb_tree_impl()
          ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_tree.h:939:7: note: in instantiation of member function 'std::_Rb_tree<std::pair<std::__cxx11::basic_string<char>, int>, std::pair<std::__cxx11::basic_string<char>, int>, std::_Identity<std::pair<std::__cxx11::basic_string<char>, int>>, (lambda at prog_joined.cpp:7:13), std::allocator<std::pair<std::__cxx11::basic_string<char>, int>>>::_Rb_tree_impl<(lambda at prog_joined.cpp:7:13), false>::_Rb_tree_impl' requested here
      _Rb_tree() = default;
      ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/tuple:1661:9: note: in instantiation of function template specialization 'std::pair<const std::__cxx11::basic_string<char>, std::set<std::pair<std::__cxx11::basic_string<char>, int>, (lambda at prog_joined.cpp:7:13), std::allocator<std::pair<std::__cxx11::basic_string<char>, int>>>>::pair<const std::__cxx11::basic_string<char> &, 0>' requested here
      : pair(__first, __second,
        ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/ext/new_allocator.h:147:23: note: in instantiation of function template specialization 'std::pair<const std::__cxx11::basic_string<char>, std::set<std::pair<std::__cxx11::basic_string<char>, int>, (lambda at prog_joined.cpp:7:13), std::allocator<std::pair<std::__cxx11::basic_string<char>, int>>>>::pair<const std::__cxx11::basic_string<char> &>' requested here
        { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
                             ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/alloc_traits.h:484:8: note: in instantiation of function template specialization '__gnu_cxx::new_allocator<std::__detail::_Hash_node<std::pair<const std::__cxx11::basic_string<char>, std::set<std::pair<std::__cxx11::basic_string<char>, int>, (lambda at prog_joined.cpp:7:13), std::allocator<std::pair<std::__cxx11::basic_string<char>, int>>>>, true>>::construct<std::pair<const std::__cxx11::basic_string<char>, std::set<std::pair<std::__cxx11::basic_string<char>, int>, (lambda at prog_joined.cpp:7:13), std::allocator<std::pair<std::__cxx11::basic_string<char>, int>>>>, const std::piecewise_construct_t &, std::tuple<const std::__cxx11::basic_string<char> &>, std::tuple<>>' requested here
        { __a.construct(__p, std::forward<_Args>(__args)...); }
              ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable_policy.h:2086:27: note: in instantiation of function template specialization 'std::allocator_traits<std::allocator<std::__detail::_Hash_node<std::pair<const std::__cxx11::basic_string<char>, std::set<std::pair<std::__cxx11::basic_string<char>, int>, (lambda at prog_joined.cpp:7:13), std::allocator<std::pair<std::__cxx11::basic_string<char>, int>>>>, true>>>>::construct<std::pair<const std::__cxx11::basic_string<char>, std::set<std::pair<std::__cxx11::basic_string<char>, int>, (lambda at prog_joined.cpp:7:13), std::allocator<std::pair<std::__cxx11::basic_string<char>, int>>>>, const std::piecewise_construct_t &, std::tuple<const std::__cxx11::basic_string<char> &>, std::tuple<>>' requested here
            __node_alloc_traits::construct(_M_node_allocator(),
                                 ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/hashtable_policy.h:701:15: note: in instantiation of function template specialization 'std::__detail::_Hashtable_alloc<std::allocator<std::__detail::_Hash_node<std::pair<const std::__cxx11::basic_string<char>, std::set<std::pair<std::__cxx11::basic_string<char>, int>, (lambda at prog_joined.cpp:7:13), std::allocator<std::pair<std::__cxx11::basic_string<char>, int>>>>, true>>>>::_M_allocate_node<const std::piecewise_construct_t &, std::tuple<const std::__cxx11::basic_string<char> &>, std::tuple<>>' requested here
          __p = __h->_M_allocate_node(std::piecewise_construct,
                     ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/unordered_map.h:985:16: note: in instantiation of member function 'std::__detail::_Map_base<std::__cxx11::basic_string<char>, std::pair<const std::__cxx11::basic_string<char>, std::set<std::pair<std::__cxx11::basic_string<char>, int>, (lambda at prog_joined.cpp:7:13), std::allocator<std::pair<std::__cxx11::basic_string<char>, int>>>>, std::allocator<std::pair<const std::__cxx11::basic_string<char>, std::set<std::pair<std::__cxx11::basic_string<char>, int>, (lambda at prog_joined.cpp:7:13), std::allocator<std::pair<std::__cxx11::basic_string<char>, int>>>>>, std::__detail::_Select1st, std::equal_to<std::__cxx11::basic_string<char>>, std::hash<std::string>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true>, true>::operator[]' requested here
      { return _M_h[__k]; }
               ^
Line 13: Char 13: note: in instantiation of member function 'std::unordered_map<std::__cxx11::basic_string<char>, std::set<std::pair<std::__cxx11::basic_string<char>, int>, (lambda at solution.cpp:7:13), std::allocator<std::pair<std::__cxx11::basic_string<char>, int>>>, std::hash<std::string>, std::equal_to<std::__cxx11::basic_string<char>>, std::allocator<std::pair<const std::__cxx11::basic_string<char>, std::set<std::pair<std::__cxx11::basic_string<char>, int>, (lambda at solution.cpp:7:13), std::allocator<std::pair<std::__cxx11::basic_string<char>, int>>>>>>>::operator[]' requested here
        data[key].insert({value, timestamp});
            ^
Line 2: Char 13: note: candidate constructor (the implicit copy constructor) not viable: requires 1 argument, but 0 were provided
auto comp = [](item const& p1, item const& p2) {return p1.second < p2.second;};
            ^
Line 2: Char 13: note: candidate constructor (the implicit move constructor) not viable: requires 1 argument, but 0 were provided
1 error generated.

问题出在data[key].insert({value, timestamp});这一行，实例化带自定义比较器的新set作为无序映射的值时失败，请问原因和修复方法？

• lambda类型没有默认构造函数，仅支持拷贝/移动构造。
• 调用unordered_map的operator[]时，若key不存在会默认构造对应的set实例，但set依赖的lambda比较器无法被默认初始化，导致编译报错。
• decltype(set<item, decltype(comp)>(comp))本质等价于set<item, decltype(comp)>，并没有把lambda实例传递给新创建的set。

方法1：用函数对象类替代lambda #

将比较器改为带默认构造的结构体，让set可以正常默认构造：

using item = pair<string, int>;

struct Comp {
    bool operator()(const item& p1, const item& p2) const {
        return p1.second < p2.second;
    }
};

class TimeMap {
    unordered_map<string, set<item, Comp>> data;
    
public:
    TimeMap() = default; // 默认构造已完成初始化，无需手动clear
    
    void set(string key, string value, int timestamp) {
        data[key].insert({value, timestamp});
    }
};

方法2：避免使用operator[]，手动构造带比较器的set #

若坚持使用lambda，可通过find和emplace手动创建set并传入lambda实例：

using item = pair<string, int>;
auto comp = [](const item& p1, const item& p2) {return p1.second < p2.second;};
using SetType = set<item, decltype(comp)>;

class TimeMap {
    unordered_map<string, SetType> data;
    
public:
    TimeMap() = default;
    
    void set(string key, string value, int timestamp) {
        auto it = data.find(key);
        if (it != data.end()) {
            it->second.insert({value, timestamp});
        } else {
            data.emplace(key, SetType(comp)); // 手动传入比较器实例
            data.at(key).insert({value, timestamp});
        }
    }
};

方法3：C++20+下使用无捕获lambda作为默认构造类型 #

C++20起允许无捕获lambda作为可默认构造的类型，可直接简化写法：

using item = pair<string, int>;

class TimeMap {
    unordered_map<string, set<item, decltype([](const item& p1, const item& p2) {
        return p1.second < p2.second;
    })>> data;
    
public:
    TimeMap() = default;
    
    void set(string key, string value, int timestamp) {
        data[key].insert({value, timestamp});
    }
};

内容的提问来源于stack exchange，提问作者Brainless