Understanding vector, map and their uncommon implementation:Explanation with their Code

Exploring the power of STL containers

Photo by Caspar Camille Rubin on Unsplash

Hey guys,this is my first article on medium so suggestions are most welcomed, I thought of writing an article which contains precise explanation with precise code as i am not going to waste my time by speaking on why this is needed and all,So i begin my series of articles based on the responses i will be writing articles further on ds algo etc…Mainly i will try to cover implementation portion of it by using real problems as most of the sites lacks that information.In this article i am going to discuss on following topics:

1. Vector
2. Map

So lets explore and understand about them in simple words and in detail:

1. Vector:-Vector is basically a dynamic array.Now you might be wondering that what exactly we mean here by dynamic?

In a nutshell:-Dynamic means flexible,means size is not fixed.Like an array has constant/fixed size,so you may have question in your mind then what is the need of using vector.See it is useful in questions where we don’t have any idea about size and in array we cannot erase values at arbitrary position,whereas we can erase values in vector using vector erase function.

Now in programming it is believed that understanding the implementation part will help you in better way rather than wasting time on reading theory,

Implementation:

1. Vector Representation:-vector<int>v;vector<int>v(n),vector<int>v[n];

Now you saw that i wrote three representations,so what are the differences between them.

1. vector<int>v:-This represents that size of vector is not fixed here,it can change according to the situation. For eg-Initially size of vector is 0,and now if i did operation v.push_back(1),here push_back is used to insert value inside vector,so now size of vector will be 1,and similarly again i perform v.push_back(8),now size of vector is 8,and lets traverse the vector…so we will write for(i=0;i<v.size();i++){v[i]……}so now we can use it as an array…push_back inserts value at the end,like in above example v[0]=1,v[1]=8…Now i told you that we can erase values in vector..So if we want to erase value at desired position then apply v.erase(v.begin()+desired position).There are other ways of erasing also.
2. vector<int>v(n):-This is exactly same as int a[n].
3. vector<int>v[n]:-This means vector of vector,this one will better understand by example.

v[0].push_back(1);v[0].push_back(8);v[4].push_back(-1);

v[6].push_back(5);

So above we saw that v[0] is one vector and inside that one another vector is present of size 2 and its elements are 1 and 8 respectively.so if we want to traverse each element individually:-

for(i=0;i<v.size();i++)

{for(j=0;j<v[i].size();j++)

{

v[i][j]……//means whatever operation you want to perform can do…as v[i][j] is individual element like v[0][1]=8,its like 2d matrix.

}

}So above v.size()==3,as one is v[0],v[4],v[6],in nutshell we understand that inside one vector one other vector is present ,this is mainly used in graphs as when you will read about depth first search there you will get to know about adjacency list.

2)Map:-Very Powerful STL tool.

Lets understand map by example.Q)Say in a class we have marks of 10 students in maths exam-10,50,50,30,24,50,20,30,10,50…our question is that count no.of students corresponding to marks obtained?Means how many have scored 50,how many have scored 10 likewise……..

So if our question would have asked calculate frequency for 50 marks only then we could have solved it easily by running a loop and taking count of 50 marks students….but here we have to calculate frequency for each individual marks….so in cases like this our Map is helpful….

Implementation:

map<int,int>m1; This is representation of map.

for(i=0;i<n;i++){

m1[a[i]]++;

}

As you can see above m1[a[i]]++,so basically map is also an array which stores value in the form of key value pair…..here key is marks and value is count of students corresponding to that marks…like m1[50]=4,m1[24]=1 in above example likewise…..so you can see map is also an array but here index is not like array one,here we have one index as 24 ,one as 50 etc…and map stores index in sorted order so like when you will traverse map..then first of all m1[10] will come then m1[24] likewise…..

Now question comes how we will traverse the map?As for traversing the array,vector we have 0-index and in ordered form…so we simply run loop for(i=0;i<n;i++) and we can easily travel them ,but in the case of map as we saw that index was like 24,50,10,30 etc..and we don’t know them beforehand so how we will tackle them…..

For traversing map,set etc we use concept of iterator

What is iterator:In simple words we can say that it is a kind of pointer.Lets move on its implementation,Like here we will traverse map using iterator,its same as traversing array using simple for loop

Implementation:

map<int,int>::iterator it=m1.begin();

for(it=m1.begin();it!=m1.end();it++)

{

int k= it->first; //means it->first refers to map key which is 24,30,50 etc..

int r= it->second; //means it->second refers to map value that is m1[50] value,m1[24] value….say m1[50]=4…so it->first=50 and it->second =4..

cout<<No.of students k marks is r<<endl;

}

3. So we saw how to traverse map using iterator…and say if we want to find maximum number of students corresponding to one particular marks,then we will apply ….if(it->second>p){p=it->second;}….inside iterator loop we will use this condition….likewise anything we can do…And we will see more applications of map,set at the end after understanding pairs ,set etc……

Above one is known as ordered map as it stores unique keys…and all keys are in sorted manner….key refers to index in basic terms….Then we have unordered map which doesn’t store keys in sorted manner and then we have multimap which allows duplicating of keys,these two we will understand further in other articles..First we should be clear with basic implementation of map..Lets discuss one more final example to have better hold on implementation part of map…say we have string=”abaaabccaababa”

And our question of is maximum frequency of occurence of any substring of size 3.I hope you have idea about string and substring and if not then let me tell you in short…A substring of size 3 in above example can be-aba,aaa,baa,aab,bcc,cca,caa etc…means continuous characters of size 3 starting from any postion is substring …in simple words

Now lets move on implementation of this question….

map<string,int>m1; Here you might be wondering that why i wrote string as key,because we are going to take count of substring so key will be string and value is count so we wrote int as value…these things you need to keep in mind while implementing map.

for(i=0;i<n-2;i++)//n=s.size(),n-2 i guess you are clear as substring of size 3 so we need to take valid input or else error will be thrown…

{

m1[s.substr(i,3)]++;

}

So here in map we will have our map like m1[“aba”],m1[“caa”],m1[“baa”] likewise…..For maximum..lets traverse the loop

map<string,int>::iterator it=m1.begin();int p=0;

for(it=m1.begin();it!=m1.end();it++)

{

if(it->second>p)

{
p=it->second;

}

}

So answer of p will be 3 as m1[“aba”]=3…and one more thing if we are required to print substring then inside that if condition just add

string s1=it->first;

So we saw the basic implementation of map,then there is one more information map contains if we will write m1.size() it returns no. of unique keys our data contains,then we have this option also m1.erase(key),means if we write m1.erase(“aba”) then our m1[“aba”] …will be erased….and we can use one more function m1.find(“aba”)…lets see its implementation

map<string,int>::iterator it1 = m1.find(“aba”);

if(it1==m1.end())

{

//means key is not present
}

else if(it1!=m1.end())

{

//means key is present

}

So using this m1.find() function we can check whether key is present or not,rest function you can study from this link…Like there is one function m1.upper_bound,lower_bound this all you can study from this link…

One thing i forgot to tell you that iterator can be written in other way also like

for(auto it:m1){}||for(auto it=m1.begin();it!=m1.end();it++)

Now you know we can travel map in reverse way also like as we know that we can travel array/vector in reverse manner using for(i=n-1;i≥0;i- -) similarly here we use for(auto it=m1.rbegin();it!=m1.rend();it- -)………

Then we can store map keys in descending order by using this function

map<int,int,greater<int>()>m1; Likewise there are many more operations which you will get to know while practicing.In my further articles i will try to cover some advanced implementation of maps by solving standardized questions,as i believe that by real problems we get better feel of any topic right?

Photo by Priscilla Du Preez on Unsplash

3)Some Basic Thing but sometimes tricky

To understand this lets study about pairs first…

Pairs is also a kind of array where in value portion we can store two values…

Like say rishav has got 20 marks in maths and 30 marks in science,similarly rohit has got 15 marks in maths and 0 marks in science…so how we will store theses values

Implementation

pair<int,int>p1;

p1[0].first=20,p1[0].second=30;p1[1].first=15,p1[1].second=0;if 0-index is of rishav and 1-index is of rohit.

pairs we can use in many ways now lets look on deeper implementation of it….

vector<pair<pair<int,int>,int>>v;

So what this above representation implies….This means if we write

v.push_back({{20,30},40});({}is used for make_pair operation)

so v[0].first.first=20;

v[0].first.second=30;

v[1].second=40;

Likewise if we write

vector<pair<pair<int,int>,pair<int,int>>>v;

v.push_back({{20,0},{10,30}});

so in this way we can store value for above representation

which means v[0].first.first=20;

v[0].first.second=0;

v[1].second.first=10;

v[1].second.second=30;

so i guess you are getting some feeling by observing few examples above.

We can use pairs in map also like see.

map<pair<string,string>,int>m1;

m1.insert({{rohit,rishav},4});

m1[{rohit,rishav}]=4;

here key is {rohit,rishav} and value is 4.

map<int,vector<int>>m1;

what does this mean…

m1[1].push_back(4);

m1[1].push_back(-1);

m1[3].push_back(6);

m1[3].push_back(4);

so how we will traverse map in such case…

map<int,vector<int>>::iterator it=m1.begin();

for(it=m1.begin();it!=m1.end();it++)

{

for(j=0;j<it->second.size();j++)

{

if(it->second[j] ) //so this it->second[j] this term tells us the values present inside the vector like m1[1] contains -1,4 etc…..likewise…so in this way we can traverse the map…for this case

}

}

We can have many operations like this say

map<pair<int,int>,vector<int>>m1;

map<int,set<int>>m1;

map<int,multiset<int>>m1;

map<string,pair<string,int>>m1;

etc…..

Set/multiset we will discuss in further articles….

Overall

So,i tried to explain three concepts from basic one was map,vector ,iterator…Based on the responses i will move further on articles of ds,algo,set/multiset etc….I will try to cover almost all data structures and algorithm with help of examples/problems only….Suggestions are welcomed and i am sorry if i did any mistakes,grammatical errors as this was my first article on medium.