1 00:00:00,000 --> 00:00:08,000 2 00:00:08,000 --> 00:00:11,000 3 00:00:11,000 --> 00:00:14,000 This presentation is delivered by the Stanford Center for Professional 4 00:00:14,000 --> 00:00:18,000 Development. 5 00:00:23,000 --> 00:00:24,000 All right. So 6 00:00:24,000 --> 00:00:28,000 where did we leave off last time? I'm gonna reiterate these things that are quirky 7 00:00:28,000 --> 00:00:32,000 about the last changes I was making at the end, was taking an existing container 8 00:00:32,000 --> 00:00:36,000 class that held only strings and turning it into this 9 00:00:36,000 --> 00:00:39,000 template form of it that would now hold 10 00:00:39,000 --> 00:00:41,000 any kind of thing I wanted to stick into it. 11 00:00:41,000 --> 00:00:44,000 And along the way, I had to make a couple changes. And each of them actually kind of has a 12 00:00:44,000 --> 00:00:48,000 little - some pitfalls in getting this a little bit wrong, and so I just want 13 00:00:48,000 --> 00:00:49,000 reiterate them. 14 00:00:49,000 --> 00:00:53,000 There's a lot of examples of these in the textbook. So you will see 15 00:00:53,000 --> 00:00:55,000 all of the templates that are implemented in the 16 00:00:55,000 --> 00:00:56,000 Chapters 17 00:00:56,000 --> 00:00:58,000 9, 10, 11, and so on, 18 00:00:58,000 --> 00:01:00,000 do have examples of this. And 19 00:01:00,000 --> 00:01:03,000 for this first assignment, we won't be building it as a template, so this is actually kind of 20 00:01:03,000 --> 00:01:06,000 more like a future thing to kind of get prepared for when you're writing a 21 00:01:06,000 --> 00:01:07,000 template later. 22 00:01:07,000 --> 00:01:10,000 But just a reminder about the things that have to happen is this 23 00:01:10,000 --> 00:01:14,000 template type name elem type, the template header we'll call that, 24 00:01:14,000 --> 00:01:16,000 gets placed sort of 25 00:01:16,000 --> 00:01:18,000 all over the place when you make that change. 26 00:01:18,000 --> 00:01:21,000 The first place it appears is in the .h on the class interface. You'll say 27 00:01:21,000 --> 00:01:23,000 template type name elem type class 28 00:01:23,000 --> 00:01:26,000 vector, class stack, class whatever it is you're building. 29 00:01:26,000 --> 00:01:29,000 That now means that the class is a template type whose name will 30 00:01:29,000 --> 00:01:34,000 only really exist in the form vector angle bracket string close angle 31 00:01:34,000 --> 00:01:36,000 bracket, from that point on. 32 00:01:36,000 --> 00:01:40,000 In the .cpp, it gets repeated on every single member function definition. 33 00:01:40,000 --> 00:01:44,000 There's not one overarching kind of scope around all of those. Each of those has 34 00:01:44,000 --> 00:01:47,000 its own little independent setup for the scope, and then it has this 35 00:01:47,000 --> 00:01:50,000 additional sort of goo that needs to go on it about, oh, it's the template form of the 36 00:01:50,000 --> 00:01:54,000 member function size that is based on the vector class template. 37 00:01:54,000 --> 00:01:56,000 So you'll have to kind of get this all over the place. 38 00:01:56,000 --> 00:01:59,000 And then the scope of the class, its new name is now 39 00:01:59,000 --> 00:02:03,000 whatever your original class name was but with the angle bracket elem type 40 00:02:03,000 --> 00:02:08,000 colon colon; there is no longer a vector unadorned once you've made that change. 41 00:02:08,000 --> 00:02:11,000 And so, when the client uses it, you'll always see that. And even on the 42 00:02:11,000 --> 00:02:15,000 scope resolution that's being used, even in the member functions themselves have 43 00:02:15,000 --> 00:02:15,000 this same 44 00:02:15,000 --> 00:02:17,000 adornment. 45 00:02:17,000 --> 00:02:19,000 And then elem type 46 00:02:19,000 --> 00:02:21,000 gets used 47 00:02:21,000 --> 00:02:25,000 everywhere you have otherwise said it's storing strings. This is a string 48 00:02:25,000 --> 00:02:28,000 argument, this is a string return type, this is a local variable that's string, this is a 49 00:02:28,000 --> 00:02:31,000 data member that is a, 50 00:02:31,000 --> 00:02:31,000 you 51 00:02:31,000 --> 00:02:35,000 know, array of strings, whatever. All those places where you were saying - 52 00:02:35,000 --> 00:02:38,000 you were earlier committing to a precise type, you're gonna now use elem type 53 00:02:38,000 --> 00:02:39,000 everywhere. 54 00:02:39,000 --> 00:02:42,000 It's pretty easy to do in like nine out of ten places you need to do it and 55 00:02:42,000 --> 00:02:46,000 leave one of them out. And the funny effect of that will be that sometimes 56 00:02:46,000 --> 00:02:48,000 it'll - you'll almost - it'll go unnoticed for a while because 57 00:02:48,000 --> 00:02:51,000 you - let's say you wrote it as a vector of strings originally. 58 00:02:51,000 --> 00:02:54,000 You change it to be a vector template, you left one of the places where there 59 00:02:54,000 --> 00:02:57,000 should've elem type still says string. But then you keep testing on vectors 60 00:02:57,000 --> 00:02:59,000 of string because you happen to have a lot of vector string code lying around that you were 61 00:02:59,000 --> 00:03:00,000 earlier using. 62 00:03:00,000 --> 00:03:03,000 And what happens is you are instantiating the vector with string 63 00:03:03,000 --> 00:03:06,000 and it's kind of - the mistake is actually being hidden 64 00:03:06,000 --> 00:03:10,000 because the one place where it's wrong, it happens to be exactly 65 00:03:10,000 --> 00:03:11,000 string, which is what you're testing against. And 66 00:03:11,000 --> 00:03:14,000 it was only when you went out of way to then put vectors of int that you would 67 00:03:14,000 --> 00:03:17,000 suddenly get this type mismatch in the middle of the code, where it says, oh, here's this place 68 00:03:17,000 --> 00:03:21,000 where you were declaring a variable of string and you're trying to put an integer 69 00:03:21,000 --> 00:03:24,000 into it or something, or you're trying to have an array that's declared as integers and it 70 00:03:24,000 --> 00:03:26,000 really needs to hold - 71 00:03:26,000 --> 00:03:29,000 it's declared to hold strings and it really needs to hold ints. 72 00:03:29,000 --> 00:03:33,000 And so you will - one way to shake that out early is actually to be sure that whatever 73 00:03:33,000 --> 00:03:37,000 testing code you're doing on one type, you also do it again on a different type, to make 74 00:03:37,000 --> 00:03:38,000 sure that you haven't 75 00:03:38,000 --> 00:03:40,000 accidentally got some 76 00:03:40,000 --> 00:03:42,000 subtle thing hiding in there. 77 00:03:42,000 --> 00:03:46,000 And then this last thing is about how the templates are compiled, 78 00:03:46,000 --> 00:03:50,000 which is truthfully just a quirky behavior of the way C++ requires 79 00:03:50,000 --> 00:03:54,000 things to be done based on how the compiler's implemented, 80 00:03:54,000 --> 00:03:59,000 that the template is not compiled normally. So all normal files, 81 00:03:59,000 --> 00:04:02,000 you've got random.cpp and name.cpp and boggle.cpp, you always put 82 00:04:02,000 --> 00:04:06,000 those in the project, and that tells the IDE 83 00:04:06,000 --> 00:04:09,000 you want this one compiled. And it says, ''Please compile this and link this in 84 00:04:09,000 --> 00:04:10,000 with all the code.'' 85 00:04:10,000 --> 00:04:11,000 86 00:04:11,000 --> 00:04:14,000 Once you have code that is templatized in here, 87 00:04:14,000 --> 00:04:18,000 you don't want it to be compiled in advance. It can't be compiled in advance, is really the 88 00:04:18,000 --> 00:04:19,000 problem. 89 00:04:19,000 --> 00:04:24,000 That looking at that code only describes the pattern from which to build vectors, 90 00:04:24,000 --> 00:04:28,000 not how to build one vector and compile it for all intents and purposes. 91 00:04:28,000 --> 00:04:31,000 It's on the fly gonna make new vector, vector, vector. 92 00:04:31,000 --> 00:04:34,000 So we pull it out of the project. 93 00:04:34,000 --> 00:04:37,000 We remove it, so we don't want the compiler trying to do something with it in 94 00:04:37,000 --> 00:04:38,000 advance. 95 00:04:38,000 --> 00:04:41,000 For some compilers, actually, you can leave it there and it'll be ignored. The better 96 00:04:41,000 --> 00:04:44,000 rule to get used to though is just take it out because some compilers can't cope 97 00:04:44,000 --> 00:04:47,000 with it. You don't want to actually get into any bad habits. Pull it out; 98 00:04:47,000 --> 00:04:50,000 it no longer is compiled like an ordinary implementation file. 99 00:04:50,000 --> 00:04:52,000 You then change your header file 100 00:04:52,000 --> 00:04:54,000 to bring in that code, 101 00:04:54,000 --> 00:04:57,000 into the visible interface space here, 102 00:04:57,000 --> 00:05:02,000 at the very end by doing this #include of a .cpp file. 103 00:05:02,000 --> 00:05:06,000 In no other situation would you ever want to #include a .cpp file. 104 00:05:06,000 --> 00:05:09,000 So as a habit, I'm almost giving you a little bit of a bad one here. 105 00:05:09,000 --> 00:05:13,000 Do not assume this means that in any other situation you do this. It is only in this one 106 00:05:13,000 --> 00:05:15,000 situation. I have a template class, 107 00:05:15,000 --> 00:05:17,000 this is the header for it, 108 00:05:17,000 --> 00:05:21,000 it needs to see the implementation body as part of the pattern to be able, to generate 109 00:05:21,000 --> 00:05:23,000 on the fly the client's 110 00:05:23,000 --> 00:05:24,000 particular types, 111 00:05:24,000 --> 00:05:26,000 and this is the way we're getting the code in there. 112 00:05:26,000 --> 00:05:30,000 The way I would say most library implementations, sort of standard 113 00:05:30,000 --> 00:05:32,000 implementations in C++ do this, 114 00:05:32,000 --> 00:05:35,000 is they just don't bother with having a separation in the .h and 115 00:05:35,000 --> 00:05:39,000 the .cpp at all. They just put everything into the .h to begin with. And they 116 00:05:39,000 --> 00:05:42,000 don't even pretend that there is 117 00:05:42,000 --> 00:05:45,000 an interface separated from the implementation. 118 00:05:45,000 --> 00:05:48,000 That's sort of sad because and sometimes that interface implementation split is an 119 00:05:48,000 --> 00:05:51,000 important psychologically of how you're thinking about the code and 120 00:05:51,000 --> 00:05:52,000 what you're doing. 121 00:05:52,000 --> 00:05:56,000 And I think jamming them together in the same file clouds that, that 122 00:05:56,000 --> 00:05:59,000 separation that we consider so important. 123 00:05:59,000 --> 00:06:02,000 But that is probably the most practical way to handle this because then it just 124 00:06:02,000 --> 00:06:05,000 doesn't - you don't have problems with thinking you can compile this 125 00:06:05,000 --> 00:06:09,000 and having to muck with this #include of cpp which is weird. So 126 00:06:09,000 --> 00:06:14,000 you'll see it done the other way in other situations, too. 127 00:06:14,000 --> 00:06:16,000 All right, so that was just like I wanted to reiterate those because 128 00:06:16,000 --> 00:06:18,000 those are all little 129 00:06:18,000 --> 00:06:19,000 quirky things that are 130 00:06:19,000 --> 00:06:22,000 worth having somebody tell you, than having to find them out the hard way by 131 00:06:22,000 --> 00:06:23,000 trial and error. Any 132 00:06:23,000 --> 00:06:27,000 questions about kind of template goo? This 133 00:06:27,000 --> 00:06:29,000 is like the biggest class I've had in years. 134 00:06:29,000 --> 00:06:32,000 What do you guys - like is this midterm day? Was that why you guys are here or just because you heard I was 135 00:06:32,000 --> 00:06:36,000 gonna 136 00:06:36,000 --> 00:06:38,000 dress in a skirt and you wanted to see it? There's 137 00:06:38,000 --> 00:06:40,000 like three times as many people as we always have. I'm gonna code. 138 00:06:40,000 --> 00:06:41,000 I'm 139 00:06:41,000 --> 00:06:48,000 gonna code, I'm gonna go to my new computer. You see my new fancy computer? It's 140 00:06:48,000 --> 00:06:51,000 like - I like it when we just code. I feel - like when I do it on the slides, I always feel like it's so dry, 141 00:06:51,000 --> 00:06:53,000 it's so boring, and it looks like it just 142 00:06:53,000 --> 00:06:57,000 you know came out of nowhere. It's good to kind of see it in real time and watch the mistakes be made live. 143 00:06:57,000 --> 00:07:00,000 So what we're gonna do over here 144 00:07:00,000 --> 00:07:01,000 is we've got 145 00:07:01,000 --> 00:07:03,000 the myvector that we were working on last time. 146 00:07:03,000 --> 00:07:07,000 So it's got a skeletal interface. It has 147 00:07:07,000 --> 00:07:08,000 size add get set 148 00:07:08,000 --> 00:07:09,000 at, and 149 00:07:09,000 --> 00:07:13,000 some of the other functions are missing. The ones like clear and insert at and remove at, and 150 00:07:13,000 --> 00:07:14,000 the 151 00:07:14,000 --> 00:07:15,000 overloaded 152 00:07:15,000 --> 00:07:18,000 bracket operator and things like that are not there. 153 00:07:18,000 --> 00:07:21,000 Okay. But as it is, it does work. 154 00:07:21,000 --> 00:07:24,000 In our simple test right here, we put nine, ten, one, 155 00:07:24,000 --> 00:07:28,000 and then we printed them back out. So let's just go ahead and run that to see that if I 156 00:07:28,000 --> 00:07:32,000 put a nine, ten, and a one and I iterate over what I got there 157 00:07:32,000 --> 00:07:35,000 using the get at and size, it seems like it has put ten - these 158 00:07:35,000 --> 00:07:38,000 three things in and can get them back out. Okay. 159 00:07:38,000 --> 00:07:39,000 Now, 160 00:07:39,000 --> 00:07:41,000 I'm gonna do - I'm 161 00:07:41,000 --> 00:07:42,000 gonna show you something that's 162 00:07:42,000 --> 00:07:46,000 gonna make us a little bit sad and then we're gonna have to figure out how to fix it. 163 00:07:46,000 --> 00:07:47,000 That 164 00:07:47,000 --> 00:07:50,000 there is behavior in C++ 165 00:07:50,000 --> 00:07:53,000 for any class that you declare, that unless you state otherwise, 166 00:07:53,000 --> 00:07:59,000 that it's capable of assigning from one to another, 167 00:07:59,000 --> 00:08:00,000 making a copy. 168 00:08:00,000 --> 00:08:03,000 So all I added here at the bottom was 169 00:08:03,000 --> 00:08:06,000 another vector I called W, who - I 170 00:08:06,000 --> 00:08:10,000 should make this size a little bigger. This is screen is, I think, a little 171 00:08:10,000 --> 00:08:16,000 different than my other resolution, so let's crank that number up; make it a little easier to see what 172 00:08:16,000 --> 00:08:22,000 we're doing. I 173 00:08:22,000 --> 00:08:25,000 declared a new myvector also of int type. It's name is W, and I said 174 00:08:25,000 --> 00:08:27,000 W=V. 175 00:08:27,000 --> 00:08:31,000 So this is actually true of all types that you declare in C++ that by default 176 00:08:31,000 --> 00:08:32,000 they have 177 00:08:32,000 --> 00:08:34,000 a default version of what we call the assignment operator, 178 00:08:34,000 --> 00:08:39,000 that does kind of what's - you can imagine just a memberwise copy of 179 00:08:39,000 --> 00:08:43,000 V onto W. So that works for structs, think about it in the simple case of a 180 00:08:43,000 --> 00:08:47,000 struct. If you have a struct with X and Y fields and you set this one to zero zero. 181 00:08:47,000 --> 00:08:48,000 And then you have point one 182 00:08:48,000 --> 00:08:52,000 has - set the X and Y to zero zero, and you say Point 2 = Point 1, it copies over the 183 00:08:52,000 --> 00:08:55,000 X and Y values. So you end up with two points who have the same field values, whatever they 184 00:08:55,000 --> 00:08:58,000 were, the same numbers. 185 00:08:58,000 --> 00:09:01,000 The same thing is true of classes, 186 00:09:01,000 --> 00:09:02,000 that unless you state otherwise, 187 00:09:02,000 --> 00:09:06,000 if you copy one instance, one object on top of another, 188 00:09:06,000 --> 00:09:10,000 it copies the values of the fields. Okay, 189 00:09:10,000 --> 00:09:13,000 let's look at the fields to 190 00:09:13,000 --> 00:09:16,000 see how this is gonna work for us. The 191 00:09:16,000 --> 00:09:18,000 fields in myvector right now 192 00:09:18,000 --> 00:09:21,000 are a pointer to a dynamic array out here, 193 00:09:21,000 --> 00:09:25,000 two integers that are recording how many slots are used in that array and what its capacity 194 00:09:25,000 --> 00:09:26,000 is, and then 195 00:09:26,000 --> 00:09:29,000 there's no other data members, so we have three data members. 196 00:09:29,000 --> 00:09:32,000 So when I have made my V 197 00:09:32,000 --> 00:09:34,000 and my W, 198 00:09:34,000 --> 00:09:36,000 each of them 199 00:09:36,000 --> 00:09:42,000 has D space for one pointer here at the top and then these two integers. 200 00:09:42,000 --> 00:09:43,000 And in the first one, 201 00:09:43,000 --> 00:09:47,000 if you remember a little about how the code works, it allocated it to some default 202 00:09:47,000 --> 00:09:50,000 size. I don't remember what it was, maybe it's, you know, ten or something. 203 00:09:50,000 --> 00:09:52,000 And then it fills it up from left to right. 204 00:09:52,000 --> 00:09:55,000 So the first one I had, I'm gonna put in the numbers, you know, 205 00:09:55,000 --> 00:09:58,000 one, two, three, let's 206 00:09:58,000 --> 00:10:01,000 say. So I add one, I add a two, I had a three, then 207 00:10:01,000 --> 00:10:05,000 the number used will be three and let's say the number allocated is ten. So 208 00:10:05,000 --> 00:10:08,000 this is num allocated, this is num used. 209 00:10:08,000 --> 00:10:13,000 Okay. So subsequent things being added to that array will get added at the end. 210 00:10:13,000 --> 00:10:16,000 We know what our bounds are and all this sort of stuff. Okay. 211 00:10:16,000 --> 00:10:18,000 Now I say 212 00:10:18,000 --> 00:10:19,000 W 213 00:10:19,000 --> 00:10:21,000 in my code, I say, ''Oh yeah, just declare W.'' 214 00:10:21,000 --> 00:10:25,000 Well, W's constructor 215 00:10:25,000 --> 00:10:29,000 builds it a ten member array, sets 216 00:10:29,000 --> 00:10:33,000 the num allocated to ten, sets the num used to zero, 217 00:10:33,000 --> 00:10:35,000 and it's got kind of empty ready to go 218 00:10:35,000 --> 00:10:35,000 vector 219 00:10:35,000 --> 00:10:37,000 to put things into. 220 00:10:37,000 --> 00:10:40,000 When I say W=V, 221 00:10:40,000 --> 00:10:43,000 it's just gonna take these fields kinda one by one 222 00:10:43,000 --> 00:10:44,000 and overwrite the ones 223 00:10:44,000 --> 00:10:46,000 that were in W. 224 00:10:46,000 --> 00:10:49,000 Let's watch how that works out. 225 00:10:49,000 --> 00:10:54,000 So we copy the num allocated over the num allocated, ten got written on ten, okay. 226 00:10:54,000 --> 00:10:57,000 We write the num used on top of the num used, 227 00:10:57,000 --> 00:11:00,000 okay. 228 00:11:00,000 --> 00:11:05,000 And then we copy the pointer on top of the pointer. This is pointer assignment, 229 00:11:05,000 --> 00:11:09,000 this is not doing any what we think of as a deep copy, it's a shallow copy or an 230 00:11:09,000 --> 00:11:10,000 alias. 231 00:11:10,000 --> 00:11:13,000 That means that W no longer points to here, 232 00:11:13,000 --> 00:11:14,000 its arr 233 00:11:14,000 --> 00:11:18,000 points to there. All right. 234 00:11:18,000 --> 00:11:19,000 This can't be good, 235 00:11:19,000 --> 00:11:22,000 right? If you look at this picture, you've already got to be worried about where 236 00:11:22,000 --> 00:11:23,000 this is heading. 237 00:11:23,000 --> 00:11:25,000 You know just immediately 238 00:11:25,000 --> 00:11:28,000 you will notice that this thing: orphaned. 239 00:11:28,000 --> 00:11:29,000 Right? No one's holding onto this, this thing's 240 00:11:29,000 --> 00:11:34,000 hanging out in the heap, this guy's dead in the water. Okay, so we've lost some memory. That, 241 00:11:34,000 --> 00:11:36,000 in itself, doesn't sound terrible, 242 00:11:36,000 --> 00:11:37,000 243 00:11:37,000 --> 00:11:41,000 but now we have V and W both pointing to the same array. 244 00:11:41,000 --> 00:11:42,000 They have the 245 00:11:42,000 --> 00:11:45,000 same values for these two things but they're actually independent. 246 00:11:45,000 --> 00:11:47,000 And now 247 00:11:47,000 --> 00:11:48,000 it is likely 248 00:11:48,000 --> 00:11:51,000 that if we were to continue on and start using V and W, we're gonna see 249 00:11:51,000 --> 00:11:53,000 some really strange effects 250 00:11:53,000 --> 00:11:56,000 of the two of them 251 00:11:56,000 --> 00:11:57,000 interfering with each other. 252 00:11:57,000 --> 00:11:59,000 So for example, if I 253 00:11:59,000 --> 00:12:02,000 do a V.SetAt - well, let's do W for that matter, 254 00:12:02,000 --> 00:12:05,000 so I say 255 00:12:05,000 --> 00:12:07,000 W.SetAt at index zero, 256 00:12:07,000 --> 00:12:10,000 the number 100. 257 00:12:10,000 --> 00:12:14,000 So W says, you know, check and make sure that's in balance. It says, ''Oh yeah, the index zero is 258 00:12:14,000 --> 00:12:16,000 within - it's greater than 259 00:12:16,000 --> 00:12:23,000 or equal to zero, it's less than my size. Okay.'' And it says, ''Go in and write 100 in there.'' 260 00:12:23,000 --> 00:12:27,000 As a result, it turns out V.GetAt also changed. 261 00:12:27,000 --> 00:12:29,000 And that would be pretty surprising 262 00:12:29,000 --> 00:12:31,000 that these happen. So now, 263 00:12:31,000 --> 00:12:34,000 they're just colliding. They have - there's one piece of memory that's being 264 00:12:34,000 --> 00:12:36,000 shared between the two of them, 265 00:12:36,000 --> 00:12:39,000 and when I change one of them, I'm changing both of them. 266 00:12:39,000 --> 00:12:42,000 They are not independent. They now have a relationship based on this assignment 267 00:12:42,000 --> 00:12:44,000 that's gonna kinda track together. 268 00:12:44,000 --> 00:12:47,000 There are actually worse consequences of that than that. So this looks kind of 269 00:12:47,000 --> 00:12:48,000 innocent 270 00:12:48,000 --> 00:12:52,000 so far, not - ''innocent'' isn't the word but at least it's the opportunity for 271 00:12:52,000 --> 00:12:55,000 malicious error still seems like, well okay, you have these values that are changing. 272 00:12:55,000 --> 00:12:58,000 The really terrible situation would happen when 273 00:12:58,000 --> 00:12:59,000 let's say V 274 00:12:59,000 --> 00:13:00,000 keeps growing, 275 00:13:00,000 --> 00:13:02,000 they keep adding more things. 276 00:13:02,000 --> 00:13:08,000 So they add the numbers four, five, six, seven, eight, nine, and then it 277 00:13:08,000 --> 00:13:09,000 fills up. 278 00:13:09,000 --> 00:13:11,000 So it has num used as ten, num allocated as ten, 279 00:13:11,000 --> 00:13:15,000 and it goes through and it says, ''Oh, it's time to grow. I want to add an 11.'' 280 00:13:15,000 --> 00:13:19,000 And the process of growing, if you remember, was to build an array that was 281 00:13:19,000 --> 00:13:22,000 twice as long, 282 00:13:22,000 --> 00:13:24,000 copy over the front values, 283 00:13:24,000 --> 00:13:29,000 and so copy up to here, have this back half-uninitialized 284 00:13:29,000 --> 00:13:32,000 and then deallocate the other one. So 285 00:13:32,000 --> 00:13:33,000 delete this piece of memory, 286 00:13:33,000 --> 00:13:37,000 and then update your pointer to point to this new one, 287 00:13:37,000 --> 00:13:40,000 that now is allocated to a length of 20. 288 00:13:40,000 --> 00:13:42,000 Okay, when you did that, 289 00:13:42,000 --> 00:13:45,000 W just got screwed. 290 00:13:45,000 --> 00:13:50,000 W points to this piece of memory that you just took away. And 291 00:13:50,000 --> 00:13:51,000 then you will 292 00:13:51,000 --> 00:13:56,000 be much more sad than just getting a junk value out or a surprisingly 293 00:13:56,000 --> 00:13:57,000 changed value out. 294 00:13:57,000 --> 00:14:01,000 Now if you ask W to go get the value at position zero, 295 00:14:01,000 --> 00:14:02,000 all bets are off. 296 00:14:02,000 --> 00:14:05,000 Right? It might happen to work, it probably will 297 00:14:05,000 --> 00:14:08,000 work for a little while, but at some point this memory will get reclaimed and 298 00:14:08,000 --> 00:14:11,000 reused and be in process for something else, and you'll just have completely 299 00:14:11,000 --> 00:14:13,000 300 00:14:13,000 --> 00:14:17,000 very random looking undetermined 301 00:14:17,000 --> 00:14:19,000 results from 302 00:14:19,000 --> 00:14:21,000 access to that W. 303 00:14:21,000 --> 00:14:24,000 So this really just can't 304 00:14:24,000 --> 00:14:26,000 exist. We do not want it to be the case that 305 00:14:26,000 --> 00:14:31,000 this default memberwise assignment goes through. It will do us no good. 306 00:14:31,000 --> 00:14:33,000 So in the case for objects 307 00:14:33,000 --> 00:14:38,000 where memberwise copying is not what you want, you have to go out of your 308 00:14:38,000 --> 00:14:40,000 way to do something about it. 309 00:14:40,000 --> 00:14:42,000 The two main strategies for this 310 00:14:42,000 --> 00:14:45,000 is to really implement a version of assignment operator 311 00:14:45,000 --> 00:14:48,000 that will do a keep copy. That's actually what our ADTs do. So the vector 312 00:14:48,000 --> 00:14:52,000 and the map and stack and queue are setup to where if you say V=W, it makes a full 313 00:14:52,000 --> 00:14:54,000 copy. And that full copy means go 314 00:14:54,000 --> 00:14:58,000 take the piece of memory, get another new piece of memory that big, copy over all the 315 00:14:58,000 --> 00:15:01,000 contents. And so then, you end up with two things that have the same number of 316 00:15:01,000 --> 00:15:04,000 elements in the same order, but in new places in memory. They're actually 317 00:15:04,000 --> 00:15:07,000 fully duplicated from here to there. 318 00:15:07,000 --> 00:15:10,000 And at the point, V and W don't have any relationship that 319 00:15:10,000 --> 00:15:13,000 is gonna be surprising or quirky in the future. They just happen to get 320 00:15:13,000 --> 00:15:16,000 cloned and then move from there. 321 00:15:16,000 --> 00:15:18,000 That's the way kind of a professional 322 00:15:18,000 --> 00:15:20,000 sort of style library would do it. 323 00:15:20,000 --> 00:15:23,000 What I'm gonna show you instead, because I don't really want you to learn 324 00:15:23,000 --> 00:15:26,000 all the goopy things about how to make that work, is I'm gonna show you how to just disallow 325 00:15:26,000 --> 00:15:27,000 that copying. 326 00:15:27,000 --> 00:15:29,000 To make it to where that 327 00:15:29,000 --> 00:15:33,000 it's an error for you to attempt to copy V onto W or W 328 00:15:33,000 --> 00:15:39,000 onto V, by basically taking the assignment operator and 329 00:15:39,000 --> 00:15:41,000 making it inaccessible, making it private. 330 00:15:41,000 --> 00:15:45,000 So I'm gonna show you how I'm gonna do that. Well actually, first I'll just show that like 331 00:15:45,000 --> 00:15:48,000 the truth about these kind of errors. And these errors can be really frustrating and hard to track 332 00:15:48,000 --> 00:15:50,000 down, so you just don't want to actually 333 00:15:50,000 --> 00:15:52,000 mess with this. If I have 334 00:15:52,000 --> 00:15:53,000 W=V here, 335 00:15:53,000 --> 00:15:56,000 and then I say 336 00:15:56,000 --> 00:15:58,000 W.SetAt 337 00:15:58,000 --> 00:15:59,000 zero is 100. 338 00:15:59,000 --> 00:16:02,000 So I was supposed to put in the numbers - 339 00:16:02,000 --> 00:16:05,000 let me go - numbers I know where to look for. I'm gonna put in one, two, and three. I change it 340 00:16:05,000 --> 00:16:06,000 in W 341 00:16:06,000 --> 00:16:09,000 and then I write another for loop here that 342 00:16:09,000 --> 00:16:13,000 should print out the values again. 343 00:16:13,000 --> 00:16:16,000 This is where I'm gonna see. 344 00:16:16,000 --> 00:16:18,000 So like 1, 2, 3 now have 100, 2, 3. 345 00:16:18,000 --> 00:16:21,000 And then actually I'm even seeing an error here at the end 346 00:16:21,000 --> 00:16:25,000 where it's saying that there was a double free at the end. The 347 00:16:25,000 --> 00:16:28,000 free is kind of the internal name for the deallocation function. 348 00:16:28,000 --> 00:16:33,000 And in this case, what happened is that the destructor for V and W were both 349 00:16:33,000 --> 00:16:37,000 being called. As I exited scope, they both tried to delete their pointer. 350 00:16:37,000 --> 00:16:40,000 So one of them deleted it and then the second one went to delete it, and the 351 00:16:40,000 --> 00:16:41,000 352 00:16:41,000 --> 00:16:44,000 libraries were complaining and said, ''You've already deleted this piece of memory. You can't 353 00:16:44,000 --> 00:16:47,000 delete it twice. It doesn't make sense. You must have some error.'' 354 00:16:47,000 --> 00:16:48,000 So in fact, we're even getting a little bit of 355 00:16:48,000 --> 00:16:51,000 helpful runtime information from what happened 356 00:16:51,000 --> 00:16:55,000 that might help us point out to what we need to do. 357 00:16:55,000 --> 00:16:58,000 So let me go and make it 358 00:16:58,000 --> 00:17:00,000 stop compiling. 359 00:17:00,000 --> 00:17:07,000 So there is a header file in our set of libraries that's called disallow copy. 360 00:17:07,000 --> 00:17:10,000 And the only thing that is in disallow copy 361 00:17:10,000 --> 00:17:14,000 is this one thing that's called a macro. It's kind of unfortunate that it has to be done 362 00:17:14,000 --> 00:17:18,000 that way. Well, I can't find the header file, so I'll just tell you what it is. 363 00:17:18,000 --> 00:17:22,000 And it looks like this. 364 00:17:22,000 --> 00:17:24,000 And I say 365 00:17:24,000 --> 00:17:27,000 disallow [inaudible] copying, in all capital letters, and then I put in 366 00:17:27,000 --> 00:17:28,000 parentheses 367 00:17:28,000 --> 00:17:32,000 the name of the class that I'm attempting to disallow copying 368 00:17:32,000 --> 00:17:33,000 on. 369 00:17:33,000 --> 00:17:36,000 You can have a semicolon at the end of this or not, it doesn't matter actually. I'll 370 00:17:36,000 --> 00:17:38,000 put one just because maybe it looks like more 371 00:17:38,000 --> 00:17:40,000 normal to see it that way. 372 00:17:40,000 --> 00:17:44,000 And by doing this in conjunction with that header file it's bringing in the macro that says put 373 00:17:44,000 --> 00:17:46,000 into the private - so we always put this in the private section. 374 00:17:46,000 --> 00:17:48,000 So we go to the private section of our class, 375 00:17:48,000 --> 00:17:51,000 we put this disallow copying macro in here. 376 00:17:51,000 --> 00:17:52,000 And what this will 377 00:17:52,000 --> 00:17:53,000 expand to 378 00:17:53,000 --> 00:17:58,000 is the right mojo. There's sort of a little bit a magic incantation that needs to 379 00:17:58,000 --> 00:18:01,000 be generated, and this is gonna do it for you. That 380 00:18:01,000 --> 00:18:06,000 will make it such that the - any attempt to clone a vector using that memberwise 381 00:18:06,000 --> 00:18:08,000 copy, and so that would happen both in 382 00:18:08,000 --> 00:18:11,000 direct assignment from V to W, or in the cases where copies are made, like in 383 00:18:11,000 --> 00:18:14,000 passing by value or returning by value, those actually are copy situations as 384 00:18:14,000 --> 00:18:15,000 well, 385 00:18:15,000 --> 00:18:18,000 that it will make all of those things illegal. 386 00:18:18,000 --> 00:18:22,000 It will take the standard default behaviors for that, and 387 00:18:22,000 --> 00:18:25,000 make them private and inaccessible and throw errors basically, so that 388 00:18:25,000 --> 00:18:27,000 you just can't use them. And 389 00:18:27,000 --> 00:18:31,000 if I go back to - have made this change, I go back to the code that was trying to do 390 00:18:31,000 --> 00:18:33,000 this, 391 00:18:33,000 --> 00:18:39,000 and I'll take out the rest of the code just so we don't have to look at it, 392 00:18:39,000 --> 00:18:42,000 that it's gonna give me this error. And it's gonna say 393 00:18:42,000 --> 00:18:43,000 that in this context, 394 00:18:43,000 --> 00:18:47,000 the errors over here, that the const myvector, and there's just a bunch of goo 395 00:18:47,000 --> 00:18:50,000 there. But it's saying that the operator equals, is the key part of that, is 396 00:18:50,000 --> 00:18:54,000 private in this context. And so, it's telling you that there is no assignment 397 00:18:54,000 --> 00:18:57,000 operator that allows one myvector to be assigned to another myvector. 398 00:18:57,000 --> 00:19:01,000 And so any attempt by the client to make one of those copies, either from 399 00:19:01,000 --> 00:19:04,000 passing, returning, assigning, 400 00:19:04,000 --> 00:19:07,000 will just balk right then and there and not let the kind of 401 00:19:07,000 --> 00:19:11,000 bad thing that then will just have all sorts of other 402 00:19:11,000 --> 00:19:16,000 following errors that we would not want to have to debug by hand. So 403 00:19:16,000 --> 00:19:19,000 this will become your mantra for 404 00:19:19,000 --> 00:19:20,000 405 00:19:20,000 --> 00:19:22,000 any class that has 406 00:19:22,000 --> 00:19:28,000 memberwise variables to where copying them in a naive way would produce 407 00:19:28,000 --> 00:19:29,000 unintended effects. 408 00:19:29,000 --> 00:19:33,000 So if all the variables in here were all integers or strings or, 409 00:19:33,000 --> 00:19:34,000 for that matter, 410 00:19:34,000 --> 00:19:38,000 vectors or other things that you know have true deep copying behavior, 411 00:19:38,000 --> 00:19:40,000 then you don't need to go out of your way to disallow copying. 412 00:19:40,000 --> 00:19:43,000 As long as each of the members that's here, 413 00:19:43,000 --> 00:19:46,000 that if you were to do an assignment from one variable of this type to the other, it 414 00:19:46,000 --> 00:19:47,000 would have the right effect, 415 00:19:47,000 --> 00:19:50,000 then you don't need to disallow. But as soon as you have one or more variables 416 00:19:50,000 --> 00:19:51,000 where 417 00:19:51,000 --> 00:19:56,000 making a simple assignment of it to another variable of that type would create some 418 00:19:56,000 --> 00:19:59,000 sort of long-term problem between those two objects, you want to disallow that 419 00:19:59,000 --> 00:20:01,000 copying and not let that bad thing happen. 420 00:20:01,000 --> 00:20:05,000 So things that have a link list in them, things that have pointers in them, dynamic 421 00:20:05,000 --> 00:20:06,000 arrays in them, 422 00:20:06,000 --> 00:20:08,000 will all need 423 00:20:08,000 --> 00:20:13,000 this protection to avoid getting into that situation. 424 00:20:13,000 --> 00:20:16,000 Question? Could you 425 00:20:16,000 --> 00:20:19,000 somehow overload the assignment [inaudible]? Well, you certainly can so that's kind of the first strategy I said, which is like, well, 426 00:20:19,000 --> 00:20:22,000 you can make them deep copy is the alternative. So one way is to say, ''Well 427 00:20:22,000 --> 00:20:25,000 the shallow copy is wrong. What are you gonna do about it?'' So I'm saying 428 00:20:25,000 --> 00:20:28,000 don't let shallow copy happen. The other alternative is to replace shallow copy 429 00:20:28,000 --> 00:20:31,000 with a real deep copy. That's what ours do. If you're interested to 430 00:20:31,000 --> 00:20:34,000 look at that, you can look at our code and see what we do. 431 00:20:34,000 --> 00:20:35,000 It just goes through - 432 00:20:35,000 --> 00:20:38,000 you can imagine what it would take. It's like, okay, get some information from here, 433 00:20:38,000 --> 00:20:41,000 make a new array, copy the things over, and then at that point you will be able 434 00:20:41,000 --> 00:20:43,000 435 00:20:43,000 --> 00:20:46,000 to continue on with two things that are cloned from each other, but no longer have 436 00:20:46,000 --> 00:20:49,000 any relationship that would cause problems. 437 00:20:49,000 --> 00:20:49,000 438 00:20:49,000 --> 00:20:52,000 It's not that it's that hard but the syntax for it is a little bit goopy, 439 00:20:52,000 --> 00:20:56,000 and ours in C++ we're not gonna see. So 440 00:20:56,000 --> 00:20:59,000 you can look at it; if you want to as Keith at 106L, he will 441 00:20:59,000 --> 00:21:02,000 tell you everything you want to know. Any 442 00:21:02,000 --> 00:21:04,000 questions about - over here? 443 00:21:04,000 --> 00:21:08,000 So the things inside of this copy, can be anything? It can be one of the variables you declared? So 444 00:21:08,000 --> 00:21:11,000 typically it'll be the name of a class. 445 00:21:11,000 --> 00:21:14,000 But could be like it'd just have a variable inside your class, you don't want people really to copy [inaudible]? 446 00:21:14,000 --> 00:21:18,000 Well it doesn't really work that way. The disallow 447 00:21:18,000 --> 00:21:22,000 copying is saying I'm taking this type and making it not able to be 448 00:21:22,000 --> 00:21:26,000 copied, and so it is an operation that applies to a type, 449 00:21:26,000 --> 00:21:27,000 not to a variable. 450 00:21:27,000 --> 00:21:32,000 And so, in this case, the name here is the name of the class who we are 451 00:21:32,000 --> 00:21:35,000 restricting assignment between things of myvector type. 452 00:21:35,000 --> 00:21:37,000 And so, it really is a type name not a variable name. If I said disallow copying of 453 00:21:37,000 --> 00:21:39,000 like arr 454 00:21:39,000 --> 00:21:42,000 or num used, it actually won't make sense. It'll expand to something that the compiler won't even 455 00:21:42,000 --> 00:21:44,000 accept. It says, ''I don't know what you're talking about.'' 456 00:21:44,000 --> 00:21:49,000 It expects a type name in that capacity, so what thing cannot be 457 00:21:49,000 --> 00:21:52,000 copied. It is things that are of myvector type. 458 00:21:52,000 --> 00:21:55,000 So there's not a way to say you can't copy this field 459 00:21:55,000 --> 00:21:58,000 by itself or something like that. It's really it's all or nothing. You can copy one of 460 00:21:58,000 --> 00:22:00,000 these objects or you can not copy 461 00:22:00,000 --> 00:22:02,000 it. And once you have some 462 00:22:02,000 --> 00:22:05,000 field that won't copy correctly without help, 463 00:22:05,000 --> 00:22:15,000 you're gonna wanna probably disallow the copying to avoid getting into trouble. All 464 00:22:15,000 --> 00:22:16,000 right, 465 00:22:16,000 --> 00:22:18,000 so you got vector; vector's a good thing. I'm gonna 466 00:22:18,000 --> 00:22:21,000 add one more member function of vector before I go away, 467 00:22:21,000 --> 00:22:27,000 which is insert at. I'll call it E. 468 00:22:27,000 --> 00:22:31,000 The insert at one is the - 469 00:22:31,000 --> 00:22:34,000 allows you to place something in an index 470 00:22:34,000 --> 00:22:43,000 in the - which one I just copy? There I go. 471 00:22:43,000 --> 00:22:46,000 Insert at index in an element type. 472 00:22:46,000 --> 00:22:48,000 So if the index is 473 00:22:48,000 --> 00:22:51,000 before the beginning or off the end, I'll raise the same out of bounds error, so 474 00:22:51,000 --> 00:22:54,000 that's I just picked up that piece of code from there. 475 00:22:54,000 --> 00:22:59,000 I also need to have this little line, 476 00:22:59,000 --> 00:23:03,000 which is if the number of elements used is equal to the capacity, then we need to make more 477 00:23:03,000 --> 00:23:06,000 space. So it - just like the case where we're adding to the end, if we're already at 478 00:23:06,000 --> 00:23:09,000 capacity, no matter where we're inserting, we have to make some more space. So we 479 00:23:09,000 --> 00:23:13,000 go ahead and do that, the initial step of checking to see if we're out of capacity and 480 00:23:13,000 --> 00:23:14,000 enlarging in place. 481 00:23:14,000 --> 00:23:15,000 Once we've got - 482 00:23:15,000 --> 00:23:17,000 we're sure we have at least enough room, 483 00:23:17,000 --> 00:23:19,000 we're gonna move everybody over. So I'm 484 00:23:19,000 --> 00:23:22,000 gonna run a for loop that goes from 485 00:23:22,000 --> 00:23:24,000 size minus one 486 00:23:24,000 --> 00:23:33,000 to - whoops, I 487 00:23:33,000 --> 00:23:35,000 need an I on that. Is greater than the index - actually, I want to do greater than or equal to index. 488 00:23:35,000 --> 00:23:37,000 And I'm gonna move everything from index 489 00:23:37,000 --> 00:23:39,000 over 490 00:23:39,000 --> 00:23:41,000 in my 491 00:23:41,000 --> 00:23:43,000 array, 492 00:23:43,000 --> 00:23:44,000 and then array of index equals E. Let 493 00:23:44,000 --> 00:23:48,000 me think about this and make sure I got the right bounds on this, right? This is 494 00:23:48,000 --> 00:23:52,000 taking the last element in the array, it's at position size minus one; and then it's moving 495 00:23:52,000 --> 00:23:56,000 it over by one, so it's reading from the left side and moving it over by one. 496 00:23:56,000 --> 00:24:00,000 And it should do that all the way down until the last iteration should be that I is 497 00:24:00,000 --> 00:24:03,000 exactly equal to index. And so, it should move the thing out of the index slot to the 498 00:24:03,000 --> 00:24:07,000 index plus one slot, so along the way moving everybody else there. Why did 499 00:24:07,000 --> 00:24:13,000 I run that loop backwards? [Inaudible]. Yeah, it 500 00:24:13,000 --> 00:24:14,000 overran the other way. 501 00:24:14,000 --> 00:24:16,000 Right? If I try to do it the other way, I try to copy, you know 502 00:24:16,000 --> 00:24:20,000 I have the numbers four, five, and six in here and I'm planning on inserting at 503 00:24:20,000 --> 00:24:23,000 zero, I can't start from the beginning and four on top of the five 504 00:24:23,000 --> 00:24:27,000 and then on top of that, without making kind of a mess of things. So it's actually - 505 00:24:27,000 --> 00:24:30,000 I can make that work but it's definitely sort of messier. It's sort of easier to think about it and say, ''Oh, 506 00:24:30,000 --> 00:24:32,000 well just move the six over, 507 00:24:32,000 --> 00:24:35,000 then move the five over, then move the four over, and then write your new element in the 508 00:24:35,000 --> 00:24:37,000 front.'' And before I'm 509 00:24:37,000 --> 00:24:38,000 done, I do that. 510 00:24:38,000 --> 00:24:43,000 And so, I have insert at; and I could probably test it to make sure that it does what 511 00:24:43,000 --> 00:24:48,000 it's supposed to do: 512 00:24:48,000 --> 00:24:50,000 V.InsertAt 513 00:24:50,000 --> 00:24:53,000 position zero, put a four in the front, 514 00:24:53,000 --> 00:24:55,000 and then move 515 00:24:55,000 --> 00:24:57,000 this loop down 516 00:24:57,000 --> 00:24:58,000 here. So I 517 00:24:58,000 --> 00:25:00,000 have one, two, three, and then I put a four in the front. Oh, 518 00:25:00,000 --> 00:25:03,000 look at that, 519 00:25:03,000 --> 00:25:05,000 something didn't work. Want to take a look at that? Four, one, two, what happened to 520 00:25:05,000 --> 00:25:07,000 my three? Where did my 521 00:25:07,000 --> 00:25:10,000 three go? Why did I 522 00:25:10,000 --> 00:25:12,000 lose my 523 00:25:12,000 --> 00:25:19,000 three? How 524 00:25:19,000 --> 00:25:22,000 does it know how many elements are in the vector? It's keeping track 525 00:25:22,000 --> 00:25:26,000 of that with num used. If you look down here, for example, at add, when it sticks it 526 00:25:26,000 --> 00:25:30,000 in the last slot, it updates the num used and increments it by one. 527 00:25:30,000 --> 00:25:32,000 I wasn't doing that over here at insert, 528 00:25:32,000 --> 00:25:35,000 right? And a result, like it didn't - you know it's admirable job. It 529 00:25:35,000 --> 00:25:38,000 moved all the numbers over, but then it never incremented its internal counter, so it thinks actually 530 00:25:38,000 --> 00:25:41,000 there's just exactly still three elements in 531 00:25:41,000 --> 00:25:47,000 there. So I'd better put in my num used ++ in there 532 00:25:47,000 --> 00:25:50,000 too. Ah, four, one, two, three. So my number was there, I just wasn't looking at it. It was just a 533 00:25:50,000 --> 00:25:53,000 little further 534 00:25:53,000 --> 00:25:59,000 in there. Okay. All right, so with that piece of code in, I think we're in a position to kinda judge the entire 535 00:25:59,000 --> 00:26:01,000 strategy of using a dynamic array 536 00:26:01,000 --> 00:26:03,000 to back the vector. 537 00:26:03,000 --> 00:26:07,000 The remove at operation is similar, in terms of needing to do that shuffle; it just 538 00:26:07,000 --> 00:26:09,000 does it in the other direction. 539 00:26:09,000 --> 00:26:13,000 And then we have seen the operations, like set at and add and get at, 540 00:26:13,000 --> 00:26:17,000 and how they're able to directly index into the vector and kind of 541 00:26:17,000 --> 00:26:20,000 overwrite some contents, return some contents. And so 542 00:26:20,000 --> 00:26:23,000 you kinda get a feel for what it is that an 543 00:26:23,000 --> 00:26:27,000 array is good at, what things it does well, and what things it does 544 00:26:27,000 --> 00:26:29,000 poorly. So a 545 00:26:29,000 --> 00:26:30,000 vector 546 00:26:30,000 --> 00:26:32,000 is an abstraction. 547 00:26:32,000 --> 00:26:35,000 You offer up to somebody a vector it's a list of things. 548 00:26:35,000 --> 00:26:38,000 That the tradeoffs that this implementation of vector is making, 549 00:26:38,000 --> 00:26:42,000 is it's assuming that what you most care about is that 550 00:26:42,000 --> 00:26:44,000 direct access to anything in the vector 551 00:26:44,000 --> 00:26:46,000 because that's what arrays are good at. 552 00:26:46,000 --> 00:26:47,000 It is a 553 00:26:47,000 --> 00:26:48,000 trivial operation to say 554 00:26:48,000 --> 00:26:50,000 start at the beginning and 555 00:26:50,000 --> 00:26:53,000 access the Nth member, because it just does a little bit of math. It takes the starting 556 00:26:53,000 --> 00:26:55,000 address in memory 557 00:26:55,000 --> 00:26:58,000 and it says, ''Oh, where's the tenth member? It's ten 558 00:26:58,000 --> 00:27:02,000 positions over in memory.'' And so, it can do that calculation in no time, and then just 559 00:27:02,000 --> 00:27:04,000 directly access that piece of memory. So 560 00:27:04,000 --> 00:27:06,000 the - 561 00:27:06,000 --> 00:27:10,000 if what you are really concerned about is this ability to retrieve things or 562 00:27:10,000 --> 00:27:12,000 update things in that vector, 563 00:27:12,000 --> 00:27:15,000 no matter where you're talking about, the front, the back, the middle, 564 00:27:15,000 --> 00:27:20,000 in constant or one time, this design is very good for that. What 565 00:27:20,000 --> 00:27:26,000 are the operations it's gonna actually bog down on? 566 00:27:26,000 --> 00:27:28,000 What is it bad at? 567 00:27:28,000 --> 00:27:32,000 When do you see sort of the consequences, let's say, of it being in contiguous memory, 568 00:27:32,000 --> 00:27:38,000 being a disadvantage rather than advantage? Adding something at the [inaudible]. 569 00:27:38,000 --> 00:27:40,000 570 00:27:40,000 --> 00:27:42,000 Adding something where? At the beginning. At the 571 00:27:42,000 --> 00:27:45,000 beginning. Certainly any operation like this one, the insert at or the remove at, 572 00:27:45,000 --> 00:27:49,000 that's operating in the front of the array is doing a big shuffle, things forward, things back, 573 00:27:49,000 --> 00:27:51,000 to make that space, 574 00:27:51,000 --> 00:27:52,000 to 575 00:27:52,000 --> 00:27:54,000 close down that gap. And so, 576 00:27:54,000 --> 00:27:56,000 for an array of 577 00:27:56,000 --> 00:27:59,000 large enough size, you'd start to notice that. You have an array of 578 00:27:59,000 --> 00:28:01,000 1,000, 10,000, 100,000, you start inserting at the beginning, you're gonna 579 00:28:01,000 --> 00:28:05,000 see this cost of the insert shuffling everything down, 580 00:28:05,000 --> 00:28:07,000 taking time, 581 00:28:07,000 --> 00:28:10,000 relative, in this case, linear, in the number of elements that are being 582 00:28:10,000 --> 00:28:14,000 moved. Which on average, you figure you're inserting kind of randomly in positions, 583 00:28:14,000 --> 00:28:18,000 it could be half of the elements or more are gonna need to move. 584 00:28:18,000 --> 00:28:22,000 It also actually pays a little cost in the 585 00:28:22,000 --> 00:28:24,000 resizing operation. 586 00:28:24,000 --> 00:28:27,000 That happens more infrequently. 587 00:28:27,000 --> 00:28:28,000 The idea that 588 00:28:28,000 --> 00:28:32,000 as you get to capacity, you're growing, in this case we're doubling, 589 00:28:32,000 --> 00:28:36,000 so we're only seeing that kind of at infrequent intervals, especially as that size gets 590 00:28:36,000 --> 00:28:39,000 large. Once you get to 1,000, it'll grow once to be 2,000. Well then, it'll grow 591 00:28:39,000 --> 00:28:43,000 once and be 4,000. So you'll have a lot of inserts before you'll see that subsequent 592 00:28:43,000 --> 00:28:46,000 resize operation. But every now and then, there'll be a little bit a 593 00:28:46,000 --> 00:28:51,000 glitch in the resizing where you would say, ''I'm adding, adding -.'' If you're adding at the end, adding at the end is easy, 594 00:28:51,000 --> 00:28:52,000 it 595 00:28:52,000 --> 00:28:55,000 increments the num used and sticks it at the end. But 596 00:28:55,000 --> 00:28:58,000 once every blue moon, it'll be a long time as it copies. And then you'll be go 597 00:28:58,000 --> 00:29:02,000 back to being fast, fast, fast, fast, fast, till you exhaust that capacity. And then again, 598 00:29:02,000 --> 00:29:03,000 every now and then, 599 00:29:03,000 --> 00:29:07,000 a little bit a hiccup when it takes the time to do the resizing. 600 00:29:07,000 --> 00:29:11,000 Overall, the number of inserts, that cost can kind of be averaged out to be 601 00:29:11,000 --> 00:29:13,000 considered small enough that you'd 602 00:29:13,000 --> 00:29:14,000 say, ''Well, 603 00:29:14,000 --> 00:29:19,000 amortized over all 1,000 inserts it took before I had to copy the 1,000 when 604 00:29:19,000 --> 00:29:23,000 I grew to 2,000, each of them paid 1/1000th of that cost, 605 00:29:23,000 --> 00:29:28,000 which ended up making it come out to, on average, still a constant cost,'' 606 00:29:28,000 --> 00:29:29,000 607 00:29:29,000 --> 00:29:32,000 is one way that we often look at those analyses. 608 00:29:32,000 --> 00:29:34,000 So this tells you that like there's certain things that the array is very good 609 00:29:34,000 --> 00:29:35,000 at. 610 00:29:35,000 --> 00:29:38,000 It has very little additional memory overhead. 611 00:29:38,000 --> 00:29:43,000 Other than the additional space we're kind of storing in the capacity 612 00:29:43,000 --> 00:29:48,000 when we enlarge, there really isn't any per element storage that's used in addition 613 00:29:48,000 --> 00:29:52,000 to the number or the string or whatever it is we're storing itself. So it has very low 614 00:29:52,000 --> 00:29:54,000 housekeeping associated with it. And it 615 00:29:54,000 --> 00:29:57,000 does some things very well but other things 616 00:29:57,000 --> 00:30:00,000 a little less efficiently because of having to stick it in memory meant we had 617 00:30:00,000 --> 00:30:03,000 to kind of do this shuffling and rearranging. 618 00:30:03,000 --> 00:30:06,000 So the other main alternative you could use for a vector is a link list. 619 00:30:06,000 --> 00:30:09,000 I'm actually not gonna go through 620 00:30:09,000 --> 00:30:13,000 the implementation of it because I'm actually gonna do stack as a link list instead. 621 00:30:13,000 --> 00:30:16,000 But it is interesting to think about, if you just sort of imagine. If I instead 622 00:30:16,000 --> 00:30:21,000 backed vector with a link list, first of all could I implement all the same operations? Like is it 623 00:30:21,000 --> 00:30:24,000 possible to use a link list, can it do the job 624 00:30:24,000 --> 00:30:27,000 if I'm determined? 625 00:30:27,000 --> 00:30:29,000 Like what will it take, for example, to 626 00:30:29,000 --> 00:30:35,000 get the element at the nth position from a link list design? 627 00:30:35,000 --> 00:30:36,000 How 628 00:30:36,000 --> 00:30:43,000 do you know where the nth element of a linked list is? 629 00:30:43,000 --> 00:30:50,000 It's [inaudible] list, you know. Help me out. [Inaudible]. You have 630 00:30:50,000 --> 00:30:53,000 to actually dereference the pointers N times. That's exactly 631 00:30:53,000 --> 00:30:57,000 what you got to do; you got to walk, right? You got to start the beginning and say, ''Okay you're 632 00:30:57,000 --> 00:30:58,000 zero. 633 00:30:58,000 --> 00:31:02,000 And after you is one, and after that's two.'' And so you're gonna walk, you're gonna 634 00:31:02,000 --> 00:31:04,000 do N arrow 635 00:31:04,000 --> 00:31:06,000 next, to work your way down. 636 00:31:06,000 --> 00:31:08,000 You will start at the beginning and - and 637 00:31:08,000 --> 00:31:10,000 we're gonna 638 00:31:10,000 --> 00:31:11,000 learn some new vocabulary while we're here. 639 00:31:11,000 --> 00:31:14,000 And so that means that accessing, for example, at the end of the list is gonna be an 640 00:31:14,000 --> 00:31:18,000 expensive proposition. In fact, every operation that accesses anything 641 00:31:18,000 --> 00:31:21,000 past the beginning is doing a walk all the way down. And so if you planned on, for 642 00:31:21,000 --> 00:31:22,000 example, just 643 00:31:22,000 --> 00:31:26,000 printing the list or averaging the list or searching the list, each of 644 00:31:26,000 --> 00:31:30,000 those things is going, ''Give me the zero, give me the next, give me the third.'' You know it's gonna 645 00:31:30,000 --> 00:31:33,000 just keep walking from the beginning each time. Like it's gonna turn 646 00:31:33,000 --> 00:31:34,000 what could've been a linear operation into N 647 00:31:34,000 --> 00:31:37,000 squared because of all those start at the beginning and walk your back down. 648 00:31:37,000 --> 00:31:40,000 So for most common uses of a vector, 649 00:31:40,000 --> 00:31:44,000 that would be so devastating that you just wouldn't even really take it seriously. 650 00:31:44,000 --> 00:31:47,000 That every time you went to get something out of it or set something into it, 651 00:31:47,000 --> 00:31:51,000 you had to make this enormous traversal from the front to the back 652 00:31:51,000 --> 00:31:53,000 would just be 653 00:31:53,000 --> 00:31:55,000 debilitating, in terms of performance implications. 654 00:31:55,000 --> 00:31:56,000 The thing that the 655 00:31:56,000 --> 00:32:00,000 link list is supposed to be good at is that manipulation of the memory. 656 00:32:00,000 --> 00:32:03,000 That the operation, like insert at or remove at, that's doing the shuffle, 657 00:32:03,000 --> 00:32:06,000 the link list doesn't have to do. 658 00:32:06,000 --> 00:32:09,000 So for example, the worst place you can insert at in a vector is zero, 659 00:32:09,000 --> 00:32:13,000 if it's implemented using an array because you have to shuffle everybody over. 660 00:32:13,000 --> 00:32:16,000 The best place you can insert at in a link list is actually at zero 661 00:32:16,000 --> 00:32:19,000 because then you just tack a new cell on the front. 662 00:32:19,000 --> 00:32:23,000 And then sort of further down the list, right? It's not the act of splicing the new cell 663 00:32:23,000 --> 00:32:25,000 in that's expensive; it was finding the position 664 00:32:25,000 --> 00:32:27,000 at which you needed to do the splice. 665 00:32:27,000 --> 00:32:30,000 So if you want to insert at halfway down the list, 666 00:32:30,000 --> 00:32:33,000 you have to walk down the list, and then you can do a very quick splice 667 00:32:33,000 --> 00:32:35,000 but you had to get there. 668 00:32:35,000 --> 00:32:40,000 So it makes this - it's kind of an inverted set of tradeoffs, relative to 669 00:32:40,000 --> 00:32:42,000 the array form, 670 00:32:42,000 --> 00:32:43,000 but 671 00:32:43,000 --> 00:32:46,000 adds a bunch memory overhead, adds a bunch of pointers, adds a bunch of 672 00:32:46,000 --> 00:32:49,000 allocation and deallocation. So there's a bunch of code complexity, 673 00:32:49,000 --> 00:32:52,000 and in the end you don't really get anywhere I think you'd want to be. So it's very unusual to 674 00:32:52,000 --> 00:32:55,000 imagine that someone would implement something like the vector 675 00:32:55,000 --> 00:33:00,000 using a link list strategy, although you could. So. 676 00:33:00,000 --> 00:33:07,000 Let's talk about stack, instead. 677 00:33:07,000 --> 00:33:09,000 I have a little stack 678 00:33:09,000 --> 00:33:11,000 template that I 679 00:33:11,000 --> 00:33:16,000 started: mystack. So I push in pop and size on. Okay. 680 00:33:16,000 --> 00:33:17,000 I'm lazy, so 681 00:33:17,000 --> 00:33:21,000 I'm going to do the easiest thing 682 00:33:21,000 --> 00:33:24,000 in terms of implementing stack: 683 00:33:24,000 --> 00:33:25,000 that is to 684 00:33:25,000 --> 00:33:31,000 layer. Okay. 685 00:33:31,000 --> 00:33:34,000 So once you've built a building block 686 00:33:34,000 --> 00:33:35,000 as an implementer, 687 00:33:35,000 --> 00:33:39,000 there's nothing that stops you from then turning around in your next job and being 688 00:33:39,000 --> 00:33:42,000 a client of that building 689 00:33:42,000 --> 00:33:44,000 block, when implementing 690 00:33:44,000 --> 00:33:47,000 the next thing you have to do. It may very well be that the piece that you just built is a great help to 691 00:33:47,000 --> 00:33:50,000 writing the next thing, and you can build what's called a layered abstraction. 692 00:33:50,000 --> 00:33:54,000 I'm ready to build stack and I've already gone to all this trouble to build vector, it's like, 693 00:33:54,000 --> 00:33:57,000 well. It turns out one of the ways I could implement a stack is to use something 694 00:33:57,000 --> 00:34:01,000 like a vector or an array. Now I could build it on a raw array, but I happen to build 695 00:34:01,000 --> 00:34:04,000 something that kind of has the behaviors of a raw array: the tradeoffs of a raw array, 696 00:34:04,000 --> 00:34:08,000 the Big-O of raw array, and it actually just manages 697 00:34:08,000 --> 00:34:12,000 convenience, it has error checking and stuff in it. It's like why not just use that? 698 00:34:12,000 --> 00:34:13,000 699 00:34:13,000 --> 00:34:15,000 I'll pay a little bit of cost in terms of 700 00:34:15,000 --> 00:34:17,000 701 00:34:17,000 --> 00:34:21,000 taking its level of indirection onto things, but it's actually gonna be worth it 702 00:34:21,000 --> 00:34:22,000 for saving me 703 00:34:22,000 --> 00:34:25,000 sort of the grungier aspects of the code. 704 00:34:25,000 --> 00:34:27,000 So if I'm gonna put stack 705 00:34:27,000 --> 00:34:31,000 contents into an array, 706 00:34:31,000 --> 00:34:33,000 and if I were going to push 707 00:34:33,000 --> 00:34:36,000 A then B then C, right? 708 00:34:36,000 --> 00:34:37,000 So then, the stack that I want 709 00:34:37,000 --> 00:34:40,000 to have would 710 00:34:40,000 --> 00:34:43,000 look like this. There's the top of the stack up here, where C is the 711 00:34:43,000 --> 00:34:46,000 last thing on. The bottom of the stack is down here; with the first thing I pushed 712 00:34:46,000 --> 00:34:48,000 on, which is A. I 713 00:34:48,000 --> 00:34:51,000 could put this in an array. 714 00:34:51,000 --> 00:34:56,000 Seems like the two obvious ways to do this would be, well, to put them in this way: 715 00:34:56,000 --> 00:34:56,000 A, B, C, or 716 00:34:56,000 --> 00:35:03,000 to put them in this way. Okay. 717 00:35:03,000 --> 00:35:04,000 So this would be the 718 00:35:04,000 --> 00:35:06,000 top of the stack is over here, the bottom 719 00:35:06,000 --> 00:35:09,000 of the stack is over there, 720 00:35:09,000 --> 00:35:14,000 and then down here it's inverted. This is the top of the stack; this is the bottom of the stack. Okay, 721 00:35:14,000 --> 00:35:15,000 they seem symmetric, you 722 00:35:15,000 --> 00:35:16,000 know 723 00:35:16,000 --> 00:35:18,000 at the very least, 724 00:35:18,000 --> 00:35:20,000 but one of those is a lot better 725 00:35:20,000 --> 00:35:22,000 for performance reasons. 726 00:35:22,000 --> 00:35:23,000 Which one is it? Do 727 00:35:23,000 --> 00:35:27,000 you want to go with Strategy 1 or Strategy 2? One. One? 728 00:35:27,000 --> 00:35:34,000 Why do I want one? What? Why? Because you don't have to move all the - 729 00:35:34,000 --> 00:35:38,000 Exactly. So if I'm ready to put my next element in, I'm ready to put D in, that 730 00:35:38,000 --> 00:35:42,000 in the Strategy 1 here, D gets added to the end of the vector. 731 00:35:42,000 --> 00:35:46,000 Right? Adding to the end of vector: easy, doesn't require any shuffling, updates the number. Sometimes it 732 00:35:46,000 --> 00:35:48,000 has to grow but easiest thing 733 00:35:48,000 --> 00:35:50,000 to do, add to the end. 734 00:35:50,000 --> 00:35:54,000 In this version, adding to the top would be moving everybody over, so 735 00:35:54,000 --> 00:35:59,000 that I have to update this to D, C, B, A, and slide everybody down. So I had to do insert and 736 00:35:59,000 --> 00:36:01,000 a shuffle: bad news, 737 00:36:01,000 --> 00:36:02,000 right? 738 00:36:02,000 --> 00:36:05,000 Similarly, when I'm ready to pop something, I want to get the 739 00:36:05,000 --> 00:36:08,000 topmost element and I want to remove it 740 00:36:08,000 --> 00:36:11,000 that the topmost element here being at the end, remove at 741 00:36:11,000 --> 00:36:13,000 is also fast at the very end. 742 00:36:13,000 --> 00:36:14,000 Right? Taking the 743 00:36:14,000 --> 00:36:17,000 last element off, there's no shuffling required; I just [inaudible] my 744 00:36:17,000 --> 00:36:18,000 num used. 745 00:36:18,000 --> 00:36:21,000 If I need to do it from here, I have to shuffle everybody down. 746 00:36:21,000 --> 00:36:23,000 So it seems that 747 00:36:23,000 --> 00:36:25,000 they were not totally symmetric, right? There was a reason, right? And I had to think it out 748 00:36:25,000 --> 00:36:28,000 and kind of do it and say, ''Oh yeah. Okay, put them 749 00:36:28,000 --> 00:36:29,000 at the end.'' 750 00:36:29,000 --> 00:36:33,000 So if I do that and I go over here, I'm gonna 751 00:36:33,000 --> 00:36:38,000 finish doing the things that make it a proper 752 00:36:38,000 --> 00:36:40,000 template. I just want to look at mystack, 753 00:36:40,000 --> 00:36:42,000 ooh, and I have the things here, is that 754 00:36:42,000 --> 00:36:46,000 I don't have anything to do with my constructor or destructor. I'm just 755 00:36:46,000 --> 00:36:49,000 gonna let the automatic construction and destruction of my members work, which is to 756 00:36:49,000 --> 00:36:50,000 say 757 00:36:50,000 --> 00:36:54,000 give me a vector, delete my vector. All that happens without me doing anything. Then I 758 00:36:54,000 --> 00:36:57,000 want to know my size. 759 00:36:57,000 --> 00:37:02,000 I don't know my size but the vector does for me, 760 00:37:02,000 --> 00:37:05,000 so I tell the vector to do it for me. When I want to push something, I 761 00:37:05,000 --> 00:37:07,000 tell 762 00:37:07,000 --> 00:37:10,000 my vector to add it for me. I'm telling 763 00:37:10,000 --> 00:37:12,000 you, this is like a 764 00:37:12,000 --> 00:37:13,000 piece of cake. 765 00:37:13,000 --> 00:37:16,000 And so then I say elem 766 00:37:16,000 --> 00:37:20,000 type top equals elems.GetAt. I can actually 767 00:37:20,000 --> 00:37:23,000 use the - I'm 768 00:37:23,000 --> 00:37:27,000 back to using the real vector, so I can use anything that has at the last 769 00:37:27,000 --> 00:37:29,000 position. Elems.RemoveAt, 770 00:37:29,000 --> 00:37:38,000 elems.size [inaudible], then I return it. 771 00:37:38,000 --> 00:37:41,000 Almost but not quite what I want to do, but I'll leave that there for 772 00:37:41,000 --> 00:37:42,000 now. And then that's defining 773 00:37:42,000 --> 00:37:44,000 the function I wanted, 774 00:37:44,000 --> 00:37:45,000 right? So they're all just 775 00:37:45,000 --> 00:37:49,000 leveraging what the vector already does for me, in terms of doing the remove. I guess 776 00:37:49,000 --> 00:37:51,000 RemoveAt actually, the name of that member 777 00:37:51,000 --> 00:37:52,000 function. 778 00:37:52,000 --> 00:37:55,000 The add that does the growing and the shifting and all this other stuff happened. Oh good, 779 00:37:55,000 --> 00:37:59,000 I have a stack and I didn't have to do any work. I love that. 780 00:37:59,000 --> 00:38:03,000 So let's see if it works. Mystack.s, push. 781 00:38:03,000 --> 00:38:17,000 Pop 782 00:38:17,000 --> 00:38:20,000 one thing off of it just for - 783 00:38:20,000 --> 00:38:25,000 even though I actually got what I was supposed to get. Oh, I'd 784 00:38:25,000 --> 00:38:34,000 better include the right header file; I'm gonna do that. 785 00:38:34,000 --> 00:38:36,000 Doesn't like size; let's see what I did with size that I got wrong. 786 00:38:36,000 --> 00:38:42,000 Okay, should be size with arguments, 787 00:38:42,000 --> 00:38:46,000 there we go. 788 00:38:46,000 --> 00:38:50,000 What did I put? One, two, three, and then I popped and I got a three. Hey, not 789 00:38:50,000 --> 00:38:55,000 bad, not bad for five minutes of work. There's something about this 790 00:38:55,000 --> 00:38:58,000 pop method though that I do want to get back. So push actually is totally fine, that's just 791 00:38:58,000 --> 00:39:03,000 delegating the authority to kind of stash the thing in the vector. 792 00:39:03,000 --> 00:39:07,000 Pop right now, what's gonna happen if there isn't anything in the stack when you pop? 793 00:39:07,000 --> 00:39:10,000 Something 794 00:39:10,000 --> 00:39:12,000 good? Something bad? 795 00:39:12,000 --> 00:39:17,000 Something helpful? Wanna 796 00:39:17,000 --> 00:39:20,000 find out? Why 797 00:39:20,000 --> 00:39:23,000 don't we find out? Never hurts to just try it. So like right now, it seems like it just you know 798 00:39:23,000 --> 00:39:28,000 digs into the elem. So if the elem size is zero, there are no 799 00:39:28,000 --> 00:39:31,000 elements in the stack, it'll say, ''Oh, give me the elements of negative one,'' and then it'll try 800 00:39:31,000 --> 00:39:34,000 to remove that negative one. I got to figure those things aren't good things. 801 00:39:34,000 --> 00:39:37,000 I'm hoping that we'll 802 00:39:37,000 --> 00:39:41,000 push one thing and then we'll pop two things. See 803 00:39:41,000 --> 00:39:43,000 how it goes. Hey, 804 00:39:43,000 --> 00:39:43,000 look at 805 00:39:43,000 --> 00:39:47,000 that. [Inaudible] access index negative one and the vector size zero, so that was good. 806 00:39:47,000 --> 00:39:51,000 It was good that we got an error from it. We didn't actually like just 807 00:39:51,000 --> 00:39:53,000 bludgeon our way through some piece of memory that we didn't know it or anything crazy 808 00:39:53,000 --> 00:39:55,000 like that. 809 00:39:55,000 --> 00:39:58,000 But the error that we got probably wasn't the most helpful. 810 00:39:58,000 --> 00:40:01,000 That upon seeing that error, it might cause you to go - kind of get a little bit 811 00:40:01,000 --> 00:40:04,000 misled. You might start looking around for where am I using a vector? Where am I making a call 812 00:40:04,000 --> 00:40:08,000 to vectors bracket? Like I look at my client code and all I see is use 813 00:40:08,000 --> 00:40:11,000 of stack. The fact that stack is implemented on vector, is something I'm not supposed to 814 00:40:11,000 --> 00:40:13,000 know or not even supposed to be worrying about. And 815 00:40:13,000 --> 00:40:16,000 so having it poke its head up there, 816 00:40:16,000 --> 00:40:18,000 might be a little less 817 00:40:18,000 --> 00:40:21,000 clear than if, instead, it had its own error message. 818 00:40:21,000 --> 00:40:24,000 And so I can actually just go in here to mystack and say, ''Yeah, you know, 819 00:40:24,000 --> 00:40:27,000 if write my size is 820 00:40:27,000 --> 00:40:28,000 zero, error, 821 00:40:28,000 --> 00:40:33,000 pop empty stack.'' That you know it doesn't really change the behavior in any meaningful way. It's 822 00:40:33,000 --> 00:40:36,000 like it still gets an error, but it gets an error in this case that's more likely to 823 00:40:36,000 --> 00:40:37,000 tell somebody 824 00:40:37,000 --> 00:40:42,000 where the trouble is and where to look for it: so start looking for 825 00:40:42,000 --> 00:40:45,000 pop on a stack, instead of expecting to go look for a vector access. So just 826 00:40:45,000 --> 00:40:50,000 being a little bit more bulletproof, a little bit more friendly to the client by doing that, that's what. 827 00:40:50,000 --> 00:40:54,000 And so all the operations on this stack are O of one right now, 828 00:40:54,000 --> 00:40:56,000 the add, the pop are - push 829 00:40:56,000 --> 00:40:57,000 and pop are both 830 00:40:57,000 --> 00:40:59,000 adding to the end of the array, which is easy to do. 831 00:40:59,000 --> 00:41:02,000 And so the - this is a pretty 832 00:41:02,000 --> 00:41:06,000 efficient implementation and pretty easy to do because we're leveraging vector. 833 00:41:06,000 --> 00:41:09,000 What we're gonna look at next time is what can a link list do for us or not, 834 00:41:09,000 --> 00:41:10,000 does it provide anything 835 00:41:10,000 --> 00:41:17,000 that might be interesting to look at.