STL maps with user-defined objects

Question

I'm wondering why I can't use STL maps with user-defined classes. When I compile the code below, I get this cryptic error message. What does it mean? Also, why is it only happening with user-defined types? (primitive types are okay when it is used for the key)

C:\MinGW\bin..\lib\gcc\mingw32\3.4.5........\include\c++\3.4.5\bits\stl_function.h||In member function `bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Class1]':|

C:\MinGW\bin..\lib\gcc\mingw32\3.4.5........\include\c++\3.4.5\bits\stl_map.h|338|instantiated from `_Tp& std::map<_Key, _Tp, _Compare, _Alloc>::operator [with _Key = Class1, _Tp = int, _Compare = std::less, _Alloc = std::allocator >]'|

C:\Users\Admin\Documents\dev\sandbox\sandbox\sandbox.cpp|24|instantiated from here|

C:\MinGW\bin..\lib\gcc\mingw32\3.4.5........\include\c++\3.4.5\bits\stl_function.h|227|error: no match for 'operator<' in '__x < __y'| ||=== Build finished: 1 errors, 0 warnings ===|

#include <iostream>
#include <map>

using namespace std;

class Class1
{
public:
    Class1(int id);

private:
    int id;
};

Class1::Class1(int id): id(id)
{}

int main()
{
    Class1 c1(1);

    map< Class1 , int> c2int;
    c2int[c1] = 12;

    return 0;
}

Answer 1

You need to define operator < for the Class1.

Map needs to compare the values using operator < and hence you need to provide the same when user defined class are used as key.

class Class1
{
public:
    Class1(int id);

    bool operator <(const Class1& rhs) const
    {
     return id < rhs.id;
    }
private:
    int id;
};

Answer 2

By default std::maps (and std::sets) use operator< to determine sorting.

You need to define operator< on your class.

To objects are deemed equal if !(a < b) && !(b < a).

If for some reason you'd like to use a different comparator, the third template argument of the map can be changed, to std::greater, for example.

Answer 3

Keys must be comparable, but you haven't defined a suitable operator< for your custom class.

Answer 4

You don't have to define operator< for your class, actually. You can also make a comparator function object class for it, and use that to specialize std::map. To extend your example:

struct Class1Compare
{
   bool operator() (const Class1& lhs, const Class1& rhs)
   {
       return lhs.id < rhs.id;
   }
};

std::map<Class1, int, Class1Compare> c2int;

It just so happens that the default for the third template parameter of std::map is std::less, which will delegate to operator< defined for your class (and fail if there is none). But sometimes you want objects to be usable as map keys, but you do not actually have any meaningful comparison semantics, and so you don't want to confuse people by providing operator< on your class just for that. If that's the case, you can use the above trick.

Yet another way to achieve the same is to specialize std::less:

namespace std
{
    template<> struct less<Class1>
    {
       bool operator() (const Class1& lhs, const Class1& rhs)
       {
           return lhs.id < rhs.id;
       }
    }
}

The advantage of this is that it will be picked by std::map "by default", and yet you do not expose operator< to client code otherwise.