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?

CodePudding user response：

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.