Everything about C++ STL MAPS - Part 1 | Competitive Programming Course | Episode 25

This video is part 1 of C++ STL MAPS. In part 1, I discuss in detail about maps, their functions, how to use them and this video due to time restriction I only discuss normal maps and next part I will discuss Unordered maps and a basic Introduction to Multimaps as well.

Practice Questions:
Note: Its hard to find practice questions particularly for STL as they are generally used with other concepts involved hence not providing a lot of them in STL videos. Below are some questions for practice:

Timestamps:
Basics of Map : (0:00)
Basic code of Map : (3:44)
Find And Erase : (11:59)
Time complexity dependency on keys: (16:45)
Question on Map : (19:10)

Be a part of our awesome Community. Join

You can follow me on below platforms for all the latest updates

Blog(Not frequently updated)

Hashtags
#maps #unordered #stl #tutorial #competitivecoding

[iamluv]

Hi everyone there is a little correction at 11:40, I said that loop is O(NLogN) but it O(N).
Explanation : Accessing values through iterator is a O(1) operation as iterator has address of the value and access value at some address if you know the address is a unit time operation. Now when we traverse the map, we start from m.begin() and are doing it++ in each step, it++ is also O(1), so whole map traversal is O(1) only. at 11:40 we are not using iterators but internally that only is happening, pr is the value at address pointer by iterator, internally range based loops is also iterating through maps using iterators and then providing us reference to to the value at that address.

But when you want to directly access some specific value in map using m[key] or m.find(key), these are log(n) operations as log(n)time is taken by map to search this key.

[aditya-]

Tbh u r the first youtuber whose cpp lectures are really understandable

[abhishekhorton]

bro your playlist is amazing I never felt that much motivated yet but after this I'm solving some good questions please complete this course for students like me it's very helpful for real thanks a lot.

[harshitsingh]

I visited this channel first time, and i am very much impressed by the ease with which luv teaches.👌🏻

[omkarnaik]

The transition at 23:50 was so smooth ^^

[an_inquisitive_boy]

Really this is one of the most underrated channel in YouTube. Hats off to you for providing detailed videos on such important concepts like these. Please continue making videos on such topics.

[VC-dmjp]

Just want to thank you for such a beautifully explained video, always had a problem with handling maps but now, it's all crystal clear. Again, thank you

[AgnivaBanerjee]

Things learnt.
//Everything about C++ STL MAPS - Part 1 | Competitive Programming Course | Episode 25
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define REP(i, a, b) for (int i=a; i<b; i++)
#define ll long long
void print(map<int, string> &m)
{
cout<<m.size() <<endl;
for(auto &p : m) //p is a pair
{
cout<<p.f<<" "<<p.s <<endl;
}
}
int _1()
{
map <int, string> m ; //maps
m[1]="abc"; //O(log n) complexity
m[5]="cdc";
m[3]="acd";
m[6]="a";
m[5]="cde";
print(m);
}
int _2()
{
map <int, string> m ; //maps
m[1]="abc"; //O(log n) complexity
m[5]="cdc";
m[3]="acd";
m[6]="a";
m[5]="cde";
print(m); cout<<endl;

auto it=m.find(3) ; // pointing to the map at key 3 if it exists, otherwise points to the end of the map
if (it==m.end()) cout<<"NO VALUE" ; //m.end() refers to the end of the map
else cout<<it->f<<" "<<it->s<<endl; ;

if(it!=m.end()) m.erase(it); //erase
print(m); cout<<endl;

m[3]="acd";
m.clear(); //clear
print(m); cout<<endl;
}
int lexico() //print unique strings in lexicographical order
{
map <string, int> m; //here the key is a string!! integer will be storing the count
int n;cin>>n;
for(int i=0;i<n;i++)
{
string s;cin>>s;m[s]++ ;
}
for (auto &p : m )
{
cout<<p.f<<" "<<p.s<<endl;
}

}
int main()
{
lexico();
}

[AnisurRahman-dgjm]

I stuck map in the last few months, But this video really help me. Your approach is very unique and helpful for all. Thank You

[smazimuddin]

I have watched many tutorial in youtube, ,but i havenot seen anyone to teach like this, , very helpful..

[gauravawasthi]

buddy you nailed it.. big tym .. i aint gonna miss any of ur content from nw on .. cheers to ur hard work mate :)

[ayushjain]

Note and Code :)
#include <bits/stdc++.h>
using namespace std;
/*
- A map element has a key and a corresponding value mapped to it.
- Internal implementation of map is Red Black Tree
- So map is basically a pair that stores key and values.
- Map elements are not stored in contiguous blocks... the elements are connected through links. Thus while using iterator dont use it+1 ....u should either use it++ or ++it
- Map → It stores the keys in ascending order
- Unordered Map → No order.
*/
void printmap(map <int, string> &m)
{

for(auto &val:m)
cout<<val.first<<" "<<val.second<<endl;
cout<<endl;
}
int main()
{
map <int, string> m;
m[3]="diid";
m[7]="eiiw";
m[6]; //this will initialise the value as empty string..if value is of int type than it would be initialised as 0
m.insert({5, "sfig"});
m[2]="aido";
map<int, string> ::iterator it;

cout<<it->first<<" "<<it->second<<endl;
//accessing(m.size(), m.find() etc..), declaring(m[6];), initialising(m[3]="diid",m.insert({4,"ffij"})) takes O(logn)
//But accessing elements using an iterator takes O(1) time...even when u use it++
//so printing the values will take O (n) time
cout<<endl;
m[7]="ffoi";//Keys in a map are unique..so when u try to insert a new value it will replace the old one
printmap(m);
auto itp=m.find(3);//find returns an iterator pointing to that key in log n time
if(itp==m.end())//If the key is not present in the map the iterator will point to m.end()
cout<<"value not found"<<endl<<endl;
else
cout<<itp->first<<" "<<itp->second<<endl<<endl;

m.erase(5);//You can pass the key or an iterator....log(n);
printmap(m);
if(itp!=m.end())//make sure that the iterator points to a valid key...else it will show segmentation fault
m.erase(itp);
printmap(m);
m.clear();//this will erase the whole map m
printmap(m);

//Insertion takes place by comparing the new key with existing keys..
//If key is an int ...it will require O(logn) time to compare..where n is the size of the map
//If key is a string of length x..then time required to compare..i.e.insertion...will be O(x*logn)

/*
Q.given n strings and q queries.In each query you are given a string print its frequency
n<=10^6 q<=10^6
|s|<=100 |s|-> length of the string
*/
map<string, int> m1;
int n, i;
string x;
cin>>n;
for(i=0;i<n;i++)
{
cin>>x;
m1[x]++;
}
for(auto itm1:m1)
cout<<itm1.first<<" "<<itm1.second<<endl;
//If the length of string |S|<=10^5 ...then doing this will exceed the time limit..coz time complexity would be (10^5)*(10^5)*log10^5
}

/*
INPUT:
8
abc
def
abc
ghj
jkl
ghj
ghj
abc

OUTPUT:
2 aido
3 diid
5 sfig
6
7 eiiw

Size:5
2 aido
3 diid
5 sfig
6
7 ffoi

3 diid

Size:4
2 aido
3 diid
6
7 ffoi

Size:3
2 aido
6
7 ffoi

Size:0

abc 3
def 1
ghj 3
jkl 1
*/

[gyanabrota]

Your efforts are really commendable ❤️

[upscshorts]

Love u bhyya thank you baki sb, Sirf view and subscriber ke liye krte hai bt aap *why when and how to use it* btate hai

[HimanshuKumar-jwsw]

I visited this channel first time, and i am very much impressed by the ease with which luv teaches

[XYZ-]

You are making my programming journey much more easier. Take love&respect from Bangladesh.💚

[rythmrana]

Great work bro, this video gave me some pointers that i didn't knew about even after reading articles on maps from gfg and other sources. Thank you for you efforts.

[harshsingh]

Your teaching style is really impressive. Thanks a lot bro for all your hard work.

[vivekmesuriya]

You cover complicate topic very easily and solve all doubts

[DhruvSharma-mhvf]

I have seen so many cpp playlists until now but yours is just on another easy to understand...thank you so much for such valueable resource brother 🌸🛐