在C ++中制作迭代器的哈希表

Question

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

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

（[wikipedia reference）

我在弄清楚迭代器的哪些成员保证唯一性（以及因此要哈希的成员时遇到麻烦）。另一个问题是这些成员可能是私人成员。

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

Answer 1

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

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

Answer 2

unordered_set<MyStruct*> myhashset;

并且C ++标准库已经实现了std::hash for any pointer。

因此，如果您需要插入或搜索std::hash，请使用listIt，它将获得类型为&(*listIt)的指针。