Using unordered_map with key only to store pointers (dismiss value)

user_11770390 0
Viewed 334

I'm implementing an algorithm that checks nodes in a mesh for a certain value. To store information on which node I have already checked I'd like to use an unordered_map with the pointer to the node as a key. I can then simply use umap.find(pointer) to see if the node was already checked and skip it. This way I can accomplish it in O(n) time.

However I don't need to actually store a value for the map. The key itself is enough information. Is std::unordered_map even the right solution then? If so, what should I put for the "value" field maximize performace? I have a 32bit embedded system, so I thought of just putting uint32_t or uint_fast32_t there.

tl;dr:

  • Is std::unordered_map the right tool to store keys without values?
  • Will the native hash function work well for pointers? Or would you suggest a different hashin algorithm?
  • What do I put as "value" for the map if using std::unordered_map to optimize for performance?
unordered-map pointers c++11 stl
2 Answers

Is std::unordered_map the right tool to store keys without values?

I would use a std::unordered_set in these situations.

Will the native hash function work well for pointers?

Yes. It is most likely just a cast from pointer to std::size_t.

What do I put as "value" for the map if using std::unordered_map to optimize for performance?

If you use a std::unordered_set instead, there is no value, only the pointers.

user_75822470

Is std::unordered_map the right tool to store keys without values?

No - std::unordered_set is the one to use when you don't have distinct keys and values.

Will the native hash function work well for pointers? Or would you suggest a different hashin algorithm?

The "native" compiler-supplied hash function probably casts the pointer value to size_t - a kind of identity hash. That may or may not work well depending on the compromises your Standard Library has chosen. GCC and clang use prime numbers of buckets in the hash table, so it will work fine. Visual C++ (and many non-Standard hash table implementations) use powers of two (i.e. 128, 256, 512...). Powers of two are used because it's very fast to map them on to buckets - just AND with a bitwise mask (127, 255, 511) to retain however-many less-significant bits you need. The problem with doing that with pointers is that often the pointed-to objects have some alignment, so they may all be multiples of e.g. 4 or 8. A multiple of 8 always has the three least significant bits set to 0: those bits don't contribute to the randomised placement of the value in a bucket. Instead, only every 8th bucket will receive any share of the elements being hashed. If you have an implementation like this, then you're probably better off using a better hash function. At the least, you could say bit-shift the pointer values right by enough to remove the known zeros.

What do I put as "value" for the map if using std::unordered_map to optimize for performance?

Again, you should use an std::unordered_set, so don't have to worry about a value.

user_4107670
Related