使用 pair 做 unordered_map 的键值

背景

标准库中 unordered_map 是使用哈希表实现的，对于内置类型标准库通过 std::hash 提供了哈希函数的实现，因此若采用非内置类型做键值，则需要程序员自己提供其哈希函数的实现。

用 pair 做键值

①．自定义哈希函数

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;
  }

};

②．代码示例

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;

万能哈希函数

①．概述

对于任意自定义类型，我们只需要提供其哈希函数即可作为 unordered_map 的 key 使用。

②．万能哈希函数

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);
}

③．代码示例

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:
  /*同上*/
};

int main()
{
    

  unordered_map<demoStruct,int, CustomHashDemo> m;
  m[{
    "张三", 12}] = 24;
  m[{
    "李四", 42}] = 42;
    
  return 0;
}