Making a hash table of iterators in C++

Question

I'm trying to accelerate a specific linked-list operation by hashing some of the node pointers. This is the code I'm using:

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

In Visual Studio 2012, I get an "error C2338: The C++ Standard doesn't provide a hash for this type", since the compiler doesn't know how to hash iterators. Therefore, I need to implement my own hash function for list iterators like so:

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)

I'm having trouble figuring out what members of the iterator guarantee uniqueness (and, therefore, the members that I want to hash). Another concern is that those members may be private.

One solution that comes to mind is re-implementing and list::iterator, but that seems like a hack and introduces more code to maintain.

Answer 1

Use the address of the element that the iterator refers to.

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

But this will only work for dereferenceable iterators, not end() or list<int>::iterator().

Answer 2

You can use pointers to the element in place of iterators. Let's say you had a list of structs MyStruct. You can use

unordered_set<MyStruct*> myhashset;

and the C++ standard library already implements std::hash for any pointer.

So if you ever need to insert or search listIt then use &(*listIt) which will get the pointer of type MyStruct*.