Can I use vector as index in map structure in c++?

Question

I attempted to do something like this but it does not compile:

class point
{
    public:
        int x;
        int y;
};



int main()
{

    vector<point> vp1;
    vector<point> vp2;
    vector<point> vp3;

    map < vector<point>, int > m;

    m[vp1] = 1;
    m[vp2] = 2;
    m[vp3] = 3;

    map < vector<point>, int >::iterator it;
    for (it=m.begin(); it!=m.end(); it++)
    {
        cout<<m[it->first]<<endl;
    }
    return 0;
}

Answer 1

You haven't defined a function to compare a vector<point> Maps make requiremets of keys checking of equivalence and comparison.

Answer 2

You can, but the type used as a key in a map needs to be comparable, either using operator<, or using a comparison function/functor you supply as the third template parameter for the map type.

Answer 3

You can use anything as the index type into a std::map as long as it supports an operator< (which could could define as a free-standing function -- doesn't have to be a member function, as long as you can write a < b for a and b being instances of your type of interest) with the usual semantics (antireflexive, transitive, ...). Or, you can pass a binary function with the same semantics to use in lieu of <, if that suits you better.

Answer 4

You have to declare the operator<. It would look like this (please keep in mind, that the three vectors in your sample code actually look the same):

bool operator<(const vector<point>& left, const vector<point>& right)
{
    return left.size() < right.size();
}

Answer 5

Yes, you can. Vectors, like all containers, are comparable. The resulting map will sort the vectors in lexicographic order.

The problem is that point is not comparable. You have to define a sort order for points, and then this will in turn define lexicographic order over vector<point>.

class point
{
    public:
        int x;
        int y;
};

bool operator<( point const &l, point const &r ) {
    return l.x < r.x? true
         : r.x < l.x? false
         : l.y < r.y;
}

A simpler solution is to use std::pair instead of defining your own point.

typedef pair< int, int > point; // point::first = x, point::second = y
   // pair is already comparable; order defined as in previous example
typedef vector<point> pointvec; // OK