Using std::map with std::list::iterator

Question

Why does this code not compile?

#include <map>
#include <list>

int main()
{
    typedef std::list<int>::iterator Iter;

    std::map<Iter, Iter> m;

    std::list<int> ints;

    m[ints.begin()] = ints.begin();
}

If I change std::list for std::vector, everything works.

The error log is as follows:

|| "==== Building Practical (release) ===="
|| main.cpp
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
|| C:/mingw32/i686-w64-mingw32/include/c++/bits/stl_function.h: In instantiation of 'bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = std::_List_iterator<int>]':
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_map.h|498 col 32| required from 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](std::map<_Key, _Tp, _Compare, _Alloc>::key_type&&) [with _Key = std::_List_iterator<int>; _Tp = std::_List_iterator<int>; _Compare = std::less<std::_List_iterator<int> >; _Alloc = std::allocator<std::pair<const std::_List_iterator<int>, std::_List_iterator<int> > >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = std::_List_iterator<int>; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::_List_iterator<int>]'
main.cpp|12 col 19| required from here
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| error: no match for 'operator<' (operand types are 'const std::_List_iterator<int>' and 'const std::_List_iterator<int>')
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_algobase.h|64| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/bits/stl_tree.h:63,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_pair.h|220 col 5| note: candidate: template<class _T1, class _T2> constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)
||      operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_pair.h|220 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   'const std::_List_iterator<int>' is not derived from 'const std::pair<_T1, _T2>'
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_algobase.h|67| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/bits/stl_tree.h:63,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_iterator.h|298 col 5| note: candidate: template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
||      operator<(const reverse_iterator<_Iterator>& __x,
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_iterator.h|298 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   'const std::_List_iterator<int>' is not derived from 'const std::reverse_iterator<_Iterator>'
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_algobase.h|67| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/bits/stl_tree.h:63,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_iterator.h|348 col 5| note: candidate: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)
||      operator<(const reverse_iterator<_IteratorL>& __x,
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_iterator.h|348 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   'const std::_List_iterator<int>' is not derived from 'const std::reverse_iterator<_Iterator>'
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_algobase.h|67| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/bits/stl_tree.h:63,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_iterator.h|1089 col 5| note: candidate: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::move_iterator<_Iterator>&, const std::move_iterator<_IteratorR>&)
||      operator<(const move_iterator<_IteratorL>& __x,
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_iterator.h|1089 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   'const std::_List_iterator<int>' is not derived from 'const std::move_iterator<_Iterator>'
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_algobase.h|67| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/bits/stl_tree.h:63,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_iterator.h|1095 col 5| note: candidate: template<class _Iterator> bool std::operator<(const std::move_iterator<_Iterator>&, const std::move_iterator<_Iterator>&)
||      operator<(const move_iterator<_Iterator>& __x,
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_iterator.h|1095 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   'const std::_List_iterator<int>' is not derived from 'const std::move_iterator<_Iterator>'
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\map|60| 0,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|1293 col 5| note: candidate: template<class _Key, class _Val, class _KeyOfValue, class _Compare, class _Alloc> bool std::operator<(const std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&, const std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&)
||      operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|1293 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   'const std::_List_iterator<int>' is not derived from 'const std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>'
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\string|52| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/stdexcept:39,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/array:38,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/tuple:39,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/bits/stl_map.h:63,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:61,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\basic_string.h|4982 col 5| note: candidate: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
||      operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\bits\basic_string.h|4982 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   'const std::_List_iterator<int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\string|52| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/stdexcept:39,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/array:38,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/tuple:39,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/bits/stl_map.h:63,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:61,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\basic_string.h|4994 col 5| note: candidate: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)
||      operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\bits\basic_string.h|4994 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   'const std::_List_iterator<int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\string|52| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/stdexcept:39,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/array:38,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/tuple:39,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/bits/stl_map.h:63,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:61,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\basic_string.h|5006 col 5| note: candidate: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)
||      operator<(const _CharT* __lhs,
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\bits\basic_string.h|5006 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   mismatched types 'const _CharT*' and 'std::_List_iterator<int>'
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\tuple|39| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/bits/stl_map.h:63,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:61,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\array|242 col 5| note: candidate: template<class _Tp, unsigned int _Nm> bool std::operator<(const std::array<_Tp, _Nm>&, const std::array<_Tp, _Nm>&)
||      operator<(const array<_Tp, _Nm>& __a, const array<_Tp, _Nm>& __b)
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\array|242 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   'const std::_List_iterator<int>' is not derived from 'const std::array<_Tp, _Nm>'
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_map.h|63| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:61,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\tuple|928 col 5| note: candidate: template<class ... _TElements, class ... _UElements> constexpr bool std::operator<(const std::tuple<_Args1 ...>&, const std::tuple<_Args2 ...>&)
||      operator<(const tuple<_TElements...>& __t,
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\tuple|928 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   'const std::_List_iterator<int>' is not derived from 'const std::tuple<_Args1 ...>'
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\map|61| 0,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_map.h|1087 col 5| note: candidate: template<class _Key, class _Tp, class _Compare, class _Alloc> bool std::operator<(const std::map<_Key, _Tp, _Compare, _Alloc>&, const std::map<_Key, _Tp, _Compare, _Alloc>&)
||      operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_map.h|1087 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   'const std::_List_iterator<int>' is not derived from 'const std::map<_Key, _Tp, _Compare, _Alloc>'
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\map|62| 0,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_multimap.h|988 col 5| note: candidate: template<class _Key, class _Tp, class _Compare, class _Alloc> bool std::operator<(const std::multimap<_Key, _Tp, _Compare, _Alloc>&, const std::multimap<_Key, _Tp, _Compare, _Alloc>&)
||      operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_multimap.h|988 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   'const std::_List_iterator<int>' is not derived from 'const std::multimap<_Key, _Tp, _Compare, _Alloc>'
||        { return __x < __y; }
||                     ^
In file included from C:\mingw32\i686-w64-mingw32\include\c++\list|63| 0,
||                  from ../src/main.cpp:2:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_list.h|1836 col 5| note: candidate: template<class _Tp, class _Alloc> bool std::operator<(const std::__cxx11::list<_Tp, _Alloc>&, const std::__cxx11::list<_Tp, _Alloc>&)
||      operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
||      ^
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_list.h|1836 col 5| note:   template argument deduction/substitution failed:
In file included from C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_tree.h|65| 0,
||                  from C:/mingw32/i686-w64-mingw32/include/c++/map:60,
||                  from ../src/main.cpp:1:
C:\mingw32\i686-w64-mingw32\include\c++\bits\stl_function.h|387 col 20| note:   'const std::_List_iterator<int>' is not derived from 'const std::__cxx11::list<_Tp, _Alloc>'
||        { return __x < __y; }
||                     ^
Practical.make|106| recipe for target 'obj/Release/main.o' failed
|| mingw32-make.exe[1]: *** [obj/Release/main.o] Error 1
makefile|16| recipe for target 'Practical' failed
|| mingw32-make.exe: *** [Practical] Error 2

StackOverflow tells me my message is mostly code, so I have to write this sentence here.

Answer 1

The std::list iterators are bidirectional iterators. They don't support comparison like random access iterators do.

And comparisons are needed for std::map, since it is ordered. Maps are sorted by the key, and for this sorting to work the keys needs to be comparable. Which as noted, the list iterators aren't.

If you don't want any ordering then use std::unordered_map instead. On the other hand, and as noted by Angew, std::unordered_map is a hashed container, and needs a specialization of std::hash to be able to work.