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 lt  Tp   operator   const  Tp amp     const  Tp amp   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 amp  std  map lt  Key   Tp     Compare   Alloc   operator   const  Key amp    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 lt   in    x  lt      y         Build finished  1 errors  0 warnings         include  lt iostream gt   include  lt map gt   using namespace std   class Class1   public      Class1 int id    private      int id      Class1  Class1 int id   id id      int main         Class1 c1 1        map lt  Class1   int gt  c2int      c2int c1    12       return 0

User · Answer

By default std  map  and std  set  use operator lt  to determine sorting  Therefore  you need to define operator lt  on your class   Two objects are deemed equivalent if   a  lt  b   amp  amp    b  lt  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

User · Answer

The right solution is to Specialize std  less for your class Struct       Basically maps in cpp are implemented as Binary Search Trees    BSTs compare elements of nodes to determine the organization of the tree  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  lt  node key  lt  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 lt  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 lt     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 lt  gt  struct  less lt MyClass gt                bool operator    const MyClass amp  lhs  const MyClass amp  rhs  const                       return lhs anyMemen  lt  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 lt  for your user defined data type  This solution will also work but its very bad as operator  lt  will be overloaded universally for your data type class  which is undesirable in client scenarios   Please check answer Pavel Minaev s answer

User · Answer

class key       int m value  public      bool operator lt  const key amp  src const               return  this- gt m value  lt  src m value             int main         key key1      key key2      map lt key int gt  mymap      mymap insert pair lt key int gt  key1 100        mymap insert pair lt key int gt  key2 200        map lt key int gt   iterator iter mymap begin        for  iter  mymap end     iter                cout lt  lt iter- gt second lt  lt endl

User · Answer

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 lt Class1 gt       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    lt  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 amp  lhs  const Class1 amp  rhs   return lhs getId    lt  rhs getId       std  map lt Class1  int  decltype comp  gt  c2int comp     Code on Ideone

User · Answer

You don t have to define operator lt  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 amp  lhs  const Class1 amp  rhs  const             return lhs id  lt  rhs id           std  map lt Class1  int  Class1Compare gt  c2int    It just so happens that the default for the third template parameter of std  map is std  less  which will delegate to operator lt  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 lt  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 lt  gt  struct less lt Class1 gt               bool operator    const Class1 amp  lhs  const Class1 amp  rhs  const                     return lhs id  lt  rhs id                      The advantage of this is that it will be picked by std  map  by default   and yet you do not expose operator lt  to client code otherwise

User · Answer

You need to define operator  lt  for the Class1   Map needs to compare the values using operator  lt  and hence you need to provide the same when user defined class are used as key   class Class1   public      Class1 int id        bool operator  lt  const Class1 amp  rhs  const               return id  lt  rhs id        private      int id

User · Answer

Keys must be comparable  but you haven t defined a suitable operator lt  for your custom class

[c++] How can I use std::maps with user-defined types as key?

Examples related to c++

Examples related to dictionary

Examples related to stl

Examples related to containers

Examples related to stdmap