Lecture 5 | Programming Abstractions (Stanford)

Lecture 5 by Julie Zelenski for the Programming Abstractions Course (CS106B) in the Stanford Computer Science Department. In the fifth lecture,

Julie discusses the use of templates, vectors and template specialization. She then goes through an example of code line by line explaining each part in detail. Finally, she goes on to explain what grid interfaces are and briefly goes over how you can use them in programming different games.

Complete Playlist for the Course:
http://www.youtube.com/view_play_list?p=FE6E58F856038C69

CS 106B Course Website:
http://cs106b.stanford.edu

Stanford Center for Professional Development:
http://scpd.stanford.edu/

Stanford University:
http://www.stanford.edu/

Stanford University Channel on YouTube:
http://www.youtube.com/stanforduniversity/

This presentation is delivered by the Stanford Center for Professional Development.

Okay, anything administratively you'd like to ask about? How many people

have completed assignment 1, and done the whole thing?

All right, you get a gold star. All right,

you guys want to be him, is what it is, because this guys is getting to go skiing guilt free. You

guys if you're going skiing won't be guilt free, and

you'll be working late to finish it off, and he

is sleeping easy.

How many people have at least one or two of the problems done?

Okay, that's a good number.

We're still making progress.

So I had just started to talk a little about this idea of a template,

which is the C++ equivalent of the Java generic,

and I

want to refresh on the rules about how do you use a template. The thing about templates

is they're a very useful and practical

component to have in the language,

but they do have a little bit of issues with resolve to when you make mistakes

with them, kinda having it reported and how you learn about them, and so they can be a

little bit of a tripping point despite their vast utility.

Let me just remind you about what it means to use a template; is that you use

include the interface file as usual. We're trying to use a vector to hold some

sequence of things, so we include the vector.H.

The name vector

by itself without specialization doesn't tell the compiler everything

it needs to know. When you're trying to

[inaudible] declare a vector, pass a vector as a parameter, return one, and any

of those situations where you would have wanted to say it's a vector, you have to

say what kind of vector, it's a vector holding character, it's a vector holding

location T's, it's

a vector holding

doubles.

And that just applies everywhere you use the name vector, the name vector by itself

doesn't mean anything. It always has to have this qualification or specialization on

it.

And then once that you've committed that to the compiler, the

vector from that point really behaves in a type safe manner. A vector

character is not the same thing as a vector holding doubles. The

compiler keeps those things separate. It doesn't let you co-mingle them.

If you expect a vector of care, and you say that as your parameter,

then you will have to pass one that has the same element type in it,

that passing a vector double is not this same thing, and so trying to put a double

into a vector of characters or

retrieve an integer out of one that's holding

student structures, is going to give you compiler errors, which is really

a nice feature for maintaining type safety.

So the vector class I had just started talking about, and I'm gonna just kinda pick up

and review the things we had started to talk about on Wednesday and go through

it,

which is what is the vector good for?

The vector is good for any

collection of things. You need to store a list is kind of the

abstraction that it's trying to model. I have a list of students in this class, I have

a list of problems that are being assigned, I have

a list of classes I'm taking this quarter, you know, whatever those things

are, a list of scores on an exam,

and the vector

manages the needs of all of those kinds of lists. You say what kind of thing

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

homogeneous, that all the elements are double or they're all students. You

can't have doubles and students co-mingle.

It's linear in the effect that it kinda lays them out in a line. It indexes them from zero

to the size minus 1.

Each one has a place in the line and there are no gaps in it, so it actually is

sequenced out.

And it doesn't - a lot of things that make for a really convenient handling of the

list as an abstraction, it knows its size at all time. You can ask it what the

size is, it'll tell me how your elements have been stored in it. Now

if you ask for an element by index it bounds checks to make sure that you

gave it a valid index for the range of size that it's currently holding.

It handles all the storage for you. If

you put ten elements and to put an eleventh, if it doesn't have space it goes

and makes space for you. This all happens without you doing anything explicit, so

as you add things, as you remove things, it handles sizing and

changing whatever internal storage needs as needed to accommodate what you asked

you.

It has convenient operations for inserting and removing; where you want to put

something in a slot, it will move everything over to make space for it or to shuffle it down to

close over that space.

It also does what we call a deep copy; a

deep copy is

sort of a CS term for if I have a vector holding ten numbers,

and I assign that to another vector,

it really does make a new vector that has the same ten numbers. That deep copy means

it's more than some sort of shallow, like they're sharing something. They really are

creating a clone of it, so taking that same - however big that vector is, whether it

has a hundred or a thousand or two entries,

it makes a whole copy, a parallel copy that has

the same size and the same entries

that was based on taking the original input and reproducing it in a new vector.

And that happens when you do assignment from one vector to another, it happens

when you do a cast by value of a vector into a function that takes a vector by

value,

or when you return a vector from a function, so in all those cases it's doing kinda

a full deep copy

that

is unlike those of you had a little experience working with a built in

array, know that it doesn't have those behaviors, and that comes as a little bit of

a surprise. The vector behaves just like the primitives in the sense that

there's no special

knowledge you need to know about how it's -

the assignment affects other copies of the same vector.

So your typical usage is you create an empty vector, you add a new insert;

remove to kind of jostle of the contents. You can access the elements

once they're in there using member function setat and getat that allow you to

change the value of the location, or get the value.

There's also an operator bracket. We'll see how you can actually just use the

syntax of the vector name and then the bracket with the index to access a

particular element,

useful for all

sorts of things.

Question here?

Student:Yeah, can you make a multi-dimensional vector? Instructor

(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

already built,

and you can also build vectors of vectors, and vectors

of vectors of vectors to build to the higher and higher dimensions. And there's a

little bit more syntax involved in doing that, but it [inaudible] the same basic functionality

kind of applies in higher dimension.

So this is the basic interface of the vector,

supplied as a template, so

all the way through it, it refers to elem type as what you get

at, what you set at, what you add and you insert all of the kind of values that are

going in and out of that

vector are

left using this place holder rather than saying it's explicitly a double or a

string or something, making no commitment about that, just leaving it open. And then

that template typed in elem type is the way that the whole class is introduced to

say

this is a pattern from which you can create a lot of different vector classes.

Let me show you a little something on the next slide that helps to

point this out.

So here I have, in blue, put all the places where the elem type shows up. I

put the type name parameter introduced, and it says within the body of the class I'm using

elem type as a place

holder, and the four places it's showing up here, the getat the setat the add and

the insert,

that when I go to create a vector as a client, I'll say vector of double.

Every place where there was elem type

and on the vector name itself has been annotated or specialized to show

that what's really going in out of this thing is double.

So this now created a class vector, angle bracket, double.

The constructor and the destructor match the class name now, and the getat, the setat,

the add, the insert,

all have been locked down. We've made that commitment, we said what we're

storing here really is vectors of

doubles, and that means that the add number function for vector double takes

a double parameter.

The getat returns a double value,

and that way once the compiler has done this transformation

that subsequent usage of that vector double variable

will be consistent with this filling in of the placeholder,

so it doesn't actually get confused about other types of

vectors you may have

been creating or working with.

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

always check size equals zero,

and so it actually doesn't really add anything to the interface.

It just turns out you do that so often in many situations, you want to know if

this thing is totally empty,

that as a convenience it offers two different ways to get at that same information. So you're

totally right, it's redundant.

Sometimes you'll see that for example the standard template library has a bunch of

the same things. The string has

a length number function. It also has a size number function. They do exactly the same thing. It's

just because sometimes people can remember size, sometimes people remember length. There's

also an empty -

it's not called is empty, but it's just empty. The

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

terms of each other,

but they

allow different ways to get at the same information.

Anything

else? You got a question? Here we go.

Is there a remove all method?

There is actually a clear method, and I should have put that up there. Actually, I think

there's a few. In each of these cases I've excerpted a little bit for the most

mainstream operations, but there is a clear operation that takes no arguments,

returns no argument, that just

takes the vector to an empty state.

So here's a little bit of

code

that shows some of the common use of vector and how you might do stuff with it

that just gets you familiar with, okay, what does the syntax look like?

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

parameter, which is the size, and it will fill a vector of integers with a sequence

of random numbers up to that size. You say I'd like a length ten vector filled with

random numbers,

it'll make a ten number vector

stuffing in

random numbers generated using the random library here.

So you'll see the declaration here, so I included vector [inaudible], the compiler knew what

I was using. I

specialized

when I declared that vector,

and so the constructor for vector creates a new empty vector of

that type, in this case vector of integer,

and then numbers.add sticking in a bunch of numbers, and then I'm returning it.

So it's totally valid to actually return a vector as the return value coming out of

a function.

It'll take that,

however many numbers I put in there, ten length vector,

and make a full copy of it.

And then when I'm down here and I'm saying nums equals make random vector, it actually

copied

that ten number vector

into the variable beings stored in main. So now I have a ten number

thing with some random contents.

The next thing I did with it was pass it to another routine that was going to print

it,

and there I am getting that vector, and this time I'm

accessing it in here

by reference.

This is just to show you that in typical because of the deep copying semantics it

does mean if I didn't pass by reference, it means the

full contents of the vector would get copied when I passed it to some function.

There's no

harm in that per se, other than the fact that it can get inefficient, especially as the

vector gets larger, it has hundreds and thousands of entries,

that making a full copy of those

can have some overall efficiency effects on the program.

Passing by reference means it didn't really copy;

it just kinda used the copy that was out here by reference, so reaching

out and accessing it out of [inaudible].

So in here using the size to know how many elements are in the vector,

and then this is what's called an overloaded operator, that the

square brackets that you have seen in the past, user array access and the

languages you know,

can be applied to the vector,

and it uses the same sort of syntax that we put an integer in that tells you what index and

indices from zero to size minus one are the valid range for

the vector, and accessed that integer and printed it out.

So anything you would have done on any kind of array,

reading a bunch of contents from a file,

printing these things out, rearranging them into sorted order, inserting

something into sorted order,

all those things are

operations that work very cleanly when mapped onto what the vector provides. One

of the really nice things is unlike most array,

like the built in array of C++,

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

on demand.

So if you were reading a bunch of numbers from a file, like you are in your assignment 1,

you don't have to have figured out ahead of time how many numbers will be there

so that I can allocate the storage and set it aside. You just keep calling

v.dot add on your vector,

and as needed it's just making space.

So if there's ten numbers in the file, there's a hundred, there's a million,

it will just make the space on demand

and you don't have to do anything special to get that access. Question? [Inaudible] The square brackets. No, the [inaudible]. Oh, the

angle

brackets. Yeah, they turn the side

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

specialization.

The square brackets here are being used for -

I'm accessing a particular member out of the array by index. [Inaudible]

So yeah, what happens in - so if you look at make random vector,

it created an empty vector, so the typical usage [inaudible] is you create it empty

and then you add things to grow it.

So you actually never in here actually have to say how big it's going to be. It

just - on demand as I call

numbers.add, it got one bigger each time through that loop, and if I did that

100 times, that'll have a hundred entry vector.

So there isn't actually a mechanism where you say

make it a hundred in advance. You will add a hundred things; it will have length

a hundred,

if you inserted a hundred things. The add me insert both

cause the size of the vector to go up by one, remove caused to go down by one. [Inaudible] brackets

to

access a specific element and write to it

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

the sub - the square brackets can only access things that are in the vector already. So you can

overwrite it if it's there, but if you have a ten-member vector, and you go to

say V sub 20,

it will not sort of

invent the ten members in between there and make that space. So the things that are

valid to access to read from are the same ones that are valid to write to, so you

can use the square

bracket on either side of the assignment operator to read or to write, but it has

to still be something that's already in there. If you really want to put

a hundred zeros into it, then you need to write a loop that puts a hundred zeros into

it

using

add. Way in the back. [Inaudible] Only for efficiency in

this case. I'm not changing it, so if I

was planning on going in here and multiplying everything by two or something,

I would do that pass by reference to see those changes permanently affected. This

actually isn't making any changes to the vector, it's just reading the contents of it,

so it could be pass by value and have the same

effect, but I wouldn't see any change in the program, it would just run a little slower

if I did that.

We will typically though - you will see that kinda just by

habit we will almost always pass our

collections by reference,

because of the concern for efficiency in the long run.

So it - even though we don't plan on changing it,

we'll use that to save ourselves some

time. Anything about

vector?

[Inaudible]

The second to the last line before printing,

the one right here where I'm going the - so this is declaring vector [inaudible], so

making the new variable, and it's assigning it

the return value from calling the make random vector function. So it's actually

declaring and assigning it in one step

where that assignment caused a function to be called that stuffed it full of random

numbers and returned it. Ten in that case means what?

Ten in this case is just the size. It's the [inaudible]

make me a random vector containing ten values,

so that's - the ten in this case is just how many things to put in the array.

[Inaudible]

Well it will make ten random numbers and stick them into the

vector, so when you get back you'll have vector of size ten that has ten random

entries in it.

If I said a hundred I'd get a hundred random entries. [Inaudible] function, which library has it? It is in random.H,

so

a lower

case random.H, which is R cs1061. Okay. Now

let me

reinforce this idea that templates are type safe, and that if you misuse them

you will get errors from the complier

that help you to alert yourself to the mistakes that you've made. If I

make a vector

specialized to hold [inaudible] is really an integer vector, I make a vector

to hold strings I call words, that

I could add integers into the first one, I could add words to the second one, but I can't

cross those lines. If I try to take nums

and add to it the string banana,

it will not compile,

so it has a very strong notion of the

add operation on this kind of vector accepts this kind of thing. So if it's a

vector of strings, the add accepts strings. If it's a vector of [inaudible] add accepts integers,

and the crossing of that will cause compiler errors.

Similarly, when I'm trying to get something out of a vector,

that return value is typed for what you put in it. If you have a vector of

strings, then what you return is strings, not characters.

Or trying to do, kind of

take one vector; one vector is not equivalent to another if their base

types are not the same. So a vector of doubles

is not the same thing as a vector of integers. And so if I have a function

that expects one or tries to use on, it really [inaudible] a vector of in, a

vector of in is not the same thing as a vector of doubles,

and the complier will not let you kind of mix those things up.

So it provides pretty

good

error messages in these cases. It's a, here's

how you've gotten your types

confused.

[Inaudible] double bracket number and then -

Yeah, so if this said vector angle bracket [inaudible] then it would fine, then I would

just be making a copy of the nums into a new variable S that had a

complete same content that nums did.

So that would be totally fine. I can definitely do assignment from one vector to another if they

are of the same type,

but vector in is not the same thing as vector double which is not the same

thing as vector string, and so

it's - basically it means that -

what the template is, is a patter for which you can make a bunch of classes, and on demand

it makes new classes, the vector double, the vector in, the vector string. And each

of those is distinct from the other ones that have been created. Can I change the types of

nums in

the

expression and then - You cannot type [inaudible],

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

stored differently, ints are a different size and doubles, so there's a bunch more things that

it

will just not do automatically in that case. If I really wanted to try to take a bunch of

integers and put them into a vector or doubles, I would end up

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.

Somebody in the back had something going on? Same question.

Same question, okay, so then we're good. Let me tell you a

little bit about grid,

which is just the extension of vector into two dimensions. Somebody asked

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

of vectors

as one way of getting into two dimension, but often what you have is really a

rectangular region, where the number of rows and columns is fixed all the way

across,

in which case it might be convenient to have something like grid

that you just specify how big you want, how many rows, how many columns, and then

you get

a full

2D

matrix to hold those values.

So it is something that you set the dimensions of the constructors, you

make a new grid on int that

has ten rows and ten columns.

There actually is a number function resize that lets you later change the number of

rows and columns,

but typically you tend to actually - once you set it, it tends to stay that way.

You have access to each element by row and column, so you say I want the to getat

this row, this column, it will return you the value that's been stored there.

And I put it over here; it says elements have default [inaudible].

So if you say I want a ten by ten grid of integers,

then it does create a full ten by ten grid of integers. If you ask it to retrieve the value at any of

those locations before you set them, they have

the same contents that

an integer declared of the stack would have, which is to say random.

So they're not zero, they're not negative one, they're not anything

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

default value?

For the primitive types that just means it's random. For some of the

more fancy types like string, it would mean they have the default value for

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

strings would be empty until I explicitly did something to set and assign their

value.

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

case, two arguments of the row and the column.

There's also an operator parens

that lets you say grid of parans, row column and separated by comma. I'll show that

syntax in just a second.

It does do full deep copying, the same way the vector does, which is if you

have a ten by ten grid which has a hundred members, when you pass or

return it by value, or you assign it, it has a full copy of that hundred member grid.

Lots of things sort of fit into the world of the grids

utility, any kind of game ward, you're doing battleship, you're doing a Sudoku, you're doing

a crossword puzzle,

designing a maze,

managing the data behind an image or any kind of mathematical matrix, or sort of table

tend to fit in the model for what a grid is good for.

This is the interface for grid,

so a template like vector was.

It has two different constructors;

one that is a little bit of an oddity. This one creates a zero row, zero

column

grids, totally empty,

which then you would later

most likely be making a resize call to change the number of rows and columns. That

might be useful in a situation where you need to create the grid before you kind of have information

about how to size it.

You can alternatively specify with a constructor the number of rows and

calls from the get go and have it set up,

and then you can later ask it for the number of rows and calls

and then you can getat and setat a

particular element within that grid

using those. There's also an operator - I'm not showing you the syntax in these for

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

client usage that

shows you how it works from that perspective.

So this is something let's say like maybe I'm playing a tic tac toe game and I

was gonna use the grid to hold the three by three board that has x's and

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

So I'm going to using characters at each slot,

I create a board of three three, so this is the way you invoke a construction in

C++ that takes argument.

If you have no arguments, you don't have the parens or anything, you just have

the name, but if it does take one or more arguments, you'll open the paren and

list them out in order. In this case, the three and three being the number of rows and

columns.

And so at this point

I will have a

grid that has num rows three, num columns three, it has nine entries in it, and they're all

garbage.

Whatever characters that were left over in that place in memory is what actually

will be at each location.

And then I did a nested four loop over the rows and columns,

and here I am showing you the syntax for the

access to the row column in kind of a shorthand form

where I say board of

and then parens bro , column = space.

Equivalently that could have been the member function setat board. Setat

row column space to accomplish the same result.

So this is still like vector sub I,

it can be used to read or to write.

It does bounced checking to make sure that row and column are greater than or

equal to zero and less than the

number of rows or number of columns respectively.

So it raises an error if you ever get outside the bounds of the

grid. And then this return at the end just returns that full grid.

In this case, the nine

by entry, three by three

back to someone else who's gonna store it and so something with it.

[Inaudible]

There is actual one distinction between a vector and a vector of a grid that's kinda interesting,

the grid is rectangular, it forces there to be

exactly the same number of rows and column kind of for the whole thing. That

a vector - if you created a vector of vector,

you could individually size each row as needed. This could have ten, this

could have three, and so like a vector vector might be interesting if you

had something - well they call that kind of the ragged right behavior, where they

don't all line up over here. But if you really have something that's tabular,

that there is a rectangular shape to it, the grid is going to

be a little bit easier to get it up and running,

but the vector vector's certainly would work, but

if you were doing

an array of

class lists where some classes have ten and some classes have four hundred, but

if you tried to do that with a grid you'd have to size the whole thing to

have a much larger row dimension than was needed in most cases.

So there's no square bracket operator?

There is not, and there is kinda an obscure reason for that, and if you are curious,

you can come to the cafe afterwards, and I'll tell you why it is,

but

some of the syntax you may have seen in the past has two square brackets, you say sub

row, sub column,

and to have that work on a class in C++

doesn't - it's not as clean. So it

turns out we use the parens, because it turns out as a cleaner was of

accomplishing the thing we wanted, which was a short hand access into

there.

So it doesn't actually use the square bracket operator. Question here?

[Inaudible] when

you

created support three by three and you

said it was forced to be a square, so why would you ever have to

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

have three rows by ten columns, but

it does mean that every row has the same number of columns, but the row

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

wrong word really rectangular is it. So

then I'm gonna very quickly tell you these last two and they're actually even easier to

get your head around, because they're actually just simplified versions of

something you already know, which is to take the vector

and actually limit what you can do with it

to produce the stack in the queue class.

It

seems like kind of a strange thing to do if you already had a class that did something, why

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

convince you of that why we have a stack and a queue.

So what a stack is about is modeling

the real world concept of a stack. If you have a stack of papers or a stack

of plates

you come and you put new things on the top of that

and then when it's time to take one off you take the top one. All right, so you don't dig

through the bottom of the stack, you don't reach over to the bottom. So if you

go up to get

a plate in the cafeteria you just take the one that's on the top. When they put new

clean ones they stick them on the top.

So this

could be - you could take a vector and model exactly that behavior where all the

edits to that - all the additions and remove operations have to happen on the

top or one end of the vector,

and that's basically what a stack does. Is

it provides something that looks like a vector

but that only allows you access to the top end of the stack.

It has the operation push

which is to say put a new thing on the top of the stack.

It has the operation pop, which is remove the top most element on the stack,

and there's actually a peak operation that looks at what's on the top without

removing it.

There is no access to anything further down.

If you want to see at the bottom or what's in the middle, the stack

doesn't let you do it. It gives a kind of a little window to look at this

information

that's restricted.

That seems a little bit strange,

why is it when you want - like sometimes you could do that with a

vector by always adding to the end and always forcing yourself to remove from the

end,

but then just ignoring the fact that you could dig through the other parts of the vector. And

there are a few really good reasons to have the stack around, because there are certain

things that really are stack based operations. A good example of is like if

you are

doing the web browser history

when you can walk forward,

but then you can back up.

You don't need to be able to jump all the way back to the end, you're just going back

in time. Or if you undoing the actions in a word processors, you type some things

and you undo it,

that you always undo the last most operations before you undo things before

that. And having it be a vector where you can kind of did through it means there's a chance

you could make a mistake. You could accidently pull from the wrong end or do

something

that you didn't intend. By having the stack it kinda forces you to use it the way

you said you planned on, which is I'm only going to stack on the end, I'm going to

remove from the end.

So it lets you model

this particular kind of limited access vector

in a way that

prevents you from making mistakes, and also very clearly indicates to someone reading

your code what you were doing.

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

classic data structures.

We think of, for example, the function calls as a stack.

You call main which calls binky which calls winky, well winky comes back and

finishes, we get back to

the binky call, we go back to main, then it always goes in this last in, first out,

that

the last thing we started

is the first one to undo and go backwards to as we work our way back

down to the bottom of the stack.

And so computer scientists have a very strong notion of what a stack is. You declare

something as a stack and that immediately says to them, I see how you're

using this. You plan on adding to the end and removing from that same end.

So you can do things like reversal sequence very easily.

Put it all on the stack, pop it all off, it came back in the opposite order you put it on.

You put ABC on you'll get CBA off. If I put

5 3 12 on, I'll get 12 3 5 off. So anytime I needed to do a

reversing thing, a stack is a great place to just temporarily throw it and then

pull it back out.

Managing any sequence of [inaudible] action, the moves and again, the keystrokes in your

edits you've made in the

word processor, tracking the history when your web browsing of where

you've been and where you want to back up to

are all stack based activities.

So if you look at stack, it actually has an even simpler interface than vector for

that matter.

It has the corresponding size n is empty, so you'll see a lot of repetition

throughout the interface where we could reuse names that you already know

and have meaning for, we just reproduce them

from class to class, so there's a size that tells you how many things are on the

stack, and is empty, that tells you whether the size is zero,

and then the push and pop operations that add something

and remove it.

And they don't allow you to specify where it goes; it is assumed it's going on the top of the

stack, and then that peak that lets you look at what's on the top without

removing it.

Yeah? So if you

[inaudible] that had

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

designing our interface was give you a simple

model you can follow, but also if you step out of the boundaries of what we

know to be acceptable,

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

empty stack, it will print and error and halt your program. It

won't make it up, it won't guess, it won't - [Inaudible]

Well, so the stack knows its size and it [inaudible] is empty,

so when you're unloading a stack you'll typically be in a loop like, well the

stacks not empty, pop.

So there's definitely ways you can check ahead of time to know whether there is something

there or not, and

it's all managed as part of the stack.

But if you blow it and you try to reach into the stack that's empty,

it won't let you get away with it.

And that's really what you want. That means that they run a little slower

than the counterparts in the standard library, but

they never let you make that kind of mistake without

alerting you to it, where as the standard library will actually respond a little

bit less graciously. It would be more likely to just make it up.

You tell it to pop

and the

contract is, yeah,

I'll return you something if I feel like it and it may be what - it may

be something that actually misleads you into thinking there was some valid contents

on the stack and causes the error to kinda propagate further before you realize

how far you've

come from what its real genesis was. So one of the nice things about reporting the error

at the first

glance is it gives you the best information about how to fix it.

So here's something that just uses the stack to invert

a string in this case, right,

something a user typed in. So I

prompted for them to enter something for me, I get that line

and then I create a stack of characters.

So the stack in this case is being created empty and then I take each

character one by

one from the first to the last and push it onto the stack, and so if they

answered

Hello, then we would put H-E-L-L-O on the stack.

And then print it backwards,

well the stack is not empty I pop and print it back out, so I'll get

O-L-L-E-H back out of that

and the loop will exit when it has emptied the

stack completely.

Stack [inaudible] just is

a simpler form of that. The

queue is just the cousin of the stack.

Same sort of idea is that

there's certain usage patterns for a vector

that form kind of their own class that's worth kinda giving a

name to and building an abstraction around, the queue.

The queue instead of being last in first out is first in first out. So the first

thing you add into the queue

is going to be the first one you remove. So you add at the front - you

add at the back and you remove from the front, it models a waiting line.

So if you think of lets say the head of the queue and tail,

or the front or the back of the line, that A was placed in the queue first,

that operation's called n queue;

n queue A, n queue B, n queue C, n queue D,

and then when you d queue, which is the remove operation on a queue, it will pull the

oldest thing in the queue, the one that was there

first who's been waiting the longest.

So removing the A and then next d queue will give you that B and so on. So

it does what you think of as your classic waiting line.

You're at the bank waiting for a teller.

The keystrokes that you're typing are being likely stored in something

that's queue like, setting up the jobs for a printer so that

there's fair access to it, where first come, first served,

and there's a couple kind of search [inaudible] that actually tend to use queue

as the way to kind of keep track of where you are.

So again, I could use vector for this,

just making a deal with myself that I'll add at one end and I'll always remove the zero with

element,

but again,

the effect is that if somebody sees me using a vector,

that they'd have to look at the code more closely

to see all my access to it, when I add, and when I remove to verify that I was

using it in a queue like manner, that I always

add it to the back an remove from the front.

If I say it's a queue,

they know that there is no other access than the n queue d queue

that operates using this FIFO, first in, first

out control,

so they don't have to look any closer at my usage of it to know what I'm up to.

The other thing that both stack and queue have which

won't be apparent now, but will

when we get a little further in the course,

is that by

defining the queue extraction to have kind of less features,

to be what seems to be less powerful

and have sort of a smaller set of things it has to support,

also has some certain advantages from the implementation side. That

if I know somebody's always going to be sticking things on this end and that end, but

not mucking around in the middle,

then I can make certain implementation decisions that support the necessary

operations very efficiently,

but don't actually do these things well because they don't need to,

in a way that vector can't make those trade offs. Vector doesn't know for sure

whether people will be mucking around with the middle or the ends or

the front or the back,

and so it has to kinda support everything equally well, that stack and

queue has a really specific usage pattern that then we can

use to guide our implementation decisions to make sure it runs

efficiently for that usage pattern.

So the same constructor or destructor in size is empty, that kind of

all our linear collections to,

and then it's operations which look just like push and pop but with a slight

change in verb here, n queue and d queue,

that add to the back, remove from the front,

and then peak

is the corresponding look at what's in the front. Like what would be d queued,

but without removing it from the queue, so just see who's at the head of the line.

And so a little piece of code I stole from the handout

which

sort of modeled a very, very simple sort of like if you're getting access to

the layer and you're getting help,

that you might ask the user, to kinda say well what do you want to do next, do you

want to add somebody to the line or do you wanna service the next customer, and so we

have this way of getting their answer.

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

the question of the first person in the queue which will be the one who's been there

the longest, waiting the longest. And

if their answer was not next, we'll assume it was a name of somebody

just stick onto the queue, so that actually adds things to the queue.

So as we would go around in this loop it would continue kind of stacking things up on

the queue

until

the response was next and then it would start pulling them off and then we could go back

to adding more and whatnot, and at any given point the queue will have the name of

all the

in-queued

waiting questions

that haven't yet been handled,

and they will be pulled off oldest first,

which is the fair way to have

access in a waiting line.

So

just the -

very similar to the stack, but they - LIFO versus FIFO

managing to

come in and come out in slightly different ways. So once you

have kind of these four guys, right,

you have what are called the

sequential containers kind of at your disposal.

Most things actually just need one of those things. You need a stack of

keystrokes, right, or actions or web pages you visited; you need a queue of

jobs being queued up for the printer. You need a vector of students who are in a class,

you need a vector of scores on a particular exam,

but there's nothing to stop you from kind of combining them in new ways to

build even fancier things out of those building blocks,

that each of them is useful in it's own right, and you can actually kind of mash them

together to

create even fancier things.

So like I can have a vector of queue of strings that modeled the checkout lines

in a supermarket, where each checkout stand has it's own queue of waiting people,

but that there's a whole vector of them from

the five or ten checkout stands that I have, and so I can find out which

one is the

shortest line

by iterating over that vector

and then asking each queue what's your size the find out which is the shortest line

there, and picking that for the place to line up with my cart.

If I were building a game, lets say, where there was a game board that was

some grid,

and that part of the features of this game which you could stack things

on top of each location,

then one way to model that would be a grid where each of the elements was a

stack itself of strings. So maybe I'm putting letters down

on a particular square of the board, and I can later cover that letter with

another letter and so on,

and so if I want to know what is the particular letter showing at any

particular grid location,

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

the top. I won't be

able to see things that are underneath, and that might be exactly need in this

game, is that you can only see the things in top,

the things underneath are irrelevant, until maybe you pop them and they are exposed.

So we just layer them on top of each other, we can make them as deep as we

need to. It's not often they need to go past probably two levels, but you can build

vectors of vectors of vectors and vectors of queues of stacks of grids and

whatever you need to kind of get the job done.

There's one little C++ quirk

that I'm gonna mention while I'm there,

which is that the vector of queue of string actually has a closer -

a pair of those closing angle brackets that are neighbors there,

where I said I have a queue of string, and that I'm enclosing that to be the element

stored in a vector,

that if I put these two right next to each other,

which would be a natural thing to do when I was typing it out,

that causes the compiler to misunderstand what we want.

It will lead the

grid stack

string,

and then when it sees the string, the next thing coming up will be these two greater

than signs. It will read them together,

so it effect tokenizing it as oh, these next two things go together,

and they are the stream extraction operator,

and then it just all

haywire - goes haywire from there. I think that you're about - you were in the

middle of declaring a type and then all of a sudden you asked me to do a stream extraction. What happens, right?

Sad, but true,

and it will produce an error message, which depending on your compiler is more or

less helpful. The one is X-code is pretty nice, it actually says,

closing template, there needs to be a space between it.

The one in visual studio is not quite as helpful, but it's

just something you need to learn to look for, is that you do actually have

to

plant that extra space in there so that it will read the closer for one, and then

the second closer without

mingling them together.

There is an on deck proposal which shows you that C++ is a live

language, it's

evolving as we speak, but in the

revision of C++ as being planned, they actually want to fix this

so that actually it will be fine to use them

without the space and the right thing will happen,

and by changing it in the standard, it means the compiler writers will eventually kind of

join to be spec compliant, will actually have to change their compilers

to handle it properly, where as they now have

little incentive to do so. And

then I just put a little note here that as you get to these more complicated things there

might be some more appeal to using typedef, which is a C++ way of

[inaudible] shorthand.

You can actually do this for any type in C++. The typing,

if you were typically something it would go up at the top of the program.

I say typedef and then I give the long name

and then I give the new short name, the nickname I'd like to give to it. So I can

say typedef into banana and then all through my program use banana as though

it were an int.

Okay, probably not that motivating in that situation, but when you have a

type name that's somehow long and complicated and a little bit awkward to reproduce throughout

your program, you can

put that type name in place and use the shorthand name to kind of add clarity

later. So maybe I'm using this to be

some information about my calendar,

where I have the

months divided into days or days divided into hours, so having kinda of a two

layer vector here,

that rather than having vector of vector of ints all over the place I can us calendar T

to be a synonym for that

once I've made that declaration.

Let me show you just a couple of things back in the compiler space before

I let you guys run away to go skiing. One of the

things that you're likely to be working on in this case is that you're

learning a new

API, API is called Application Programming Interface,

it's the way you interact with the libraries, knowing what routine does what and what

it's name is and what it's arguments are,

and that's likely to be one of the things that's a little bit more of a

sticking point early on here, is just kind of saying, oh I know this exists in a

random library, but what's the name of the function, is it random numbers, is it random

integers, is it random it? And

being familiar with the ways you kind find out this information. So let me

just give you a little hint about this; one is that you can open the header

files, so I just opened in this case, the grid.h header file,

and I can look at it and see what it says. It says, oh, here's some information, it actually has

some sample code here,

and as I scroll down

it'll tell me about what the class is, and then it has comma's on each of the

constructor and

member function calls that tells me how it works and what errors it raises and

what I need to know to be able to use this call correctly. And so

for any of our libraries, opening the header file is likely to be an

illuminating experience.

We try to write them for humans to read, so they actually do have

some

helpfulness. If you go to open a standard header file,

they're not quite as useful. For example, let's go look at I stream

and keep going.

You'll get

in there and you'll see, okay, it's typedef template car basic I stream and then there's some goo and

then there's a bunch of typedef's

and then it gets down to here, there's a little bit of information that tells

you about

what the constructor might do and stuff.

You can read this, but it's not - it doesn't tend to be actually

targeted at getting the novice up to speed about what's going on. There is

some information here, but

in those cases you may be better of using one of our references, going back

to the reader,

or looking at

one of the websites that we give a point or two on the reference handout that

just kind of

tries to extract the

information you need to know as a client rather than trying to go look in here, because once you

get in here, oh what is gettake, and it's like what is all this stuff with these underbars

and stuff, it's not the best place to learn the interface, I think, from their

header files.

The other place that

I will note that we have is up here on the website

there is a documentation link, let me show you where I got to that just to remind you,

is up here in the top,

over on this side,

and what this is, is actually this is our header files having been run through

something that generates a webpage from them, so it has the same information

available in the header files, but it's just organized in a

clickable browsable way to get to things.

And so if you

dink this down and you look at the class list, you can say, yeah, tell me about queue, I'd like

to know more about it and then it'll give you the public member function. This

projector's really very

fuzzy, I wonder if someone can sharpen that,

that tells you that here's the constructor, here's the n queue d queue peak,

there's a clear operator that empties the whole thing and then there's some other

operations that are involved with the deep copying that are actually explicitly named out.

And then if you go down, you can say, well tell me more about n queue,

you can come down here, it'll tell you the documentation we had that's

been extracted from the header files tells you about what the arguments are, what their

turn value is,

what things you need to know to use that properly.

And so you'll probably find yourself using one or both of these, like going and actually

reading the header files or reading the kind of cleaned up pretty printed header files

just to get familiar with what those interfaces are, what the names are, and

how you call them

so

that when you're working you know, and have a web browser kind of up

aside to help you navigate that stuff

without too much guess work.

And so I just wanted to

show you that before I let you go.

Anybody questions about that? Hopefully you should feel a

little bit like, hey,

that starts to be useful. By Wednesday I'll show you map and set and

then you'll realize there's a lot of really cool things you can do with all these

objects around in your arsenal.

So have a good weekend,

enjoy the holiday,

come to Truman,

I'll see you on Wednesday.