11

我试图通过散列一些节点指针来加速特定的链表操作。这是我正在使用的代码：

unordered_set< typename list< int >::iterator > myhashset;

在 Visual Studio 2012 中，我收到“错误 C2338：C++ 标准不提供这种类型的散列”，因为编译器不知道如何散列迭代器。因此，我需要为列表迭代器实现自己的哈希函数，如下所示：

struct X{int i,j,k;};

struct hash_X{
  size_t operator()(const X &x) const{
    return hash<int>()(x.i) ^ hash<int>()(x.j) ^ hash<int>()(x.k);
  }
};

（维基百科参考）

我无法确定迭代器的哪些成员保证唯一性（因此，我想要散列的成员）。另一个担忧是这些成员可能是私人的。

想到的一个解决方案是重新实现和 list::iterator，但这似乎是一种 hack，并且引入了更多需要维护的代码。

4

2 回答 2

11

使用迭代器引用的元素的地址。

struct list_iterator_hash {
    size_t operator()(const list<int>::iterator &i) const {
        return hash<int*>()(&*i);
    }
};

但这仅适用于可取消引用的迭代器，而不适用于end()or list<int>::iterator()。

于 2013-06-24T18:27:56.887 回答
1

您可以使用指向元素的指针代替迭代器。假设您有一个 structs 列表MyStruct。您可以使用

unordered_set<MyStruct*> myhashset;

并且 C++ 标准库已经实现std::hash了任何指针。

因此，如果您需要插入或搜索，请listIt使用&(*listIt)which 将获取 type 的指针MyStruct*。

于 2020-03-21T04:53:58.747 回答