Home > OS >  How to correctly use a map of sets with custom comparator in C ?
How to correctly use a map of sets with custom comparator in C ?

Time:10-07

I want to use a map of sets, with the set having a custom comparator. Here is my code:

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});
    }
};

This yields the following compile error:

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.

In this line : data[key].insert({value, timestamp});, a new set (with my custom comparator) is tentatively instantiated as a value of the map, but that fails. What causes this failure and how to fix it?

CodePudding user response:

The value of unordered_map is set. set requires a comparator object which should be default constructible. Unfortunately, lambdas are default constructible since C 20, so compile your code at least with this standard, or use functor object like:

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

class TimeMap 
{
    unordered_map<string, set<item, Comp> > data;

instead of lambda.

  • Related