difference between map and unordered map : Time complexity

Question

Hi

AFAIK, map sorts data based on key value where as unordered map maintains order in which data was inserted. Is this true?

Another doubt is it's use case. If order of data is not imp, can we use both intergengably?
If i am not wrong, does finding data in unordered map quicker than map?

Answer 1

Unordered_maps occupy a slightly bigger space since the key you provided is first passed through a hash function producing a hash that is mostly larger than the original key that you provided.It is this hash that is then used in a hash table as the new key to store your data.

Unordered_maps are quicker since the element that you want to access is retrieved directly from the hash table(since the hash,which is used as the key, is unique to each element).Maps use red-black binary trees that typically involve moving from one element to another down the tree structure before you reach your intended element,hence they are slightly slower

Answer 2

The answer to the first question is no.As far as I know an unordered_map does not always maintain the order of insertion of its elements due to a number of reasons such as the hash function used,the load factor etc.

For an example,run the short code below 👇that I wrote to demonstrate this

https://code.sololearn.com/ckrhE20lau6B/?ref=app

Answer 3

As for interchangeability of the two,I would say yes you can use them interchangeably.However the decision to choose one over the other rests squarely on the programmer's hands since each has its own set of advantages and disadvantages.
For example unordered_maps offer quick access to the contained elements(O(1) time complexity) but occupy more space than the corresponding map.
Maps occupy less space but have a higher access time(O(log n))

Answer 4

Anthony Maina any reason why unordered_map occupy more space even though both of them store same thing i.e. value and key.

Also why unordered_map is quick in search algorithm?

Answer 5

What is that "AFAIK" Means bro?

Answer 6

AMOGHA. A. K. Could you please help by elaborating on map helps balancing tree structure?

Answer 7

Thanks Anthony Maina and AMOGHA. A. K.