1
00:00:00,000 --> 00:00:09,000


2
00:00:09,000 --> 00:00:12,000
This presentation is delivered by the Stanford Center for Professional Development.

3
00:00:12,000 --> 00:00:22,000

4
00:00:22,000 --> 00:00:25,000
Okay, anything administratively you'd like to ask about? How many people 

5
00:00:25,000 --> 00:00:29,000
have completed assignment 1, and done the whole thing? 

6
00:00:29,000 --> 00:00:32,000
All right, you get a gold star. All right, 

7
00:00:32,000 --> 00:00:36,000
you guys want to be him, is what it is, because this guys is getting to go skiing guilt free. You 

8
00:00:36,000 --> 00:00:39,000
guys if you're going skiing won't be guilt free, and 

9
00:00:39,000 --> 00:00:42,000
you'll be working late to finish it off, and he 

10
00:00:42,000 --> 00:00:44,000
is sleeping easy. 

11
00:00:44,000 --> 00:00:47,000
How many people have at least one or two of the problems done? 

12
00:00:47,000 --> 00:00:51,000
Okay, that's a good number. 

13
00:00:51,000 --> 00:00:54,000
We're still making progress. 

14
00:00:54,000 --> 00:00:57,000
So I had just started to talk a little about this idea of a template, 

15
00:00:57,000 --> 00:01:02,000
which is the C++ equivalent of the Java generic, 

16
00:01:02,000 --> 00:01:03,000
and I 

17
00:01:03,000 --> 00:01:07,000
want to refresh on the rules about how do you use a template. The thing about templates 

18
00:01:07,000 --> 00:01:10,000
is they're a very useful and practical 

19
00:01:10,000 --> 00:01:11,000
component to have in the language, 

20
00:01:11,000 --> 00:01:14,000
but they do have a little bit of issues with resolve to when you make mistakes 

21
00:01:14,000 --> 00:01:17,000
with them, kinda having it reported and how you learn about them, and so they can be a 

22
00:01:17,000 --> 00:01:21,000
little bit of a tripping point despite their vast utility. 

23
00:01:21,000 --> 00:01:24,000
Let me just remind you about what it means to use a template; is that you use 

24
00:01:24,000 --> 00:01:27,000
include the interface file as usual. We're trying to use a vector to hold some 

25
00:01:27,000 --> 00:01:30,000
sequence of things, so we include the vector.H. 

26
00:01:30,000 --> 00:01:32,000
The name vector 

27
00:01:32,000 --> 00:01:36,000
by itself without specialization doesn't tell the compiler everything 

28
00:01:36,000 --> 00:01:38,000
it needs to know. When you're trying to 

29
00:01:38,000 --> 00:01:42,000
[inaudible] declare a vector, pass a vector as a parameter, return one, and any 

30
00:01:42,000 --> 00:01:45,000
of those situations where you would have wanted to say it's a vector, you have to 

31
00:01:45,000 --> 00:01:48,000
say what kind of vector, it's a vector holding character, it's a vector holding 

32
00:01:48,000 --> 00:01:49,000
location T's, it's 

33
00:01:49,000 --> 00:01:50,000
a vector holding 

34
00:01:50,000 --> 00:01:51,000
doubles. 

35
00:01:51,000 --> 00:01:54,000
And that just applies everywhere you use the name vector, the name vector by itself 

36
00:01:54,000 --> 00:01:57,000
doesn't mean anything. It always has to have this qualification or specialization on 

37
00:01:57,000 --> 00:01:58,000
it. 

38
00:01:58,000 --> 00:02:02,000
And then once that you've committed that to the compiler, the 

39
00:02:02,000 --> 00:02:05,000
vector from that point really behaves in a type safe manner. A vector 

40
00:02:05,000 --> 00:02:08,000
character is not the same thing as a vector holding doubles. The 

41
00:02:08,000 --> 00:02:11,000
compiler keeps those things separate. It doesn't let you co-mingle them. 

42
00:02:11,000 --> 00:02:14,000
If you expect a vector of care, and you say that as your parameter, 

43
00:02:14,000 --> 00:02:17,000
then you will have to pass one that has the same element type in it, 

44
00:02:17,000 --> 00:02:21,000
that passing a vector double is not this same thing, and so trying to put a double 

45
00:02:21,000 --> 00:02:23,000
into a vector of characters or 

46
00:02:23,000 --> 00:02:26,000
retrieve an integer out of one that's holding 

47
00:02:26,000 --> 00:02:30,000
student structures, is going to give you compiler errors, which is really 

48
00:02:30,000 --> 00:02:34,000
a nice feature for maintaining type safety. 

49
00:02:34,000 --> 00:02:38,000
So the vector class I had just started talking about, and I'm gonna just kinda pick up 

50
00:02:38,000 --> 00:02:42,000
and review the things we had started to talk about on Wednesday and go through 

51
00:02:42,000 --> 00:02:42,000
it, 

52
00:02:42,000 --> 00:02:44,000
which is what is the vector good for? 

53
00:02:44,000 --> 00:02:47,000
The vector is good for any 

54
00:02:47,000 --> 00:02:50,000
collection of things. You need to store a list is kind of the 

55
00:02:50,000 --> 00:02:53,000
abstraction that it's trying to model. I have a list of students in this class, I have 

56
00:02:53,000 --> 00:02:56,000
a list of problems that are being assigned, I have 

57
00:02:56,000 --> 00:02:59,000
a list of classes I'm taking this quarter, you know, whatever those things 

58
00:02:59,000 --> 00:03:02,000
are, a list of scores on an exam, 

59
00:03:02,000 --> 00:03:04,000
and the vector 

60
00:03:04,000 --> 00:03:06,000
manages the needs of all of those kinds of lists. You say what kind of thing 

61
00:03:06,000 --> 00:03:09,000
you're storing in it. Every element has to be the same type, so that's what I mean by 

62
00:03:09,000 --> 00:03:13,000
homogeneous, that all the elements are double or they're all students. You 

63
00:03:13,000 --> 00:03:15,000
can't have doubles and students co-mingle. 

64
00:03:15,000 --> 00:03:20,000
It's linear in the effect that it kinda lays them out in a line. It indexes them from zero 

65
00:03:20,000 --> 00:03:21,000
to the size minus 1. 

66
00:03:21,000 --> 00:03:25,000
Each one has a place in the line and there are no gaps in it, so it actually is 

67
00:03:25,000 --> 00:03:26,000
sequenced out. 

68
00:03:26,000 --> 00:03:30,000
And it doesn't - a lot of things that make for a really convenient handling of the 

69
00:03:30,000 --> 00:03:33,000
list as an abstraction, it knows its size at all time. You can ask it what the 

70
00:03:33,000 --> 00:03:36,000
size is, it'll tell me how your elements have been stored in it. Now 

71
00:03:36,000 --> 00:03:39,000
if you ask for an element by index it bounds checks to make sure that you 

72
00:03:39,000 --> 00:03:43,000
gave it a valid index for the range of size that it's currently holding. 

73
00:03:43,000 --> 00:03:45,000
It handles all the storage for you. If 

74
00:03:45,000 --> 00:03:48,000
you put ten elements and to put an eleventh, if it doesn't have space it goes 

75
00:03:48,000 --> 00:03:52,000
and makes space for you. This all happens without you doing anything explicit, so 

76
00:03:52,000 --> 00:03:55,000
as you add things, as you remove things, it handles sizing and 

77
00:03:55,000 --> 00:03:59,000
changing whatever internal storage needs as needed to accommodate what you asked 

78
00:03:59,000 --> 00:04:00,000
you. 

79
00:04:00,000 --> 00:04:03,000
It has convenient operations for inserting and removing; where you want to put 

80
00:04:03,000 --> 00:04:07,000
something in a slot, it will move everything over to make space for it or to shuffle it down to 

81
00:04:07,000 --> 00:04:09,000
close over that space. 

82
00:04:09,000 --> 00:04:11,000
It also does what we call a deep copy; a 

83
00:04:11,000 --> 00:04:13,000
deep copy is 

84
00:04:13,000 --> 00:04:17,000
sort of a CS term for if I have a vector holding ten numbers, 

85
00:04:17,000 --> 00:04:19,000
and I assign that to another vector, 

86
00:04:19,000 --> 00:04:23,000
it really does make a new vector that has the same ten numbers. That deep copy means 

87
00:04:23,000 --> 00:04:27,000
it's more than some sort of shallow, like they're sharing something. They really are 

88
00:04:27,000 --> 00:04:30,000
creating a clone of it, so taking that same - however big that vector is, whether it 

89
00:04:30,000 --> 00:04:33,000
has a hundred or a thousand or two entries, 

90
00:04:33,000 --> 00:04:36,000
it makes a whole copy, a parallel copy that has 

91
00:04:36,000 --> 00:04:38,000
the same size and the same entries 

92
00:04:38,000 --> 00:04:43,000
that was based on taking the original input and reproducing it in a new vector. 

93
00:04:43,000 --> 00:04:46,000
And that happens when you do assignment from one vector to another, it happens 

94
00:04:46,000 --> 00:04:50,000
when you do a cast by value of a vector into a function that takes a vector by 

95
00:04:50,000 --> 00:04:50,000
value, 

96
00:04:50,000 --> 00:04:54,000
or when you return a vector from a function, so in all those cases it's doing kinda 

97
00:04:54,000 --> 00:04:56,000
a full deep copy 

98
00:04:56,000 --> 00:04:57,000
that 

99
00:04:57,000 --> 00:05:00,000
is unlike those of you had a little experience working with a built in 

100
00:05:00,000 --> 00:05:03,000
array, know that it doesn't have those behaviors, and that comes as a little bit of 

101
00:05:03,000 --> 00:05:06,000
a surprise. The vector behaves just like the primitives in the sense that 

102
00:05:06,000 --> 00:05:07,000
there's no special 

103
00:05:07,000 --> 00:05:10,000
knowledge you need to know about how it's - 

104
00:05:10,000 --> 00:05:14,000
the assignment affects other copies of the same vector. 

105
00:05:14,000 --> 00:05:17,000
So your typical usage is you create an empty vector, you add a new insert; 

106
00:05:17,000 --> 00:05:21,000
remove to kind of jostle of the contents. You can access the elements 

107
00:05:21,000 --> 00:05:25,000
once they're in there using member function setat and getat that allow you to 

108
00:05:25,000 --> 00:05:27,000
change the value of the location, or get the value. 

109
00:05:27,000 --> 00:05:31,000
There's also an operator bracket. We'll see how you can actually just use the 

110
00:05:31,000 --> 00:05:34,000
syntax of the vector name and then the bracket with the index to access a 

111
00:05:34,000 --> 00:05:35,000
particular element, 

112
00:05:35,000 --> 00:05:37,000
useful for all 

113
00:05:37,000 --> 00:05:39,000
sorts of things. 

114
00:05:39,000 --> 00:05:41,000
Question here? 

115
00:05:41,000 --> 00:05:43,000
Student:Yeah, can you make a multi-dimensional vector? Instructor 

116
00:05:43,000 --> 00:05:47,000
(Julie Zelenski):You can make a vector or vectors. The next class I'll talk about is a grid, which is kind of just a tooty thing that is 

117
00:05:47,000 --> 00:05:47,000
already built, 

118
00:05:47,000 --> 00:05:50,000
and you can also build vectors of vectors, and vectors 

119
00:05:50,000 --> 00:05:53,000
of vectors of vectors to build to the higher and higher dimensions. And there's a 

120
00:05:53,000 --> 00:05:56,000
little bit more syntax involved in doing that, but it [inaudible] the same basic functionality 

121
00:05:56,000 --> 00:06:00,000
kind of applies in higher dimension. 

122
00:06:00,000 --> 00:06:03,000
So this is the basic interface of the vector, 

123
00:06:03,000 --> 00:06:05,000
supplied as a template, so 

124
00:06:05,000 --> 00:06:09,000
all the way through it, it refers to elem type as what you get 

125
00:06:09,000 --> 00:06:13,000
at, what you set at, what you add and you insert all of the kind of values that are 

126
00:06:13,000 --> 00:06:14,000
going in and out of that 

127
00:06:14,000 --> 00:06:15,000
vector are 

128
00:06:15,000 --> 00:06:19,000
left using this place holder rather than saying it's explicitly a double or a 

129
00:06:19,000 --> 00:06:22,000
string or something, making no commitment about that, just leaving it open. And then 

130
00:06:22,000 --> 00:06:25,000
that template typed in elem type is the way that the whole class is introduced to 

131
00:06:25,000 --> 00:06:25,000
say 

132
00:06:25,000 --> 00:06:30,000
this is a pattern from which you can create a lot of different vector classes. 

133
00:06:30,000 --> 00:06:33,000
Let me show you a little something on the next slide that helps to 

134
00:06:33,000 --> 00:06:34,000
point this out. 

135
00:06:34,000 --> 00:06:38,000
So here I have, in blue, put all the places where the elem type shows up. I 

136
00:06:38,000 --> 00:06:42,000
put the type name parameter introduced, and it says within the body of the class I'm using 

137
00:06:42,000 --> 00:06:44,000
elem type as a place 

138
00:06:44,000 --> 00:06:47,000
holder, and the four places it's showing up here, the getat the setat the add and 

139
00:06:47,000 --> 00:06:48,000
the insert, 

140
00:06:48,000 --> 00:06:53,000
that when I go to create a vector as a client, I'll say vector of double. 

141
00:06:53,000 --> 00:06:56,000
Every place where there was elem type 

142
00:06:56,000 --> 00:06:57,000


143
00:06:57,000 --> 00:07:01,000
and on the vector name itself has been annotated or specialized to show 

144
00:07:01,000 --> 00:07:04,000
that what's really going in out of this thing is double. 

145
00:07:04,000 --> 00:07:08,000
So this now created a class vector, angle bracket, double. 

146
00:07:08,000 --> 00:07:12,000
The constructor and the destructor match the class name now, and the getat, the setat, 

147
00:07:12,000 --> 00:07:13,000
the add, the insert, 

148
00:07:13,000 --> 00:07:16,000
all have been locked down. We've made that commitment, we said what we're 

149
00:07:16,000 --> 00:07:18,000
storing here really is vectors of 

150
00:07:18,000 --> 00:07:22,000
doubles, and that means that the add number function for vector double takes 

151
00:07:22,000 --> 00:07:23,000
a double parameter. 

152
00:07:23,000 --> 00:07:26,000
The getat returns a double value, 

153
00:07:26,000 --> 00:07:30,000
and that way once the compiler has done this transformation 

154
00:07:30,000 --> 00:07:33,000
that subsequent usage of that vector double variable 

155
00:07:33,000 --> 00:07:37,000
will be consistent with this filling in of the placeholder, 

156
00:07:37,000 --> 00:07:40,000
so it doesn't actually get confused about other types of 

157
00:07:40,000 --> 00:07:40,000
vectors you may have 

158
00:07:40,000 --> 00:07:45,000
been creating or working with. 

159
00:07:45,000 --> 00:07:50,000
Question? [Inaudible] No, these empty functions are really just a convenience off of size. You could 

160
00:07:50,000 --> 00:07:52,000
always check size equals zero, 

161
00:07:52,000 --> 00:07:54,000
and so it actually doesn't really add anything to the interface. 

162
00:07:54,000 --> 00:07:58,000
It just turns out you do that so often in many situations, you want to know if 

163
00:07:58,000 --> 00:07:59,000
this thing is totally empty, 

164
00:07:59,000 --> 00:08:03,000
that as a convenience it offers two different ways to get at that same information. So you're 

165
00:08:03,000 --> 00:08:04,000
totally right, it's redundant. 

166
00:08:04,000 --> 00:08:08,000
Sometimes you'll see that for example the standard template library has a bunch of 

167
00:08:08,000 --> 00:08:09,000
the same things. The string has 

168
00:08:09,000 --> 00:08:13,000
a length number function. It also has a size number function. They do exactly the same thing. It's 

169
00:08:13,000 --> 00:08:16,000
just because sometimes people can remember size, sometimes people remember length. There's 

170
00:08:16,000 --> 00:08:17,000
also an empty - 

171
00:08:17,000 --> 00:08:19,000
it's not called is empty, but it's just empty. The 

172
00:08:19,000 --> 00:08:22,000
[inaudible] is the length or size zero, and so all of those things are kind of written in 

173
00:08:22,000 --> 00:08:23,000
terms of each other, 

174
00:08:23,000 --> 00:08:25,000
but they 

175
00:08:25,000 --> 00:08:28,000
allow different ways to get at the same information. 

176
00:08:28,000 --> 00:08:30,000
Anything 

177
00:08:30,000 --> 00:08:32,000
else? You got a question? Here we go. 

178
00:08:32,000 --> 00:08:34,000
Is there a remove all method? 

179
00:08:34,000 --> 00:08:39,000
There is actually a clear method, and I should have put that up there. Actually, I think 

180
00:08:39,000 --> 00:08:42,000
there's a few. In each of these cases I've excerpted a little bit for the most 

181
00:08:42,000 --> 00:08:45,000
mainstream operations, but there is a clear operation that takes no arguments, 

182
00:08:45,000 --> 00:08:46,000
returns no argument, that just 

183
00:08:46,000 --> 00:08:55,000
takes the vector to an empty state. 

184
00:08:55,000 --> 00:08:56,000
So here's a little bit of 

185
00:08:56,000 --> 00:08:56,000
code 

186
00:08:56,000 --> 00:09:00,000
that shows some of the common use of vector and how you might do stuff with it 

187
00:09:00,000 --> 00:09:03,000
that just gets you familiar with, okay, what does the syntax look like? 

188
00:09:03,000 --> 00:09:07,000
So I'll look at this top function together, this is make random vector. You give it a 

189
00:09:07,000 --> 00:09:10,000
parameter, which is the size, and it will fill a vector of integers with a sequence 

190
00:09:10,000 --> 00:09:15,000
of random numbers up to that size. You say I'd like a length ten vector filled with 

191
00:09:15,000 --> 00:09:16,000
random numbers, 

192
00:09:16,000 --> 00:09:18,000
it'll make a ten number vector 

193
00:09:18,000 --> 00:09:19,000
stuffing in 

194
00:09:19,000 --> 00:09:23,000
random numbers generated using the random library here. 

195
00:09:23,000 --> 00:09:26,000
So you'll see the declaration here, so I included vector [inaudible], the compiler knew what 

196
00:09:26,000 --> 00:09:29,000
I was using. I 

197
00:09:29,000 --> 00:09:30,000
specialized 

198
00:09:30,000 --> 00:09:32,000
when I declared that vector, 

199
00:09:32,000 --> 00:09:36,000
and so the constructor for vector creates a new empty vector of 

200
00:09:36,000 --> 00:09:38,000
that type, in this case vector of integer, 

201
00:09:38,000 --> 00:09:42,000
and then numbers.add sticking in a bunch of numbers, and then I'm returning it. 

202
00:09:42,000 --> 00:09:46,000
So it's totally valid to actually return a vector as the return value coming out of 

203
00:09:46,000 --> 00:09:47,000
a function. 

204
00:09:47,000 --> 00:09:48,000
It'll take that, 

205
00:09:48,000 --> 00:09:52,000
however many numbers I put in there, ten length vector, 

206
00:09:52,000 --> 00:09:53,000
and make a full copy of it. 

207
00:09:53,000 --> 00:09:56,000
And then when I'm down here and I'm saying nums equals make random vector, it actually 

208
00:09:56,000 --> 00:09:57,000
copied 

209
00:09:57,000 --> 00:09:59,000
that ten number vector 

210
00:09:59,000 --> 00:10:03,000
into the variable beings stored in main. So now I have a ten number 

211
00:10:03,000 --> 00:10:04,000
thing with some random contents. 

212
00:10:04,000 --> 00:10:07,000
The next thing I did with it was pass it to another routine that was going to print 

213
00:10:07,000 --> 00:10:08,000
it, 

214
00:10:08,000 --> 00:10:11,000
and there I am getting that vector, and this time I'm 

215
00:10:11,000 --> 00:10:12,000
accessing it in here 

216
00:10:12,000 --> 00:10:14,000
by reference. 

217
00:10:14,000 --> 00:10:18,000
This is just to show you that in typical because of the deep copying semantics it 

218
00:10:18,000 --> 00:10:20,000
does mean if I didn't pass by reference, it means the 

219
00:10:20,000 --> 00:10:25,000
full contents of the vector would get copied when I passed it to some function. 

220
00:10:25,000 --> 00:10:26,000
There's no 

221
00:10:26,000 --> 00:10:30,000
harm in that per se, other than the fact that it can get inefficient, especially as the 

222
00:10:30,000 --> 00:10:33,000
vector gets larger, it has hundreds and thousands of entries, 

223
00:10:33,000 --> 00:10:34,000
that making a full copy of those 

224
00:10:34,000 --> 00:10:38,000
can have some overall efficiency effects on the program. 

225
00:10:38,000 --> 00:10:40,000
Passing by reference means it didn't really copy; 

226
00:10:40,000 --> 00:10:44,000
it just kinda used the copy that was out here by reference, so reaching 

227
00:10:44,000 --> 00:10:47,000
out and accessing it out of [inaudible]. 

228
00:10:47,000 --> 00:10:51,000
So in here using the size to know how many elements are in the vector, 

229
00:10:51,000 --> 00:10:54,000
and then this is what's called an overloaded operator, that the 

230
00:10:54,000 --> 00:10:57,000
square brackets that you have seen in the past, user array access and the 

231
00:10:57,000 --> 00:10:59,000
languages you know, 

232
00:10:59,000 --> 00:11:01,000
can be applied to the vector, 

233
00:11:01,000 --> 00:11:05,000
and it uses the same sort of syntax that we put an integer in that tells you what index and 

234
00:11:05,000 --> 00:11:08,000
indices from zero to size minus one are the valid range for 

235
00:11:08,000 --> 00:11:12,000
the vector, and accessed that integer and printed it out. 

236
00:11:12,000 --> 00:11:15,000
So anything you would have done on any kind of array, 

237
00:11:15,000 --> 00:11:18,000
reading a bunch of contents from a file, 

238
00:11:18,000 --> 00:11:21,000
printing these things out, rearranging them into sorted order, inserting 

239
00:11:21,000 --> 00:11:22,000
something into sorted order, 

240
00:11:22,000 --> 00:11:24,000
all those things are 

241
00:11:24,000 --> 00:11:28,000
operations that work very cleanly when mapped onto what the vector provides. One 

242
00:11:28,000 --> 00:11:31,000
of the really nice things is unlike most array, 

243
00:11:31,000 --> 00:11:33,000
like the built in array of C++, 

244
00:11:33,000 --> 00:11:36,000
you don't have to know in advance how big the vector's gonna be, it just grows 

245
00:11:36,000 --> 00:11:37,000
on demand. 

246
00:11:37,000 --> 00:11:42,000
So if you were reading a bunch of numbers from a file, like you are in your assignment 1, 

247
00:11:42,000 --> 00:11:45,000
you don't have to have figured out ahead of time how many numbers will be there 

248
00:11:45,000 --> 00:11:48,000
so that I can allocate the storage and set it aside. You just keep calling 

249
00:11:48,000 --> 00:11:50,000
v.dot add on your vector, 

250
00:11:50,000 --> 00:11:51,000
and as needed it's just making space. 

251
00:11:51,000 --> 00:11:55,000
So if there's ten numbers in the file, there's a hundred, there's a million, 

252
00:11:55,000 --> 00:11:57,000
it will just make the space on demand 

253
00:11:57,000 --> 00:12:05,000
and you don't have to do anything special to get that access. Question? [Inaudible] The square brackets. No, the [inaudible]. Oh, the 

254
00:12:05,000 --> 00:12:07,000
angle 

255
00:12:07,000 --> 00:12:11,000
brackets. Yeah, they turn the side 

256
00:12:11,000 --> 00:12:14,000
of it and then - no? No, no. The angle brackets are used in this case just for the vector 

257
00:12:14,000 --> 00:12:15,000
specialization. 

258
00:12:15,000 --> 00:12:18,000
The square brackets here are being used for - 

259
00:12:18,000 --> 00:12:23,000
I'm accessing a particular member out of the array by index. [Inaudible] 

260
00:12:23,000 --> 00:12:26,000
So yeah, what happens in - so if you look at make random vector, 

261
00:12:26,000 --> 00:12:30,000
it created an empty vector, so the typical usage [inaudible] is you create it empty 

262
00:12:30,000 --> 00:12:32,000
and then you add things to grow it. 

263
00:12:32,000 --> 00:12:36,000
So you actually never in here actually have to say how big it's going to be. It 

264
00:12:36,000 --> 00:12:38,000
just - on demand as I call 

265
00:12:38,000 --> 00:12:41,000
numbers.add, it got one bigger each time through that loop, and if I did that 

266
00:12:41,000 --> 00:12:44,000
100 times, that'll have a hundred entry vector. 

267
00:12:44,000 --> 00:12:45,000
So there isn't actually a mechanism where you say 

268
00:12:45,000 --> 00:12:48,000
make it a hundred in advance. You will add a hundred things; it will have length 

269
00:12:48,000 --> 00:12:50,000
a hundred, 

270
00:12:50,000 --> 00:12:53,000
if you inserted a hundred things. The add me insert both 

271
00:12:53,000 --> 00:12:58,000
cause the size of the vector to go up by one, remove caused to go down by one. [Inaudible] brackets 

272
00:12:58,000 --> 00:12:59,000
to 

273
00:12:59,000 --> 00:13:02,000
access a specific element and write to it 

274
00:13:02,000 --> 00:13:07,000
and it's not yet at the - will it automatically fill in [inaudible]? No, it will not, so 

275
00:13:07,000 --> 00:13:12,000
the sub - the square brackets can only access things that are in the vector already. So you can 

276
00:13:12,000 --> 00:13:15,000
overwrite it if it's there, but if you have a ten-member vector, and you go to 

277
00:13:15,000 --> 00:13:17,000
say V sub 20, 

278
00:13:17,000 --> 00:13:18,000
it will not sort of 

279
00:13:18,000 --> 00:13:21,000
invent the ten members in between there and make that space. So the things that are 

280
00:13:21,000 --> 00:13:24,000
valid to access to read from are the same ones that are valid to write to, so you 

281
00:13:24,000 --> 00:13:25,000
can use the square 

282
00:13:25,000 --> 00:13:29,000
bracket on either side of the assignment operator to read or to write, but it has 

283
00:13:29,000 --> 00:13:31,000
to still be something that's already in there. If you really want to put 

284
00:13:31,000 --> 00:13:34,000
a hundred zeros into it, then you need to write a loop that puts a hundred zeros into 

285
00:13:34,000 --> 00:13:36,000
it 

286
00:13:36,000 --> 00:13:39,000
using 

287
00:13:39,000 --> 00:13:40,000


288
00:13:40,000 --> 00:13:44,000
add. Way in the back. [Inaudible] Only for efficiency in 

289
00:13:44,000 --> 00:13:47,000
this case. I'm not changing it, so if I 

290
00:13:47,000 --> 00:13:50,000
was planning on going in here and multiplying everything by two or something, 

291
00:13:50,000 --> 00:13:53,000
I would do that pass by reference to see those changes permanently affected. This 

292
00:13:53,000 --> 00:13:56,000
actually isn't making any changes to the vector, it's just reading the contents of it, 

293
00:13:56,000 --> 00:13:59,000
so it could be pass by value and have the same 

294
00:13:59,000 --> 00:14:03,000
effect, but I wouldn't see any change in the program, it would just run a little slower 

295
00:14:03,000 --> 00:14:04,000
if I did that. 

296
00:14:04,000 --> 00:14:07,000
We will typically though - you will see that kinda just by 

297
00:14:07,000 --> 00:14:09,000
habit we will almost always pass our 

298
00:14:09,000 --> 00:14:11,000
collections by reference, 

299
00:14:11,000 --> 00:14:14,000
because of the concern for efficiency in the long run. 

300
00:14:14,000 --> 00:14:17,000
So it - even though we don't plan on changing it, 

301
00:14:17,000 --> 00:14:21,000
we'll use that to save ourselves some 

302
00:14:21,000 --> 00:14:24,000
time. Anything about 

303
00:14:24,000 --> 00:14:28,000
vector? 

304
00:14:28,000 --> 00:14:29,000
[Inaudible] 

305
00:14:29,000 --> 00:14:32,000
The second to the last line before printing, 

306
00:14:32,000 --> 00:14:35,000
the one right here where I'm going the - so this is declaring vector [inaudible], so 

307
00:14:35,000 --> 00:14:37,000
making the new variable, and it's assigning it 

308
00:14:37,000 --> 00:14:41,000
the return value from calling the make random vector function. So it's actually 

309
00:14:41,000 --> 00:14:43,000
declaring and assigning it in one step 

310
00:14:43,000 --> 00:14:46,000
where that assignment caused a function to be called that stuffed it full of random 

311
00:14:46,000 --> 00:14:50,000
numbers and returned it. Ten in that case means what? 

312
00:14:50,000 --> 00:14:54,000
Ten in this case is just the size. It's the [inaudible] 

313
00:14:54,000 --> 00:14:56,000
make me a random vector containing ten values, 

314
00:14:56,000 --> 00:14:59,000
so that's - the ten in this case is just how many things to put in the array. 

315
00:14:59,000 --> 00:15:01,000
[Inaudible] 

316
00:15:01,000 --> 00:15:04,000
Well it will make ten random numbers and stick them into the 

317
00:15:04,000 --> 00:15:08,000
vector, so when you get back you'll have vector of size ten that has ten random 

318
00:15:08,000 --> 00:15:09,000
entries in it. 

319
00:15:09,000 --> 00:15:13,000
If I said a hundred I'd get a hundred random entries. [Inaudible] function, which library has it? It is in random.H, 

320
00:15:13,000 --> 00:15:14,000
so 

321
00:15:14,000 --> 00:15:17,000


322
00:15:17,000 --> 00:15:19,000
a lower 

323
00:15:19,000 --> 00:15:27,000
case random.H, which is R cs1061. Okay. Now 

324
00:15:27,000 --> 00:15:29,000
let me 

325
00:15:29,000 --> 00:15:33,000
reinforce this idea that templates are type safe, and that if you misuse them 

326
00:15:33,000 --> 00:15:34,000


327
00:15:34,000 --> 00:15:36,000
you will get errors from the complier 

328
00:15:36,000 --> 00:15:39,000
that help you to alert yourself to the mistakes that you've made. If I 

329
00:15:39,000 --> 00:15:41,000
make a vector 

330
00:15:41,000 --> 00:15:44,000
specialized to hold [inaudible] is really an integer vector, I make a vector 

331
00:15:44,000 --> 00:15:47,000
to hold strings I call words, that 

332
00:15:47,000 --> 00:15:51,000
I could add integers into the first one, I could add words to the second one, but I can't 

333
00:15:51,000 --> 00:15:54,000
cross those lines. If I try to take nums 

334
00:15:54,000 --> 00:15:55,000
and add to it the string banana, 

335
00:15:55,000 --> 00:15:57,000
it will not compile, 

336
00:15:57,000 --> 00:15:59,000
so it has a very strong notion of the 

337
00:15:59,000 --> 00:16:04,000
add operation on this kind of vector accepts this kind of thing. So if it's a 

338
00:16:04,000 --> 00:16:08,000
vector of strings, the add accepts strings. If it's a vector of [inaudible] add accepts integers, 

339
00:16:08,000 --> 00:16:11,000
and the crossing of that will cause compiler errors. 

340
00:16:11,000 --> 00:16:15,000
Similarly, when I'm trying to get something out of a vector, 

341
00:16:15,000 --> 00:16:19,000
that return value is typed for what you put in it. If you have a vector of 

342
00:16:19,000 --> 00:16:21,000
strings, then what you return is strings, not characters. 

343
00:16:21,000 --> 00:16:23,000
Or trying to do, kind of 

344
00:16:23,000 --> 00:16:26,000
take one vector; one vector is not equivalent to another if their base 

345
00:16:26,000 --> 00:16:29,000
types are not the same. So a vector of doubles 

346
00:16:29,000 --> 00:16:32,000
is not the same thing as a vector of integers. And so if I have a function 

347
00:16:32,000 --> 00:16:35,000
that expects one or tries to use on, it really [inaudible] a vector of in, a 

348
00:16:35,000 --> 00:16:38,000
vector of in is not the same thing as a vector of doubles, 

349
00:16:38,000 --> 00:16:41,000
and the complier will not let you kind of mix those things up. 

350
00:16:41,000 --> 00:16:43,000
So it provides pretty 

351
00:16:43,000 --> 00:16:44,000
good 

352
00:16:44,000 --> 00:16:47,000
error messages in these cases. It's a, here's 

353
00:16:47,000 --> 00:16:49,000
how you've gotten your types 

354
00:16:49,000 --> 00:16:53,000
confused. 

355
00:16:53,000 --> 00:16:56,000
[Inaudible] double bracket number and then - 

356
00:16:56,000 --> 00:16:59,000
Yeah, so if this said vector angle bracket [inaudible] then it would fine, then I would 

357
00:16:59,000 --> 00:17:02,000
just be making a copy of the nums into a new variable S that had a 

358
00:17:02,000 --> 00:17:04,000
complete same content that nums did. 

359
00:17:04,000 --> 00:17:07,000
So that would be totally fine. I can definitely do assignment from one vector to another if they 

360
00:17:07,000 --> 00:17:09,000
are of the same type, 

361
00:17:09,000 --> 00:17:12,000
but vector in is not the same thing as vector double which is not the same 

362
00:17:12,000 --> 00:17:14,000
thing as vector string, and so 

363
00:17:14,000 --> 00:17:16,000
it's - basically it means that - 

364
00:17:16,000 --> 00:17:19,000
what the template is, is a patter for which you can make a bunch of classes, and on demand 

365
00:17:19,000 --> 00:17:22,000
it makes new classes, the vector double, the vector in, the vector string. And each 

366
00:17:22,000 --> 00:17:26,000
of those is distinct from the other ones that have been created. Can I change the types of 

367
00:17:26,000 --> 00:17:27,000
nums in 

368
00:17:27,000 --> 00:17:28,000
the 

369
00:17:28,000 --> 00:17:30,000
expression and then - You cannot type [inaudible], 

370
00:17:30,000 --> 00:17:33,000
so it's not like I can type cast it down, they really are just different things and they're 

371
00:17:33,000 --> 00:17:36,000
stored differently, ints are a different size and doubles, so there's a bunch more things that 

372
00:17:36,000 --> 00:17:37,000
it 

373
00:17:37,000 --> 00:17:40,000
will just not do automatically in that case. If I really wanted to try to take a bunch of 

374
00:17:40,000 --> 00:17:44,000
integers and put them into a vector or doubles, I would end up 

375
00:17:44,000 --> 00:17:48,000
having to kind of do a one by one, take each int, convert it to a double and stick it into a new vector to get that effect. 

376
00:17:48,000 --> 00:17:50,000
Somebody in the back had something going on? Same question. 

377
00:17:50,000 --> 00:17:56,000
Same question, okay, so then we're good. Let me tell you a 

378
00:17:56,000 --> 00:17:57,000
little bit about grid, 

379
00:17:57,000 --> 00:18:00,000
which is just the extension of vector into two dimensions. Somebody asked 

380
00:18:00,000 --> 00:18:03,000
about this a minute ago, which is like, well can we do this? We can still [inaudible] vectors 

381
00:18:03,000 --> 00:18:04,000
of vectors 

382
00:18:04,000 --> 00:18:07,000
as one way of getting into two dimension, but often what you have is really a 

383
00:18:07,000 --> 00:18:11,000
rectangular region, where the number of rows and columns is fixed all the way 

384
00:18:11,000 --> 00:18:12,000
across, 

385
00:18:12,000 --> 00:18:15,000
in which case it might be convenient to have something like grid 

386
00:18:15,000 --> 00:18:18,000
that you just specify how big you want, how many rows, how many columns, and then 

387
00:18:18,000 --> 00:18:19,000
you get 

388
00:18:19,000 --> 00:18:20,000
a full 

389
00:18:20,000 --> 00:18:22,000
2D 

390
00:18:22,000 --> 00:18:24,000
matrix to hold those values. 

391
00:18:24,000 --> 00:18:27,000
So it is something that you set the dimensions of the constructors, you 

392
00:18:27,000 --> 00:18:28,000
make a new grid on int that 

393
00:18:28,000 --> 00:18:30,000
has ten rows and ten columns. 

394
00:18:30,000 --> 00:18:34,000
There actually is a number function resize that lets you later change the number of 

395
00:18:34,000 --> 00:18:37,000
rows and columns, 

396
00:18:37,000 --> 00:18:41,000
but typically you tend to actually - once you set it, it tends to stay that way. 

397
00:18:41,000 --> 00:18:47,000
You have access to each element by row and column, so you say I want the to getat 

398
00:18:47,000 --> 00:18:50,000
this row, this column, it will return you the value that's been stored there. 

399
00:18:50,000 --> 00:18:54,000
And I put it over here; it says elements have default [inaudible]. 

400
00:18:54,000 --> 00:18:57,000
So if you say I want a ten by ten grid of integers, 

401
00:18:57,000 --> 00:19:01,000
then it does create a full ten by ten grid of integers. If you ask it to retrieve the value at any of 

402
00:19:01,000 --> 00:19:03,000
those locations before you set them, they have 

403
00:19:03,000 --> 00:19:05,000
the same contents that 

404
00:19:05,000 --> 00:19:08,000
an integer declared of the stack would have, which is to say random. 

405
00:19:08,000 --> 00:19:10,000
So they're not zero, they're not negative one, they're not anything 

406
00:19:10,000 --> 00:19:13,000
special. They're whatever - kind of if you just have int setting around, what is its 

407
00:19:13,000 --> 00:19:15,000
default value? 

408
00:19:15,000 --> 00:19:18,000
For the primitive types that just means it's random. For some of the 

409
00:19:18,000 --> 00:19:21,000
more fancy types like string, it would mean they have the default value for 

410
00:19:21,000 --> 00:19:25,000
string, which is the empty string. So if I'm in a 2D grid of strings, then all the 

411
00:19:25,000 --> 00:19:29,000
strings would be empty until I explicitly did something to set and assign their 

412
00:19:29,000 --> 00:19:30,000
value. 

413
00:19:30,000 --> 00:19:33,000
So there's a getat setat pair that looks very much like the vector form that takes, in this 

414
00:19:33,000 --> 00:19:35,000
case, two arguments of the row and the column. 

415
00:19:35,000 --> 00:19:38,000
There's also an operator parens 

416
00:19:38,000 --> 00:19:43,000
that lets you say grid of parans, row column and separated by comma. I'll show that 

417
00:19:43,000 --> 00:19:44,000
syntax in just a second. 

418
00:19:44,000 --> 00:19:47,000
It does do full deep copying, the same way the vector does, which is if you 

419
00:19:47,000 --> 00:19:51,000
have a ten by ten grid which has a hundred members, when you pass or 

420
00:19:51,000 --> 00:19:56,000
return it by value, or you assign it, it has a full copy of that hundred member grid. 

421
00:19:56,000 --> 00:20:00,000
Lots of things sort of fit into the world of the grids 

422
00:20:00,000 --> 00:20:03,000
utility, any kind of game ward, you're doing battleship, you're doing a Sudoku, you're doing 

423
00:20:03,000 --> 00:20:06,000
a crossword puzzle, 

424
00:20:06,000 --> 00:20:08,000
designing a maze, 

425
00:20:08,000 --> 00:20:11,000
managing the data behind an image or any kind of mathematical matrix, or sort of table 

426
00:20:11,000 --> 00:20:16,000
tend to fit in the model for what a grid is good for. 

427
00:20:16,000 --> 00:20:19,000
This is the interface for grid, 

428
00:20:19,000 --> 00:20:21,000
so a template like vector was. 

429
00:20:21,000 --> 00:20:23,000
It has two different constructors; 

430
00:20:23,000 --> 00:20:29,000
one that is a little bit of an oddity. This one creates a zero row, zero 

431
00:20:29,000 --> 00:20:30,000
column 

432
00:20:30,000 --> 00:20:32,000
grids, totally empty, 

433
00:20:32,000 --> 00:20:34,000
which then you would later 

434
00:20:34,000 --> 00:20:38,000
most likely be making a resize call to change the number of rows and columns. That 

435
00:20:38,000 --> 00:20:41,000
might be useful in a situation where you need to create the grid before you kind of have information 

436
00:20:41,000 --> 00:20:43,000
about how to size it. 

437
00:20:43,000 --> 00:20:47,000
You can alternatively specify with a constructor the number of rows and 

438
00:20:47,000 --> 00:20:50,000
calls from the get go and have it set up, 

439
00:20:50,000 --> 00:20:52,000
and then you can later ask it for the number of rows and calls 

440
00:20:52,000 --> 00:20:55,000
and then you can getat and setat a 

441
00:20:55,000 --> 00:20:58,000
particular element within that grid 

442
00:20:58,000 --> 00:21:01,000
using those. There's also an operator - I'm not showing you the syntax in these for 

443
00:21:01,000 --> 00:21:04,000
the operator open parens, just because it's a little bit goopy, but I'll show you in the 

444
00:21:04,000 --> 00:21:07,000
client usage that 

445
00:21:07,000 --> 00:21:11,000
shows you how it works from that perspective. 

446
00:21:11,000 --> 00:21:14,000
So this is something let's say like maybe I'm playing a tic tac toe game and I 

447
00:21:14,000 --> 00:21:18,000
was gonna use the grid to hold the three by three board that has x's and 

448
00:21:18,000 --> 00:21:22,000
o's in it, and I want to start it off by having all of them have the space character. 

449
00:21:22,000 --> 00:21:24,000
So I'm going to using characters at each slot, 

450
00:21:24,000 --> 00:21:28,000
I create a board of three three, so this is the way you invoke a construction in 

451
00:21:28,000 --> 00:21:30,000
C++ that takes argument. 

452
00:21:30,000 --> 00:21:32,000
If you have no arguments, you don't have the parens or anything, you just have 

453
00:21:32,000 --> 00:21:37,000
the name, but if it does take one or more arguments, you'll open the paren and 

454
00:21:37,000 --> 00:21:40,000
list them out in order. In this case, the three and three being the number of rows and 

455
00:21:40,000 --> 00:21:41,000
columns. 

456
00:21:41,000 --> 00:21:42,000
And so at this point 

457
00:21:42,000 --> 00:21:44,000
I will have a 

458
00:21:44,000 --> 00:21:47,000
grid that has num rows three, num columns three, it has nine entries in it, and they're all 

459
00:21:47,000 --> 00:21:49,000
garbage. 

460
00:21:49,000 --> 00:21:51,000
Whatever characters that were left over in that place in memory is what actually 

461
00:21:51,000 --> 00:21:53,000
will be at each location. 

462
00:21:53,000 --> 00:21:56,000
And then I did a nested four loop over the rows and columns, 

463
00:21:56,000 --> 00:21:59,000
and here I am showing you the syntax for the 

464
00:21:59,000 --> 00:22:02,000
access to the row column in kind of a shorthand form 

465
00:22:02,000 --> 00:22:04,000
where I say board of 

466
00:22:04,000 --> 00:22:07,000
and then parens bro , column = space. 

467
00:22:07,000 --> 00:22:11,000
Equivalently that could have been the member function setat board. Setat 

468
00:22:11,000 --> 00:22:15,000
row column space to accomplish the same result. 

469
00:22:15,000 --> 00:22:17,000
So this is still like vector sub I, 

470
00:22:17,000 --> 00:22:20,000
it can be used to read or to write. 

471
00:22:20,000 --> 00:22:23,000
It does bounced checking to make sure that row and column are greater than or 

472
00:22:23,000 --> 00:22:26,000
equal to zero and less than the 

473
00:22:26,000 --> 00:22:28,000
number of rows or number of columns respectively. 

474
00:22:28,000 --> 00:22:32,000
So it raises an error if you ever get outside the bounds of the 

475
00:22:32,000 --> 00:22:35,000
grid. And then this return at the end just returns that full grid. 

476
00:22:35,000 --> 00:22:37,000
In this case, the nine 

477
00:22:37,000 --> 00:22:39,000
by entry, three by three 

478
00:22:39,000 --> 00:22:48,000
back to someone else who's gonna store it and so something with it. 

479
00:22:48,000 --> 00:22:50,000


480
00:22:50,000 --> 00:22:51,000
[Inaudible] 

481
00:22:51,000 --> 00:22:55,000


482
00:22:55,000 --> 00:22:58,000


483
00:22:58,000 --> 00:23:01,000
There is actual one distinction between a vector and a vector of a grid that's kinda interesting, 

484
00:23:01,000 --> 00:23:04,000
the grid is rectangular, it forces there to be 

485
00:23:04,000 --> 00:23:07,000
exactly the same number of rows and column kind of for the whole thing. That 

486
00:23:07,000 --> 00:23:09,000
a vector - if you created a vector of vector, 

487
00:23:09,000 --> 00:23:13,000
you could individually size each row as needed. This could have ten, this 

488
00:23:13,000 --> 00:23:16,000
could have three, and so like a vector vector might be interesting if you 

489
00:23:16,000 --> 00:23:20,000
had something - well they call that kind of the ragged right behavior, where they 

490
00:23:20,000 --> 00:23:23,000
don't all line up over here. But if you really have something that's tabular, 

491
00:23:23,000 --> 00:23:26,000
that there is a rectangular shape to it, the grid is going to 

492
00:23:26,000 --> 00:23:28,000
be a little bit easier to get it up and running, 

493
00:23:28,000 --> 00:23:30,000
but the vector vector's certainly would work, but 

494
00:23:30,000 --> 00:23:32,000
if you were doing 

495
00:23:32,000 --> 00:23:34,000
an array of 

496
00:23:34,000 --> 00:23:38,000
class lists where some classes have ten and some classes have four hundred, but 

497
00:23:38,000 --> 00:23:41,000
if you tried to do that with a grid you'd have to size the whole thing to 

498
00:23:41,000 --> 00:23:48,000
have a much larger row dimension than was needed in most cases. 

499
00:23:48,000 --> 00:23:50,000
So there's no square bracket operator? 

500
00:23:50,000 --> 00:23:53,000
There is not, and there is kinda an obscure reason for that, and if you are curious, 

501
00:23:53,000 --> 00:23:56,000
you can come to the cafe afterwards, and I'll tell you why it is, 

502
00:23:56,000 --> 00:23:58,000
but 

503
00:23:58,000 --> 00:24:01,000
some of the syntax you may have seen in the past has two square brackets, you say sub 

504
00:24:01,000 --> 00:24:03,000
row, sub column, 

505
00:24:03,000 --> 00:24:07,000
and to have that work on a class in C++ 

506
00:24:07,000 --> 00:24:08,000
doesn't - it's not as clean. So it 

507
00:24:08,000 --> 00:24:11,000
turns out we use the parens, because it turns out as a cleaner was of 

508
00:24:11,000 --> 00:24:14,000
accomplishing the thing we wanted, which was a short hand access into 

509
00:24:14,000 --> 00:24:15,000
there. 

510
00:24:15,000 --> 00:24:21,000
So it doesn't actually use the square bracket operator. Question here? 

511
00:24:21,000 --> 00:24:22,000
[Inaudible] when 

512
00:24:22,000 --> 00:24:25,000
you 

513
00:24:25,000 --> 00:24:27,000
created support three by three and you 

514
00:24:27,000 --> 00:24:32,000
said it was forced to be a square, so why would you ever have to 

515
00:24:32,000 --> 00:24:35,000
enter the second? It's forced to be rectangular; it's not forced to be square. It could be three by ten, so I could 

516
00:24:35,000 --> 00:24:38,000
have three rows by ten columns, but 

517
00:24:38,000 --> 00:24:40,000
it does mean that every row has the same number of columns, but the row 

518
00:24:40,000 --> 00:24:44,000
and number of rows and columns doesn't have to be equal, I'm sorry. [Inaudible] if I made squares, the 

519
00:24:44,000 --> 00:24:52,000
wrong word really rectangular is it. So 

520
00:24:52,000 --> 00:24:54,000
then I'm gonna very quickly tell you these last two and they're actually even easier to 

521
00:24:54,000 --> 00:24:57,000
get your head around, because they're actually just simplified versions of 

522
00:24:57,000 --> 00:25:00,000
something you already know, which is to take the vector 

523
00:25:00,000 --> 00:25:02,000
and actually limit what you can do with it 

524
00:25:02,000 --> 00:25:05,000
to produce the stack in the queue class. 

525
00:25:05,000 --> 00:25:06,000
It 

526
00:25:06,000 --> 00:25:09,000
seems like kind of a strange thing to do if you already had a class that did something, why 

527
00:25:09,000 --> 00:25:12,000
would you want to dumb it down, but there actually are some good reasons that I'll hopefully 

528
00:25:12,000 --> 00:25:15,000
convince you of that why we have a stack and a queue. 

529
00:25:15,000 --> 00:25:17,000
So what a stack is about is modeling 

530
00:25:17,000 --> 00:25:21,000
the real world concept of a stack. If you have a stack of papers or a stack 

531
00:25:21,000 --> 00:25:22,000
of plates 

532
00:25:22,000 --> 00:25:24,000
you come and you put new things on the top of that 

533
00:25:24,000 --> 00:25:28,000
and then when it's time to take one off you take the top one. All right, so you don't dig 

534
00:25:28,000 --> 00:25:30,000
through the bottom of the stack, you don't reach over to the bottom. So if you 

535
00:25:30,000 --> 00:25:32,000
go up to get 

536
00:25:32,000 --> 00:25:33,000


537
00:25:33,000 --> 00:25:36,000
a plate in the cafeteria you just take the one that's on the top. When they put new 

538
00:25:36,000 --> 00:25:38,000
clean ones they stick them on the top. 

539
00:25:38,000 --> 00:25:40,000
So this 

540
00:25:40,000 --> 00:25:45,000
could be - you could take a vector and model exactly that behavior where all the 

541
00:25:45,000 --> 00:25:49,000
edits to that - all the additions and remove operations have to happen on the 

542
00:25:49,000 --> 00:25:50,000
top or one end of the vector, 

543
00:25:50,000 --> 00:25:53,000
and that's basically what a stack does. Is 

544
00:25:53,000 --> 00:25:56,000
it provides something that looks like a vector 

545
00:25:56,000 --> 00:25:59,000
but that only allows you access to the top end of the stack. 

546
00:25:59,000 --> 00:26:01,000
It has the operation push 

547
00:26:01,000 --> 00:26:04,000
which is to say put a new thing on the top of the stack. 

548
00:26:04,000 --> 00:26:08,000
It has the operation pop, which is remove the top most element on the stack, 

549
00:26:08,000 --> 00:26:11,000
and there's actually a peak operation that looks at what's on the top without 

550
00:26:11,000 --> 00:26:12,000
removing it. 

551
00:26:12,000 --> 00:26:15,000
There is no access to anything further down. 

552
00:26:15,000 --> 00:26:18,000
If you want to see at the bottom or what's in the middle, the stack 

553
00:26:18,000 --> 00:26:22,000
doesn't let you do it. It gives a kind of a little window to look at this 

554
00:26:22,000 --> 00:26:23,000
information 

555
00:26:23,000 --> 00:26:25,000
that's restricted. 

556
00:26:25,000 --> 00:26:28,000
That seems a little bit strange, 

557
00:26:28,000 --> 00:26:31,000
why is it when you want - like sometimes you could do that with a 

558
00:26:31,000 --> 00:26:34,000
vector by always adding to the end and always forcing yourself to remove from the 

559
00:26:34,000 --> 00:26:34,000
end, 

560
00:26:34,000 --> 00:26:37,000
but then just ignoring the fact that you could dig through the other parts of the vector. And 

561
00:26:37,000 --> 00:26:38,000


562
00:26:38,000 --> 00:26:41,000
there are a few really good reasons to have the stack around, because there are certain 

563
00:26:41,000 --> 00:26:44,000
things that really are stack based operations. A good example of is like if 

564
00:26:44,000 --> 00:26:46,000
you are 

565
00:26:46,000 --> 00:26:48,000
doing the web browser history 

566
00:26:48,000 --> 00:26:49,000
when you can walk forward, 

567
00:26:49,000 --> 00:26:51,000
but then you can back up. 

568
00:26:51,000 --> 00:26:54,000
You don't need to be able to jump all the way back to the end, you're just going back 

569
00:26:54,000 --> 00:26:57,000
in time. Or if you undoing the actions in a word processors, you type some things 

570
00:26:57,000 --> 00:26:58,000
and you undo it, 

571
00:26:58,000 --> 00:27:02,000
that you always undo the last most operations before you undo things before 

572
00:27:02,000 --> 00:27:05,000
that. And having it be a vector where you can kind of did through it means there's a chance 

573
00:27:05,000 --> 00:27:08,000
you could make a mistake. You could accidently pull from the wrong end or do 

574
00:27:08,000 --> 00:27:08,000
something 

575
00:27:08,000 --> 00:27:11,000
that you didn't intend. By having the stack it kinda forces you to use it the way 

576
00:27:11,000 --> 00:27:15,000
you said you planned on, which is I'm only going to stack on the end, I'm going to 

577
00:27:15,000 --> 00:27:17,000
remove from the end. 

578
00:27:17,000 --> 00:27:18,000
So it lets you model 

579
00:27:18,000 --> 00:27:22,000
this particular kind of limited access vector 

580
00:27:22,000 --> 00:27:23,000
in a way that 

581
00:27:23,000 --> 00:27:26,000
prevents you from making mistakes, and also very clearly indicates to someone reading 

582
00:27:26,000 --> 00:27:28,000
your code what you were doing. 

583
00:27:28,000 --> 00:27:31,000
So for example, stacks are very well known to all computer scientists. It's one of the 

584
00:27:31,000 --> 00:27:33,000
classic data structures. 

585
00:27:33,000 --> 00:27:36,000
We think of, for example, the function calls as a stack. 

586
00:27:36,000 --> 00:27:40,000
You call main which calls binky which calls winky, well winky comes back and 

587
00:27:40,000 --> 00:27:41,000
finishes, we get back to 

588
00:27:41,000 --> 00:27:45,000
the binky call, we go back to main, then it always goes in this last in, first out, 

589
00:27:45,000 --> 00:27:46,000
that 

590
00:27:46,000 --> 00:27:47,000
the last thing we started 

591
00:27:47,000 --> 00:27:51,000
is the first one to undo and go backwards to as we work our way back 

592
00:27:51,000 --> 00:27:53,000
down to the bottom of the stack. 

593
00:27:53,000 --> 00:27:56,000
And so computer scientists have a very strong notion of what a stack is. You declare 

594
00:27:56,000 --> 00:27:59,000
something as a stack and that immediately says to them, I see how you're 

595
00:27:59,000 --> 00:28:03,000
using this. You plan on adding to the end and removing from that same end. 

596
00:28:03,000 --> 00:28:06,000
So you can do things like reversal sequence very easily. 

597
00:28:06,000 --> 00:28:09,000
Put it all on the stack, pop it all off, it came back in the opposite order you put it on. 

598
00:28:09,000 --> 00:28:13,000
You put ABC on you'll get CBA off. If I put 

599
00:28:13,000 --> 00:28:16,000
5 3 12 on, I'll get 12 3 5 off. So anytime I needed to do a 

600
00:28:16,000 --> 00:28:19,000
reversing thing, a stack is a great place to just temporarily throw it and then 

601
00:28:19,000 --> 00:28:21,000
pull it back out. 

602
00:28:21,000 --> 00:28:25,000
Managing any sequence of [inaudible] action, the moves and again, the keystrokes in your 

603
00:28:25,000 --> 00:28:27,000
edits you've made in the 

604
00:28:27,000 --> 00:28:30,000
word processor, tracking the history when your web browsing of where 

605
00:28:30,000 --> 00:28:32,000
you've been and where you want to back up to 

606
00:28:32,000 --> 00:28:36,000
are all stack based activities. 

607
00:28:36,000 --> 00:28:39,000
So if you look at stack, it actually has an even simpler interface than vector for 

608
00:28:39,000 --> 00:28:41,000
that matter. 

609
00:28:41,000 --> 00:28:45,000
It has the corresponding size n is empty, so you'll see a lot of repetition 

610
00:28:45,000 --> 00:28:49,000
throughout the interface where we could reuse names that you already know 

611
00:28:49,000 --> 00:28:52,000
and have meaning for, we just reproduce them 

612
00:28:52,000 --> 00:28:55,000
from class to class, so there's a size that tells you how many things are on the 

613
00:28:55,000 --> 00:28:58,000
stack, and is empty, that tells you whether the size is zero, 

614
00:28:58,000 --> 00:29:01,000
and then the push and pop operations that add something 

615
00:29:01,000 --> 00:29:02,000
and remove it. 

616
00:29:02,000 --> 00:29:05,000
And they don't allow you to specify where it goes; it is assumed it's going on the top of the 

617
00:29:05,000 --> 00:29:08,000
stack, and then that peak that lets you look at what's on the top without 

618
00:29:08,000 --> 00:29:15,000
removing it. 

619
00:29:15,000 --> 00:29:18,000
Yeah? So if you 

620
00:29:18,000 --> 00:29:19,000
[inaudible] that had 

621
00:29:19,000 --> 00:29:22,000
nothing in it, would you just get - You get an error. So these guys are very bullet proof. One of the things we tried to do in 

622
00:29:22,000 --> 00:29:24,000
designing our interface was give you a simple 

623
00:29:24,000 --> 00:29:27,000
model you can follow, but also if you step out of the boundaries of what we 

624
00:29:27,000 --> 00:29:28,000
know to be acceptable, 

625
00:29:28,000 --> 00:29:33,000
we really stop hard and fast. So if you try to pop from an empty stacker, peak at an 

626
00:29:33,000 --> 00:29:35,000
empty stack, it will print and error and halt your program. It 

627
00:29:35,000 --> 00:29:42,000
won't make it up, it won't guess, it won't - [Inaudible] 

628
00:29:42,000 --> 00:29:46,000
Well, so the stack knows its size and it [inaudible] is empty, 

629
00:29:46,000 --> 00:29:50,000
so when you're unloading a stack you'll typically be in a loop like, well the 

630
00:29:50,000 --> 00:29:52,000
stacks not empty, pop. 

631
00:29:52,000 --> 00:29:54,000
So there's definitely ways you can check ahead of time to know whether there is something 

632
00:29:54,000 --> 00:29:56,000
there or not, and 

633
00:29:56,000 --> 00:29:58,000
it's all managed as part of the stack. 

634
00:29:58,000 --> 00:30:01,000
But if you blow it and you try to reach into the stack that's empty, 

635
00:30:01,000 --> 00:30:02,000


636
00:30:02,000 --> 00:30:03,000
it won't let you get away with it. 

637
00:30:03,000 --> 00:30:07,000
And that's really what you want. That means that they run a little slower 

638
00:30:07,000 --> 00:30:10,000
than the counterparts in the standard library, but 

639
00:30:10,000 --> 00:30:13,000
they never let you make that kind of mistake without 

640
00:30:13,000 --> 00:30:16,000
alerting you to it, where as the standard library will actually respond a little 

641
00:30:16,000 --> 00:30:19,000
bit less graciously. It would be more likely to just make it up. 

642
00:30:19,000 --> 00:30:20,000
You tell it to pop 

643
00:30:20,000 --> 00:30:22,000
and the 

644
00:30:22,000 --> 00:30:22,000
contract is, yeah, 

645
00:30:22,000 --> 00:30:27,000
I'll return you something if I feel like it and it may be what - it may 

646
00:30:27,000 --> 00:30:29,000
be something that actually misleads you into thinking there was some valid contents 

647
00:30:29,000 --> 00:30:33,000
on the stack and causes the error to kinda propagate further before you realize 

648
00:30:33,000 --> 00:30:35,000
how far you've 

649
00:30:35,000 --> 00:30:39,000
come from what its real genesis was. So one of the nice things about reporting the error 

650
00:30:39,000 --> 00:30:40,000
at the first 

651
00:30:40,000 --> 00:30:45,000
glance is it gives you the best information about how to fix it. 

652
00:30:45,000 --> 00:30:48,000
So here's something that just uses the stack to invert 

653
00:30:48,000 --> 00:30:48,000


654
00:30:48,000 --> 00:30:50,000
a string in this case, right, 

655
00:30:50,000 --> 00:30:53,000
something a user typed in. So I 

656
00:30:53,000 --> 00:30:56,000
prompted for them to enter something for me, I get that line 

657
00:30:56,000 --> 00:30:58,000
and then I create a stack of characters. 

658
00:30:58,000 --> 00:31:02,000
So the stack in this case is being created empty and then I take each 

659
00:31:02,000 --> 00:31:03,000
character one by 

660
00:31:03,000 --> 00:31:07,000
one from the first to the last and push it onto the stack, and so if they 

661
00:31:07,000 --> 00:31:07,000
answered 

662
00:31:07,000 --> 00:31:10,000
Hello, then we would put H-E-L-L-O on the stack. 

663
00:31:10,000 --> 00:31:12,000
And then print it backwards, 

664
00:31:12,000 --> 00:31:16,000
well the stack is not empty I pop and print it back out, so I'll get 

665
00:31:16,000 --> 00:31:16,000


666
00:31:16,000 --> 00:31:18,000
O-L-L-E-H back out of that 

667
00:31:18,000 --> 00:31:20,000
and the loop will exit when it has emptied the 

668
00:31:20,000 --> 00:31:26,000
stack completely. 

669
00:31:26,000 --> 00:31:30,000


670
00:31:30,000 --> 00:31:32,000
Stack [inaudible] just is 

671
00:31:32,000 --> 00:31:34,000
a simpler form of that. The 

672
00:31:34,000 --> 00:31:37,000
queue is just the cousin of the stack. 

673
00:31:37,000 --> 00:31:39,000
Same sort of idea is that 

674
00:31:39,000 --> 00:31:42,000
there's certain usage patterns for a vector 

675
00:31:42,000 --> 00:31:47,000
that form kind of their own class that's worth kinda giving a 

676
00:31:47,000 --> 00:31:50,000
name to and building an abstraction around, the queue. 

677
00:31:50,000 --> 00:31:54,000
The queue instead of being last in first out is first in first out. So the first 

678
00:31:54,000 --> 00:31:56,000
thing you add into the queue 

679
00:31:56,000 --> 00:32:00,000
is going to be the first one you remove. So you add at the front - you 

680
00:32:00,000 --> 00:32:03,000
add at the back and you remove from the front, it models a waiting line. 

681
00:32:03,000 --> 00:32:07,000
So if you think of lets say the head of the queue and tail, 

682
00:32:07,000 --> 00:32:11,000
or the front or the back of the line, that A was placed in the queue first, 

683
00:32:11,000 --> 00:32:13,000
that operation's called n queue; 

684
00:32:13,000 --> 00:32:16,000
n queue A, n queue B, n queue C, n queue D, 

685
00:32:16,000 --> 00:32:21,000
and then when you d queue, which is the remove operation on a queue, it will pull the 

686
00:32:21,000 --> 00:32:22,000
oldest thing in the queue, the one that was there 

687
00:32:22,000 --> 00:32:24,000
first who's been waiting the longest. 

688
00:32:24,000 --> 00:32:30,000
So removing the A and then next d queue will give you that B and so on. So 

689
00:32:30,000 --> 00:32:33,000
it does what you think of as your classic waiting line. 

690
00:32:33,000 --> 00:32:35,000
You're at the bank waiting for a teller. 

691
00:32:35,000 --> 00:32:38,000
The keystrokes that you're typing are being likely stored in something 

692
00:32:38,000 --> 00:32:42,000
that's queue like, setting up the jobs for a printer so that 

693
00:32:42,000 --> 00:32:45,000
there's fair access to it, where first come, first served, 

694
00:32:45,000 --> 00:32:48,000
and there's a couple kind of search [inaudible] that actually tend to use queue 

695
00:32:48,000 --> 00:32:51,000
as the way to kind of keep track of where you are. 

696
00:32:51,000 --> 00:32:54,000
So again, I could use vector for this, 

697
00:32:54,000 --> 00:32:58,000
just making a deal with myself that I'll add at one end and I'll always remove the zero with 

698
00:32:58,000 --> 00:32:59,000
element, 

699
00:32:59,000 --> 00:33:00,000
but again, 

700
00:33:00,000 --> 00:33:03,000
the effect is that if somebody sees me using a vector, 

701
00:33:03,000 --> 00:33:06,000
that they'd have to look at the code more closely 

702
00:33:06,000 --> 00:33:10,000
to see all my access to it, when I add, and when I remove to verify that I was 

703
00:33:10,000 --> 00:33:12,000
using it in a queue like manner, that I always 

704
00:33:12,000 --> 00:33:14,000
add it to the back an remove from the front. 

705
00:33:14,000 --> 00:33:16,000
If I say it's a queue, 

706
00:33:16,000 --> 00:33:20,000
they know that there is no other access than the n queue d queue 

707
00:33:20,000 --> 00:33:23,000
that operates using this FIFO, first in, first 

708
00:33:23,000 --> 00:33:25,000
out control, 

709
00:33:25,000 --> 00:33:29,000
so they don't have to look any closer at my usage of it to know what I'm up to. 

710
00:33:29,000 --> 00:33:32,000
The other thing that both stack and queue have which 

711
00:33:32,000 --> 00:33:34,000
won't be apparent now, but will 

712
00:33:34,000 --> 00:33:36,000
when we get a little further in the course, 

713
00:33:36,000 --> 00:33:37,000
is that by 

714
00:33:37,000 --> 00:33:40,000
defining the queue extraction to have kind of less features, 

715
00:33:40,000 --> 00:33:43,000
to be what seems to be less powerful 

716
00:33:43,000 --> 00:33:47,000
and have sort of a smaller set of things it has to support, 

717
00:33:47,000 --> 00:33:50,000
also has some certain advantages from the implementation side. That 

718
00:33:50,000 --> 00:33:53,000
if I know somebody's always going to be sticking things on this end and that end, but 

719
00:33:53,000 --> 00:33:55,000
not mucking around in the middle, 

720
00:33:55,000 --> 00:33:58,000
then I can make certain implementation decisions that support the necessary 

721
00:33:58,000 --> 00:34:00,000
operations very efficiently, 

722
00:34:00,000 --> 00:34:03,000
but don't actually do these things well because they don't need to, 

723
00:34:03,000 --> 00:34:06,000
in a way that vector can't make those trade offs. Vector doesn't know for sure 

724
00:34:06,000 --> 00:34:09,000
whether people will be mucking around with the middle or the ends or 

725
00:34:09,000 --> 00:34:10,000
the front or the back, 

726
00:34:10,000 --> 00:34:13,000
and so it has to kinda support everything equally well, that stack and 

727
00:34:13,000 --> 00:34:17,000
queue has a really specific usage pattern that then we can 

728
00:34:17,000 --> 00:34:20,000
use to guide our implementation decisions to make sure it runs 

729
00:34:20,000 --> 00:34:23,000
efficiently for that usage pattern. 

730
00:34:23,000 --> 00:34:27,000
So the same constructor or destructor in size is empty, that kind of 

731
00:34:27,000 --> 00:34:28,000
all our linear collections to, 

732
00:34:28,000 --> 00:34:32,000
and then it's operations which look just like push and pop but with a slight 

733
00:34:32,000 --> 00:34:36,000
change in verb here, n queue and d queue, 

734
00:34:36,000 --> 00:34:39,000
that add to the back, remove from the front, 

735
00:34:39,000 --> 00:34:40,000
and then peak 

736
00:34:40,000 --> 00:34:43,000
is the corresponding look at what's in the front. Like what would be d queued, 

737
00:34:43,000 --> 00:34:51,000
but without removing it from the queue, so just see who's at the head of the line. 

738
00:34:51,000 --> 00:34:54,000
And so a little piece of code I stole from the handout 

739
00:34:54,000 --> 00:34:56,000
which 

740
00:34:56,000 --> 00:34:59,000
sort of modeled a very, very simple sort of like if you're getting access to 

741
00:34:59,000 --> 00:35:00,000
the layer and you're getting help, 

742
00:35:00,000 --> 00:35:01,000


743
00:35:01,000 --> 00:35:05,000
that you might ask the user, to kinda say well what do you want to do next, do you 

744
00:35:05,000 --> 00:35:09,000
want to add somebody to the line or do you wanna service the next customer, and so we 

745
00:35:09,000 --> 00:35:11,000
have this way of getting their answer. 

746
00:35:11,000 --> 00:35:15,000
And if they said, okay, it's time to service the next customer then we d queue and answer 

747
00:35:15,000 --> 00:35:17,000
the question of the first person in the queue which will be the one who's been there 

748
00:35:17,000 --> 00:35:20,000
the longest, waiting the longest. And 

749
00:35:20,000 --> 00:35:23,000
if their answer was not next, we'll assume it was a name of somebody 

750
00:35:23,000 --> 00:35:26,000
just stick onto the queue, so that actually adds things to the queue. 

751
00:35:26,000 --> 00:35:29,000
So as we would go around in this loop it would continue kind of stacking things up on 

752
00:35:29,000 --> 00:35:31,000
the queue 

753
00:35:31,000 --> 00:35:33,000
until 

754
00:35:33,000 --> 00:35:36,000
the response was next and then it would start pulling them off and then we could go back 

755
00:35:36,000 --> 00:35:40,000
to adding more and whatnot, and at any given point the queue will have the name of 

756
00:35:40,000 --> 00:35:41,000
all the 

757
00:35:41,000 --> 00:35:43,000
in-queued 

758
00:35:43,000 --> 00:35:44,000
waiting questions 

759
00:35:44,000 --> 00:35:46,000
that haven't yet been handled, 

760
00:35:46,000 --> 00:35:49,000
and they will be pulled off oldest first, 

761
00:35:49,000 --> 00:35:51,000
which is the fair way to have 

762
00:35:51,000 --> 00:35:55,000
access in a waiting line. 

763
00:35:55,000 --> 00:35:57,000
So 

764
00:35:57,000 --> 00:35:59,000
just the - 

765
00:35:59,000 --> 00:36:04,000
very similar to the stack, but they - LIFO versus FIFO 

766
00:36:04,000 --> 00:36:07,000
managing to 

767
00:36:07,000 --> 00:36:14,000
come in and come out in slightly different ways. So once you 

768
00:36:14,000 --> 00:36:16,000
have kind of these four guys, right, 

769
00:36:16,000 --> 00:36:18,000
you have what are called the 

770
00:36:18,000 --> 00:36:20,000
sequential containers kind of at your disposal. 

771
00:36:20,000 --> 00:36:26,000
Most things actually just need one of those things. You need a stack of 

772
00:36:26,000 --> 00:36:30,000
keystrokes, right, or actions or web pages you visited; you need a queue of 

773
00:36:30,000 --> 00:36:34,000
jobs being queued up for the printer. You need a vector of students who are in a class, 

774
00:36:34,000 --> 00:36:38,000
you need a vector of scores on a particular exam, 

775
00:36:38,000 --> 00:36:41,000
but there's nothing to stop you from kind of combining them in new ways to 

776
00:36:41,000 --> 00:36:44,000
build even fancier things out of those building blocks, 

777
00:36:44,000 --> 00:36:47,000
that each of them is useful in it's own right, and you can actually kind of mash them 

778
00:36:47,000 --> 00:36:48,000
together to 

779
00:36:48,000 --> 00:36:50,000
create even fancier things. 

780
00:36:50,000 --> 00:36:55,000
So like I can have a vector of queue of strings that modeled the checkout lines 

781
00:36:55,000 --> 00:36:59,000
in a supermarket, where each checkout stand has it's own queue of waiting people, 

782
00:36:59,000 --> 00:37:01,000
but that there's a whole vector of them from 

783
00:37:01,000 --> 00:37:05,000
the five or ten checkout stands that I have, and so I can find out which 

784
00:37:05,000 --> 00:37:06,000
one is the 

785
00:37:06,000 --> 00:37:07,000
shortest line 

786
00:37:07,000 --> 00:37:09,000
by iterating over that vector 

787
00:37:09,000 --> 00:37:14,000
and then asking each queue what's your size the find out which is the shortest line 

788
00:37:14,000 --> 00:37:18,000
there, and picking that for the place to line up with my cart. 

789
00:37:18,000 --> 00:37:19,000


790
00:37:19,000 --> 00:37:22,000
If I were building a game, lets say, where there was a game board that was 

791
00:37:22,000 --> 00:37:23,000
some grid, 

792
00:37:23,000 --> 00:37:27,000
and that part of the features of this game which you could stack things 

793
00:37:27,000 --> 00:37:29,000
on top of each location, 

794
00:37:29,000 --> 00:37:33,000
then one way to model that would be a grid where each of the elements was a 

795
00:37:33,000 --> 00:37:36,000
stack itself of strings. So maybe I'm putting letters down 

796
00:37:36,000 --> 00:37:39,000
on a particular square of the board, and I can later cover that letter with 

797
00:37:39,000 --> 00:37:41,000
another letter and so on, 

798
00:37:41,000 --> 00:37:44,000
and so if I want to know what is the particular letter showing at any 

799
00:37:44,000 --> 00:37:45,000
particular grid location, 

800
00:37:45,000 --> 00:37:49,000
I can dig out the row column location, pull that stack out and then peek at what's on 

801
00:37:49,000 --> 00:37:51,000
the top. I won't be 

802
00:37:51,000 --> 00:37:53,000
able to see things that are underneath, and that might be exactly need in this 

803
00:37:53,000 --> 00:37:56,000
game, is that you can only see the things in top, 

804
00:37:56,000 --> 00:38:00,000
the things underneath are irrelevant, until maybe you pop them and they are exposed. 

805
00:38:00,000 --> 00:38:03,000
So we just layer them on top of each other, we can make them as deep as we 

806
00:38:03,000 --> 00:38:07,000
need to. It's not often they need to go past probably two levels, but you can build 

807
00:38:07,000 --> 00:38:10,000
vectors of vectors of vectors and vectors of queues of stacks of grids and 

808
00:38:10,000 --> 00:38:13,000
whatever you need to kind of get the job done. 

809
00:38:13,000 --> 00:38:16,000
There's one little C++ quirk 

810
00:38:16,000 --> 00:38:18,000
that I'm gonna mention while I'm there, 

811
00:38:18,000 --> 00:38:22,000
which is that the vector of queue of string actually has a closer - 

812
00:38:22,000 --> 00:38:26,000
a pair of those closing angle brackets that are neighbors there, 

813
00:38:26,000 --> 00:38:29,000
where I said I have a queue of string, and that I'm enclosing that to be the element 

814
00:38:29,000 --> 00:38:30,000
stored in a vector, 

815
00:38:30,000 --> 00:38:34,000
that if I put these two right next to each other, 

816
00:38:34,000 --> 00:38:37,000
which would be a natural thing to do when I was typing it out, 

817
00:38:37,000 --> 00:38:41,000
that causes the compiler to misunderstand what we want. 

818
00:38:41,000 --> 00:38:43,000
It will lead the 

819
00:38:43,000 --> 00:38:44,000
grid stack 

820
00:38:44,000 --> 00:38:45,000
string, 

821
00:38:45,000 --> 00:38:49,000
and then when it sees the string, the next thing coming up will be these two greater 

822
00:38:49,000 --> 00:38:52,000
than signs. It will read them together, 

823
00:38:52,000 --> 00:38:57,000
so it effect tokenizing it as oh, these next two things go together, 

824
00:38:57,000 --> 00:38:59,000
and they are the stream extraction operator, 

825
00:38:59,000 --> 00:39:01,000
and then it just all 

826
00:39:01,000 --> 00:39:04,000
haywire - goes haywire from there. I think that you're about - you were in the 

827
00:39:04,000 --> 00:39:09,000
middle of declaring a type and then all of a sudden you asked me to do a stream extraction. What happens, right? 

828
00:39:09,000 --> 00:39:11,000
Sad, but true, 

829
00:39:11,000 --> 00:39:14,000
and it will produce an error message, which depending on your compiler is more or 

830
00:39:14,000 --> 00:39:18,000
less helpful. The one is X-code is pretty nice, it actually says, 

831
00:39:18,000 --> 00:39:22,000
closing template, there needs to be a space between it. 

832
00:39:22,000 --> 00:39:25,000
The one in visual studio is not quite as helpful, but it's 

833
00:39:25,000 --> 00:39:27,000
just something you need to learn to look for, is that you do actually have 

834
00:39:27,000 --> 00:39:28,000
to 

835
00:39:28,000 --> 00:39:33,000
plant that extra space in there so that it will read the closer for one, and then 

836
00:39:33,000 --> 00:39:35,000
the second closer without 

837
00:39:35,000 --> 00:39:37,000
mingling them together. 

838
00:39:37,000 --> 00:39:40,000
There is an on deck proposal which shows you that C++ is a live 

839
00:39:40,000 --> 00:39:41,000
language, it's 

840
00:39:41,000 --> 00:39:43,000
evolving as we speak, but in the 

841
00:39:43,000 --> 00:39:47,000
revision of C++ as being planned, they actually want to fix this 

842
00:39:47,000 --> 00:39:49,000
so that actually it will be fine to use them 

843
00:39:49,000 --> 00:39:52,000
without the space and the right thing will happen, 

844
00:39:52,000 --> 00:39:55,000
and by changing it in the standard, it means the compiler writers will eventually kind of 

845
00:39:55,000 --> 00:40:00,000
join to be spec compliant, will actually have to change their compilers 

846
00:40:00,000 --> 00:40:02,000
to handle it properly, where as they now have 

847
00:40:02,000 --> 00:40:04,000
little incentive to do so. And 

848
00:40:04,000 --> 00:40:08,000
then I just put a little note here that as you get to these more complicated things there 

849
00:40:08,000 --> 00:40:09,000


850
00:40:09,000 --> 00:40:13,000
might be some more appeal to using typedef, which is a C++ way of 

851
00:40:13,000 --> 00:40:16,000
[inaudible] shorthand. 

852
00:40:16,000 --> 00:40:19,000
You can actually do this for any type in C++. The typing, 

853
00:40:19,000 --> 00:40:22,000
if you were typically something it would go up at the top of the program. 

854
00:40:22,000 --> 00:40:25,000
I say typedef and then I give the long name 

855
00:40:25,000 --> 00:40:28,000
and then I give the new short name, the nickname I'd like to give to it. So I can 

856
00:40:28,000 --> 00:40:32,000
say typedef into banana and then all through my program use banana as though 

857
00:40:32,000 --> 00:40:33,000
it were an int. 

858
00:40:33,000 --> 00:40:37,000
Okay, probably not that motivating in that situation, but when you have a 

859
00:40:37,000 --> 00:40:40,000
type name that's somehow long and complicated and a little bit awkward to reproduce throughout 

860
00:40:40,000 --> 00:40:42,000
your program, you can 

861
00:40:42,000 --> 00:40:45,000
put that type name in place and use the shorthand name to kind of add clarity 

862
00:40:45,000 --> 00:40:48,000
later. So maybe I'm using this to be 

863
00:40:48,000 --> 00:40:49,000


864
00:40:49,000 --> 00:40:51,000
some information about my calendar, 

865
00:40:51,000 --> 00:40:53,000
where I have the 

866
00:40:53,000 --> 00:40:57,000
months divided into days or days divided into hours, so having kinda of a two 

867
00:40:57,000 --> 00:40:59,000
layer vector here, 

868
00:40:59,000 --> 00:41:03,000
that rather than having vector of vector of ints all over the place I can us calendar T 

869
00:41:03,000 --> 00:41:05,000
to be a synonym for that 

870
00:41:05,000 --> 00:41:09,000
once I've made that declaration. 

871
00:41:09,000 --> 00:41:13,000
Let me show you just a couple of things back in the compiler space before 

872
00:41:13,000 --> 00:41:19,000
I let you guys run away to go skiing. One of the 

873
00:41:19,000 --> 00:41:23,000
things that you're likely to be working on in this case is that you're 

874
00:41:23,000 --> 00:41:24,000
learning a new 

875
00:41:24,000 --> 00:41:28,000
API, API is called Application Programming Interface, 

876
00:41:28,000 --> 00:41:31,000
it's the way you interact with the libraries, knowing what routine does what and what 

877
00:41:31,000 --> 00:41:33,000
it's name is and what it's arguments are, 

878
00:41:33,000 --> 00:41:36,000
and that's likely to be one of the things that's a little bit more of a 

879
00:41:36,000 --> 00:41:40,000
sticking point early on here, is just kind of saying, oh I know this exists in a 

880
00:41:40,000 --> 00:41:43,000
random library, but what's the name of the function, is it random numbers, is it random 

881
00:41:43,000 --> 00:41:45,000
integers, is it random it? And 

882
00:41:45,000 --> 00:41:46,000


883
00:41:46,000 --> 00:41:49,000
being familiar with the ways you kind find out this information. So let me 

884
00:41:49,000 --> 00:41:53,000
just give you a little hint about this; one is that you can open the header 

885
00:41:53,000 --> 00:41:56,000
files, so I just opened in this case, the grid.h header file, 

886
00:41:56,000 --> 00:42:00,000
and I can look at it and see what it says. It says, oh, here's some information, it actually has 

887
00:42:00,000 --> 00:42:01,000
some sample code here, 

888
00:42:01,000 --> 00:42:05,000
and as I scroll down 

889
00:42:05,000 --> 00:42:09,000
it'll tell me about what the class is, and then it has comma's on each of the 

890
00:42:09,000 --> 00:42:11,000
constructor and 

891
00:42:11,000 --> 00:42:12,000


892
00:42:12,000 --> 00:42:15,000
member function calls that tells me how it works and what errors it raises and 

893
00:42:15,000 --> 00:42:19,000
what I need to know to be able to use this call correctly. And so 

894
00:42:19,000 --> 00:42:23,000
for any of our libraries, opening the header file is likely to be an 

895
00:42:23,000 --> 00:42:26,000
illuminating experience. 

896
00:42:26,000 --> 00:42:29,000
We try to write them for humans to read, so they actually do have 

897
00:42:29,000 --> 00:42:31,000


898
00:42:31,000 --> 00:42:33,000
some 

899
00:42:33,000 --> 00:42:37,000
helpfulness. If you go to open a standard header file, 

900
00:42:37,000 --> 00:42:42,000
they're not quite as useful. For example, let's go look at I stream 

901
00:42:42,000 --> 00:42:44,000
and keep going. 

902
00:42:44,000 --> 00:42:45,000
You'll get 

903
00:42:45,000 --> 00:42:49,000
in there and you'll see, okay, it's typedef template car basic I stream and then there's some goo and 

904
00:42:49,000 --> 00:42:51,000
then there's a bunch of typedef's 

905
00:42:51,000 --> 00:42:55,000
and then it gets down to here, there's a little bit of information that tells 

906
00:42:55,000 --> 00:42:56,000
you about 

907
00:42:56,000 --> 00:42:58,000
what the constructor might do and stuff. 

908
00:42:58,000 --> 00:43:03,000
You can read this, but it's not - it doesn't tend to be actually 

909
00:43:03,000 --> 00:43:05,000
targeted at getting the novice up to speed about what's going on. There is 

910
00:43:05,000 --> 00:43:07,000
some information here, but 

911
00:43:07,000 --> 00:43:10,000
in those cases you may be better of using one of our references, going back 

912
00:43:10,000 --> 00:43:11,000
to the reader, 

913
00:43:11,000 --> 00:43:13,000
or looking at 

914
00:43:13,000 --> 00:43:16,000
one of the websites that we give a point or two on the reference handout that 

915
00:43:16,000 --> 00:43:16,000
just kind of 

916
00:43:16,000 --> 00:43:18,000
tries to extract the 

917
00:43:18,000 --> 00:43:20,000


918
00:43:20,000 --> 00:43:22,000
information you need to know as a client rather than trying to go look in here, because once you 

919
00:43:22,000 --> 00:43:25,000
get in here, oh what is gettake, and it's like what is all this stuff with these underbars 

920
00:43:25,000 --> 00:43:28,000
and stuff, it's not the best place to learn the interface, I think, from their 

921
00:43:28,000 --> 00:43:30,000
header files. 

922
00:43:30,000 --> 00:43:31,000
The other place that 

923
00:43:31,000 --> 00:43:34,000
I will note that we have is up here on the website 

924
00:43:34,000 --> 00:43:38,000
there is a documentation link, let me show you where I got to that just to remind you, 

925
00:43:38,000 --> 00:43:42,000
is up here in the top, 

926
00:43:42,000 --> 00:43:43,000
over on this side, 

927
00:43:43,000 --> 00:43:47,000
and what this is, is actually this is our header files having been run through 

928
00:43:47,000 --> 00:43:49,000
something that generates a webpage from them, so it has the same information 

929
00:43:49,000 --> 00:43:52,000
available in the header files, but it's just organized in a 

930
00:43:52,000 --> 00:43:55,000
clickable browsable way to get to things. 

931
00:43:55,000 --> 00:43:56,000
And so if you 

932
00:43:56,000 --> 00:44:00,000
dink this down and you look at the class list, you can say, yeah, tell me about queue, I'd like 

933
00:44:00,000 --> 00:44:04,000
to know more about it and then it'll give you the public member function. This 

934
00:44:04,000 --> 00:44:06,000
projector's really very 

935
00:44:06,000 --> 00:44:09,000
fuzzy, I wonder if someone can sharpen that, 

936
00:44:09,000 --> 00:44:10,000


937
00:44:10,000 --> 00:44:13,000
that tells you that here's the constructor, here's the n queue d queue peak, 

938
00:44:13,000 --> 00:44:16,000
there's a clear operator that empties the whole thing and then there's some other 

939
00:44:16,000 --> 00:44:20,000
operations that are involved with the deep copying that are actually explicitly named out. 

940
00:44:20,000 --> 00:44:23,000
And then if you go down, you can say, well tell me more about n queue, 

941
00:44:23,000 --> 00:44:27,000
you can come down here, it'll tell you the documentation we had that's 

942
00:44:27,000 --> 00:44:30,000
been extracted from the header files tells you about what the arguments are, what their 

943
00:44:30,000 --> 00:44:31,000
turn value is, 

944
00:44:31,000 --> 00:44:32,000


945
00:44:32,000 --> 00:44:34,000
what things you need to know to use that properly. 

946
00:44:34,000 --> 00:44:37,000
And so you'll probably find yourself using one or both of these, like going and actually 

947
00:44:37,000 --> 00:44:41,000
reading the header files or reading the kind of cleaned up pretty printed header files 

948
00:44:41,000 --> 00:44:43,000
just to get familiar with what those interfaces are, what the names are, and 

949
00:44:43,000 --> 00:44:45,000
how you call them 

950
00:44:45,000 --> 00:44:46,000
so 

951
00:44:46,000 --> 00:44:48,000
that when you're working you know, and have a web browser kind of up 

952
00:44:48,000 --> 00:44:52,000
aside to help you navigate that stuff 

953
00:44:52,000 --> 00:44:54,000
without too much guess work. 

954
00:44:54,000 --> 00:44:56,000
And so I just wanted to 

955
00:44:56,000 --> 00:44:58,000
show you that before I let you go. 

956
00:44:58,000 --> 00:45:00,000
Anybody questions about that? Hopefully you should feel a 

957
00:45:00,000 --> 00:45:01,000
little bit like, hey, 

958
00:45:01,000 --> 00:45:05,000
that starts to be useful. By Wednesday I'll show you map and set and 

959
00:45:05,000 --> 00:45:08,000
then you'll realize there's a lot of really cool things you can do with all these 

960
00:45:08,000 --> 00:45:09,000
objects around in your arsenal. 

961
00:45:09,000 --> 00:45:11,000
So have a good weekend, 

962
00:45:11,000 --> 00:45:12,000
enjoy the holiday, 

963
00:45:12,000 --> 00:45:13,000
come to Truman, 

964
00:45:13,000 --> 00:45:17,000
I'll see you on Wednesday.