0:00:00.000,0:00:09.000


0:00:09.000,0:00:12.000
This presentation is delivered by the Stanford Center for Professional Development.

0:00:12.000,0:00:22.000


0:00:22.000,0:00:25.000
Okay, anything administratively you'd like to ask about? How many people

0:00:25.000,0:00:29.000
have completed assignment 1, and done the whole thing?

0:00:29.000,0:00:32.000
All right, you get a gold star. All right,

0:00:32.000,0:00:36.000
you guys want to be him, is what it is, because this guys is getting to go skiing guilt free. You

0:00:36.000,0:00:39.000
guys if you're going skiing won't be guilt free, and

0:00:39.000,0:00:42.000
you'll be working late to finish it off, and he

0:00:42.000,0:00:44.000
is sleeping easy.

0:00:44.000,0:00:47.000
How many people have at least one or two of the problems done?

0:00:47.000,0:00:51.000
Okay, that's a good number.

0:00:51.000,0:00:54.000
We're still making progress.

0:00:54.000,0:00:57.000
So I had just started to talk a little about this idea of a template,

0:00:57.000,0:01:02.000
which is the C++ equivalent of the Java generic,

0:01:02.000,0:01:03.000
and I

0:01:03.000,0:01:07.000
want to refresh on the rules about how do you use a template. The thing about templates

0:01:07.000,0:01:10.000
is they're a very useful and practical

0:01:10.000,0:01:11.000
component to have in the language,

0:01:11.000,0:01:14.000
but they do have a little bit of issues with resolve to when you make mistakes

0:01:14.000,0:01:17.000
with them, kinda having it reported and how you learn about them, and so they can be a

0:01:17.000,0:01:21.000
little bit of a tripping point despite their vast utility.

0:01:21.000,0:01:24.000
Let me just remind you about what it means to use a template; is that you use

0:01:24.000,0:01:27.000
include the interface file as usual. We're trying to use a vector to hold some

0:01:27.000,0:01:30.000
sequence of things, so we include the vector.H.

0:01:30.000,0:01:32.000
The name vector

0:01:32.000,0:01:36.000
by itself without specialization doesn't tell the compiler everything

0:01:36.000,0:01:38.000
it needs to know. When you're trying to

0:01:38.000,0:01:42.000
[inaudible] declare a vector, pass a vector as a parameter, return one, and any

0:01:42.000,0:01:45.000
of those situations where you would have wanted to say it's a vector, you have to

0:01:45.000,0:01:48.000
say what kind of vector, it's a vector holding character, it's a vector holding

0:01:48.000,0:01:49.000
location T's, it's

0:01:49.000,0:01:50.000
a vector holding

0:01:50.000,0:01:51.000
doubles.

0:01:51.000,0:01:54.000
And that just applies everywhere you use the name vector, the name vector by itself

0:01:54.000,0:01:57.000
doesn't mean anything. It always has to have this qualification or specialization on

0:01:57.000,0:01:58.000
it.

0:01:58.000,0:02:02.000
And then once that you've committed that to the compiler, the

0:02:02.000,0:02:05.000
vector from that point really behaves in a type safe manner. A vector

0:02:05.000,0:02:08.000
character is not the same thing as a vector holding doubles. The

0:02:08.000,0:02:11.000
compiler keeps those things separate. It doesn't let you co-mingle them.

0:02:11.000,0:02:14.000
If you expect a vector of care, and you say that as your parameter,

0:02:14.000,0:02:17.000
then you will have to pass one that has the same element type in it,

0:02:17.000,0:02:21.000
that passing a vector double is not this same thing, and so trying to put a double

0:02:21.000,0:02:23.000
into a vector of characters or

0:02:23.000,0:02:26.000
retrieve an integer out of one that's holding

0:02:26.000,0:02:30.000
student structures, is going to give you compiler errors, which is really

0:02:30.000,0:02:34.000
a nice feature for maintaining type safety.

0:02:34.000,0:02:38.000
So the vector class I had just started talking about, and I'm gonna just kinda pick up

0:02:38.000,0:02:42.000
and review the things we had started to talk about on Wednesday and go through

0:02:42.000,0:02:42.000
it,

0:02:42.000,0:02:44.000
which is what is the vector good for?

0:02:44.000,0:02:47.000
The vector is good for any

0:02:47.000,0:02:50.000
collection of things. You need to store a list is kind of the

0:02:50.000,0:02:53.000
abstraction that it's trying to model. I have a list of students in this class, I have

0:02:53.000,0:02:56.000
a list of problems that are being assigned, I have

0:02:56.000,0:02:59.000
a list of classes I'm taking this quarter, you know, whatever those things

0:02:59.000,0:03:02.000
are, a list of scores on an exam,

0:03:02.000,0:03:04.000
and the vector

0:03:04.000,0:03:06.000
manages the needs of all of those kinds of lists. You say what kind of thing

0:03:06.000,0:03:09.000
you're storing in it. Every element has to be the same type, so that's what I mean by

0:03:09.000,0:03:13.000
homogeneous, that all the elements are double or they're all students. You

0:03:13.000,0:03:15.000
can't have doubles and students co-mingle.

0:03:15.000,0:03:20.000
It's linear in the effect that it kinda lays them out in a line. It indexes them from zero

0:03:20.000,0:03:21.000
to the size minus 1.

0:03:21.000,0:03:25.000
Each one has a place in the line and there are no gaps in it, so it actually is

0:03:25.000,0:03:26.000
sequenced out.

0:03:26.000,0:03:30.000
And it doesn't - a lot of things that make for a really convenient handling of the

0:03:30.000,0:03:33.000
list as an abstraction, it knows its size at all time. You can ask it what the

0:03:33.000,0:03:36.000
size is, it'll tell me how your elements have been stored in it. Now

0:03:36.000,0:03:39.000
if you ask for an element by index it bounds checks to make sure that you

0:03:39.000,0:03:43.000
gave it a valid index for the range of size that it's currently holding.

0:03:43.000,0:03:45.000
It handles all the storage for you. If

0:03:45.000,0:03:48.000
you put ten elements and to put an eleventh, if it doesn't have space it goes

0:03:48.000,0:03:52.000
and makes space for you. This all happens without you doing anything explicit, so

0:03:52.000,0:03:55.000
as you add things, as you remove things, it handles sizing and

0:03:55.000,0:03:59.000
changing whatever internal storage needs as needed to accommodate what you asked

0:03:59.000,0:04:00.000
you.

0:04:00.000,0:04:03.000
It has convenient operations for inserting and removing; where you want to put

0:04:03.000,0:04:07.000
something in a slot, it will move everything over to make space for it or to shuffle it down to

0:04:07.000,0:04:09.000
close over that space.

0:04:09.000,0:04:11.000
It also does what we call a deep copy; a

0:04:11.000,0:04:13.000
deep copy is

0:04:13.000,0:04:17.000
sort of a CS term for if I have a vector holding ten numbers,

0:04:17.000,0:04:19.000
and I assign that to another vector,

0:04:19.000,0:04:23.000
it really does make a new vector that has the same ten numbers. That deep copy means

0:04:23.000,0:04:27.000
it's more than some sort of shallow, like they're sharing something. They really are

0:04:27.000,0:04:30.000
creating a clone of it, so taking that same - however big that vector is, whether it

0:04:30.000,0:04:33.000
has a hundred or a thousand or two entries,

0:04:33.000,0:04:36.000
it makes a whole copy, a parallel copy that has

0:04:36.000,0:04:38.000
the same size and the same entries

0:04:38.000,0:04:43.000
that was based on taking the original input and reproducing it in a new vector.

0:04:43.000,0:04:46.000
And that happens when you do assignment from one vector to another, it happens

0:04:46.000,0:04:50.000
when you do a cast by value of a vector into a function that takes a vector by

0:04:50.000,0:04:50.000
value,

0:04:50.000,0:04:54.000
or when you return a vector from a function, so in all those cases it's doing kinda

0:04:54.000,0:04:56.000
a full deep copy

0:04:56.000,0:04:57.000
that

0:04:57.000,0:05:00.000
is unlike those of you had a little experience working with a built in

0:05:00.000,0:05:03.000
array, know that it doesn't have those behaviors, and that comes as a little bit of

0:05:03.000,0:05:06.000
a surprise. The vector behaves just like the primitives in the sense that

0:05:06.000,0:05:07.000
there's no special

0:05:07.000,0:05:10.000
knowledge you need to know about how it's -

0:05:10.000,0:05:14.000
the assignment affects other copies of the same vector.

0:05:14.000,0:05:17.000
So your typical usage is you create an empty vector, you add a new insert;

0:05:17.000,0:05:21.000
remove to kind of jostle of the contents. You can access the elements

0:05:21.000,0:05:25.000
once they're in there using member function setat and getat that allow you to

0:05:25.000,0:05:27.000
change the value of the location, or get the value.

0:05:27.000,0:05:31.000
There's also an operator bracket. We'll see how you can actually just use the

0:05:31.000,0:05:34.000
syntax of the vector name and then the bracket with the index to access a

0:05:34.000,0:05:35.000
particular element,

0:05:35.000,0:05:37.000
useful for all

0:05:37.000,0:05:39.000
sorts of things.

0:05:39.000,0:05:41.000
Question here?

0:05:41.000,0:05:43.000
Student:Yeah, can you make a multi-dimensional vector? Instructor

0:05:43.000,0: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

0:05:47.000,0:05:47.000
already built,

0:05:47.000,0:05:50.000
and you can also build vectors of vectors, and vectors

0:05:50.000,0:05:53.000
of vectors of vectors to build to the higher and higher dimensions. And there's a

0:05:53.000,0:05:56.000
little bit more syntax involved in doing that, but it [inaudible] the same basic functionality

0:05:56.000,0:06:00.000
kind of applies in higher dimension.

0:06:00.000,0:06:03.000
So this is the basic interface of the vector,

0:06:03.000,0:06:05.000
supplied as a template, so

0:06:05.000,0:06:09.000
all the way through it, it refers to elem type as what you get

0:06:09.000,0:06:13.000
at, what you set at, what you add and you insert all of the kind of values that are

0:06:13.000,0:06:14.000
going in and out of that

0:06:14.000,0:06:15.000
vector are

0:06:15.000,0:06:19.000
left using this place holder rather than saying it's explicitly a double or a

0:06:19.000,0:06:22.000
string or something, making no commitment about that, just leaving it open. And then

0:06:22.000,0:06:25.000
that template typed in elem type is the way that the whole class is introduced to

0:06:25.000,0:06:25.000
say

0:06:25.000,0:06:30.000
this is a pattern from which you can create a lot of different vector classes.

0:06:30.000,0:06:33.000
Let me show you a little something on the next slide that helps to

0:06:33.000,0:06:34.000
point this out.

0:06:34.000,0:06:38.000
So here I have, in blue, put all the places where the elem type shows up. I

0:06:38.000,0:06:42.000
put the type name parameter introduced, and it says within the body of the class I'm using

0:06:42.000,0:06:44.000
elem type as a place

0:06:44.000,0:06:47.000
holder, and the four places it's showing up here, the getat the setat the add and

0:06:47.000,0:06:48.000
the insert,

0:06:48.000,0:06:53.000
that when I go to create a vector as a client, I'll say vector of double.

0:06:53.000,0:06:56.000
Every place where there was elem type

0:06:56.000,0:06:57.000


0:06:57.000,0:07:01.000
and on the vector name itself has been annotated or specialized to show

0:07:01.000,0:07:04.000
that what's really going in out of this thing is double.

0:07:04.000,0:07:08.000
So this now created a class vector, angle bracket, double.

0:07:08.000,0:07:12.000
The constructor and the destructor match the class name now, and the getat, the setat,

0:07:12.000,0:07:13.000
the add, the insert,

0:07:13.000,0:07:16.000
all have been locked down. We've made that commitment, we said what we're

0:07:16.000,0:07:18.000
storing here really is vectors of

0:07:18.000,0:07:22.000
doubles, and that means that the add number function for vector double takes

0:07:22.000,0:07:23.000
a double parameter.

0:07:23.000,0:07:26.000
The getat returns a double value,

0:07:26.000,0:07:30.000
and that way once the compiler has done this transformation

0:07:30.000,0:07:33.000
that subsequent usage of that vector double variable

0:07:33.000,0:07:37.000
will be consistent with this filling in of the placeholder,

0:07:37.000,0:07:40.000
so it doesn't actually get confused about other types of

0:07:40.000,0:07:40.000
vectors you may have

0:07:40.000,0:07:45.000
been creating or working with.

0:07:45.000,0:07:50.000
Question? [Inaudible] No, these empty functions are really just a convenience off of size. You could

0:07:50.000,0:07:52.000
always check size equals zero,

0:07:52.000,0:07:54.000
and so it actually doesn't really add anything to the interface.

0:07:54.000,0:07:58.000
It just turns out you do that so often in many situations, you want to know if

0:07:58.000,0:07:59.000
this thing is totally empty,

0:07:59.000,0:08:03.000
that as a convenience it offers two different ways to get at that same information. So you're

0:08:03.000,0:08:04.000
totally right, it's redundant.

0:08:04.000,0:08:08.000
Sometimes you'll see that for example the standard template library has a bunch of

0:08:08.000,0:08:09.000
the same things. The string has

0:08:09.000,0:08:13.000
a length number function. It also has a size number function. They do exactly the same thing. It's

0:08:13.000,0:08:16.000
just because sometimes people can remember size, sometimes people remember length. There's

0:08:16.000,0:08:17.000
also an empty -

0:08:17.000,0:08:19.000
it's not called is empty, but it's just empty. The

0:08:19.000,0:08:22.000
[inaudible] is the length or size zero, and so all of those things are kind of written in

0:08:22.000,0:08:23.000
terms of each other,

0:08:23.000,0:08:25.000
but they

0:08:25.000,0:08:28.000
allow different ways to get at the same information.

0:08:28.000,0:08:30.000
Anything

0:08:30.000,0:08:32.000
else? You got a question? Here we go.

0:08:32.000,0:08:34.000
Is there a remove all method?

0:08:34.000,0:08:39.000
There is actually a clear method, and I should have put that up there. Actually, I think

0:08:39.000,0:08:42.000
there's a few. In each of these cases I've excerpted a little bit for the most

0:08:42.000,0:08:45.000
mainstream operations, but there is a clear operation that takes no arguments,

0:08:45.000,0:08:46.000
returns no argument, that just

0:08:46.000,0:08:55.000
takes the vector to an empty state.

0:08:55.000,0:08:56.000
So here's a little bit of

0:08:56.000,0:08:56.000
code

0:08:56.000,0:09:00.000
that shows some of the common use of vector and how you might do stuff with it

0:09:00.000,0:09:03.000
that just gets you familiar with, okay, what does the syntax look like?

0:09:03.000,0:09:07.000
So I'll look at this top function together, this is make random vector. You give it a

0:09:07.000,0:09:10.000
parameter, which is the size, and it will fill a vector of integers with a sequence

0:09:10.000,0:09:15.000
of random numbers up to that size. You say I'd like a length ten vector filled with

0:09:15.000,0:09:16.000
random numbers,

0:09:16.000,0:09:18.000
it'll make a ten number vector

0:09:18.000,0:09:19.000
stuffing in

0:09:19.000,0:09:23.000
random numbers generated using the random library here.

0:09:23.000,0:09:26.000
So you'll see the declaration here, so I included vector [inaudible], the compiler knew what

0:09:26.000,0:09:29.000
I was using. I

0:09:29.000,0:09:30.000
specialized

0:09:30.000,0:09:32.000
when I declared that vector,

0:09:32.000,0:09:36.000
and so the constructor for vector creates a new empty vector of

0:09:36.000,0:09:38.000
that type, in this case vector of integer,

0:09:38.000,0:09:42.000
and then numbers.add sticking in a bunch of numbers, and then I'm returning it.

0:09:42.000,0:09:46.000
So it's totally valid to actually return a vector as the return value coming out of

0:09:46.000,0:09:47.000
a function.

0:09:47.000,0:09:48.000
It'll take that,

0:09:48.000,0:09:52.000
however many numbers I put in there, ten length vector,

0:09:52.000,0:09:53.000
and make a full copy of it.

0:09:53.000,0:09:56.000
And then when I'm down here and I'm saying nums equals make random vector, it actually

0:09:56.000,0:09:57.000
copied

0:09:57.000,0:09:59.000
that ten number vector

0:09:59.000,0:10:03.000
into the variable beings stored in main. So now I have a ten number

0:10:03.000,0:10:04.000
thing with some random contents.

0:10:04.000,0:10:07.000
The next thing I did with it was pass it to another routine that was going to print

0:10:07.000,0:10:08.000
it,

0:10:08.000,0:10:11.000
and there I am getting that vector, and this time I'm

0:10:11.000,0:10:12.000
accessing it in here

0:10:12.000,0:10:14.000
by reference.

0:10:14.000,0:10:18.000
This is just to show you that in typical because of the deep copying semantics it

0:10:18.000,0:10:20.000
does mean if I didn't pass by reference, it means the

0:10:20.000,0:10:25.000
full contents of the vector would get copied when I passed it to some function.

0:10:25.000,0:10:26.000
There's no

0:10:26.000,0:10:30.000
harm in that per se, other than the fact that it can get inefficient, especially as the

0:10:30.000,0:10:33.000
vector gets larger, it has hundreds and thousands of entries,

0:10:33.000,0:10:34.000
that making a full copy of those

0:10:34.000,0:10:38.000
can have some overall efficiency effects on the program.

0:10:38.000,0:10:40.000
Passing by reference means it didn't really copy;

0:10:40.000,0:10:44.000
it just kinda used the copy that was out here by reference, so reaching

0:10:44.000,0:10:47.000
out and accessing it out of [inaudible].

0:10:47.000,0:10:51.000
So in here using the size to know how many elements are in the vector,

0:10:51.000,0:10:54.000
and then this is what's called an overloaded operator, that the

0:10:54.000,0:10:57.000
square brackets that you have seen in the past, user array access and the

0:10:57.000,0:10:59.000
languages you know,

0:10:59.000,0:11:01.000
can be applied to the vector,

0:11:01.000,0:11:05.000
and it uses the same sort of syntax that we put an integer in that tells you what index and

0:11:05.000,0:11:08.000
indices from zero to size minus one are the valid range for

0:11:08.000,0:11:12.000
the vector, and accessed that integer and printed it out.

0:11:12.000,0:11:15.000
So anything you would have done on any kind of array,

0:11:15.000,0:11:18.000
reading a bunch of contents from a file,

0:11:18.000,0:11:21.000
printing these things out, rearranging them into sorted order, inserting

0:11:21.000,0:11:22.000
something into sorted order,

0:11:22.000,0:11:24.000
all those things are

0:11:24.000,0:11:28.000
operations that work very cleanly when mapped onto what the vector provides. One

0:11:28.000,0:11:31.000
of the really nice things is unlike most array,

0:11:31.000,0:11:33.000
like the built in array of C++,

0:11:33.000,0:11:36.000
you don't have to know in advance how big the vector's gonna be, it just grows

0:11:36.000,0:11:37.000
on demand.

0:11:37.000,0:11:42.000
So if you were reading a bunch of numbers from a file, like you are in your assignment 1,

0:11:42.000,0:11:45.000
you don't have to have figured out ahead of time how many numbers will be there

0:11:45.000,0:11:48.000
so that I can allocate the storage and set it aside. You just keep calling

0:11:48.000,0:11:50.000
v.dot add on your vector,

0:11:50.000,0:11:51.000
and as needed it's just making space.

0:11:51.000,0:11:55.000
So if there's ten numbers in the file, there's a hundred, there's a million,

0:11:55.000,0:11:57.000
it will just make the space on demand

0:11:57.000,0: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

0:12:05.000,0:12:07.000
angle

0:12:07.000,0:12:11.000
brackets. Yeah, they turn the side

0:12:11.000,0:12:14.000
of it and then - no? No, no. The angle brackets are used in this case just for the vector

0:12:14.000,0:12:15.000
specialization.

0:12:15.000,0:12:18.000
The square brackets here are being used for -

0:12:18.000,0:12:23.000
I'm accessing a particular member out of the array by index. [Inaudible]

0:12:23.000,0:12:26.000
So yeah, what happens in - so if you look at make random vector,

0:12:26.000,0:12:30.000
it created an empty vector, so the typical usage [inaudible] is you create it empty

0:12:30.000,0:12:32.000
and then you add things to grow it.

0:12:32.000,0:12:36.000
So you actually never in here actually have to say how big it's going to be. It

0:12:36.000,0:12:38.000
just - on demand as I call

0:12:38.000,0:12:41.000
numbers.add, it got one bigger each time through that loop, and if I did that

0:12:41.000,0:12:44.000
100 times, that'll have a hundred entry vector.

0:12:44.000,0:12:45.000
So there isn't actually a mechanism where you say

0:12:45.000,0:12:48.000
make it a hundred in advance. You will add a hundred things; it will have length

0:12:48.000,0:12:50.000
a hundred,

0:12:50.000,0:12:53.000
if you inserted a hundred things. The add me insert both

0:12:53.000,0:12:58.000
cause the size of the vector to go up by one, remove caused to go down by one. [Inaudible] brackets

0:12:58.000,0:12:59.000
to

0:12:59.000,0:13:02.000
access a specific element and write to it

0:13:02.000,0:13:07.000
and it's not yet at the - will it automatically fill in [inaudible]? No, it will not, so

0:13:07.000,0:13:12.000
the sub - the square brackets can only access things that are in the vector already. So you can

0:13:12.000,0:13:15.000
overwrite it if it's there, but if you have a ten-member vector, and you go to

0:13:15.000,0:13:17.000
say V sub 20,

0:13:17.000,0:13:18.000
it will not sort of

0:13:18.000,0:13:21.000
invent the ten members in between there and make that space. So the things that are

0:13:21.000,0:13:24.000
valid to access to read from are the same ones that are valid to write to, so you

0:13:24.000,0:13:25.000
can use the square

0:13:25.000,0:13:29.000
bracket on either side of the assignment operator to read or to write, but it has

0:13:29.000,0:13:31.000
to still be something that's already in there. If you really want to put

0:13:31.000,0:13:34.000
a hundred zeros into it, then you need to write a loop that puts a hundred zeros into

0:13:34.000,0:13:36.000
it

0:13:36.000,0:13:39.000
using

0:13:39.000,0:13:40.000


0:13:40.000,0:13:44.000
add. Way in the back. [Inaudible] Only for efficiency in

0:13:44.000,0:13:47.000
this case. I'm not changing it, so if I

0:13:47.000,0:13:50.000
was planning on going in here and multiplying everything by two or something,

0:13:50.000,0:13:53.000
I would do that pass by reference to see those changes permanently affected. This

0:13:53.000,0:13:56.000
actually isn't making any changes to the vector, it's just reading the contents of it,

0:13:56.000,0:13:59.000
so it could be pass by value and have the same

0:13:59.000,0:14:03.000
effect, but I wouldn't see any change in the program, it would just run a little slower

0:14:03.000,0:14:04.000
if I did that.

0:14:04.000,0:14:07.000
We will typically though - you will see that kinda just by

0:14:07.000,0:14:09.000
habit we will almost always pass our

0:14:09.000,0:14:11.000
collections by reference,

0:14:11.000,0:14:14.000
because of the concern for efficiency in the long run.

0:14:14.000,0:14:17.000
So it - even though we don't plan on changing it,

0:14:17.000,0:14:21.000
we'll use that to save ourselves some

0:14:21.000,0:14:24.000
time. Anything about

0:14:24.000,0:14:28.000
vector?

0:14:28.000,0:14:29.000
[Inaudible]

0:14:29.000,0:14:32.000
The second to the last line before printing,

0:14:32.000,0:14:35.000
the one right here where I'm going the - so this is declaring vector [inaudible], so

0:14:35.000,0:14:37.000
making the new variable, and it's assigning it

0:14:37.000,0:14:41.000
the return value from calling the make random vector function. So it's actually

0:14:41.000,0:14:43.000
declaring and assigning it in one step

0:14:43.000,0:14:46.000
where that assignment caused a function to be called that stuffed it full of random

0:14:46.000,0:14:50.000
numbers and returned it. Ten in that case means what?

0:14:50.000,0:14:54.000
Ten in this case is just the size. It's the [inaudible]

0:14:54.000,0:14:56.000
make me a random vector containing ten values,

0:14:56.000,0:14:59.000
so that's - the ten in this case is just how many things to put in the array.

0:14:59.000,0:15:01.000
[Inaudible]

0:15:01.000,0:15:04.000
Well it will make ten random numbers and stick them into the

0:15:04.000,0:15:08.000
vector, so when you get back you'll have vector of size ten that has ten random

0:15:08.000,0:15:09.000
entries in it.

0:15:09.000,0: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,

0:15:13.000,0:15:14.000
so

0:15:14.000,0:15:17.000


0:15:17.000,0:15:19.000
a lower

0:15:19.000,0:15:27.000
case random.H, which is R cs1061. Okay. Now

0:15:27.000,0:15:29.000
let me

0:15:29.000,0:15:33.000
reinforce this idea that templates are type safe, and that if you misuse them

0:15:33.000,0:15:34.000


0:15:34.000,0:15:36.000
you will get errors from the complier

0:15:36.000,0:15:39.000
that help you to alert yourself to the mistakes that you've made. If I

0:15:39.000,0:15:41.000
make a vector

0:15:41.000,0:15:44.000
specialized to hold [inaudible] is really an integer vector, I make a vector

0:15:44.000,0:15:47.000
to hold strings I call words, that

0:15:47.000,0:15:51.000
I could add integers into the first one, I could add words to the second one, but I can't

0:15:51.000,0:15:54.000
cross those lines. If I try to take nums

0:15:54.000,0:15:55.000
and add to it the string banana,

0:15:55.000,0:15:57.000
it will not compile,

0:15:57.000,0:15:59.000
so it has a very strong notion of the

0:15:59.000,0:16:04.000
add operation on this kind of vector accepts this kind of thing. So if it's a

0:16:04.000,0:16:08.000
vector of strings, the add accepts strings. If it's a vector of [inaudible] add accepts integers,

0:16:08.000,0:16:11.000
and the crossing of that will cause compiler errors.

0:16:11.000,0:16:15.000
Similarly, when I'm trying to get something out of a vector,

0:16:15.000,0:16:19.000
that return value is typed for what you put in it. If you have a vector of

0:16:19.000,0:16:21.000
strings, then what you return is strings, not characters.

0:16:21.000,0:16:23.000
Or trying to do, kind of

0:16:23.000,0:16:26.000
take one vector; one vector is not equivalent to another if their base

0:16:26.000,0:16:29.000
types are not the same. So a vector of doubles

0:16:29.000,0:16:32.000
is not the same thing as a vector of integers. And so if I have a function

0:16:32.000,0:16:35.000
that expects one or tries to use on, it really [inaudible] a vector of in, a

0:16:35.000,0:16:38.000
vector of in is not the same thing as a vector of doubles,

0:16:38.000,0:16:41.000
and the complier will not let you kind of mix those things up.

0:16:41.000,0:16:43.000
So it provides pretty

0:16:43.000,0:16:44.000
good

0:16:44.000,0:16:47.000
error messages in these cases. It's a, here's

0:16:47.000,0:16:49.000
how you've gotten your types

0:16:49.000,0:16:53.000
confused.

0:16:53.000,0:16:56.000
[Inaudible] double bracket number and then -

0:16:56.000,0:16:59.000
Yeah, so if this said vector angle bracket [inaudible] then it would fine, then I would

0:16:59.000,0:17:02.000
just be making a copy of the nums into a new variable S that had a

0:17:02.000,0:17:04.000
complete same content that nums did.

0:17:04.000,0:17:07.000
So that would be totally fine. I can definitely do assignment from one vector to another if they

0:17:07.000,0:17:09.000
are of the same type,

0:17:09.000,0:17:12.000
but vector in is not the same thing as vector double which is not the same

0:17:12.000,0:17:14.000
thing as vector string, and so

0:17:14.000,0:17:16.000
it's - basically it means that -

0:17:16.000,0:17:19.000
what the template is, is a patter for which you can make a bunch of classes, and on demand

0:17:19.000,0:17:22.000
it makes new classes, the vector double, the vector in, the vector string. And each

0:17:22.000,0:17:26.000
of those is distinct from the other ones that have been created. Can I change the types of

0:17:26.000,0:17:27.000
nums in

0:17:27.000,0:17:28.000
the

0:17:28.000,0:17:30.000
expression and then - You cannot type [inaudible],

0:17:30.000,0:17:33.000
so it's not like I can type cast it down, they really are just different things and they're

0:17:33.000,0:17:36.000
stored differently, ints are a different size and doubles, so there's a bunch more things that

0:17:36.000,0:17:37.000
it

0:17:37.000,0:17:40.000
will just not do automatically in that case. If I really wanted to try to take a bunch of

0:17:40.000,0:17:44.000
integers and put them into a vector or doubles, I would end up

0:17:44.000,0: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.

0:17:48.000,0:17:50.000
Somebody in the back had something going on? Same question.

0:17:50.000,0:17:56.000
Same question, okay, so then we're good. Let me tell you a

0:17:56.000,0:17:57.000
little bit about grid,

0:17:57.000,0:18:00.000
which is just the extension of vector into two dimensions. Somebody asked

0:18:00.000,0:18:03.000
about this a minute ago, which is like, well can we do this? We can still [inaudible] vectors

0:18:03.000,0:18:04.000
of vectors

0:18:04.000,0:18:07.000
as one way of getting into two dimension, but often what you have is really a

0:18:07.000,0:18:11.000
rectangular region, where the number of rows and columns is fixed all the way

0:18:11.000,0:18:12.000
across,

0:18:12.000,0:18:15.000
in which case it might be convenient to have something like grid

0:18:15.000,0:18:18.000
that you just specify how big you want, how many rows, how many columns, and then

0:18:18.000,0:18:19.000
you get

0:18:19.000,0:18:20.000
a full

0:18:20.000,0:18:22.000
2D

0:18:22.000,0:18:24.000
matrix to hold those values.

0:18:24.000,0:18:27.000
So it is something that you set the dimensions of the constructors, you

0:18:27.000,0:18:28.000
make a new grid on int that

0:18:28.000,0:18:30.000
has ten rows and ten columns.

0:18:30.000,0:18:34.000
There actually is a number function resize that lets you later change the number of

0:18:34.000,0:18:37.000
rows and columns,

0:18:37.000,0:18:41.000
but typically you tend to actually - once you set it, it tends to stay that way.

0:18:41.000,0:18:47.000
You have access to each element by row and column, so you say I want the to getat

0:18:47.000,0:18:50.000
this row, this column, it will return you the value that's been stored there.

0:18:50.000,0:18:54.000
And I put it over here; it says elements have default [inaudible].

0:18:54.000,0:18:57.000
So if you say I want a ten by ten grid of integers,

0:18:57.000,0: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

0:19:01.000,0:19:03.000
those locations before you set them, they have

0:19:03.000,0:19:05.000
the same contents that

0:19:05.000,0:19:08.000
an integer declared of the stack would have, which is to say random.

0:19:08.000,0:19:10.000
So they're not zero, they're not negative one, they're not anything

0:19:10.000,0:19:13.000
special. They're whatever - kind of if you just have int setting around, what is its

0:19:13.000,0:19:15.000
default value?

0:19:15.000,0:19:18.000
For the primitive types that just means it's random. For some of the

0:19:18.000,0:19:21.000
more fancy types like string, it would mean they have the default value for

0:19:21.000,0:19:25.000
string, which is the empty string. So if I'm in a 2D grid of strings, then all the

0:19:25.000,0:19:29.000
strings would be empty until I explicitly did something to set and assign their

0:19:29.000,0:19:30.000
value.

0:19:30.000,0:19:33.000
So there's a getat setat pair that looks very much like the vector form that takes, in this

0:19:33.000,0:19:35.000
case, two arguments of the row and the column.

0:19:35.000,0:19:38.000
There's also an operator parens

0:19:38.000,0:19:43.000
that lets you say grid of parans, row column and separated by comma. I'll show that

0:19:43.000,0:19:44.000
syntax in just a second.

0:19:44.000,0:19:47.000
It does do full deep copying, the same way the vector does, which is if you

0:19:47.000,0:19:51.000
have a ten by ten grid which has a hundred members, when you pass or

0:19:51.000,0:19:56.000
return it by value, or you assign it, it has a full copy of that hundred member grid.

0:19:56.000,0:20:00.000
Lots of things sort of fit into the world of the grids

0:20:00.000,0:20:03.000
utility, any kind of game ward, you're doing battleship, you're doing a Sudoku, you're doing

0:20:03.000,0:20:06.000
a crossword puzzle,

0:20:06.000,0:20:08.000
designing a maze,

0:20:08.000,0:20:11.000
managing the data behind an image or any kind of mathematical matrix, or sort of table

0:20:11.000,0:20:16.000
tend to fit in the model for what a grid is good for.

0:20:16.000,0:20:19.000
This is the interface for grid,

0:20:19.000,0:20:21.000
so a template like vector was.

0:20:21.000,0:20:23.000
It has two different constructors;

0:20:23.000,0:20:29.000
one that is a little bit of an oddity. This one creates a zero row, zero

0:20:29.000,0:20:30.000
column

0:20:30.000,0:20:32.000
grids, totally empty,

0:20:32.000,0:20:34.000
which then you would later

0:20:34.000,0:20:38.000
most likely be making a resize call to change the number of rows and columns. That

0:20:38.000,0:20:41.000
might be useful in a situation where you need to create the grid before you kind of have information

0:20:41.000,0:20:43.000
about how to size it.

0:20:43.000,0:20:47.000
You can alternatively specify with a constructor the number of rows and

0:20:47.000,0:20:50.000
calls from the get go and have it set up,

0:20:50.000,0:20:52.000
and then you can later ask it for the number of rows and calls

0:20:52.000,0:20:55.000
and then you can getat and setat a

0:20:55.000,0:20:58.000
particular element within that grid

0:20:58.000,0:21:01.000
using those. There's also an operator - I'm not showing you the syntax in these for

0:21:01.000,0:21:04.000
the operator open parens, just because it's a little bit goopy, but I'll show you in the

0:21:04.000,0:21:07.000
client usage that

0:21:07.000,0:21:11.000
shows you how it works from that perspective.

0:21:11.000,0:21:14.000
So this is something let's say like maybe I'm playing a tic tac toe game and I

0:21:14.000,0:21:18.000
was gonna use the grid to hold the three by three board that has x's and

0:21:18.000,0:21:22.000
o's in it, and I want to start it off by having all of them have the space character.

0:21:22.000,0:21:24.000
So I'm going to using characters at each slot,

0:21:24.000,0:21:28.000
I create a board of three three, so this is the way you invoke a construction in

0:21:28.000,0:21:30.000
C++ that takes argument.

0:21:30.000,0:21:32.000
If you have no arguments, you don't have the parens or anything, you just have

0:21:32.000,0:21:37.000
the name, but if it does take one or more arguments, you'll open the paren and

0:21:37.000,0:21:40.000
list them out in order. In this case, the three and three being the number of rows and

0:21:40.000,0:21:41.000
columns.

0:21:41.000,0:21:42.000
And so at this point

0:21:42.000,0:21:44.000
I will have a

0:21:44.000,0:21:47.000
grid that has num rows three, num columns three, it has nine entries in it, and they're all

0:21:47.000,0:21:49.000
garbage.

0:21:49.000,0:21:51.000
Whatever characters that were left over in that place in memory is what actually

0:21:51.000,0:21:53.000
will be at each location.

0:21:53.000,0:21:56.000
And then I did a nested four loop over the rows and columns,

0:21:56.000,0:21:59.000
and here I am showing you the syntax for the

0:21:59.000,0:22:02.000
access to the row column in kind of a shorthand form

0:22:02.000,0:22:04.000
where I say board of

0:22:04.000,0:22:07.000
and then parens bro , column = space.

0:22:07.000,0:22:11.000
Equivalently that could have been the member function setat board. Setat

0:22:11.000,0:22:15.000
row column space to accomplish the same result.

0:22:15.000,0:22:17.000
So this is still like vector sub I,

0:22:17.000,0:22:20.000
it can be used to read or to write.

0:22:20.000,0:22:23.000
It does bounced checking to make sure that row and column are greater than or

0:22:23.000,0:22:26.000
equal to zero and less than the

0:22:26.000,0:22:28.000
number of rows or number of columns respectively.

0:22:28.000,0:22:32.000
So it raises an error if you ever get outside the bounds of the

0:22:32.000,0:22:35.000
grid. And then this return at the end just returns that full grid.

0:22:35.000,0:22:37.000
In this case, the nine

0:22:37.000,0:22:39.000
by entry, three by three

0:22:39.000,0:22:48.000
back to someone else who's gonna store it and so something with it.

0:22:48.000,0:22:50.000


0:22:50.000,0:22:51.000
[Inaudible]

0:22:51.000,0:22:55.000


0:22:55.000,0:22:58.000


0:22:58.000,0:23:01.000
There is actual one distinction between a vector and a vector of a grid that's kinda interesting,

0:23:01.000,0:23:04.000
the grid is rectangular, it forces there to be

0:23:04.000,0:23:07.000
exactly the same number of rows and column kind of for the whole thing. That

0:23:07.000,0:23:09.000
a vector - if you created a vector of vector,

0:23:09.000,0:23:13.000
you could individually size each row as needed. This could have ten, this

0:23:13.000,0:23:16.000
could have three, and so like a vector vector might be interesting if you

0:23:16.000,0:23:20.000
had something - well they call that kind of the ragged right behavior, where they

0:23:20.000,0:23:23.000
don't all line up over here. But if you really have something that's tabular,

0:23:23.000,0:23:26.000
that there is a rectangular shape to it, the grid is going to

0:23:26.000,0:23:28.000
be a little bit easier to get it up and running,

0:23:28.000,0:23:30.000
but the vector vector's certainly would work, but

0:23:30.000,0:23:32.000
if you were doing

0:23:32.000,0:23:34.000
an array of

0:23:34.000,0:23:38.000
class lists where some classes have ten and some classes have four hundred, but

0:23:38.000,0:23:41.000
if you tried to do that with a grid you'd have to size the whole thing to

0:23:41.000,0:23:48.000
have a much larger row dimension than was needed in most cases.

0:23:48.000,0:23:50.000
So there's no square bracket operator?

0:23:50.000,0:23:53.000
There is not, and there is kinda an obscure reason for that, and if you are curious,

0:23:53.000,0:23:56.000
you can come to the cafe afterwards, and I'll tell you why it is,

0:23:56.000,0:23:58.000
but

0:23:58.000,0:24:01.000
some of the syntax you may have seen in the past has two square brackets, you say sub

0:24:01.000,0:24:03.000
row, sub column,

0:24:03.000,0:24:07.000
and to have that work on a class in C++

0:24:07.000,0:24:08.000
doesn't - it's not as clean. So it

0:24:08.000,0:24:11.000
turns out we use the parens, because it turns out as a cleaner was of

0:24:11.000,0:24:14.000
accomplishing the thing we wanted, which was a short hand access into

0:24:14.000,0:24:15.000
there.

0:24:15.000,0:24:21.000
So it doesn't actually use the square bracket operator. Question here?

0:24:21.000,0:24:22.000
[Inaudible] when

0:24:22.000,0:24:25.000
you

0:24:25.000,0:24:27.000
created support three by three and you

0:24:27.000,0:24:32.000
said it was forced to be a square, so why would you ever have to

0:24:32.000,0: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

0:24:35.000,0:24:38.000
have three rows by ten columns, but

0:24:38.000,0:24:40.000
it does mean that every row has the same number of columns, but the row

0:24:40.000,0:24:44.000
and number of rows and columns doesn't have to be equal, I'm sorry. [Inaudible] if I made squares, the

0:24:44.000,0:24:52.000
wrong word really rectangular is it. So

0:24:52.000,0:24:54.000
then I'm gonna very quickly tell you these last two and they're actually even easier to

0:24:54.000,0:24:57.000
get your head around, because they're actually just simplified versions of

0:24:57.000,0:25:00.000
something you already know, which is to take the vector

0:25:00.000,0:25:02.000
and actually limit what you can do with it

0:25:02.000,0:25:05.000
to produce the stack in the queue class.

0:25:05.000,0:25:06.000
It

0:25:06.000,0:25:09.000
seems like kind of a strange thing to do if you already had a class that did something, why

0:25:09.000,0:25:12.000
would you want to dumb it down, but there actually are some good reasons that I'll hopefully

0:25:12.000,0:25:15.000
convince you of that why we have a stack and a queue.

0:25:15.000,0:25:17.000
So what a stack is about is modeling

0:25:17.000,0:25:21.000
the real world concept of a stack. If you have a stack of papers or a stack

0:25:21.000,0:25:22.000
of plates

0:25:22.000,0:25:24.000
you come and you put new things on the top of that

0:25:24.000,0: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

0:25:28.000,0:25:30.000
through the bottom of the stack, you don't reach over to the bottom. So if you

0:25:30.000,0:25:32.000
go up to get

0:25:32.000,0:25:33.000


0:25:33.000,0:25:36.000
a plate in the cafeteria you just take the one that's on the top. When they put new

0:25:36.000,0:25:38.000
clean ones they stick them on the top.

0:25:38.000,0:25:40.000
So this

0:25:40.000,0:25:45.000
could be - you could take a vector and model exactly that behavior where all the

0:25:45.000,0:25:49.000
edits to that - all the additions and remove operations have to happen on the

0:25:49.000,0:25:50.000
top or one end of the vector,

0:25:50.000,0:25:53.000
and that's basically what a stack does. Is

0:25:53.000,0:25:56.000
it provides something that looks like a vector

0:25:56.000,0:25:59.000
but that only allows you access to the top end of the stack.

0:25:59.000,0:26:01.000
It has the operation push

0:26:01.000,0:26:04.000
which is to say put a new thing on the top of the stack.

0:26:04.000,0:26:08.000
It has the operation pop, which is remove the top most element on the stack,

0:26:08.000,0:26:11.000
and there's actually a peak operation that looks at what's on the top without

0:26:11.000,0:26:12.000
removing it.

0:26:12.000,0:26:15.000
There is no access to anything further down.

0:26:15.000,0:26:18.000
If you want to see at the bottom or what's in the middle, the stack

0:26:18.000,0:26:22.000
doesn't let you do it. It gives a kind of a little window to look at this

0:26:22.000,0:26:23.000
information

0:26:23.000,0:26:25.000
that's restricted.

0:26:25.000,0:26:28.000
That seems a little bit strange,

0:26:28.000,0:26:31.000
why is it when you want - like sometimes you could do that with a

0:26:31.000,0:26:34.000
vector by always adding to the end and always forcing yourself to remove from the

0:26:34.000,0:26:34.000
end,

0:26:34.000,0:26:37.000
but then just ignoring the fact that you could dig through the other parts of the vector. And

0:26:37.000,0:26:38.000


0:26:38.000,0:26:41.000
there are a few really good reasons to have the stack around, because there are certain

0:26:41.000,0:26:44.000
things that really are stack based operations. A good example of is like if

0:26:44.000,0:26:46.000
you are

0:26:46.000,0:26:48.000
doing the web browser history

0:26:48.000,0:26:49.000
when you can walk forward,

0:26:49.000,0:26:51.000
but then you can back up.

0:26:51.000,0:26:54.000
You don't need to be able to jump all the way back to the end, you're just going back

0:26:54.000,0:26:57.000
in time. Or if you undoing the actions in a word processors, you type some things

0:26:57.000,0:26:58.000
and you undo it,

0:26:58.000,0:27:02.000
that you always undo the last most operations before you undo things before

0:27:02.000,0:27:05.000
that. And having it be a vector where you can kind of did through it means there's a chance

0:27:05.000,0:27:08.000
you could make a mistake. You could accidently pull from the wrong end or do

0:27:08.000,0:27:08.000
something

0:27:08.000,0:27:11.000
that you didn't intend. By having the stack it kinda forces you to use it the way

0:27:11.000,0:27:15.000
you said you planned on, which is I'm only going to stack on the end, I'm going to

0:27:15.000,0:27:17.000
remove from the end.

0:27:17.000,0:27:18.000
So it lets you model

0:27:18.000,0:27:22.000
this particular kind of limited access vector

0:27:22.000,0:27:23.000
in a way that

0:27:23.000,0:27:26.000
prevents you from making mistakes, and also very clearly indicates to someone reading

0:27:26.000,0:27:28.000
your code what you were doing.

0:27:28.000,0:27:31.000
So for example, stacks are very well known to all computer scientists. It's one of the

0:27:31.000,0:27:33.000
classic data structures.

0:27:33.000,0:27:36.000
We think of, for example, the function calls as a stack.

0:27:36.000,0:27:40.000
You call main which calls binky which calls winky, well winky comes back and

0:27:40.000,0:27:41.000
finishes, we get back to

0:27:41.000,0:27:45.000
the binky call, we go back to main, then it always goes in this last in, first out,

0:27:45.000,0:27:46.000
that

0:27:46.000,0:27:47.000
the last thing we started

0:27:47.000,0:27:51.000
is the first one to undo and go backwards to as we work our way back

0:27:51.000,0:27:53.000
down to the bottom of the stack.

0:27:53.000,0:27:56.000
And so computer scientists have a very strong notion of what a stack is. You declare

0:27:56.000,0:27:59.000
something as a stack and that immediately says to them, I see how you're

0:27:59.000,0:28:03.000
using this. You plan on adding to the end and removing from that same end.

0:28:03.000,0:28:06.000
So you can do things like reversal sequence very easily.

0:28:06.000,0:28:09.000
Put it all on the stack, pop it all off, it came back in the opposite order you put it on.

0:28:09.000,0:28:13.000
You put ABC on you'll get CBA off. If I put

0:28:13.000,0:28:16.000
5 3 12 on, I'll get 12 3 5 off. So anytime I needed to do a

0:28:16.000,0:28:19.000
reversing thing, a stack is a great place to just temporarily throw it and then

0:28:19.000,0:28:21.000
pull it back out.

0:28:21.000,0:28:25.000
Managing any sequence of [inaudible] action, the moves and again, the keystrokes in your

0:28:25.000,0:28:27.000
edits you've made in the

0:28:27.000,0:28:30.000
word processor, tracking the history when your web browsing of where

0:28:30.000,0:28:32.000
you've been and where you want to back up to

0:28:32.000,0:28:36.000
are all stack based activities.

0:28:36.000,0:28:39.000
So if you look at stack, it actually has an even simpler interface than vector for

0:28:39.000,0:28:41.000
that matter.

0:28:41.000,0:28:45.000
It has the corresponding size n is empty, so you'll see a lot of repetition

0:28:45.000,0:28:49.000
throughout the interface where we could reuse names that you already know

0:28:49.000,0:28:52.000
and have meaning for, we just reproduce them

0:28:52.000,0:28:55.000
from class to class, so there's a size that tells you how many things are on the

0:28:55.000,0:28:58.000
stack, and is empty, that tells you whether the size is zero,

0:28:58.000,0:29:01.000
and then the push and pop operations that add something

0:29:01.000,0:29:02.000
and remove it.

0:29:02.000,0: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

0:29:05.000,0:29:08.000
stack, and then that peak that lets you look at what's on the top without

0:29:08.000,0:29:15.000
removing it.

0:29:15.000,0:29:18.000
Yeah? So if you

0:29:18.000,0:29:19.000
[inaudible] that had

0:29:19.000,0: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

0:29:22.000,0:29:24.000
designing our interface was give you a simple

0:29:24.000,0:29:27.000
model you can follow, but also if you step out of the boundaries of what we

0:29:27.000,0:29:28.000
know to be acceptable,

0:29:28.000,0:29:33.000
we really stop hard and fast. So if you try to pop from an empty stacker, peak at an

0:29:33.000,0:29:35.000
empty stack, it will print and error and halt your program. It

0:29:35.000,0:29:42.000
won't make it up, it won't guess, it won't - [Inaudible]

0:29:42.000,0:29:46.000
Well, so the stack knows its size and it [inaudible] is empty,

0:29:46.000,0:29:50.000
so when you're unloading a stack you'll typically be in a loop like, well the

0:29:50.000,0:29:52.000
stacks not empty, pop.

0:29:52.000,0:29:54.000
So there's definitely ways you can check ahead of time to know whether there is something

0:29:54.000,0:29:56.000
there or not, and

0:29:56.000,0:29:58.000
it's all managed as part of the stack.

0:29:58.000,0:30:01.000
But if you blow it and you try to reach into the stack that's empty,

0:30:01.000,0:30:02.000


0:30:02.000,0:30:03.000
it won't let you get away with it.

0:30:03.000,0:30:07.000
And that's really what you want. That means that they run a little slower

0:30:07.000,0:30:10.000
than the counterparts in the standard library, but

0:30:10.000,0:30:13.000
they never let you make that kind of mistake without

0:30:13.000,0:30:16.000
alerting you to it, where as the standard library will actually respond a little

0:30:16.000,0:30:19.000
bit less graciously. It would be more likely to just make it up.

0:30:19.000,0:30:20.000
You tell it to pop

0:30:20.000,0:30:22.000
and the

0:30:22.000,0:30:22.000
contract is, yeah,

0:30:22.000,0:30:27.000
I'll return you something if I feel like it and it may be what - it may

0:30:27.000,0:30:29.000
be something that actually misleads you into thinking there was some valid contents

0:30:29.000,0:30:33.000
on the stack and causes the error to kinda propagate further before you realize

0:30:33.000,0:30:35.000
how far you've

0:30:35.000,0:30:39.000
come from what its real genesis was. So one of the nice things about reporting the error

0:30:39.000,0:30:40.000
at the first

0:30:40.000,0:30:45.000
glance is it gives you the best information about how to fix it.

0:30:45.000,0:30:48.000
So here's something that just uses the stack to invert

0:30:48.000,0:30:48.000


0:30:48.000,0:30:50.000
a string in this case, right,

0:30:50.000,0:30:53.000
something a user typed in. So I

0:30:53.000,0:30:56.000
prompted for them to enter something for me, I get that line

0:30:56.000,0:30:58.000
and then I create a stack of characters.

0:30:58.000,0:31:02.000
So the stack in this case is being created empty and then I take each

0:31:02.000,0:31:03.000
character one by

0:31:03.000,0:31:07.000
one from the first to the last and push it onto the stack, and so if they

0:31:07.000,0:31:07.000
answered

0:31:07.000,0:31:10.000
Hello, then we would put H-E-L-L-O on the stack.

0:31:10.000,0:31:12.000
And then print it backwards,

0:31:12.000,0:31:16.000
well the stack is not empty I pop and print it back out, so I'll get

0:31:16.000,0:31:16.000


0:31:16.000,0:31:18.000
O-L-L-E-H back out of that

0:31:18.000,0:31:20.000
and the loop will exit when it has emptied the

0:31:20.000,0:31:26.000
stack completely.

0:31:26.000,0:31:30.000


0:31:30.000,0:31:32.000
Stack [inaudible] just is

0:31:32.000,0:31:34.000
a simpler form of that. The

0:31:34.000,0:31:37.000
queue is just the cousin of the stack.

0:31:37.000,0:31:39.000
Same sort of idea is that

0:31:39.000,0:31:42.000
there's certain usage patterns for a vector

0:31:42.000,0:31:47.000
that form kind of their own class that's worth kinda giving a

0:31:47.000,0:31:50.000
name to and building an abstraction around, the queue.

0:31:50.000,0:31:54.000
The queue instead of being last in first out is first in first out. So the first

0:31:54.000,0:31:56.000
thing you add into the queue

0:31:56.000,0:32:00.000
is going to be the first one you remove. So you add at the front - you

0:32:00.000,0:32:03.000
add at the back and you remove from the front, it models a waiting line.

0:32:03.000,0:32:07.000
So if you think of lets say the head of the queue and tail,

0:32:07.000,0:32:11.000
or the front or the back of the line, that A was placed in the queue first,

0:32:11.000,0:32:13.000
that operation's called n queue;

0:32:13.000,0:32:16.000
n queue A, n queue B, n queue C, n queue D,

0:32:16.000,0:32:21.000
and then when you d queue, which is the remove operation on a queue, it will pull the

0:32:21.000,0:32:22.000
oldest thing in the queue, the one that was there

0:32:22.000,0:32:24.000
first who's been waiting the longest.

0:32:24.000,0:32:30.000
So removing the A and then next d queue will give you that B and so on. So

0:32:30.000,0:32:33.000
it does what you think of as your classic waiting line.

0:32:33.000,0:32:35.000
You're at the bank waiting for a teller.

0:32:35.000,0:32:38.000
The keystrokes that you're typing are being likely stored in something

0:32:38.000,0:32:42.000
that's queue like, setting up the jobs for a printer so that

0:32:42.000,0:32:45.000
there's fair access to it, where first come, first served,

0:32:45.000,0:32:48.000
and there's a couple kind of search [inaudible] that actually tend to use queue

0:32:48.000,0:32:51.000
as the way to kind of keep track of where you are.

0:32:51.000,0:32:54.000
So again, I could use vector for this,

0:32:54.000,0:32:58.000
just making a deal with myself that I'll add at one end and I'll always remove the zero with

0:32:58.000,0:32:59.000
element,

0:32:59.000,0:33:00.000
but again,

0:33:00.000,0:33:03.000
the effect is that if somebody sees me using a vector,

0:33:03.000,0:33:06.000
that they'd have to look at the code more closely

0:33:06.000,0:33:10.000
to see all my access to it, when I add, and when I remove to verify that I was

0:33:10.000,0:33:12.000
using it in a queue like manner, that I always

0:33:12.000,0:33:14.000
add it to the back an remove from the front.

0:33:14.000,0:33:16.000
If I say it's a queue,

0:33:16.000,0:33:20.000
they know that there is no other access than the n queue d queue

0:33:20.000,0:33:23.000
that operates using this FIFO, first in, first

0:33:23.000,0:33:25.000
out control,

0:33:25.000,0:33:29.000
so they don't have to look any closer at my usage of it to know what I'm up to.

0:33:29.000,0:33:32.000
The other thing that both stack and queue have which

0:33:32.000,0:33:34.000
won't be apparent now, but will

0:33:34.000,0:33:36.000
when we get a little further in the course,

0:33:36.000,0:33:37.000
is that by

0:33:37.000,0:33:40.000
defining the queue extraction to have kind of less features,

0:33:40.000,0:33:43.000
to be what seems to be less powerful

0:33:43.000,0:33:47.000
and have sort of a smaller set of things it has to support,

0:33:47.000,0:33:50.000
also has some certain advantages from the implementation side. That

0:33:50.000,0:33:53.000
if I know somebody's always going to be sticking things on this end and that end, but

0:33:53.000,0:33:55.000
not mucking around in the middle,

0:33:55.000,0:33:58.000
then I can make certain implementation decisions that support the necessary

0:33:58.000,0:34:00.000
operations very efficiently,

0:34:00.000,0:34:03.000
but don't actually do these things well because they don't need to,

0:34:03.000,0:34:06.000
in a way that vector can't make those trade offs. Vector doesn't know for sure

0:34:06.000,0:34:09.000
whether people will be mucking around with the middle or the ends or

0:34:09.000,0:34:10.000
the front or the back,

0:34:10.000,0:34:13.000
and so it has to kinda support everything equally well, that stack and

0:34:13.000,0:34:17.000
queue has a really specific usage pattern that then we can

0:34:17.000,0:34:20.000
use to guide our implementation decisions to make sure it runs

0:34:20.000,0:34:23.000
efficiently for that usage pattern.

0:34:23.000,0:34:27.000
So the same constructor or destructor in size is empty, that kind of

0:34:27.000,0:34:28.000
all our linear collections to,

0:34:28.000,0:34:32.000
and then it's operations which look just like push and pop but with a slight

0:34:32.000,0:34:36.000
change in verb here, n queue and d queue,

0:34:36.000,0:34:39.000
that add to the back, remove from the front,

0:34:39.000,0:34:40.000
and then peak

0:34:40.000,0:34:43.000
is the corresponding look at what's in the front. Like what would be d queued,

0:34:43.000,0:34:51.000
but without removing it from the queue, so just see who's at the head of the line.

0:34:51.000,0:34:54.000
And so a little piece of code I stole from the handout

0:34:54.000,0:34:56.000
which

0:34:56.000,0:34:59.000
sort of modeled a very, very simple sort of like if you're getting access to

0:34:59.000,0:35:00.000
the layer and you're getting help,

0:35:00.000,0:35:01.000


0:35:01.000,0:35:05.000
that you might ask the user, to kinda say well what do you want to do next, do you

0:35:05.000,0:35:09.000
want to add somebody to the line or do you wanna service the next customer, and so we

0:35:09.000,0:35:11.000
have this way of getting their answer.

0:35:11.000,0:35:15.000
And if they said, okay, it's time to service the next customer then we d queue and answer

0:35:15.000,0:35:17.000
the question of the first person in the queue which will be the one who's been there

0:35:17.000,0:35:20.000
the longest, waiting the longest. And

0:35:20.000,0:35:23.000
if their answer was not next, we'll assume it was a name of somebody

0:35:23.000,0:35:26.000
just stick onto the queue, so that actually adds things to the queue.

0:35:26.000,0:35:29.000
So as we would go around in this loop it would continue kind of stacking things up on

0:35:29.000,0:35:31.000
the queue

0:35:31.000,0:35:33.000
until

0:35:33.000,0:35:36.000
the response was next and then it would start pulling them off and then we could go back

0:35:36.000,0:35:40.000
to adding more and whatnot, and at any given point the queue will have the name of

0:35:40.000,0:35:41.000
all the

0:35:41.000,0:35:43.000
in-queued

0:35:43.000,0:35:44.000
waiting questions

0:35:44.000,0:35:46.000
that haven't yet been handled,

0:35:46.000,0:35:49.000
and they will be pulled off oldest first,

0:35:49.000,0:35:51.000
which is the fair way to have

0:35:51.000,0:35:55.000
access in a waiting line.

0:35:55.000,0:35:57.000
So

0:35:57.000,0:35:59.000
just the -

0:35:59.000,0:36:04.000
very similar to the stack, but they - LIFO versus FIFO

0:36:04.000,0:36:07.000
managing to

0:36:07.000,0:36:14.000
come in and come out in slightly different ways. So once you

0:36:14.000,0:36:16.000
have kind of these four guys, right,

0:36:16.000,0:36:18.000
you have what are called the

0:36:18.000,0:36:20.000
sequential containers kind of at your disposal.

0:36:20.000,0:36:26.000
Most things actually just need one of those things. You need a stack of

0:36:26.000,0:36:30.000
keystrokes, right, or actions or web pages you visited; you need a queue of

0:36:30.000,0:36:34.000
jobs being queued up for the printer. You need a vector of students who are in a class,

0:36:34.000,0:36:38.000
you need a vector of scores on a particular exam,

0:36:38.000,0:36:41.000
but there's nothing to stop you from kind of combining them in new ways to

0:36:41.000,0:36:44.000
build even fancier things out of those building blocks,

0:36:44.000,0:36:47.000
that each of them is useful in it's own right, and you can actually kind of mash them

0:36:47.000,0:36:48.000
together to

0:36:48.000,0:36:50.000
create even fancier things.

0:36:50.000,0:36:55.000
So like I can have a vector of queue of strings that modeled the checkout lines

0:36:55.000,0:36:59.000
in a supermarket, where each checkout stand has it's own queue of waiting people,

0:36:59.000,0:37:01.000
but that there's a whole vector of them from

0:37:01.000,0:37:05.000
the five or ten checkout stands that I have, and so I can find out which

0:37:05.000,0:37:06.000
one is the

0:37:06.000,0:37:07.000
shortest line

0:37:07.000,0:37:09.000
by iterating over that vector

0:37:09.000,0:37:14.000
and then asking each queue what's your size the find out which is the shortest line

0:37:14.000,0:37:18.000
there, and picking that for the place to line up with my cart.

0:37:18.000,0:37:19.000


0:37:19.000,0:37:22.000
If I were building a game, lets say, where there was a game board that was

0:37:22.000,0:37:23.000
some grid,

0:37:23.000,0:37:27.000
and that part of the features of this game which you could stack things

0:37:27.000,0:37:29.000
on top of each location,

0:37:29.000,0:37:33.000
then one way to model that would be a grid where each of the elements was a

0:37:33.000,0:37:36.000
stack itself of strings. So maybe I'm putting letters down

0:37:36.000,0:37:39.000
on a particular square of the board, and I can later cover that letter with

0:37:39.000,0:37:41.000
another letter and so on,

0:37:41.000,0:37:44.000
and so if I want to know what is the particular letter showing at any

0:37:44.000,0:37:45.000
particular grid location,

0:37:45.000,0:37:49.000
I can dig out the row column location, pull that stack out and then peek at what's on

0:37:49.000,0:37:51.000
the top. I won't be

0:37:51.000,0:37:53.000
able to see things that are underneath, and that might be exactly need in this

0:37:53.000,0:37:56.000
game, is that you can only see the things in top,

0:37:56.000,0:38:00.000
the things underneath are irrelevant, until maybe you pop them and they are exposed.

0:38:00.000,0:38:03.000
So we just layer them on top of each other, we can make them as deep as we

0:38:03.000,0:38:07.000
need to. It's not often they need to go past probably two levels, but you can build

0:38:07.000,0:38:10.000
vectors of vectors of vectors and vectors of queues of stacks of grids and

0:38:10.000,0:38:13.000
whatever you need to kind of get the job done.

0:38:13.000,0:38:16.000
There's one little C++ quirk

0:38:16.000,0:38:18.000
that I'm gonna mention while I'm there,

0:38:18.000,0:38:22.000
which is that the vector of queue of string actually has a closer -

0:38:22.000,0:38:26.000
a pair of those closing angle brackets that are neighbors there,

0:38:26.000,0:38:29.000
where I said I have a queue of string, and that I'm enclosing that to be the element

0:38:29.000,0:38:30.000
stored in a vector,

0:38:30.000,0:38:34.000
that if I put these two right next to each other,

0:38:34.000,0:38:37.000
which would be a natural thing to do when I was typing it out,

0:38:37.000,0:38:41.000
that causes the compiler to misunderstand what we want.

0:38:41.000,0:38:43.000
It will lead the

0:38:43.000,0:38:44.000
grid stack

0:38:44.000,0:38:45.000
string,

0:38:45.000,0:38:49.000
and then when it sees the string, the next thing coming up will be these two greater

0:38:49.000,0:38:52.000
than signs. It will read them together,

0:38:52.000,0:38:57.000
so it effect tokenizing it as oh, these next two things go together,

0:38:57.000,0:38:59.000
and they are the stream extraction operator,

0:38:59.000,0:39:01.000
and then it just all

0:39:01.000,0:39:04.000
haywire - goes haywire from there. I think that you're about - you were in the

0:39:04.000,0: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?

0:39:09.000,0:39:11.000
Sad, but true,

0:39:11.000,0:39:14.000
and it will produce an error message, which depending on your compiler is more or

0:39:14.000,0:39:18.000
less helpful. The one is X-code is pretty nice, it actually says,

0:39:18.000,0:39:22.000
closing template, there needs to be a space between it.

0:39:22.000,0:39:25.000
The one in visual studio is not quite as helpful, but it's

0:39:25.000,0:39:27.000
just something you need to learn to look for, is that you do actually have

0:39:27.000,0:39:28.000
to

0:39:28.000,0:39:33.000
plant that extra space in there so that it will read the closer for one, and then

0:39:33.000,0:39:35.000
the second closer without

0:39:35.000,0:39:37.000
mingling them together.

0:39:37.000,0:39:40.000
There is an on deck proposal which shows you that C++ is a live

0:39:40.000,0:39:41.000
language, it's

0:39:41.000,0:39:43.000
evolving as we speak, but in the

0:39:43.000,0:39:47.000
revision of C++ as being planned, they actually want to fix this

0:39:47.000,0:39:49.000
so that actually it will be fine to use them

0:39:49.000,0:39:52.000
without the space and the right thing will happen,

0:39:52.000,0:39:55.000
and by changing it in the standard, it means the compiler writers will eventually kind of

0:39:55.000,0:40:00.000
join to be spec compliant, will actually have to change their compilers

0:40:00.000,0:40:02.000
to handle it properly, where as they now have

0:40:02.000,0:40:04.000
little incentive to do so. And

0:40:04.000,0:40:08.000
then I just put a little note here that as you get to these more complicated things there

0:40:08.000,0:40:09.000


0:40:09.000,0:40:13.000
might be some more appeal to using typedef, which is a C++ way of

0:40:13.000,0:40:16.000
[inaudible] shorthand.

0:40:16.000,0:40:19.000
You can actually do this for any type in C++. The typing,

0:40:19.000,0:40:22.000
if you were typically something it would go up at the top of the program.

0:40:22.000,0:40:25.000
I say typedef and then I give the long name

0:40:25.000,0:40:28.000
and then I give the new short name, the nickname I'd like to give to it. So I can

0:40:28.000,0:40:32.000
say typedef into banana and then all through my program use banana as though

0:40:32.000,0:40:33.000
it were an int.

0:40:33.000,0:40:37.000
Okay, probably not that motivating in that situation, but when you have a

0:40:37.000,0:40:40.000
type name that's somehow long and complicated and a little bit awkward to reproduce throughout

0:40:40.000,0:40:42.000
your program, you can

0:40:42.000,0:40:45.000
put that type name in place and use the shorthand name to kind of add clarity

0:40:45.000,0:40:48.000
later. So maybe I'm using this to be

0:40:48.000,0:40:49.000


0:40:49.000,0:40:51.000
some information about my calendar,

0:40:51.000,0:40:53.000
where I have the

0:40:53.000,0:40:57.000
months divided into days or days divided into hours, so having kinda of a two

0:40:57.000,0:40:59.000
layer vector here,

0:40:59.000,0:41:03.000
that rather than having vector of vector of ints all over the place I can us calendar T

0:41:03.000,0:41:05.000
to be a synonym for that

0:41:05.000,0:41:09.000
once I've made that declaration.

0:41:09.000,0:41:13.000
Let me show you just a couple of things back in the compiler space before

0:41:13.000,0:41:19.000
I let you guys run away to go skiing. One of the

0:41:19.000,0:41:23.000
things that you're likely to be working on in this case is that you're

0:41:23.000,0:41:24.000
learning a new

0:41:24.000,0:41:28.000
API, API is called Application Programming Interface,

0:41:28.000,0:41:31.000
it's the way you interact with the libraries, knowing what routine does what and what

0:41:31.000,0:41:33.000
it's name is and what it's arguments are,

0:41:33.000,0:41:36.000
and that's likely to be one of the things that's a little bit more of a

0:41:36.000,0:41:40.000
sticking point early on here, is just kind of saying, oh I know this exists in a

0:41:40.000,0:41:43.000
random library, but what's the name of the function, is it random numbers, is it random

0:41:43.000,0:41:45.000
integers, is it random it? And

0:41:45.000,0:41:46.000


0:41:46.000,0:41:49.000
being familiar with the ways you kind find out this information. So let me

0:41:49.000,0:41:53.000
just give you a little hint about this; one is that you can open the header

0:41:53.000,0:41:56.000
files, so I just opened in this case, the grid.h header file,

0:41:56.000,0:42:00.000
and I can look at it and see what it says. It says, oh, here's some information, it actually has

0:42:00.000,0:42:01.000
some sample code here,

0:42:01.000,0:42:05.000
and as I scroll down

0:42:05.000,0:42:09.000
it'll tell me about what the class is, and then it has comma's on each of the

0:42:09.000,0:42:11.000
constructor and

0:42:11.000,0:42:12.000


0:42:12.000,0:42:15.000
member function calls that tells me how it works and what errors it raises and

0:42:15.000,0:42:19.000
what I need to know to be able to use this call correctly. And so

0:42:19.000,0:42:23.000
for any of our libraries, opening the header file is likely to be an

0:42:23.000,0:42:26.000
illuminating experience.

0:42:26.000,0:42:29.000
We try to write them for humans to read, so they actually do have

0:42:29.000,0:42:31.000


0:42:31.000,0:42:33.000
some

0:42:33.000,0:42:37.000
helpfulness. If you go to open a standard header file,

0:42:37.000,0:42:42.000
they're not quite as useful. For example, let's go look at I stream

0:42:42.000,0:42:44.000
and keep going.

0:42:44.000,0:42:45.000
You'll get

0:42:45.000,0: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

0:42:49.000,0:42:51.000
then there's a bunch of typedef's

0:42:51.000,0:42:55.000
and then it gets down to here, there's a little bit of information that tells

0:42:55.000,0:42:56.000
you about

0:42:56.000,0:42:58.000
what the constructor might do and stuff.

0:42:58.000,0:43:03.000
You can read this, but it's not - it doesn't tend to be actually

0:43:03.000,0:43:05.000
targeted at getting the novice up to speed about what's going on. There is

0:43:05.000,0:43:07.000
some information here, but

0:43:07.000,0:43:10.000
in those cases you may be better of using one of our references, going back

0:43:10.000,0:43:11.000
to the reader,

0:43:11.000,0:43:13.000
or looking at

0:43:13.000,0:43:16.000
one of the websites that we give a point or two on the reference handout that

0:43:16.000,0:43:16.000
just kind of

0:43:16.000,0:43:18.000
tries to extract the

0:43:18.000,0:43:20.000


0:43:20.000,0:43:22.000
information you need to know as a client rather than trying to go look in here, because once you

0:43:22.000,0:43:25.000
get in here, oh what is gettake, and it's like what is all this stuff with these underbars

0:43:25.000,0:43:28.000
and stuff, it's not the best place to learn the interface, I think, from their

0:43:28.000,0:43:30.000
header files.

0:43:30.000,0:43:31.000
The other place that

0:43:31.000,0:43:34.000
I will note that we have is up here on the website

0:43:34.000,0:43:38.000
there is a documentation link, let me show you where I got to that just to remind you,

0:43:38.000,0:43:42.000
is up here in the top,

0:43:42.000,0:43:43.000
over on this side,

0:43:43.000,0:43:47.000
and what this is, is actually this is our header files having been run through

0:43:47.000,0:43:49.000
something that generates a webpage from them, so it has the same information

0:43:49.000,0:43:52.000
available in the header files, but it's just organized in a

0:43:52.000,0:43:55.000
clickable browsable way to get to things.

0:43:55.000,0:43:56.000
And so if you

0:43:56.000,0:44:00.000
dink this down and you look at the class list, you can say, yeah, tell me about queue, I'd like

0:44:00.000,0:44:04.000
to know more about it and then it'll give you the public member function. This

0:44:04.000,0:44:06.000
projector's really very

0:44:06.000,0:44:09.000
fuzzy, I wonder if someone can sharpen that,

0:44:09.000,0:44:10.000


0:44:10.000,0:44:13.000
that tells you that here's the constructor, here's the n queue d queue peak,

0:44:13.000,0:44:16.000
there's a clear operator that empties the whole thing and then there's some other

0:44:16.000,0:44:20.000
operations that are involved with the deep copying that are actually explicitly named out.

0:44:20.000,0:44:23.000
And then if you go down, you can say, well tell me more about n queue,

0:44:23.000,0:44:27.000
you can come down here, it'll tell you the documentation we had that's

0:44:27.000,0:44:30.000
been extracted from the header files tells you about what the arguments are, what their

0:44:30.000,0:44:31.000
turn value is,

0:44:31.000,0:44:32.000


0:44:32.000,0:44:34.000
what things you need to know to use that properly.

0:44:34.000,0:44:37.000
And so you'll probably find yourself using one or both of these, like going and actually

0:44:37.000,0:44:41.000
reading the header files or reading the kind of cleaned up pretty printed header files

0:44:41.000,0:44:43.000
just to get familiar with what those interfaces are, what the names are, and

0:44:43.000,0:44:45.000
how you call them

0:44:45.000,0:44:46.000
so

0:44:46.000,0:44:48.000
that when you're working you know, and have a web browser kind of up

0:44:48.000,0:44:52.000
aside to help you navigate that stuff

0:44:52.000,0:44:54.000
without too much guess work.

0:44:54.000,0:44:56.000
And so I just wanted to

0:44:56.000,0:44:58.000
show you that before I let you go.

0:44:58.000,0:45:00.000
Anybody questions about that? Hopefully you should feel a

0:45:00.000,0:45:01.000
little bit like, hey,

0:45:01.000,0:45:05.000
that starts to be useful. By Wednesday I'll show you map and set and

0:45:05.000,0:45:08.000
then you'll realize there's a lot of really cool things you can do with all these

0:45:08.000,0:45:09.000
objects around in your arsenal.

0:45:09.000,0:45:11.000
So have a good weekend,

0:45:11.000,0:45:12.000
enjoy the holiday,

0:45:12.000,0:45:13.000
come to Truman,

0:45:13.000,0:45:17.000
I'll see you on Wednesday.