1 00:00:01,290 --> 00:00:06,620 However even so in this video we're going to see this topic in world maps in C++. 2 00:00:07,260 --> 00:00:10,260 So in C++ there are basically two types of map. 3 00:00:10,770 --> 00:00:18,790 So the name of first one is only map and the name of the second one is basically an order to map so 4 00:00:18,790 --> 00:00:24,140 both these two maps are basically implemented in SD in standard them liability. 5 00:00:24,220 --> 00:00:31,030 So just like vector that implemented in SDL stakes out president and Fs SDL queues up visited SDL. 6 00:00:31,240 --> 00:00:33,600 So likewise maps and an ordered a map. 7 00:00:33,640 --> 00:00:41,350 They both are present in SDL so as discussed in last radio so this map is basically implemented using 8 00:00:41,350 --> 00:00:49,490 balanced BSG so that's why all the major function insert delete search so all the functions will take 9 00:00:49,570 --> 00:00:55,820 lo fi in time almost log off and time and this one on read a map. 10 00:00:55,820 --> 00:01:02,600 So this is implemented using hash table so we will learn hash table we will learn about hash table mode 11 00:01:03,020 --> 00:01:05,800 throughout our lessons but not in this radio. 12 00:01:05,870 --> 00:01:10,370 We will also implement our own history well so if you will use hash table. 13 00:01:10,430 --> 00:01:17,990 So basically in order to map uses hash table then all the functions insert delete search all the functions 14 00:01:17,990 --> 00:01:21,350 will take big off one time almost constant time. 15 00:01:21,410 --> 00:01:21,690 OK. 16 00:01:21,710 --> 00:01:22,250 Almost. 17 00:01:22,250 --> 00:01:24,500 Big offer in time almost constant. 18 00:01:25,270 --> 00:01:28,930 So the name of this map is basically unordered. 19 00:01:29,030 --> 00:01:37,850 So that means this map is that our data map via this map is ordered map because it uses BSD and if we 20 00:01:37,850 --> 00:01:39,020 will see the BSD. 21 00:01:39,200 --> 00:01:43,850 So BSD basically ordered there is ordering to your elements. 22 00:01:43,850 --> 00:01:47,770 I can see one case bigger than an edit if you will do D and read. 23 00:01:47,800 --> 00:01:52,850 I was in love BSD so the output will be sorted so we can say if you would like. 24 00:01:52,840 --> 00:02:01,670 Great map you can I the map you can I read this map in the SA data miner because this is ordered Okay 25 00:02:01,970 --> 00:02:06,410 so in this video let's see the invert implementation. 26 00:02:06,410 --> 00:02:09,120 Let's use the inbuilt on an ordered the map. 27 00:02:09,400 --> 00:02:17,010 Okay so in this radial let's see the inmate on order to map so all the functions that are present for 28 00:02:17,120 --> 00:02:23,660 order the map that also present for map all the functions are similar but the time complexities are 29 00:02:23,660 --> 00:02:24,210 different. 30 00:02:24,350 --> 00:02:29,480 So the functions are not present in our road map they will drown in big off one time and the functions 31 00:02:29,480 --> 00:02:34,360 that are present in order to map they will run and log off on time. 32 00:02:34,370 --> 00:02:37,940 So in this we do let's use an outdated map. 33 00:02:37,970 --> 00:02:40,280 Let's use the invoked on that map. 34 00:02:40,370 --> 00:02:42,050 OK so let's start 35 00:02:46,920 --> 00:02:48,570 OK so let's write the code. 36 00:02:48,570 --> 00:02:53,910 So first of all on a map and let's say the name of map is my map. 37 00:02:53,940 --> 00:02:54,870 So is this correct. 38 00:02:54,870 --> 00:02:59,330 No this is not correct because this unaware the map is actually a template. 39 00:02:59,370 --> 00:03:06,310 So basically you have to give the type of key and you also have to give that type of value so my key 40 00:03:06,310 --> 00:03:14,920 should be a string and my value should be integer so my key is basically string and my value is basically 41 00:03:14,920 --> 00:03:15,610 integer. 42 00:03:15,670 --> 00:03:20,080 So if you're using an outdated map let us also include and I read a map. 43 00:03:20,500 --> 00:03:25,390 Otherwise it will give us compilation error and we are also using string. 44 00:03:25,390 --> 00:03:27,130 So let us include string also 45 00:03:33,850 --> 00:03:40,110 Okay so let's first run our program so that if there is in compiling an error through our program is 46 00:03:40,110 --> 00:03:40,730 working fine. 47 00:03:40,740 --> 00:03:45,110 So there are no compulsion at a certain text phase I will call this correct. 48 00:03:45,240 --> 00:03:54,370 So let us first see how can we insert elements. 49 00:03:54,400 --> 00:03:59,080 So first let's see how can we insert elements inside the map. 50 00:03:59,080 --> 00:04:02,090 So basically what do we want to insert. 51 00:04:02,170 --> 00:04:08,800 So we want to insert two things we want to insert key and we want to insert value. 52 00:04:08,800 --> 00:04:18,610 So basically this in order to map this road map it stores this give a loop here in form of beer it will 53 00:04:18,610 --> 00:04:21,920 store this give a loop in form of beers. 54 00:04:22,300 --> 00:04:28,780 So if you really remember we have started about beer glass so what I will do I will make a beer. 55 00:04:29,080 --> 00:04:31,080 First one key. 56 00:04:31,120 --> 00:04:35,900 The second one value and I will push this beer in and out of the map. 57 00:04:35,910 --> 00:04:37,170 I am repeating myself. 58 00:04:38,040 --> 00:04:47,130 This a map so in order to map store give a loop here in form of store key values in form of beers. 59 00:04:47,150 --> 00:04:48,920 So what I will do I will make up here. 60 00:04:49,370 --> 00:04:54,590 So this is basically inbuilt in world class beers and middle class actually. 61 00:04:54,590 --> 00:04:56,810 So I will use the inbuilt glass. 62 00:04:56,870 --> 00:05:02,090 I will give my key which will be string I will give my value which will mean digit and then I will push 63 00:05:02,420 --> 00:05:04,670 this beer inside the map. 64 00:05:04,670 --> 00:05:05,670 Simple. 65 00:05:05,870 --> 00:05:11,910 Let's see so first of all I have to make beer so beer. 66 00:05:11,980 --> 00:05:16,170 First one is string keys a string and the values integer. 67 00:05:16,540 --> 00:05:20,710 And let's say the name B so we can use constructor that is present inside. 68 00:05:20,710 --> 00:05:21,580 This being a class 69 00:05:25,770 --> 00:05:32,090 so ABC common instinct domain teacher and then we can use the insert function. 70 00:05:32,280 --> 00:05:35,510 So my map dart. 71 00:05:35,520 --> 00:05:36,060 Insert 72 00:05:38,770 --> 00:05:44,210 and what I will do I will insert BHP simple. 73 00:05:44,330 --> 00:05:51,960 Now let us run our program so that if there's any syntax edit we can come do no so our program is working 74 00:05:51,960 --> 00:05:54,180 fine so there is no syntax in it. 75 00:05:54,730 --> 00:05:58,750 So this was the first way of inserting. 76 00:05:59,010 --> 00:06:02,680 There is another way of inserting just like Eddie. 77 00:06:02,820 --> 00:06:06,230 So the second way of inserting is very similar to it is what do we do. 78 00:06:06,240 --> 00:06:18,030 We will use squared backwards so my map square brackets G is the E F which is a string and the value 79 00:06:18,150 --> 00:06:20,270 is to. 80 00:06:20,370 --> 00:06:22,950 So this is second way to insert. 81 00:06:22,950 --> 00:06:24,950 So I always use this way to insert. 82 00:06:24,960 --> 00:06:30,060 So this is much much better than first making up here and then using the insert function. 83 00:06:30,150 --> 00:06:37,550 So this is like just like any So this is like Eddie. 84 00:06:37,750 --> 00:06:45,090 So we are inserting the elements inside my map to this is key which is in string and this is value which 85 00:06:45,090 --> 00:06:46,550 is in danger. 86 00:06:46,620 --> 00:06:52,890 Okay so later in our program our program is working fine so there is no errors. 87 00:06:54,460 --> 00:06:54,680 Okay. 88 00:06:54,690 --> 00:07:00,280 So after inserting what we can do let's see how can we access elements. 89 00:07:00,280 --> 00:07:03,070 How can we find on excess elements 90 00:07:07,850 --> 00:07:12,140 so we can access elements using this great backwards just like in 80. 91 00:07:12,150 --> 00:07:22,280 Okay so what I will do I will write C out my map of ABC. 92 00:07:22,280 --> 00:07:28,200 So give me the value corresponding to key ABC so their value will be 1. 93 00:07:28,260 --> 00:07:28,620 Okay. 94 00:07:28,620 --> 00:07:30,810 I inserted 1 inside the map so let's see 95 00:07:33,870 --> 00:07:34,870 so the value is 1 96 00:07:38,000 --> 00:07:44,150 so we can use the square brackets to access the values and we can also choose a squared because to insert 97 00:07:45,160 --> 00:07:48,440 give a loop here inside the map. 98 00:07:48,490 --> 00:07:53,980 Now there is one more function to access the elements using the add function. 99 00:07:54,040 --> 00:08:00,980 So what I will do see out my map dart we can use at function. 100 00:08:01,110 --> 00:08:07,620 So give me the value present at ABC. 101 00:08:07,750 --> 00:08:15,750 So again the output will be when N1 celebrities one and when one is so first one is due to squared records 102 00:08:15,780 --> 00:08:18,690 and the second one is using add function. 103 00:08:18,690 --> 00:08:22,440 So what is the difference between add function and the square brackets. 104 00:08:22,560 --> 00:08:30,600 So it does try to understand so if the key so if the key is present inside the map then they both are 105 00:08:30,600 --> 00:08:33,800 working same they are working the same no difference. 106 00:08:34,040 --> 00:08:43,530 Now let us try to print something which is not present inside the map so see out my map. 107 00:08:43,580 --> 00:08:54,380 Let's use add function to give me the value present at GHG so if you will see carefully we have not 108 00:08:54,380 --> 00:08:56,450 pushed JJ into the my map. 109 00:08:56,720 --> 00:09:02,480 So basically JJ does not exist inside the map so let's end our program and let's see what will happen 110 00:09:05,790 --> 00:09:12,450 so we'll see who does giving me the outer fringe so that basically means the given key is not present 111 00:09:12,480 --> 00:09:13,550 inside the map. 112 00:09:13,590 --> 00:09:19,620 So this added function is throwing me at it when the key is not present inside the map. 113 00:09:19,650 --> 00:09:27,640 So this is going exception when the keys are not present inside the map okay so let's come and get out 114 00:09:30,310 --> 00:09:32,710 and now let us use this grid backwards. 115 00:09:34,560 --> 00:09:44,070 So my map of GJ so give me the value doesn't that give me the value corresponding to key GHC. 116 00:09:44,120 --> 00:09:46,690 Now what do you think what will happen. 117 00:09:46,720 --> 00:09:54,260 So basically these square brackets so there are two possibilities. 118 00:09:54,260 --> 00:09:56,140 First one if the key is present. 119 00:09:56,150 --> 00:09:59,560 So if the key exists it will return me the value. 120 00:09:59,630 --> 00:10:05,190 Now the second is if the key if this key does not exist inside the map then what. 121 00:10:05,210 --> 00:10:12,380 This is great backwards will do so it will push this key inside the map and the value the default value 122 00:10:12,380 --> 00:10:14,370 it will insert will be zero. 123 00:10:14,390 --> 00:10:16,370 So what this square about good will do. 124 00:10:16,370 --> 00:10:22,970 So if the key does not exist inside the map it will push the key value pair inside the map and by default 125 00:10:23,000 --> 00:10:26,520 the value will be zero and it will return me zero. 126 00:10:26,600 --> 00:10:35,380 Okay it will return the value 0 so let's see so this key GHG is not present inside the map. 127 00:10:35,380 --> 00:10:41,350 So this squared Beckett will insert the value value will be zero and it will return to zero. 128 00:10:41,350 --> 00:10:41,800 Let's see 129 00:10:46,340 --> 00:10:52,430 so it is returning with zero it is first pushing the key inside the map with the value zero over the 130 00:10:52,430 --> 00:11:00,990 default value zero and then it is returning me the default value which is zero now my question is how 131 00:11:00,990 --> 00:11:03,410 to check whether a given key is present or not. 132 00:11:04,540 --> 00:11:09,880 Okay so how to check whether a given keys basically present inside the map or not. 133 00:11:09,880 --> 00:11:16,180 So if you will use the add function it will give us added it will throw this exception to the given 134 00:11:16,180 --> 00:11:22,180 keys are not present so we cannot use our function if we will use the square brackets then it will push 135 00:11:22,240 --> 00:11:27,240 it will insert the key inside the map and it will identity the default value which is zero. 136 00:11:27,340 --> 00:11:29,910 So I cannot use this square backwards. 137 00:11:30,070 --> 00:11:31,200 So what can I do. 138 00:11:31,210 --> 00:11:33,880 So basically I have a special function count. 139 00:11:34,300 --> 00:11:38,860 I will use the current function to check whether a given key is present inside the map or not. 140 00:11:38,860 --> 00:11:39,490 So let's see 141 00:11:44,350 --> 00:11:49,140 so I have to check the presence of a key 142 00:11:52,740 --> 00:11:54,980 and we cannot use add function. 143 00:11:54,990 --> 00:12:00,640 Our Square Records so how to check whether a given keys present or not. 144 00:12:00,750 --> 00:12:07,490 So I have a function count so I will do my map not count and I will give key. 145 00:12:07,530 --> 00:12:12,540 So for example I want to check whether the key in GHG is peasant or not. 146 00:12:12,540 --> 00:12:15,250 So what this current function will do. 147 00:12:15,390 --> 00:12:20,980 So what this current function will do it will count how many times the key is present inside the map. 148 00:12:22,680 --> 00:12:29,960 So this current function it will count how many how many times the given key is present inside the map. 149 00:12:30,000 --> 00:12:36,000 So in map a key will represent only one time because I told you the keys are unique. 150 00:12:36,000 --> 00:12:40,900 The keys are unique so called function will return under two things. 151 00:12:40,920 --> 00:12:42,080 0 or 1. 152 00:12:42,960 --> 00:12:49,140 So this current function can return only 2 things to 0 and 1 0 means the key is not present one means 153 00:12:49,140 --> 00:12:50,290 the key is present. 154 00:12:50,430 --> 00:12:54,450 Simple. 155 00:12:54,510 --> 00:12:58,410 So basically if the count is good then zero. 156 00:12:58,560 --> 00:13:00,100 Basically if the count this one. 157 00:13:00,120 --> 00:13:08,770 That means the given keys present so you can write the keys present so keys GJ so JJ is present 158 00:13:13,830 --> 00:13:14,960 in the US part. 159 00:13:15,940 --> 00:13:17,140 You can say at present 160 00:13:31,050 --> 00:13:32,200 let's put in line here. 161 00:13:32,210 --> 00:13:32,550 Also 162 00:13:39,190 --> 00:13:46,500 so if you in the program what will our output so add this line but this great record will look so the 163 00:13:46,500 --> 00:13:52,160 square brackets will push GSA so this condition will become true because the chase present and you're 164 00:13:52,160 --> 00:13:54,130 an output will be JJ is present. 165 00:13:54,140 --> 00:13:54,770 So let's see 166 00:13:58,280 --> 00:14:02,270 JJ is present. 167 00:14:02,400 --> 00:14:08,630 So now let's see how we can update our keys so updating keys. 168 00:14:08,800 --> 00:14:14,520 So just like in every my dear use we will use a square backwards. 169 00:14:14,600 --> 00:14:19,580 So my map of let's say I want to update the value of key ABC. 170 00:14:19,580 --> 00:14:22,110 So what I will do ABC is do. 171 00:14:22,280 --> 00:14:24,550 So initially the value of ABC was 1. 172 00:14:24,590 --> 00:14:27,640 Now I make its value to 20. 173 00:14:27,710 --> 00:14:31,290 Okay so that's how we will update. 174 00:14:31,350 --> 00:14:34,980 Now let us see how to find the size of the map. 175 00:14:35,010 --> 00:14:38,370 How many key value here are present. 176 00:14:38,370 --> 00:14:41,450 So let's put size here 177 00:14:45,840 --> 00:14:46,600 see out. 178 00:14:46,600 --> 00:14:47,170 Size 179 00:14:51,770 --> 00:14:52,780 so have a function. 180 00:14:52,780 --> 00:14:53,830 My God size. 181 00:14:53,890 --> 00:15:00,100 So it will give me how many give a loop here are presently inside the map so I am printing the size 182 00:15:00,100 --> 00:15:09,660 here and let us also parentheses after JJ so I am printing sides two beams okay. 183 00:15:09,670 --> 00:15:12,280 So first one is here before this is squared Beckett. 184 00:15:12,460 --> 00:15:13,670 And the second one is here. 185 00:15:13,720 --> 00:15:18,080 So hopefully this size will increase by 1 because the square brackets will push. 186 00:15:18,080 --> 00:15:18,530 J. 187 00:15:23,250 --> 00:15:25,490 So the size of those two then. 188 00:15:25,520 --> 00:15:33,330 J was pushed and then the size becomes three and JJ is spending. 189 00:15:33,360 --> 00:15:35,700 So now let's see how can we. 190 00:15:35,700 --> 00:15:37,290 It is how can we delude 191 00:15:45,890 --> 00:15:48,320 so it is ing an entry from the map. 192 00:15:50,270 --> 00:15:52,220 So I have a function da. 193 00:15:52,250 --> 00:16:00,470 So what I will do my map dart it is so this it is function will take key as input so I won't do it is 194 00:16:00,470 --> 00:16:10,330 key GHC I am erasing the Kijiji and now let copy this one and let us also copy the size. 195 00:16:10,410 --> 00:16:17,710 So what will happen the size will decrease by 1 and the key G A Change is not present anymore okay so 196 00:16:17,940 --> 00:16:24,690 Kijiji is not present and the size of the map will decrease by 1 because I'm erasing an element so nullity 197 00:16:29,850 --> 00:16:37,240 so JJ was present then I deleted the GHB I erase the key Kijiji so size becomes too so it's decreased 198 00:16:37,240 --> 00:16:42,710 by 1 and JJ is not pleasant anymore. 199 00:16:42,970 --> 00:16:51,070 So basically we know how to insert element how do insert give a loop here and it is just like any so 200 00:16:51,100 --> 00:16:56,350 we know basically how to access the elements using squared records just like get it all using add function 201 00:16:57,700 --> 00:17:03,840 so we have a function my map God size with the help of which we can find out the size of the map. 202 00:17:04,090 --> 00:17:06,760 So now we have a function count. 203 00:17:06,760 --> 00:17:10,660 So with the help of function count we can check whether a given key is present or not. 204 00:17:10,690 --> 00:17:16,780 So this current function it counts how many time a given key is present so it can only return 2 things 205 00:17:16,840 --> 00:17:25,420 0 or 1 0 means not present when means present and for looting for beating our values again just like 206 00:17:25,440 --> 00:17:31,810 today we will use this grid backwards for it using an entry we can use it is function and it will take 207 00:17:31,900 --> 00:17:37,520 key as input then again same function and then again common function. 208 00:17:37,520 --> 00:17:43,640 So for order to map for simple map all the functions are same but their time complexities are different 209 00:17:43,700 --> 00:17:49,710 they will run in log in time and hit all the functions are running in big off one time question time. 210 00:17:49,910 --> 00:17:53,650 So in next video in next few lessons what do we do. 211 00:17:53,750 --> 00:17:59,150 We will solve some problems with the help of an order to map and build a map so that you can have a 212 00:17:59,150 --> 00:18:00,630 better understanding. 213 00:18:00,710 --> 00:18:01,100 Thank you.