Is std::unordered_set contiguous (like std::vector)?

Question

I'm storing pointers in std::unordered_set. I do this because I don't want any duplicates (I delete the pointers in the collection, so if there is a duplicate, I will attempt to delete an already deleted pointer). I loop heavily through these sets, and since I know std::vector is the fastest container for looping (contiguous memory), I wondered if std::unordered_set does the same.

If it doesn't, would using a std::vector and checking if the pointer has already been deleted be faster?

Answer 1

Is std::unordered_set contiguous ?

The exact implementation of containers is not detailed by the standard... however the standard does prescribes a number of behaviors which constrains the actual representation.

For example, std::unordered_set is required to be memory stable: a reference to/address of an element is valid even when adding/removing other elements.

The only way to achieve this is by allocating elements more or less independently. It cannot be achieved with a contiguous memory allocation as such an allocation would necessarily be bounded, and thus could be overgrown with no possibility of re-allocating the elements in a bigger chunk.