-1

I am trying to convert the entire elements of a matrix in to a hashmap. for that what i tried is using map<pair<int,int>,int>mp;

where pair<int,int> are the array indices and the value is the value in the element of a matrix. so i tried this way mp[{i,j}]=value;

It works fine but what i am interested in is finding the time complexity .In general if there and n keys maping to a value what will be the time complexity and how.

Doddi girish
  • 75
  • 1
  • 7

1 Answers1

1

Just to clarify, map container in C++ is a tree-based structure. You mentioned using a hashmap. unordered_map is a hash-based container in C++.

As for the unordered_map (https://en.cppreference.com/w/cpp/container/unordered_map):

Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.

Piotr Kózka
  • 69
  • 5
  • I got a clarifiation about map and unordered_map but in the above mentioned link i didn't get any information about hashmap with two keys or in general n keys – Doddi girish Jan 12 '21 at 12:03
  • @Doddigirish If 2 keys need 2 comparisons in Order Notation `O(n) + O(n)` is `2O(n)` which is `O(n)`. Substitute the actual Order and number of keys into the above. – Richard Critten Jan 12 '21 at 12:05
  • @Doddigirish If you mean how to use a pair as a key, for example, you need to provide a hash function for your key type. Please have a look at this: [link](https://stackoverflow.com/questions/32685540/why-cant-i-compile-an-unordered-map-with-a-pair-as-key) – Piotr Kózka Jan 12 '21 at 12:44