How can I use a struct as key in a std::map?

32
votes

I have the following code, but I get an error on on the last line:

struct coord { 
    int x, y; 

    bool operator=(const coord &o) {
        return x == o.x && y == o.y;
    }

    bool operator<(const coord &o) {
        return x < o.x || (x == o.x && y < o.y);
    }
};

map<coord, int> m;
pair<coord, int> p((coord{0,0}),123);
m.insert(p); // ERROR here

How can I use a struct as key in a map?

I tried to change the code to this:

struct coord { 
    int x, y; 

    bool const operator==(const coord &o) {
        return x == o.x && y == o.y;
    }

    bool const operator<(const coord &o) {
        return x < o.x || (x == o.x && y < o.y);
    }
};

But I'm still getting the following error:

C:\Users\tomc\Desktop\g>mingw32-make g++ test.cpp -std=c++0x In file included from c:\mingw\bin\../lib/gcc/mingw32/4.5.2/include/c++/string:5 0:0,
                 from c:\mingw\bin\../lib/gcc/mingw32/4.5.2/include/c++/bits/loc ale_classes.h:42,
                 from c:\mingw\bin\../lib/gcc/mingw32/4.5.2/include/c++/bits/ios
_base.h:43,
                 from c:\mingw\bin\../lib/gcc/mingw32/4.5.2/include/c++/ios:43,
                 from c:\mingw\bin\../lib/gcc/mingw32/4.5.2/include/c++/ostream: 40,
                 from c:\mingw\bin\../lib/gcc/mingw32/4.5.2/include/c++/iostream :40,
                 from test.cpp:1: c:\mingw\bin\../lib/gcc/mingw32/4.5.2/include/c++/bits/stl_function.h: In member  function 'bool std::less<_Tp>::operator()(const _Tp&, const
_Tp&) const [with _ Tp = coord]': c:\mingw\bin\../lib/gcc/mingw32/4.5.2/include/c++/bits/stl_tree.h:1184:4: inst antiated from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key,  _Val, _KeyOfValue, _Compare,
_Alloc>::_M_insert_unique(const _Val&) [with _Key
= coord, _Val = std::pair<const coord, int>, _KeyOfValue = std::_Select1st<std:: pair<const coord, int> >, _Compare = std::less<coord>, _Alloc = std::allocator<std::pair<const coord, int>>]' c:\mingw\bin\../lib/gcc/mingw32/4.5.2/include/c++/bits/stl_map.h:501:41: insta ntiated from 'std::pair<typename std::_Rb_tree<_Key, std::pair<const _Key, _Tp>,  std::_Select1st<std::pair<const _Key,
_Tp> >, _Compare, typename _Alloc::rebind <std::map<_Key, _Tp,
_Compare, _Alloc>::value_type>::other>::iterator, bool> std ::map<_Key, _Tp, _Compare, _Alloc>::insert(const std::map<_Key, _Tp,
_Compare, _ Alloc>::value_type&) [with _Key = coord, _Tp = int,
_Compare = std::less<coord>,  _Alloc = std::allocator<std::pair<const coord, int> >, typename std::_Rb_tree<_ Key, std::pair<const _Key,
_Tp>, std::_Select1st<std::pair<const _Key, _Tp> >, _ Compare, typename _Alloc::rebind<std::map<_Key, _Tp, _Compare,
_Alloc>::value_ty pe>::other>::iterator = std::_Rb_tree_iterator<std::pair<const coord, int> >, st d::map<_Key,
_Tp, _Compare, _Alloc>::value_type = std::pair<const coord, int>]' test.cpp:56:12:   instantiated from here c:\mingw\bin\../lib/gcc/mingw32/4.5.2/include/c++/bits/stl_function.h:230:22: er ror: passing 'const coord' as 'this' argument of 'const bool coord::operator<(co nst coord&)' discards qualifiers mingw32-make: *** [game] Error 1
4
c++c++11stdmap
What error do you get? - R. Martinho Fernandes
This isn't your problem but your operator= needs to be operator== - jcoder
It should be bool operator<(const coord &o) const - Andreas Brinck
const in the wrong place, after the argument list not before. What you did makes the return type const i.e. const bool, but you want to make the method const. - john
Read the Operator Overloading FAQ entry. In fact, this should be closed as a dupe, since it's all explained there. - sbi

4 Answers

52
votes

Try and make operator < const:

bool operator<(const coord &o)  const {

(Your = operator should probably be == operator and const as well)

10
votes

By far the simplest is to define a global "less than" operator for your struct in stead of as a member function.

std::map uses - by default - the 'lessthan' functor which, in turn, uses the global "operator<" defined for the key type of the map.

bool operator<(const coord& l, const coord& r) {
     return (l.x<r.x || (l.x==r.x && l.y<r.y));
}
7
votes

As mentioned in the answer by Andrii, you can provide a custom comparison object to the map instead of defining operator< for your struct. Since C++11, you can also use a lambda expression instead of defining a comparison object. Moreover, you don't need to define operator== for your struct to make the map work. As a result, you can keep your struct as short as this:

struct coord {
    int x, y;
};

And the rest of your code could be written as follows:

auto comp = [](const coord& c1, const coord& c2){
    return c1.x < c2.x || (c1.x == c2.x && c1.y < c2.y);
};
std::map<coord, int, decltype(comp)> m(comp);

Code on Ideone

2
votes

Another solution, which may be used for third-party data types, is to pass a Comparison object as third template parameter. example