vector<int>::iterator versus list<int>::iterator keys in std::map

Question

Why can a map of vector::iterator to int be defined but a map of list::iterator to int cannot?

#include <vector>
#include <list>
#include <map>
#include <algorithm>
using namespace std;


int main()
{
    int ia[] = {1,2,3,4,5,6,7,8,9,0};

    vector<int> v(begin(ia), end(ia));
    auto it1 = find(begin(v), end(v), 4);
    map< vector<int>::const_iterator, int > m1;
    m1.insert(map<vector<int>::const_iterator, int>::value_type(it1,*it1));

    list<int> l(begin(ia), end(ia));
    auto it2 = find(begin(l), end(l),5);
    map< list<int>::const_iterator, int> m2;
    m2.insert(map<list<int>::const_iterator, int>::value_type(it2,*it2)); //doesn't compile

}

Error 1 error C2678: binary '<' : no operator found which takes a left-hand operand of type 'const std::_List_const_iterator<_Mylist>' (or there is no acceptable conversion)

Error 1 error C2678: binary '<' : no operator found which takes a left-hand operand of type 'const std::_List_const_iterator<_Mylist>' (or there is no acceptable conversion) — hhbilly
That should be in the question (so I've added it). Out of interest, was that on the m2.insert line, or the declaration of m2? — Useless
@Useless: that could easily be on the insert line, since until then, the compiler doesn't instantiate any code that needs the comparison. — jpalecek

Useless Useless · Accepted Answer · 2012-10-06T20:11:01

std::map requires that the key be comparable, either with <, or a provided comparator.

Conceptually, random-access iterators are comparable, but bidirectional iterators aren't. std::vector iterators are random access, and std::list iterators are bidirectional.

So, your list iterator doesn't satisfy the comparable requirement of a std::map key type. If you provide a comparator which can usefully decide which std::list::const_iterator should come before another, you can pass it to the map and this will work. Rough sketch:

struct ListIterCmp {
    bool operator() (list<int>::const_iterator a, list<int>::const_iterator b)
    {
        // how?
    }
};
map< list<int>::const_iterator, int, ListIterCmp> m2;
// this should work now...

The cppreference documentation covers everything I used to use the old SGI docs for, and is still updated. See that both describe a<b for the RandomAccessIterator, and not for the BidirectionalIterator concept.

vector<int>::iterator versus list<int>::iterator keys in std::map

3 Answers