UnorderedMap

How would you implement bidirectional iterators for generic UnorederedMap class with:
++, --, < and *.
Well first you need to decide and define what say ++ means on your usage of unordered_map. unordered_map means that there is no order relationship between the stored elements (other than as defined by the hash). Would it be just a wrapper around incrementing an iterator? The same with -- and * (de-reference as opposed to multiply)?
Last edited on
Do you know what an UnorderedMap is? Some understanding of the data structure would help.
Unordered map is an associative container that contains key-value pairs with unique keys. Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. Keys with the same hash code appear in the same bucket.

So, the elements do have "some" order, but one must not assume any particular order! There is nothing that prevents you from implementing a bidirectional iterator for an unordered map: Simply start at the first element in the first (none-empty) bucket. The ++ operator moves the iterator to the next element in the current bucket; or, if there are no more elements in the current bucket, to the first element in the next (non-empty) bucket. And the -- operator moves the iterator to the preceding element in the current bucket; or, if there is no preceding element in the current bucket, to the last element in the preceding (non-empty) bucket.
Last edited on
What is the purpose of it?

Normally you access the value by its key. From back and forth is not the way to use a unordered map.
Note that a bidirectional iterator doesn't need to support < comparison (only == and !=).

https://en.cppreference.com/w/cpp/named_req/BidirectionalIterator
Last edited on
yeah I meant == and != not < sry
Registered users can post here. Sign in or register to post.