1 00:00:01,200 --> 00:00:01,920 Hi, everyone. 2 00:00:01,950 --> 00:00:09,510 So in this video, we are going to see this topic in maps in C++, so in C++ there are basically two 3 00:00:09,510 --> 00:00:10,280 types of map. 4 00:00:10,710 --> 00:00:16,650 So the name of first one is only map and the name of a second one is basically unordered map. 5 00:00:18,520 --> 00:00:25,990 So both these two maps are basically implemented in still standard, no liability, so just like they 6 00:00:26,020 --> 00:00:32,470 are implemented and still states, our president still argues that both are still so likewise maps. 7 00:00:32,470 --> 00:00:33,590 And I don't need a map. 8 00:00:33,640 --> 00:00:35,560 They both are present and still. 9 00:00:36,850 --> 00:00:42,520 So as discussed in last radio, so this map is basically implemented using balanced besty. 10 00:00:43,520 --> 00:00:49,850 So that's why all the major function, insert, delete, search, so all the functions will take a lot 11 00:00:49,940 --> 00:00:55,380 of time, almost log off and time and this one on Redmap. 12 00:00:55,760 --> 00:00:58,780 So this is implemented using hash table. 13 00:00:59,480 --> 00:01:05,000 So we will learn how stable we will learn about how stable more throughout our lessons, but not in 14 00:01:05,000 --> 00:01:05,590 this video. 15 00:01:05,780 --> 00:01:07,270 We will also implement our own. 16 00:01:08,510 --> 00:01:15,380 So if you will use hash table, so basically in order to map uses hash table, then all the functions, 17 00:01:15,380 --> 00:01:21,090 insert, delete, search, all the functions will take big off runtime, almost constant. 18 00:01:21,410 --> 00:01:24,290 OK, almost big oftentime almost constant time. 19 00:01:25,230 --> 00:01:28,480 So the name of this map is basically unordered. 20 00:01:28,940 --> 00:01:32,120 So that means this map is the order to map. 21 00:01:33,470 --> 00:01:40,700 Why this map is already mapped, because it uses besty and if you will see the beast so best basically 22 00:01:40,700 --> 00:01:43,470 ordered there is ordering to your elements. 23 00:01:43,760 --> 00:01:48,830 I can see one case bigger than another, if you will, do the reversal of Vesty. 24 00:01:48,830 --> 00:01:50,350 So the output will be sorted. 25 00:01:50,900 --> 00:01:55,760 So we can see if you like a great map, you can rotate map. 26 00:01:55,790 --> 00:02:00,020 You can edit this map in a manner because this is ordered. 27 00:02:01,250 --> 00:02:08,690 OK, so in this video, let us see the inbuilt implementation, let's use the inbuilt on and order the 28 00:02:08,690 --> 00:02:09,020 map. 29 00:02:09,289 --> 00:02:13,850 OK, so in this video, let's see the inmate in order to map. 30 00:02:14,180 --> 00:02:21,200 So all the functions that are present for in order to map that also present for MAP, all the functions 31 00:02:21,200 --> 00:02:24,080 are similar, but the time complexities are different. 32 00:02:24,320 --> 00:02:26,720 So the functions are not present in our roadmap. 33 00:02:26,750 --> 00:02:32,320 They will run in big off one time and the functions that are present in order to map, they will run 34 00:02:32,320 --> 00:02:33,780 and log oftentime time. 35 00:02:34,340 --> 00:02:37,930 So in this video, let's use an order to map. 36 00:02:37,940 --> 00:02:40,310 Let's use the inbuilt on road map. 37 00:02:40,340 --> 00:02:42,050 OK, so let's start. 38 00:02:46,830 --> 00:02:53,260 OK, so let's write the code, so first of all, on A and let's say the name of map is my map. 39 00:02:53,880 --> 00:02:54,840 So is this correct? 40 00:02:54,870 --> 00:02:59,000 No, this is not correct because this unrooted map is actually a template. 41 00:02:59,310 --> 00:03:03,810 So basically, you have to give the type of key and you also have to give that type of value. 42 00:03:05,080 --> 00:03:10,220 So my guess should be strength and my value should be in danger. 43 00:03:10,960 --> 00:03:15,380 So key is basically string and my value is basically integer. 44 00:03:15,640 --> 00:03:21,660 So if you are using an order map, let us also include I don't need a map, otherwise it will give us 45 00:03:22,840 --> 00:03:23,830 compiler error. 46 00:03:23,830 --> 00:03:25,340 And we are also using string. 47 00:03:25,360 --> 00:03:27,160 So let us include string also. 48 00:03:33,730 --> 00:03:37,840 OK, so let's first run our program so that if there is incompletion error. 49 00:03:39,180 --> 00:03:40,710 So our program is working fine. 50 00:03:40,740 --> 00:03:44,320 So there are no compulsion at a certain tax, I will call this correct. 51 00:03:45,180 --> 00:03:48,540 So let's first see how can we insert elements? 52 00:03:54,340 --> 00:03:58,460 So first, let's see how can we insert elements inside the map? 53 00:03:59,020 --> 00:04:02,120 So basically, what do we want to insert? 54 00:04:02,140 --> 00:04:03,970 So we want to insert two things. 55 00:04:04,670 --> 00:04:07,550 We want to insert key and we want to insert value. 56 00:04:08,740 --> 00:04:17,320 So basically this in order to map this and map it stores, this key will appear in form of paper. 57 00:04:18,130 --> 00:04:21,760 It will store this key value in form of this. 58 00:04:22,270 --> 00:04:25,240 So if you will remember, we have started about Berglas. 59 00:04:25,780 --> 00:04:34,240 So what I will do, I will make upir first one key, the second one value, and I will push this paper 60 00:04:34,260 --> 00:04:35,340 in order to map. 61 00:04:35,830 --> 00:04:36,940 I'm repeating myself. 62 00:04:38,010 --> 00:04:39,270 This Redmap. 63 00:04:40,340 --> 00:04:46,730 So in order to map store, give loopier in the form of stalky values in form of beers. 64 00:04:47,120 --> 00:04:48,900 So what I will do, I will make a beer. 65 00:04:49,340 --> 00:04:54,250 So this is basically in built in world class beers and world class, actually. 66 00:04:54,530 --> 00:04:56,360 So I will use the inbuilt class. 67 00:04:56,780 --> 00:04:58,960 I will give Mickey, which will be strong. 68 00:04:58,970 --> 00:05:04,220 I will give my value, which will be integer, and then I will push this beer inside the map. 69 00:05:04,640 --> 00:05:06,320 Simple LNC. 70 00:05:08,890 --> 00:05:15,970 So first of all, I have to make beer, so beer first one is string a string and the values integer 71 00:05:16,420 --> 00:05:21,580 and let's say the name FCP so we can use constructor that is present inside this class. 72 00:05:25,710 --> 00:05:33,510 So ABC cameraman, stinko main teacher, and then we can use the insert function, so my map. 73 00:05:35,010 --> 00:05:36,000 Not insert. 74 00:05:38,650 --> 00:05:41,050 And what I will do, I will insert BRP. 75 00:05:43,400 --> 00:05:49,490 Simple, now let us run our program so that if there's anything that we can come to know. 76 00:05:50,850 --> 00:05:54,070 So our program is working fine, so there is no one takes at it. 77 00:05:54,660 --> 00:06:01,920 So this was the first way of inserting there is another way of inserting, just like Eddie. 78 00:06:02,760 --> 00:06:07,520 So the second way of inserting is very similar to areas where we will use square records. 79 00:06:07,950 --> 00:06:08,760 So my map. 80 00:06:10,940 --> 00:06:11,900 Square scratchcards. 81 00:06:13,420 --> 00:06:15,880 He is DCF, which is a string. 82 00:06:16,950 --> 00:06:18,750 And the value is to. 83 00:06:20,280 --> 00:06:26,400 So this is second way to insert, so I always use this way to insert, so this is much, much better 84 00:06:26,400 --> 00:06:29,560 than first making up here and then using the insert function. 85 00:06:30,090 --> 00:06:32,040 So this is like just like any. 86 00:06:34,060 --> 00:06:34,870 So this is. 87 00:06:36,290 --> 00:06:39,980 Like Eddie, so we are inserting the elements inside. 88 00:06:40,980 --> 00:06:45,780 My map to this is key, which is a string, and this is value, which is integer. 89 00:06:46,530 --> 00:06:48,090 OK, so let's run our program. 90 00:06:48,660 --> 00:06:51,160 Our program is working fine. 91 00:06:51,720 --> 00:06:52,860 So there is no this. 92 00:06:54,390 --> 00:06:55,860 OK, so after inserting. 93 00:06:56,920 --> 00:07:03,040 What we can do, let's see, how can we access elements, how can we find or access elements? 94 00:07:07,790 --> 00:07:13,220 So we can access elements using this square, because just like in any case, we were will do. 95 00:07:15,270 --> 00:07:16,830 I will write out. 96 00:07:18,460 --> 00:07:19,690 My map of. 97 00:07:21,680 --> 00:07:23,360 ABC, so give me the value. 98 00:07:24,330 --> 00:07:28,160 Corresponding to Gey ABC, so there value will be one. 99 00:07:28,230 --> 00:07:30,190 OK, I inserted one inside the map. 100 00:07:30,210 --> 00:07:30,810 So let's see. 101 00:07:33,880 --> 00:07:34,900 So the value is one. 102 00:07:37,910 --> 00:07:44,180 So we can use the square brackets to access the values and we can also use square records to insert. 103 00:07:45,250 --> 00:07:46,900 Give a little bit inside the map. 104 00:07:48,400 --> 00:07:53,030 Now, there is one more function to access the elements using the ADD function. 105 00:07:53,980 --> 00:07:55,600 So what I will do out? 106 00:07:57,240 --> 00:08:04,440 My map not we can use add function, so give me the value present at ABC. 107 00:08:07,690 --> 00:08:09,760 So, again, the output will be one in one. 108 00:08:12,000 --> 00:08:17,160 So I'll put this one in when one is so first one is due to square records and the second one is using 109 00:08:17,310 --> 00:08:18,010 add function. 110 00:08:18,630 --> 00:08:22,030 So what is the difference between ad function and the square brackets? 111 00:08:22,500 --> 00:08:23,850 So let us try to understand. 112 00:08:25,210 --> 00:08:32,320 So if the key so if the key is present inside the map, then they both are working same, they're working 113 00:08:32,320 --> 00:08:33,260 the same, no difference. 114 00:08:34,000 --> 00:08:38,080 Now, let's try to print something which is not present inside the map. 115 00:08:39,650 --> 00:08:40,760 So, Skout. 116 00:08:42,559 --> 00:08:49,700 My map, let's use add function to give me the value present at GHC. 117 00:08:51,710 --> 00:08:56,400 So if you will see carefully, we have not pushed into the map. 118 00:08:56,660 --> 00:09:01,440 So basically, JJ does not exist inside the map, so let's have no problem. 119 00:09:01,530 --> 00:09:02,500 Let's see what will happen. 120 00:09:05,730 --> 00:09:08,130 So we'll see you just giving me at it out of range. 121 00:09:09,630 --> 00:09:16,590 So that basically means the Gilinsky is not present inside the map, so this ad function is throwing 122 00:09:16,590 --> 00:09:19,590 me at it when the key is not present inside the map. 123 00:09:19,620 --> 00:09:24,450 So this is throwing exception when the key is not present inside the map. 124 00:09:26,140 --> 00:09:27,670 OK, so let's come get out. 125 00:09:30,190 --> 00:09:32,590 And now let us use the square because. 126 00:09:34,500 --> 00:09:35,280 So my map. 127 00:09:36,380 --> 00:09:42,590 Of JJ, so give me the value besant that give me the value corresponding to Kiguchi. 128 00:09:44,030 --> 00:09:45,500 Now, what do you think, what will happen? 129 00:09:46,630 --> 00:09:49,990 So basically, these square brackets. 130 00:09:52,550 --> 00:09:53,930 So there are two possibilities. 131 00:09:54,230 --> 00:09:58,850 First one, if the key is present, so if the key exist, it will return me to value. 132 00:09:59,570 --> 00:10:06,140 Now, the second is if the key if this key does not exist inside the map, then what the square brackets 133 00:10:06,140 --> 00:10:06,490 will do. 134 00:10:06,980 --> 00:10:13,790 So it will push this key inside the map and the value the default value it will insert will be zero. 135 00:10:14,330 --> 00:10:16,320 So what this square bracket will do. 136 00:10:16,340 --> 00:10:22,550 So if the key does not exist inside the map, it will push the key value pair inside the map and by 137 00:10:22,550 --> 00:10:25,760 default the value will be zero and it will return mesero. 138 00:10:26,870 --> 00:10:28,310 It will return the value zero. 139 00:10:29,400 --> 00:10:30,090 So let's see. 140 00:10:31,990 --> 00:10:39,370 So this guy is not present inside the map, so this square brackets will insert the value, value will 141 00:10:39,370 --> 00:10:41,220 be zero and it will return Mesero. 142 00:10:41,320 --> 00:10:41,800 Let's see. 143 00:10:46,310 --> 00:10:47,670 So it is returning with zero. 144 00:10:47,690 --> 00:10:53,990 It is first pushing the key inside the map with the value zero, with the default value zero, and then 145 00:10:53,990 --> 00:10:56,540 it is returning me the default value, which is zero. 146 00:10:58,800 --> 00:11:03,200 Now, my question is how to check whether a given key is present or not. 147 00:11:04,420 --> 00:11:09,310 OK, so how to check whether a given keys basically present inside the map or not? 148 00:11:09,790 --> 00:11:16,210 So if you will use the ADD function, it will give us added, it will throw us exceptional at the given 149 00:11:16,210 --> 00:11:17,020 keys not present. 150 00:11:17,320 --> 00:11:23,020 So we cannot use that function, if you will use the square, because then it will push, it will insert 151 00:11:23,020 --> 00:11:27,030 the key inside the map and it will be the default value which is zero. 152 00:11:27,280 --> 00:11:30,890 So I cannot use this square because so what can I do. 153 00:11:31,150 --> 00:11:33,370 So basically I have a special function count. 154 00:11:34,210 --> 00:11:38,770 I will use the current function to check whether given keys present inside the map or not. 155 00:11:38,800 --> 00:11:39,490 So let's see. 156 00:11:44,300 --> 00:11:45,620 So I have to check. 157 00:11:47,190 --> 00:11:49,140 The presence of a key. 158 00:11:52,620 --> 00:11:56,280 And we cannot use add function or square records. 159 00:11:57,690 --> 00:12:04,500 So how to check whether a given is present or not, so I have a function count, so I will do my map 160 00:12:04,830 --> 00:12:06,710 not count and I will give key. 161 00:12:07,470 --> 00:12:12,090 So, for example, I want to check whether the key is BESANT or not. 162 00:12:12,510 --> 00:12:14,560 So what this current function will do. 163 00:12:15,330 --> 00:12:20,840 So what this function will do, it will count how many times the key is present inside the map. 164 00:12:22,620 --> 00:12:29,040 So this current function, it will count how many how many times the given key is present inside the 165 00:12:29,040 --> 00:12:29,370 map. 166 00:12:29,940 --> 00:12:36,590 So in MAP, a key will represent only one time because I told you the keys are unique, the keys are 167 00:12:36,600 --> 00:12:36,960 unique. 168 00:12:37,170 --> 00:12:42,080 So called function will return only to things zero or one. 169 00:12:42,930 --> 00:12:48,300 So this count function can return only two things to zero and one zero means the key is not present. 170 00:12:48,540 --> 00:12:50,910 One means the keys present simple. 171 00:12:54,450 --> 00:13:01,080 So basically, if the count is good, then zero, basically, if the count is one, that means the given 172 00:13:01,080 --> 00:13:03,360 keys present so you can write. 173 00:13:04,390 --> 00:13:08,790 The keys present, so keys JJ, so JJ is present. 174 00:13:13,830 --> 00:13:14,790 In the early part. 175 00:13:15,850 --> 00:13:17,170 You can say not present. 176 00:13:31,020 --> 00:13:32,580 Let's put a line here also. 177 00:13:39,130 --> 00:13:43,330 So if you read the program, what will your output so add this line. 178 00:13:44,540 --> 00:13:47,670 But this great record will do so, this will record will push. 179 00:13:48,590 --> 00:13:54,140 So this condition will become true because the judges present and output will be judges present. 180 00:13:54,170 --> 00:13:54,770 So let's see. 181 00:13:58,250 --> 00:13:59,480 JJ is Besant. 182 00:14:02,340 --> 00:14:05,130 So now let's see how we can update our quiz. 183 00:14:07,210 --> 00:14:10,420 So updating is so just like in Inari. 184 00:14:12,470 --> 00:14:15,590 Martellus we will square Becket's So my map of. 185 00:14:16,820 --> 00:14:22,490 Let's say I want to update the value of GABSI, so what I will do, ABC is do so. 186 00:14:22,490 --> 00:14:24,140 Initially the value of ABC was one. 187 00:14:24,530 --> 00:14:27,540 Now I make its value to 20. 188 00:14:27,610 --> 00:14:29,210 OK, so that's how we will update. 189 00:14:31,260 --> 00:14:38,850 Now, let us see how to find the size of the map, how many give a loopier are present so. 190 00:14:40,310 --> 00:14:41,480 Let's put here. 191 00:14:45,790 --> 00:14:47,170 Scout says. 192 00:14:51,940 --> 00:14:58,900 So I have a function, my Web site, so it will give me how many developers are inside the map, so 193 00:14:59,050 --> 00:15:00,400 I'm printing the size here. 194 00:15:01,500 --> 00:15:04,010 And let us also Prentice's after GHC. 195 00:15:05,200 --> 00:15:06,910 So I'm printing, say, two times. 196 00:15:09,340 --> 00:15:14,710 OK, so first one is here before this great beckert and the second one is here, so hopefully the size 197 00:15:14,710 --> 00:15:18,560 will increase by one because the square brackets will push GHC. 198 00:15:23,190 --> 00:15:30,200 So the size of stool, then JJ was pushed and then the size becomes three and JJ is president. 199 00:15:33,270 --> 00:15:37,320 So now let's see, how can we it is how can we delete? 200 00:15:45,830 --> 00:15:48,320 So it is an entry from the map. 201 00:15:50,210 --> 00:15:52,970 So I have a function, Daughtry's, so what I will do. 202 00:15:54,350 --> 00:16:01,490 My God, it is so dysfunctional will take as input, so I want to raise Kijiji. 203 00:16:03,360 --> 00:16:05,940 I'm raising the kids and now letus. 204 00:16:07,200 --> 00:16:09,900 Copy this one and let us also copy the site. 205 00:16:10,350 --> 00:16:11,180 So what will happen? 206 00:16:11,190 --> 00:16:13,080 The sites will decrease by one. 207 00:16:14,080 --> 00:16:16,660 And the Kiguchi is not pleasant anymore. 208 00:16:16,810 --> 00:16:23,360 OK, so Kijiji is not Besant and the size of the map will decrease by one because it is an element. 209 00:16:23,800 --> 00:16:24,820 So now let's see. 210 00:16:29,790 --> 00:16:31,200 So JJ was present. 211 00:16:32,350 --> 00:16:38,890 Then I deleted the GSA, I read the Kijiji, so size becomes torso's decreased by one and Jayjay is 212 00:16:38,890 --> 00:16:40,020 not present anymore. 213 00:16:42,910 --> 00:16:49,930 So basically, we know how to insert elements, how to insert given loopier, and it is just like any 214 00:16:50,710 --> 00:16:56,380 so we know basically how to access the elements using square records, just like at all using add function. 215 00:16:57,670 --> 00:17:02,490 So we have a function, my stepdad says, with the help of which we can find out the size of the map. 216 00:17:04,030 --> 00:17:09,339 So now we have a function count, so with the help of function called, we can check whether a given 217 00:17:09,339 --> 00:17:10,369 keys present or not. 218 00:17:10,630 --> 00:17:16,839 So this current function, it counts how many time a given key is present so it can only return to things 219 00:17:16,839 --> 00:17:20,200 zero or one zero means not present one misprision. 220 00:17:21,339 --> 00:17:28,380 And for updating for updating our values again, just like today, we will use the square records for 221 00:17:28,390 --> 00:17:32,680 erasing an entry we can use, it is function and it will take as input. 222 00:17:34,070 --> 00:17:40,280 Then again, faith function and then again, can't function, so for our data map, for a simple map, 223 00:17:40,280 --> 00:17:41,480 all the functions are the same. 224 00:17:41,720 --> 00:17:43,670 But there are time, complexities are different. 225 00:17:43,700 --> 00:17:49,490 They will run in, log in time and hear all the functions are running in big off one time question time. 226 00:17:49,850 --> 00:17:55,550 So in next video and next few lessons, what we will do, we will solve some problems with the help 227 00:17:55,550 --> 00:18:00,090 of an order to map and build a map so that you can have a better understanding. 228 00:18:00,650 --> 00:18:01,130 Thank you.