Use pair to do unordered_ Key value of map

background

Standard library unordered_map It is implemented using hash table , For the built-in type standard library, pass std::hash Provides the implementation of hash function , Therefore, if non built-in types are used as key values , The programmer needs to provide the implementation of its hash function .

use pair Make key value

①． Custom hash function

struct pairHash
{
    
  template<typename T,typename U>
  size_t operator()(const pair<T, U> & p) const
  {
    
    return hash<T>()(p.first) ^ hash<U>()(p.second);
  }

  template<typename T, typename U>
  bool operator() (const pair<T, U> & p1, const pair<T, U> & p2) const
{
    
    return p1.first == p2.first && p1.second == p2.second;
  }

};

②． Code example

unordered_map<pair<int, int>, int, pairHash, pairHash> m;
m[{
    2, 4}] = 24;
m[{
    4, 2}] = 42;

cout << m[{
    2, 4}] << endl;
cout << m[{
    4, 2}] << endl;

Universal hash function

①． summary

For any custom type , We only need to provide its hash function as unordered_map Of key Use .

②． Universal hash function

template <typename... Types>
size_t hash_val(const Types&... args)const
{
    
  size_t seed = 0;
  hash_value(seed, args...);
  return seed;
}

template <typename T, typename... Types>
void hash_value(size_t& seed,const T& firstArg,const Types&... args) const
{
    
  hash_combine(seed, firstArg);
  hash_value(seed, args...);
}

template <typename T>
void hash_value(size_t& seed,const T& val) const
{
    
  hash_combine(seed, val);
}

template<typename T>
void hash_combine(size_t& seed,const T& val) const
{
    
  seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

③． Code example

struct demoStruct
{
    
  string name;
  int id;
    
  demoStruct( const string & m_name ,int m_id):name(m_name),id(m_id){
    }
  bool operator == (const demoStruct &demo) const
  {
    
    return demo.id == id && demo.name == name;
  }
};

class CustomHashDemo
{
    
public:
  std::size_t operator()(const demoStruct& c) const
  {
    
    return hash_val(c.name, c.id);
  }
private:
  /* ditto */
};

int main()
{
    

  unordered_map<demoStruct,int, CustomHashDemo> m;
  m[{
    " Zhang San ", 12}] = 24;
  m[{
    " Li Si ", 42}] = 42;
    
  return 0;
}