使用 std::map 和 std::list::iterator

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

为什么这段代码无法编译?

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

如果我将 std::list 更改为 std::vector,一切正常。

错误日志如下:

|| "==== 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

Whosebug 告诉我我的消息主要是代码,所以我必须在这里写这句话。

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

并且 std::map 需要比较,因为它是 有序的 。映射是按键排序的,要使这种排序起作用,键需要具有可比性。如前所述,列表迭代器不是。

如果您不想进行任何排序,则使用 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 即可。