I'm currently working on implementing all the major data structures from C++ to better understand them and I arrived at the unordered_map, which should be a hash table implementation (it's actually not) and wondered that even if I implement the hash table, how could I make it iterable?
Let's say I'm implementing the hash table with a contiguous array in which I store the elements. When needed I resize the array and copy the elements over.
Since the positions of the elements are determined by the hash function, I cannot guarantee that each position is filled, but also, when iterating over each position in the contiguous array I don't know if it is filled by an actual element or it's just the default value there.
The only solution I thought of is to have a separate contiguous array of boolean values which determine which slots are filled and which are not, but I don't really like this solution.
Do you know of any other solutions of how to solve this issue, while still retaining the O(1) element access?