C unordered map using a custom class type as the key

Question

I am trying to use a custom class as key for an unordered map  like the following    include  lt iostream gt   include  lt algorithm gt   include  lt unordered map gt   using namespace std   class node  class Solution   class Node   public      int a      int b       int c      Node         Node vector lt int gt  v            sort v begin    v end             a   v 0                  b   v 1                  c   v 2                     bool operator   Node i            if   i a  this- gt a  amp  amp  i b  this- gt b  amp  amp i c  this- gt c                 return true            else               return false                      int main         unordered map lt Node  int gt  m           vector lt int gt  v      v push back 3       v push back 8       v push back 9       Node n v        m n    0       return 0      However  g   gives me the following error   In file included from  usr include c   4 6 string 50 0                   from  usr include c   4 6 bits locale classes h 42                   from  usr include c   4 6 bits ios base h 43                   from  usr include c   4 6 ios 43                   from  usr include c   4 6 ostream 40                   from  usr include c   4 6 iostream 40                   from 3sum cpp 4   usr include c   4 6 bits stl function h  In member function    bool std  equal to lt  Tp gt   operator   const  Tp amp   const  Tp amp   const  with  Tp   Node       usr include c   4 6 bits hashtable policy h 768 48    instantiated from    bool std    detail   Hash code base lt  Key   Value   ExtractKey   Equal   H1   H2  std    detail   Default ranged hash  false gt    M compare const  Key amp   std    detail   Hash code base lt  Key   Value   ExtractKey   Equal   H1   H2  std    detail   Default ranged hash  false gt    Hash code type  std    detail   Hash node lt  Value  false gt    const  with  Key   Node   Value   std  pair lt const Node  int gt    ExtractKey   std   Select1st lt std  pair lt const Node  int gt   gt    Equal   std  equal to lt Node gt    H1   std  hash lt Node gt    H2   std    detail   Mod range hashing  std    detail   Hash code base lt  Key   Value   ExtractKey   Equal   H1   H2  std    detail   Default ranged hash  false gt    Hash code type   long unsigned int      usr include c   4 6 bits hashtable h 897 2    instantiated from    std   Hashtable lt  Key   Value   Allocator   ExtractKey   Equal   H1   H2   Hash   RehashPolicy    cache hash code    constant iterators    unique keys gt    Node  std   Hashtable lt  Key   Value   Allocator   ExtractKey   Equal   H1   H2   Hash   RehashPolicy    cache hash code    constant iterators    unique keys gt    M find node std   Hashtable lt  Key   Value   Allocator   ExtractKey   Equal   H1   H2   Hash   RehashPolicy    cache hash code    constant iterators    unique keys gt    Node   const key type amp   typename std   Hashtable lt  Key   Value   Allocator   ExtractKey   Equal   H1   H2   Hash   RehashPolicy    cache hash code    constant iterators    unique keys gt    Hash code type  const  with  Key   Node   Value   std  pair lt const Node  int gt    Allocator   std  allocator lt std  pair lt const Node  int gt   gt    ExtractKey   std   Select1st lt std  pair lt const Node  int gt   gt    Equal   std  equal to lt Node gt    H1   std  hash lt Node gt    H2   std    detail   Mod range hashing   Hash   std    detail   Default ranged hash   RehashPolicy   std    detail   Prime rehash policy  bool   cache hash code   false  bool   constant iterators   false  bool   unique keys   true  std   Hashtable lt  Key   Value   Allocator   ExtractKey   Equal   H1   H2   Hash   RehashPolicy    cache hash code    constant iterators    unique keys gt    Node   std    detail   Hash node lt std  pair lt const Node  int gt   false gt   std   Hashtable lt  Key   Value   Allocator   ExtractKey   Equal   H1   H2   Hash   RehashPolicy    cache hash code    constant iterators    unique keys gt   key type   Node  typename std   Hashtable lt  Key   Value   Allocator   ExtractKey   Equal   H1   H2   Hash   RehashPolicy    cache hash code    constant iterators    unique keys gt    Hash code type   long unsigned int      usr include c   4 6 bits hashtable policy h 546 53    instantiated from    std    detail   Map base lt  Key   Pair  std   Select1st lt  Pair gt   true   Hashtable gt   mapped type amp  std    detail   Map base lt  Key   Pair  std   Select1st lt  Pair gt   true   Hashtable gt   operator   const  Key amp    with  Key   Node   Pair   std  pair lt const Node  int gt    Hashtable   std   Hashtable lt Node  std  pair lt const Node  int gt   std  allocator lt std  pair lt const Node  int gt   gt   std   Select1st lt std  pair lt const Node  int gt   gt   std  equal to lt Node gt   std  hash lt Node gt   std    detail   Mod range hashing  std    detail   Default ranged hash  std    detail   Prime rehash policy  false  false  true gt   std    detail   Map base lt  Key   Pair  std   Select1st lt  Pair gt   true   Hashtable gt   mapped type   int     3sum cpp 149 5    instantiated from here  usr include c   4 6 bits stl function h 209 23  error  passing    const Node    as    this    argument of    bool Node  operator   Node     discards qualifiers  -fpermissive  make       threeSum  Error 1   I guess  I need the tell C   how to hash class Node  however  I am not quite sure how to do it  How can I accomplish this tasks

User · Answer

For enum type  I think this is a suitable way  and the difference between class is how to calculate hash value  template  lt typename T gt  struct EnumTypeHash     std  size t operator   const T amp  type  const       return static cast lt std  size t gt  type           enum MyEnum     class MyValue      std  unordered map lt MyEnum  MyValue  EnumTypeHash lt MyEnum gt  gt  map

User · Answer

check the following link https   www geeksforgeeks org how-to-create-an-unordered map-of-user-defined-class-in-cpp  for more details   the custom class must implement the    operator must create a hash function for the class  for primitive types like int and also types like string the hash function is predefined

User · Answer

Most basic possible copy paste complete runnable example of using a custom class as the key for an unordered map  basic implementation of a sparse matrix      UnorderedMapObjectAsKey cpp   include  lt iostream gt   include  lt vector gt   include  lt unordered map gt   struct Pos     int row    int col     Pos         Pos int row  int col          this- gt row   row      this- gt col   col         bool operator   const Pos amp  otherPos  const         if  this- gt row    otherPos row  amp  amp  this- gt col    otherPos col  return true      else return false         struct HashFunction         size t operator   const Pos amp  pos  const             size t rowHash   std  hash lt int gt    pos row         size t colHash   std  hash lt int gt    pos col   lt  lt  1        return rowHash   colHash                 int main void      std  unordered map lt Pos  int  Pos  HashFunction gt  umap        at row 1  col 2  set value to 5   umap Pos 1  2     5        at row 3  col 4  set value to 10   umap Pos 3  4     10        print the umap   std  cout  lt  lt   quot  n quot     for  auto amp  element   umap          std  cout  lt  lt   quot    quot   lt  lt  element first row  lt  lt   quot    quot   lt  lt  element first col  lt  lt   quot       quot   lt  lt  element second  lt  lt   quot  n quot         std  cout  lt  lt   quot  n quot      return 0

User · Answer

I think  jogojapan gave an very good and exhaustive answer  You definitively should take a look at it before reading my post  However  I d like to add the following    You can define a comparison function for an unordered map separately  instead of using the equality comparison operator  operator     This might be helpful  for example  if you want to use the latter for comparing all members of two Node objects to each other  but only some specific members as key of an unordered map  You can also use lambda expressions instead of defining the hash and comparison functions    All in all  for your Node class  the code could be written as follows   using h   std  hash lt int gt   auto hash      const Node amp  n  return   17   31   h   n a     31   h   n b     31   h   n c     auto equal      const Node amp  l  const Node amp  r  return l a    r a  amp  amp  l b    r b  amp  amp  l c    r c    std  unordered map lt Node  int  decltype hash   decltype equal  gt  m 8  hash  equal     Notes    I just reused the hashing method at the end of jogojapan s answer  but you can find the idea for a more general solution here  if you don t want to use Boost   My code is maybe a bit too minified  For a slightly more readable version  please see this code on Ideone

User · Answer

To be able to use std  unordered map  or one of the other unordered associative containers  with a user-defined key-type  you need to define two things    A hash function  this must be a class that overrides operator   and calculates the hash value given an object of the key-type  One particularly straight-forward way of doing this is to specialize the std  hash template for your key-type  A comparison function for equality  this is required because the hash cannot rely on the fact that the hash function will always provide a unique hash value for every distinct key  i e   it needs to be able to deal with collisions   so it needs a way to compare two given keys for an exact match  You can implement this either as a class that overrides operator    or as a specialization of std  equal  or  ndash  easiest of all  ndash  by overloading operator     for your key type  as you did already     The difficulty with the hash function is that if your key type consists of several members  you will usually have the hash function calculate hash values for the individual members  and then somehow combine them into one hash value for the entire object  For good performance  i e   few collisions  you should think carefully about how to combine the individual hash values to ensure you avoid getting the same output for different objects too often   A fairly good starting point for a hash function is one that uses bit shifting and bitwise XOR to combine the individual hash values  For example  assuming a key-type like this   struct Key     std  string first    std  string second    int         third     bool operator   const Key  amp other  const     return  first    other first              amp  amp  second    other second              amp  amp  third    other third            Here is a simple hash function  adapted from the one used in the cppreference example for user-defined hash functions    namespace std      template  lt  gt    struct hash lt Key gt          std  size t operator   const Key amp  k  const             using std  size t        using std  hash        using std  string            Compute individual hash values for first           second and third and combine them using XOR          and bit shifting         return   hash lt string gt    k first                    hash lt string gt    k second   lt  lt  1    gt  gt  1                    hash lt int gt    k third   lt  lt  1                   With this in place  you can instantiate a std  unordered map for the key-type   int main       std  unordered map lt Key std  string gt  m6             John    Doe   12    example            Mary    Sue   21    another            It will automatically use std  hash lt Key gt  as defined above for the hash value calculations  and the operator   defined as member function of Key for equality checks   If you don t want to specialize template inside the std namespace  although it s perfectly legal in this case   you can define the hash function as a separate class and add it to the template argument list for the map   struct KeyHasher     std  size t operator   const Key amp  k  const         using std  size t      using std  hash      using std  string       return   hash lt string gt    k first                  hash lt string gt    k second   lt  lt  1    gt  gt  1                  hash lt int gt    k third   lt  lt  1           int main       std  unordered map lt Key std  string KeyHasher gt  m6             John    Doe   12    example            Mary    Sue   21    another            How to define a better hash function  As said above  defining a good hash function is important to avoid collisions and get good performance  For a real good one you need to take into account the distribution of possible values of all fields and define a hash function that projects that distribution to a space of possible results as wide and evenly distributed as possible   This can be difficult  the XOR bit-shifting method above is probably not a bad start  For a slightly better start  you may use the hash value and hash combine function template from the Boost library  The former acts in a similar way as std  hash for standard types  recently also including tuples and other useful standard types   the latter helps you combine individual hash values into one  Here is a rewrite of the hash function that uses the Boost helper functions    include  lt boost functional hash hpp gt   struct KeyHasher     std  size t operator   const Key amp  k  const           using boost  hash value        using boost  hash combine            Start with a hash value of 0            std  size t seed   0            Modify  seed  by XORing and bit-shifting in          one member of  Key  after the other        hash combine seed hash value k first          hash combine seed hash value k second          hash combine seed hash value k third              Return the result        return seed           And here   s a rewrite that doesn   t use boost  yet uses good method of combining the hashes   namespace std       template  lt  gt      struct hash lt Key gt                size t operator    const Key amp  k   const                          Compute individual hash values for first  second and third                http   stackoverflow com a 1646913 126995             size t res   17              res   res   31   hash lt string gt     k first                res   res   31   hash lt string gt     k second                res   res   31   hash lt int gt     k third                return res

[c++] C++ unordered_map using a custom class type as the key

Examples related to c++

Examples related to hash

Examples related to g++

Examples related to unordered-map

Examples related to hashtree