Using std::map in CPP

Maps are associative containers where values are mapped to their unique keys. The keys are sorted in ascending order by default.

Maps are widely used because of its freedom of datatype assignment. Also, the keys are assigned dynamically which results in better memory management than any trivial DS (like, arrays).

Map in C++ is one of the most important topics for Competitive Programming.

Features:

1. Freedom of datatype assignment: The keys should be a set of any homogenous datatype (string, int, float) and the mapped values should be a set of another (or same) homogenous datatype.
2. Keys are assigned dynamically: If you want 1000 as an Integer index (or key), a simple array would require you to allocate memory worth of 1000 integers. But, the same task using map will require a single integer block allocation.

Sample Problem:

You are given N strings as input. Print the frequency of all distinct strings encountered.

General Solution –

• A basic solution would be to run two loops and count the frequency of all strings encountered.
• Complexity: O(N * N)

Optimized solution –

• Maintain a Map with string datatype as the key and integer datatype as its mapped value.
• The idea is to map the count of string to the string itself. Whenever we encounter a string, we increment its mapped integer value. Now, if a string repeats itself, the count value will be incremented leaving us will the frequency of the string.
• Complexity: O(N)

Code:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    //Defining the map with key as a string and value as an integer
    map <string, int> frequency_map;
    
    //Number of strings
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++)
    {
        string input;
        cin >> input;
        
        //Incrementing the count of inputted string
        frequency_map[input]++;
    }
    
    //Traversing the map
    for(auto i = frequency_map.begin(); i != frequency_map.end(); i++)
    {
        // first value denoted the key while second denotes the value
        cout << i->first << " : " << i->second << '\n';
    }
}

Input:-
5
Rohit
Ayush
Raman
Rohit
Raman

Output:-
Ayush : 1
Raman : 2
Rohit : 2

Comment out your feedback, suggestions or any mistakes. Hope it was a great learning session for you.
Do not forget to share and Subscribe.

Happy coding!! ?

Recommended -