C ++ STL map container with class key and class value

Question

So, suppose I have a class like this:

class Point { private: int x, y; public: void setX(int arg_x) { x = arg_x; } void sety(int arg_y) { y = arg_y; } int getX() const { return x; } int gety() const { return y; } }; 

Now I want to have a map like this:

 map<Point, Point> m; 

But I need a third parameter. I read in cplusplus that this third parameter is something to compare, but I did not understand what it was. Can anyone explain this to me?

Answer 1

You can extend your class this way if you do not need a separate comparison function

 class Point { private: int x, y; public: bool operator<( const Point& other) const { if ( x == other.x ) { return y < other.y; } return x < other.x; } }; 

By default, an stl map arranges all the elements in it using some sort of ordering concept. In this case, this operator is used. Sometimes you do not have control over the Point class or you can use it on two different maps, each of which defines its own order. For example, one map can sort points by x first, and another - sort by y first. Therefore, it would be useful if the comparison operator is independent of the Point class. You can do something like this.

 class Point { public: int x, y; }; struct PointComparer { bool operator()( const Point& first , const Point& second) const { if ( first.x == second.x ) { return first.y < second.y; } return first.x < second.x; } }; map<Point, Point , PointComparer> m; 

Answer 2

You need to determine the order of the Point points.

This can be done in different ways:

Overload operator < for point

You can overload the < operator, the prototype of which is:

 bool operator < (const Point & p_lhs, const Point & p_rhs) ; 

For example, for my tests, I used the following command:

 bool operator < (const Point & p_lhs, const Point & p_rhs) { if(p_lhs.getX() < p_rhs.getX()) { return true ; } if(p_lhs.getX() > p_rhs.getX()) { return false ; } return (p_lhs.getY() < p_rhs.getY()) ; } 

This is the easiest way, but semantically assumes that the ordering described above is correct by default .

Providing Functor

If you do not want to provide an operator < or want to have several cards, each of which has its own order, your decision should provide a functor card. This is the third template parameter defined for the map:

 template < class Key, class T, class Compare = less<Key>, class Allocator = allocator<pair<const Key,T> > > class map; 

The functor must have the following signature:

 struct MyCompareFunctor { bool operator() (const Point & p_lhs, const Point & p_rhs) { // the code for comparison } } ; 

So, for my tests, I just wrote the following:

 struct MyCompare { bool operator() (const Point & p_lhs, const Point & p_rhs) { if(p_lhs.getX() > p_rhs.getX()) { return true ; } if(p_lhs.getX() < p_rhs.getX()) { return false ; } return (p_lhs.getY() > p_rhs.getY()) ; } } ; 

And used it on my map:

 std::map<Point, Point, MyCompare> map ; 

Et voilà ...

Specialization std::less for Point

I don’t see the point in this, but it’s always useful to know: you can specialize the structure of the std::less template for your Point class

 #include <functional> namespace std { template<> struct less<Point> : binary_function <Point,Point,bool> { bool operator() (const Point & p_lhs, const Point & p_rhs) { if(p_lhs.getX() < p_rhs.getX()) { return true ; } if(p_lhs.getX() > p_rhs.getX()) { return false ; } return (p_lhs.getY() < p_rhs.getY()) ; } } ; } 

This has the same effect as operator < overloading, at least with respect to the map.

Regarding the above operator < solution, semantically, this solution assumes that the ordering described above is the correct default value for std:less .

Note that the default implementation of std::less calls operator < template type. If you give different results than others, you can consider it as a semantic error.

Answer 3

When you use a user-defined class as a key in std :: map , a comparison class is required to determine the positions of elements in the map container: a class that takes two arguments of the key type and returns bool.

This is basically a comparison function / function that compares two key values.

Answer 4

You do not need the third parameter, you just need operator== and operator<

 bool operator<(const Point& other) const{ if ( x == other.x ) return y < other.y; return x < other.x; } bool operator==(const Point& other) const{ return x == other.x && y == other.y; } 

Answer 5

I think the above code slightly improves @parapura rajkumar's solutions.

 class Point{ private: int x, y; public: bool operator<( const Point& other) const{ return ((x < other.x) || (y < other.y)); } }; 

Answer 6

What you call the third parameter is called the Comparator in STL. For the default types as keys, you do not need to specify one of them as the compiler does this work for you. But for your specific types, you must provide it OR otherwise, how the compiler will maintain the sort order in map / set, etc.