How can I use std::maps with user-defined types as key?

Question

I'm wondering why I can't use STL maps with user-defined classes. When I compile the code below, I get the following cryptic error message. What does it mean? Also, why is it only happening with user-defined types? (Primitive types are okay when they are used as 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[](const _Key&) [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 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) const
   {
       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) const
       {
           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.

Answer 2

By default std::map (and std::set) use operator< to determine sorting. Therefore, you need to define operator< on your class.

Two objects are deemed equivalent 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

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 4

class key
{
    int m_value;
public:
    bool operator<(const key& src)const
    {
        return (this->m_value < src.m_value);
    }

};
int main()
{
    key key1;
    key key2;
    map<key,int> mymap;
    mymap.insert(pair<key,int>(key1,100));
    mymap.insert(pair<key,int>(key2,200));
    map<key,int>::iterator iter=mymap.begin();
    for(;iter!=mymap.end();++iter)
    {
        cout<<iter->second<<endl;
    }


}

Answer 5

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

Answer 6

I'd like to expand a little bit on Pavel Minaev's answer, which you should read before reading my answer. Both solutions presented by Pavel won't compile if the member to be compared (such as id in the question's code) is private. In this case, VS2013 throws the following error for me:

error C2248: 'Class1::id' : cannot access private member declared in class 'Class1'

As mentioned by SkyWalker in the comments on Pavel's answer, using a friend declaration helps. If you wonder about the correct syntax, here it is:

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

private:
    int id;
    friend struct Class1Compare;      // Use this for Pavel's first solution.
    friend struct std::less<Class1>;  // Use this for Pavel's second solution.
};

Code on Ideone

However, if you have an access function for your private member, for example getId() for id, as follows:

class Class1
{
public:
    Class1(int id) : id(id) {}
    int getId() const { return id; }

private:
    int id;
};

then you can use it instead of a friend declaration (i.e. you compare lhs.getId() < rhs.getId()). Since C++11, you can also use a lambda expression for Pavel's first solution instead of defining a comparator function object class. Putting everything together, the code could be writtem as follows:

auto comp = [](const Class1& lhs, const Class1& rhs){ return lhs.getId() < rhs.getId(); };
std::map<Class1, int, decltype(comp)> c2int(comp);

Code on Ideone

Answer 7

The right solution is to Specialize std::less for your class/Struct.

• Basically maps in cpp are implemented as Binary Search Trees.

1. BSTs compare elements of nodes to determine the organization of the tree.
2. Nodes who's element compares less than that of the parent node are placed on the left of the parent and nodes whose elements compare greater than the parent nodes element are placed on the right. i.e.

For each node, node.left.key < node.key < node.right.key

Every node in the BST contains Elements and in case of maps its KEY and a value, And keys are supposed to be ordered. More About Map implementation : The Map data Type.

In case of cpp maps , keys are the elements of the nodes and values does not take part in the organization of the tree its just a supplementary data .

So It means keys should be compatible with std::less or operator< so that they can be organized. Please check map parameters.

Else if you are using user defined data type as keys then need to give meaning full comparison semantics for that data type.

Solution : Specialize std::less:

The third parameter in map template is optional and it is std::less which will delegate to operator< ,

So create a new std::less for your user defined data type. Now this new std::less will be picked by std::map by default.

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

}

Note: You need to create specialized std::less for every user defined data type(if you want to use that data type as key for cpp maps).

Bad Solution: Overloading operator< for your user defined data type. This solution will also work but its very bad as operator < will be overloaded universally for your data type/class. which is undesirable in client scenarios.

Please check answer Pavel Minaev's answer