std::set_difference on map and a vector throws conversion errors

Question

The following code should compute the difference of a map and a vector

std::map<int, int> cursorMap;
QVector<User> userList;
...
std::vector<int> offlineUserIds{};
std::vector<int>::iterator it;
it = std::set_difference(cursorMap.begin(), cursorMap.end(), userList.begin(), userList.end(), offlineUserIds.begin(),
[](const std::pair<int, int> &e, const User &u){ return u.getId() == e.first; });

before invoking set_difference, userList is converted to a std::vector and sorted. The problem is that it gaves me the following errors:

error: cannot convert 'std::pair<const int, int>' to 'int' in assignment
...
error: no match for call to '(TextEditor::updateCursorMap(QVector<User>)::<lambda(const std::pair<int, int>&, const User&)>) (User&, std::pair<const int, int>&)'
         { return bool(_M_comp(*__it1, *__it2)); }
...
note: candidate: 'TextEditor::updateCursorMap(QVector<User>)::<lambda(const std::pair<int, int>&, const User&)>'
...
     it = std::set_difference(cursorMap.begin(), cursorMap.end(), userList.begin(), userList.end(), offlineUserIds.begin(), [](const std::pair<int, int> &e, const User &u){ return u.getId() == e.first; });
...
note:   no known conversion for argument 1 from 'User' to 'const std::pair<int, int>&'

EDIT:

I tried the following code

std::map<int, int> cursorMap;
QVector<User> userList;
...
std::vector<std::pair<int, int>> offlineUserIds{};
std::vector<std::pair<int, int>>::iterator it;
it = std::set_difference(cursorMap.begin(), cursorMap.end(), userList.begin(), userList.end(), offlineUserIds.begin(), [](const std::pair<int, int> &e, const User &u){ return e.first < u.getId(); });

but now it gives me

note: candidate: 'TextEditor::updateCursorMap(QVector<User>)::<lambda(const std::pair<int, int>&, const User&)>'
     it = std::set_difference(cursorMap.begin(), cursorMap.end(), userList.begin(), userList.end(), offlineUserIds.begin(), [](const std::pair<int, int> &e, const User &u){ return e.first < u.getId(); });
...
note:   no known conversion for argument 1 from 'User' to 'const std::pair<int, int>&'

EDIT2:

Here is a minimal reproducible example:

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

class User {
    int id;
public:
    int getId() const { return id; }
};


int main() {
    std::vector<User> newUserList{};
    std::map<int, int> cursorMap{};
    std::vector<User> userList = std::vector(newUserList.begin(), newUserList.end());
    std::sort(userList.begin(), userList.end(), [](const User &u1, const User &u2) { return u1.getId() < u2.getId(); });

    std::vector<std::pair<int, int>> offlineUserIds{};
    std::vector<std::pair<int, int>>::iterator it;
    it = std::set_difference(cursorMap.begin(), cursorMap.end(), userList.begin(), userList.end(), offlineUserIds.begin(), [](std::pair<int, int> e, User u){ return e.first < u.getId(); });

    return 0;
}

build output

In file included from C:/Qt/Tools/mingw810_64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algobase.h:71,
                 from C:/Qt/Tools/mingw810_64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/char_traits.h:39,
                 from C:/Qt/Tools/mingw810_64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/ios:40,
                 from C:/Qt/Tools/mingw810_64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/ostream:38,
                 from C:/Qt/Tools/mingw810_64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/iostream:39,
                 from D:\asant\workspace\CLionProjects\untitled\main.cpp:1:
C:/Qt/Tools/mingw810_64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<User*, std::vector<User> >; _Iterator2 = std::_Rb_tree_iterator<std::pair<const int, int> >; _Compare = main()::<lambda(std::pair<int, int>, User)>]':
C:/Qt/Tools/mingw810_64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:5343:17:   required from '_OutputIterator std::__set_difference(_InputIterator1, _InputIterator1, _InputIterator2, _InputIterator2, _OutputIterator, _Compare) [with _InputIterator1 = std::_Rb_tree_iterator<std::pair<const int, int> >; _InputIterator2 = __gnu_cxx::__normal_iterator<User*, std::vector<User> >; _OutputIterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(std::pair<int, int>, User)> >]'
C:/Qt/Tools/mingw810_64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:5447:46:   required from '_OIter std::set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare) [with _IIter1 = std::_Rb_tree_iterator<std::pair<const int, int> >; _IIter2 = __gnu_cxx::__normal_iterator<User*, std::vector<User> >; _OIter = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = main()::<lambda(std::pair<int, int>, User)>]'
D:\asant\workspace\CLionProjects\untitled\main.cpp:21:188:   required from here
C:/Qt/Tools/mingw810_64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/predefined_ops.h:143:18: error: no match for call to '(main()::<lambda(std::pair<int, int>, User)>) (User&, std::pair<const int, int>&)'
         { return bool(_M_comp(*__it1, *__it2)); }
                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
C:/Qt/Tools/mingw810_64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/predefined_ops.h:143:18: note: candidate: 'bool (*)(std::pair<int, int>, User)' <conversion>
C:/Qt/Tools/mingw810_64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/predefined_ops.h:143:18: note:   candidate expects 3 arguments, 3 provided
D:\asant\workspace\CLionProjects\untitled\main.cpp:21:156: note: candidate: 'main()::<lambda(std::pair<int, int>, User)>'
     it = std::set_difference(cursorMap.begin(), cursorMap.end(), userList.begin(), userList.end(), offlineUserIds.begin(), [](std::pair<int, int> e, User u){ return e.first < u.getId(); });
                                                                                                                                                            ^
D:\asant\workspace\CLionProjects\untitled\main.cpp:21:156: note:   no known conversion for argument 1 from 'User' to 'std::pair<int, int>'
mingw32-make.exe[3]: *** [CMakeFiles\untitled.dir\build.make:82: CMakeFiles/untitled.dir/main.cpp.obj] Error 1
mingw32-make.exe[2]: *** [CMakeFiles\Makefile2:95: CMakeFiles/untitled.dir/all] Error 2
mingw32-make.exe[1]: *** [CMakeFiles\Makefile2:102: CMakeFiles/untitled.dir/rule] Error 2
mingw32-make.exe: *** [Makefile:137: untitled] Error 2

Answer 1

For a reason that is not known to me:

The types Type1 and Type2 must be such that objects of types InputIt1 and InputIt2 can be dereferenced and then implicitly converted to both Type1 and Type2

See cppreference. Last sentence under Parameters -> comp. Highlighted by me.

Answer 2

The comparator cmp for set_difference is LessCompare and the equivalence will be checked with something like:

 pair<int, int> e == User u <==> !(e < u) && !(u < e) <==> !cmp(e,u) && !cmp(u,e)

This will work only if e and u are convertible to each other, which is not the case.

Answer 3

The value type of the template class std::map is defined like

typedef pair<const Key, T> value_type;

However the value type of the class std::vector<int> is int.

You can not assign an object of the typs std::pair to an object of the type int.

So the compiler issues an error.

Moreover the comparison function can be called with any order of the passed arguments. So again the compiler can issue an error that invalid arguments are used because the types of parameters are different and there is no implicit conversion from one type to another..

Answer 4

You may want either roll own difference function or provide User with conversion operator which would allow set_difference to compare pair and User.

set_difference requires mutual conversion and ability to insert Type1 to output sequence. With use of std::map mutual conversion is not possible because conversion operator must be member of std::pair in that case.

Answer 5

I believe your lambda is taking parameters in the wrong order. Try the one below.

[](const User &u, const std::pair<int, int> &e){ return u.getId() == e.first; });