C++ STL: Maps

Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value. No two mapped values can have the same key values.

C++ allows us to use 2 kinds of maps: Ordered and Unordered Maps.

Ordered Maps:

This will store data in sorted order. The inbuilt implementation uses Balanced Search Trees(BST). Hence, the time complexities for various operations is O(LogN).

Unordered Maps:

Unordered maps use hash functions to store data. Hence, the time complexities for addition, deletion, and lookups are generally O(1), but in worst cases when the hash function isn’t efficient then it might shoot up to O(N) due to hash collisions.

Implementation:

#include <bits/stdc++.h>
using namespace std;
int main ()
{
  std::map<char,int> mymap;
  std::map<char,int>::iterator it;
mymap['a']=50;
  mymap['b']=100;
  mymap['c']=150;
  mymap.insert({'d',200}); //insert a key:value pair
  
  for(auto p:mymap)     //printing all contents in map
    cout<<p.first<<" "<<p.second<<endl;
it = mymap.find('b');
  if (it != mymap.end())    //erasing one entry
    mymap.erase (it);
cout <<"d => "<<mymap.find('d')->second<< '\n';   //finding a particular entry
return 0;
}

Questions based on maps :

Q1: https://codeforces.com/contest/918/problem/B

Q2: https://codeforces.com/contest/903/problem/C

Q3: https://codeforces.com/contest/855/problem/A

Q4: https://codeforces.com/contest/4/problem/C

Discord link: https://discord.gg/zEHhKWQm for any questions, debugging sessions.

Flipkart SDE1 Interview Experience

Amazon SDE1 Interview Experience

Google L3 Interview Experience