samedi 16 octobre 2021

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

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?

Aucun commentaire:

Enregistrer un commentaire