24

I posted a similar question regarding using pointers as Keys on maps in C++ STL. How are pointers hashed in unordered_maps when used as Keys. More specifically if I define:

std::unordered_map< CustomClass*, int > foo;

Would the default C++ std::hash implementation work to handle these pointers? Is it safe to use? Is this good practice?

underscore_d
  • 6,309
  • 3
  • 38
  • 64
Ammar Husain
  • 1,789
  • 2
  • 12
  • 26
  • you probably mean std::unordered_map and the answer is practicaly the same: you can use pointers if you really mean to hash pointers (and not the object they point to). You can as well implement your own hash (or hash-redirection) to work with the pointed-to objects. – firda Aug 04 '14 at 18:19
  • Yes that's what I meant! I have edited the post to make the correction. Thanks! – Ammar Husain Aug 04 '14 at 18:27

1 Answers1

31

std::hash<T*> is defined but the details of how it operates are implementation dependent. It will certainly be safe to use, and I'd consider it good practice - as long as it's the pointer you need as the key, and not the object contents itself.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • Why does the pointer need to be a pointer to the key instead of a pointer to the entire object? What if I want the key to be a pointer to the object itself? – echo Nov 06 '18 at 14:53
  • 2
    @echo I think you missed my point - the pointer itself is the key, not a pointer *to* the key. So two objects will be separate in `unordered_map` even if the contents of the key object are identical. – Mark Ransom Nov 06 '18 at 15:24
  • Ahhh ok, yes I misunderstood your original comment but now re-reading with new context, I understand what you were saying. It seems like in cases where object contents can be identical for two distinct objects, and the objects don't have a unique key/identifier, you might want to hash object pointers. – echo Nov 06 '18 at 15:37
  • @echo I've actually used this in real code. If you have a callback that passes a void pointer, and you want to know if the object still exists before you use the pointer, you can look it up in an `unordered_set`. – Mark Ransom Nov 06 '18 at 16:25
  • One important consideration is make sure your entries are removed if the pointed-to object is freed, since that address might be re-used by a different object later. – kylefinn Jan 26 '22 at 14:06
  • @kylefinn the one time I used this technique, I used the destructor in the object to remove itself from the table. I also used different tables for different classes, so there was no possibility of mixing unrelated types. There was still probably a slight chance of reusing the same address for a different object of the same type, but at least you wouldn't be risking undefined behavior. – Mark Ransom Jan 26 '22 at 17:34
  • Using the object's pointer as its identity leaves the implementation open for subtle bugs, namely an ABA problem of sorts. Let's say an event is created for an object. Then the object is destroyed and another object is allocated at the same exact address. When the event gets processed, it appears as if the object is still alive when in fact another has taken its place and the event is delivered to the wrong object. The solution to this that I've seen used is instead to use a global counter to uniquely identify the objects. A 64-bit int is more than enough to prevent these sorts of problems. – markusjm Jun 25 '23 at 19:31
  • @markusjm I tried that, but my use case was retrofitting existing code that already used a pointer. I made a generic base class that would work either way, with the default being a counter. In fact I made the counter use only odd numbers so there was no possibility of a collision with a pointer. – Mark Ransom Jun 25 '23 at 20:18
  • One option is to also combine both approaches: use a pointer as the hashtable key but then perform an additional check on the counter value that's stored in the object itself. This way you can use pointers as keys and you only have to change the code that does the equality comparison instead of having to change the code that adds or removes values to the hashtable to use the counter. – markusjm Jun 26 '23 at 12:13