unordered_map中使用struct作为key

Question

unordered_map中使用struct作为key

6

我遇到了一个问题，使用结构体作为键将数据放入unordered_map中：


typedef struct osdpi_flow_identificator {
 u32 lower_ip;
 u32 upper_ip;
 u16 lower_port;
 u16 upper_port;
 u8 protocol;
} osdpi_flow_identificator_t;

// custom hash function for osdpi_flow_identificator
struct osdpi_flow_hash {
 std::size_t operator() (osdpi_flow_identificator * key) const {
  hash hash_function;
  std::size_t returnValue =
   hash_function(key->lower_ip)
   + hash_function(key->upper_ip)
   + hash_function(key->lower_port)
   + hash_function(key->upper_port)
   + hash_function(key->protocol);

  printf(" calculated hash: %i\n", returnValue);

  return returnValue;
 }
};

typedef unordered_map <osdpi_flow_identificator*, osdpi_flow*, osdpi_flow_hash> osdpi_flows_hashmap;
typedef osdpi_flows_hashmap::value_type osdpi_flows_pair;
static osdpi_flows_hashmap osdpi_flows;

我的问题是哈希函数对于具有相同值的osdpi_flow_identificators返回相同的值，但是

（涉及it技术）


 osdpi_flow_identificator * flow_id = new osdpi_flow_identificator;
 osdpi_flows_hashmap::const_iterator iter;
 iter = osdpi_flows.find(flow_id);
 if (iter != osdpi_flows.end()) {
  ...

虽然哈希映射中已经有一个具有完全相同值的flow_id条目，但无序映射并未找到它。我通过输出整个哈希映射以及哈希函数打印出相同的值进行了验证。因此，很难理解为什么unordered_map无法找到具有相同哈希值的条目。

我还尝试过重载operator==和operator<，这是我在网络上找到的提示之一，但这些函数也没有被调用。

解决这个问题的方法是不初始化flow_id，但这当然最终会导致分段错误。

任何帮助都将不胜感激！

谢谢 Steffen

- StephenKing

1

这显然是错误的： typedef unordered_map osdpi_flows_hashmap;请问您能否写出unordered_map的正确模板参数？ - Scharron

首先，哈希函数会在您的键上调用，然后如果存在具有相同哈希的某些对象，则会调用operator==。只有在std::map（有序映射）中才会调用operator<。 - Scharron

不需要那个。结构体上存在一个默认的operator==，它会在所有字段上应用==。这应该满足您的需求。正如我所说，只有在哈希冲突时才会调用它。 - Scharron

1

我犯了一个错误。即使没有碰撞，它也必须调用operator==，因为它无法知道找到的元素是否是正确的。我的答案马上就来了;-) - Scharron

所以你有什么想法，为什么我找不到元素？当我搜索条目并且随后插入一个新条目（具有相同的哈希）时，我会得到输出（因为哈希函数中的printf），为什么这能正常工作，而我不初始化flow_id又是什么神秘呢？ - StephenKing

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Scharron · Accepted Answer

好的，我终于找到了 :-)

实际上，您需要为您的哈希定义一个EqualOperator，因为您正在使用指针。应该是这样的：

struct Eq
{
  bool operator() ( osdpi_flow_identificator * id1, osdpi_flow_identificator * id2) const
  {
    id1->lower_ip == id2->lower_ip && // compare all fields.
  }
};

那么你的哈希表声明就变成了

typedef unordered_map <osdpi_flow_identificator*, osdpi_flow*, osdpi_flow_hash, Eq> osdpi_flows_hashmap;

另一种方法是将对象存储在哈希映射中，而不是指针。这取决于你是否真的需要它里面有指针。