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.

That's no iterator! Your future, shrouded is. Iterators, confused are. hashing [iterators] leads to anger, anger leads to hate, hate leads to gdb. — kfsone, Jun 24 '13 at 18:15
@kfsone: I don't particularly like iterators either (after implementing one). Sometimes I miss the days of writing good old C. I don't see any alternatives to iterators in C++, though. — DarthShader, Jun 24 '13 at 18:45
option a) I close my stackoverflow account, option b) I reply "the force be with (*youIt)". — kfsone, Jun 24 '13 at 18:49

score 12 · Accepted Answer · edited Jan 14 '21 at 07:11

12

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().

edited Jan 14 '21 at 07:11

Aykhan Hagverdili

28,141
6
41
93

answered Jun 24 '13 at 18:27

Derek Ledbetter

4,675
3
20
18

@KonradRudolph The iterator may be passed by value, but the address is of the thing it's *pointing to*. – Timothy Shields Jun 24 '13 at 18:31
Do you need more parenthesis there? `return hash()(&*i);` worked better for me. – Eyal Jul 05 '20 at 23:01
@Eyal yes, you do. I added that in with an edit. – Aykhan Hagverdili Jan 14 '21 at 07:31

score 2 · Answer 2 · answered Mar 21 '20 at 04:53

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*.

Making a hash table of iterators in C++

2 Answers2