[ Silence ]
>> Alright!
Welcome back to CS50.
This is the end of week 4.
So, if you haven't already, do pull up
or follow along while I do here a simple Google search
for this keyword recursion
which we discussed last week, and do you get it?
[ Inaudible Remarks ]
>> Ah, ha ha ha.
Okay, so many new jokes available to us now.
So, someone has a sense of humor on the Google humor team, right?
[ Inaudible Remarks ]
>> Alright, we're all a bunch of dorks now, alright.
So, a couple of recaps and announcements.
So last time, recall that we focused on algorithms
and actually solving some problems a bit more efficiently
and we started to use this so-called asymptotic notation,
just big O in omega and there's also feta [phonetic]
but we'll focus mostly on big O in--
in Omega and just to toss some jargon out here,
know that we focused a lot on big O of N linear
and so linear then perhaps brings back memories
of the straight lines that we do while graphing.
We looked at big O of N squared, bubble sort, selection sort,
these were in big O of N squared and we found
that that was generally slow.
If definitely felt or looked slow when we compared it
to something faster, namely N log N. Now,
frankly most people don't tend to say supralinear
but it is an apt word but N log N was kind of a sweet spot
between N squared which was really slow and N
which was generally unrealistic, at least thus far
for doing something like sorting.
But know too that anytime you have an algorithm
that takes the same amount of time, irrespective of the size
of the problem, irrespective of the number of students
in the room, irrespective of the number of inputs provided,
well that's what we would call constant time.
And just as we cross out things like divided by 2 and times 2,
anytime you wanna express the notion that an algorithm runs
in constant time, 5 seconds, 10 seconds,
no matter how big the input is,
you would typically say big O of 1.
Well, what's an example of a constant algorithm?
Well, I mean you can think of something simple like--
at the start of lecture, rather than taking something
like attendance, the algorithm can be greet students,
so I execute that algorithm, "hello",
like no matter what that's gonna take constant time.
Even if I say three things like "hello class", okay,
so that's two steps but again we get rid
of this constant multiplier so it's still constant time.
We saw binary search with Shawn up at the board on video
where log N was the ultimate conclusion there.
But know that there are other things.
Sometimes, you even can't do N squared,
the problem is just too big or too complex, so you might have
to have something polynomial, N raised to the something power,
where that something, call it C, is bigger than 2,
and really bad algorithms are things that are in, say,
factorial-- N a factorial which we'll typically avoid
but there are-- there is the potential to write algorithms
that really are that slow.
And then exponential is
yet another one not even depicted here,
and that too tends to be quite slow.
But today we return now to the practice
of actually coding things and understanding what's going
on inside of a computer and peel back a layer called pointers
that is both empowering as we'll see but also quite dangerous.
So if you don't recall,
WiFi should now be available here in Sanders.
What we've also done, thanks to HUIT,
is Quincy House whose wireless we broke last Wednesday
at office hours since we had 209 students there in attendance.
They have added six more wireless access points for us,
so tonight's office hours in Quincy should be much improved,
and the other houses have been bolstered as well.
Also, too, if you've been trying to catch me for pass/fail forms
or add/drop questions and I have been quiet on email,
it's just because I've gotten kind of overwhelmed.
Please don't hesitate to just re-ping me, and I'll do my best
to catch up today and tomorrow, but certainly you engage me,
or Matt, or Rob, or your TF in a chat if you have any questions
or concerns at this point in the term.
So, a little teaser before we move
on to some milk and OJ here.
So this was a-- a little video that should tease us
as to today's focus, this topic of pointers.
In a nutshell, a pointer is going to be an address,
the address of something in memory
but we'll see what damage we can actually do
if we use these things incorrectly,
so a clip from a certain Stanford University Computer
Science professor here.
[ Music ]
>> Hey Binky, wake up, its time for Pointer Fun.
>> What's that?
Learn about pointers?
Oh goody!
[ Laughter ]
>> That's all you get right now, we will conclude
with the-- the follow up there.
It's just fun to imagine Nick,
this esteemed computer science professor at Stanford kind
of playing at home with his clay models
and recording himself do this, so more on that later today.
So, recall that we ran into some problems early on when we tried
to do something so simple like swapping variables
and writing our own swap function also failed ultimately.
And so consider how we solve the problem like this.
I'm gonna get rid of things like instant charge here
because we can just generalize with pseudo code,
but here might be two variables, A and B,
and they've already been initialized to be orange juice
and milk, respectively.
Well, suppose that the goal here is
to swap the contents of A and B, right?
And sort of intuitive term, the goal is to put this over here,
this over here, but obviously
if you take the straightforward approach, that kind of looks
at first glance, correct, AB goes into A, A goes into B,
of course, you get a bit of a mess if this is A, this is B
and you try doing-- that is disgusting.
This-- right, there's no way I'm gonna be able
to move just the white stuff back over here on to the left.
And so, right, this is buggy, right, broken algorithm,
if that weren't clear already.
So, how do we solve this?
Perhaps, in real world, obvious problem.
Right, so you have some kind of temporary variable.
So if we introduce for instance just an extra 32 bits
or whatever the data size is,
then we can actually fix this whereby-- let's try this again--
whereby we have a fresh cup of A, fresh cup of B,
and then we're gonna need-- whoops let's not do that.
[ Laughter ]
>> Alright, fresh cup of B, so now we need
of course a temporary variable.
If there's any suspense, really, we should know
where this is going, right?
So-- so we have A with orange juice, we put A into temp,
okay, that was productive.
Now, we have B going into A, so that's over here,
little cross contamination but not nearly as bad.
And now, temp goes into B, right,
so this is kind of a fun game, right?
We could do this all day.
[ Laughter ]
>> But thank you.
Thank you.
[ Applause ]
>> So, not bad.
We've solved it, but then we broke this, right?
You could implement something like this,
albeit in C in a function like main,
and it would actually work.
So you could swap two variables, A and B, if they're integers
or whatnot, and it would work in main
but then we kinda got arrogant and introduced our own function,
swap, whereby we pass in A and B,
and we claim this is good practice, right?
You factor out sort of conceptual chunks of code
into functions that are aptly named, we slapped the label,
hierarchical dot decomposition on it, but then this broke,
this simple, simple, simple thing of swapping.
And what was the simple answer as to why the inputs
to this function are not in fact swapped once this
function executes?
Yeah, so it's this issue of scope.
When you pass in two variables, say X and Y, into a function
like swap, what's actually passed
in is two copies of those things.
So, what's really been happening in the case
of an actual swap function is if this is, say X and Y,
and this exist in main.
Well, when you actually call swap, what happens is--
I'm gonna have to do a little bit of a magic here.
So if this is X, this is Y, this is going to be A, this is going
to be B, what actually goes into this cup?
Like it's a copy of whatever X is,
so it wouldn't really make sense to pour this in here just
yet so I'm just gonna cheat and say this is a copy,
which pretty much is, half a glass of orange juice.
Y goes into B so we have a perfect copy of this.
And then what happens in this swap function?
Well, the swap function again is actually correct.
We have this local temp variable so we go ahead and move A
into temp, then we go ahead and move B into A,
and then we go ahead and move temp into B,
this is all working really well
and then we return, and what happens.
Well, the slice of memory that was allocated
to the swap function is effectively gone.
I mean, it's actually still there
but the computer just forgets about it
so you kind of fast forward.
If we ever call another function, we might end
up with orange juice or milk by default in those new variables,
just because of those remnants,
so there actually is something still here in memory
but now we have X and Y, we didn't really do anything.
So how do we actually solve this?
Like just kind of intuitively, if the swap function isn't
so much a function but rather it's just a friend and you want
to hand your friend, X and Y, and you want that friend
to swap X and Y for you,
what should you really be handing your friend?
Yeah, so ideally, you just hand him or her the actual cups,
the originals, X and Y, and let him or her do their thing
with an extra temp variable--
variable and actually do the swap.
So how do you actually hand to a function the original X and Y?
Well, what you can do is this.
If you have a little scrap paper,
and you say to your friend, alright, well, let's suppose now
that X-- actually this is an unrealistic, suppose that X
and Y are kind of bolted to this table in the same sense
that a variable X and Y are in one place in RAM, right,
the variables aren't gonna move.
They are where the computer allocated them in RAM.
So, what I can do is I can't really hand my friend these
variables because that would be to move them from memory,
but I can say, you know what, dear friend,
the OJ is at location 1, 2, 3, 4 in RAM and the location
of Y is at 4, 5, 6, 7.
>> I'm just making these numbers up.
So what you hand your friend is not X and Y
but rather this little chi-chi, the address of X and Y. So that
when your friend receives this, he or she can say alright,
the X is apparently at location 1, 2, 3, 4,
so I need to swap these cups for David
so I'm gonna allocate my temporary variable, TMP,
I'm gonna go ahead and bring it with me
to location 1, 2, 3, 4 in memory.
Okay, I'm gonna go ahead now and pour that location's contents
into the temporary variable.
Now, what am I gonna do?
Alright, I need to now go to location 4, 5, 6, 7,
so I go there, I find it and I realize, oh okay,
I'm gonna move its contents to that same temporary variable.
And then what do I have to do?
Right, well now I have to go back to the original cup
and actually say, alright, now I have to move the--
I got completely lost-- what goes next?
Orange juice goes next.
I have to take those contents, move it over,
and if I didn't completely screw up this algorithm,
they are indeed swapped but they're swapped
at the original locations
because I actually followed this map, if you will,
to my friend's cups of OJ and milk, change those values,
albeit with the help of my extra temporary cup
and then the original contents are changed.
So on the one hand I'm saving memory
and that I'm not making copies of milk
and orange juice this time, but I am spending some memory--
what am I spending in this scenario?
Whatever the costs of these pieces of paper are,
so it turns out inside of a computer these little slips
of paper will cost you generally 32 bits, a pointer,
otherwise known as an address in memory will cost you 4 bytes
or 32 bits, at least on many computers including
the appliance.
Now, if you're familiar with your own personal MAC
or PC being 64 bit Intel Inside,
well that actually means these slips of paper are twice
as long, you can fit bigger addresses in them
and so pointers can also be 64 bits.
And on hardware that's 10 years old, 20 years old, 30 years old,
you might have pointers that are just 16 bits
or 8 bits, but that's all it is.
A pointer is just the address of something in memory
and so this seems to now solve the problem.
We can just inform someone where these things actually are.
So what's this gonna look like?
Well, this is before.
This is the broken version of swap.
But the after version, if I now spoil this here,
is going to be that.
So we have to introduce a little bit of more syntax
and there's actually one tweak we're gonna have
to make to main.
But if we want to rewrite our swap function
so that it does still swap, but it swaps correctly by passing
in the address of X and Y or whatever the inputs are called
and actually changes them at their original locations,
we essentially have to introduce some of these stars,
these asterisks before the variable names.
So we'll tease apart exactly why that is but let's now see--
let's now just toss out a bit of jargon so that
when we start seeing these things
on the screen, its not so scary.
So I have to teach you how to count again,
so we've done this a couple of times now, right?
You came in presumably knowing decimal, well, 0 through 9,
we spent a little bit of time in week 01 binary
where you only have two digits, 0 and 1, but we realized
in the first week that if I wanna express the number 0
in binary, it's actually pretty easy.
I can just say 0.
But then remember that we said,
you don't typically just use one bit, you typically work
in units of at least what?
So at least 8, a byte is 8 bits
so even though it's a little tedious to write
on a chalkboard, really, if you want to represent the number 0
in binary, you would probably store 8 bits,
all of which are 0, and it got pretty easy after this.
If you wanna represent the number 1, you have seven zeroes
and then one 1, but then we actually had to think
for the first time, right, in this scenario
where we can't just go 00000002 'cause we don't have that digit,
we only have a-- a binary number of digits, 0 and 1,
so we didn't do this, so what was the number 2 in binary?
Yeah, so it's actually 1, 0, so we had to move this here,
so it's like carrying the 1, this then becomes a 0.
And if you then think back to what this is,
this is the 1's columns, the 2's, 4's, 8, 16, 32, 64,
128 and so forth, if you have more bits.
So even though it's a little longer, it takes more chalk
to write these numbers, we can represent all possible integers
with which we already are familiar.
So this is binary, we already know decimal,
let's introduce a bit of hexadecimal.
Hexadecimal is gonna be useful here only in so far as some
of the numbers we're gonna start seeing
on the screen are little less scary although in reality,
we're rarely going to care
about what the address of some variable is.
It could be 12345, could be 4567, it could be a huge number
of digits, we just care that these addresses exist,
we're not gonna typically care what they actually are.
But what we're gonna start seeing in a moment is
that a hexadecimal number-- so that everyone can see,
let me move to just the window up here.
What we're gonna see now is a whole lot of numbers that start
with 0X, which is just a human convention
that says here comes a hexadecimal number.
Hexa, in this case, means 16, so in a hexadecimal system,
you don't have 2, you don't have 10,
you have 16 digits available to you.
So how do you go about counting in hexadecimal?
Typically, you would start at 0, then you would go up to 1,
and thankfully hexadecimal is actually a little easier,
now you can go to 2, then you can go to 3, then you can go
to 4, 5, 6, 7, 8, 9, and?
[ Inaudible Remark ]
>> Ooh, very good, so it's A, it's not 10.
Right, so each of these digits,
each of these values here can be any of 16 possible values.
Of course, once you start counting at 0,
you get all the way up to 7, 8, 9, and you wanna say 10,
but expressing 10 takes two digits but we need--
we have 16 available so the world decided that after you get
to 9, you actually go to A, to B, to C, to D, to-- oops, to E--
and capital or lower case doesn't really matter,
its just a convention.
And then after you get to F, which is actually the 16th digit
if we count all these up, I've just typed
out 16 hexadecimal digits, what do you get to after F?
One zero, so then you carry the 1, you go from the biggest value
which in the normal world is 9,
and you carry the 1 and you get to10.
In the hexadecimal world, you get to F, then you carry the 1
and you get to 1-0 and then it's 1-1, 1-2, 1-3, 1-4, 1--
dot dot dot, 1A, 1B and you can keep counting up like this.
So we're gonna start seeing a lot of things in hexadecimal.
What's nice about hexadecimal is that each of these digits,
and there's 16 possible ones,
takes up an exact number of bits.
Every hexadecimal digit is 4 bits,
so if you write 4 bits followed by 4 bits, you get a byte,
so it's very convenient to express numbers as hexadecimal
because with just two digits, you can represent a whole byte,
whereas in binary, my god, you have to write
out eight separate digits.
So this is just a more succinct base system.
Now we're gonna see it in a very arcane sense this week and next
but fast forward toward term's end and we start doing things
like web programming and a language called HTML
and a language called CSS, Cascading Style Sheets.
We're actually gonna re-see--
see these things again because they're also used
on the web for colors.
So just to fast forward, if you ever want
to express the color red on a web page,
you can either just say "red"
which is actually pretty compelling,
or you can actually say FF 00, 00,
and that should be consistent today, FF,
but it doesn't matter.
Now, why is this?
Little teaser, if you've ever heard of the expression RG--
whoops-- RGB, red, green, blue,
the way we're gonna implement colors in a few weeks and also
in the multimedia section of one of our problem sets,
FF is kind of the biggest possible hexadecimal digit you
can write, it's the-- the--
before you have to roll over to a 1 and a 0,
well this means a lot of red, no green, no blue,
so what's the result
if you combine these various paint colors?
Only you get just red, so that's red.
Alright, so that was a bit of a tangent only to emphasize
that we're gonna start seeing these things now
but it's really not a big deal, it's just a more succinct way
of representing numbers than binary is
and even then decimal itself is.
So let's go ahead and solve something.
I'm gonna go ahead and open up a new window in G edit
and we're gonna go ahead and try
to compare something very simple, so let me go ahead
and start from scratch here,
though the code is available online and I'm gonna go ahead
and say-- let's zoom in-- let's go ahead and save this
as compare1.c and I'm gonna go ahead
and say "int main void" alright, and the goal
of this program ultimately is to get two strings from the user
and then just compare them and say yes or no,
the user typed the same word twice or here she did not.
So let's go ahead and say we wanna get a string
from the user, so printf--
let's just do something like "say something" alright,
I put a space for aesthetics and now how do I get a string?
Little recap-- so string S--
let's call it S1 'cause I'm gonna need two,
so S1 gets-- GetString.
Okay, not quite, I need to now kind of remind myself,
wait a minute, I've just used two functions
that I did not invent.
So what do I need to include at the top?
Okay, so CS50, and also-- yup, standard I/O for printf.
And now, it should compile okay at this point in the story.
So let's assume that the user doesn't try to be difficult.
Here she just types in a word, so now let's go ahead
and do the same thing, and we could use-- whoops!
We could use a loop here but it's only a finite number
of things, so it's actually pretty reasonable just
to copy paste these two lines of code and get something
from the user but this time say "say something again".
>> So I want the user to type in some word, then another word,
and now let's go ahead and compare these things.
So we know how to do branches in both C and scratch, so let's say
if S1 equals equals S2, well let me go ahead and say
to the user printf, you typed the same thing,
exclamation point, semicolon, else let's say printf,
you typed different things exclamation point semicolon.
Any bugs jumped out at anyone?
Or any syntax bugs?
Typos? Okay, feels pretty reasonable, right?
So we get a string S1, get a string S2, we then compare it
and I didn't make this mistake, right?
This could be the first possible mistake, very commonly happens,
but I am using equals equals and that's as comparative things,
don't assign one to the other, so I print--
you print the type the same thing or different thing,
so let's compile this.
Let me go down to my terminal window here.
Let me go ahead and do make compare 1.
Looks like you compiled okay.
Let me make this a little bigger and let's go ahead and run,
compare 1, enter, say something, let's say hello, okay, hello.
Now I did it, right?
So, let's try this again and make sure maybe--
maybe we got it all backwards, alright, so hello and goodbye.
Okay, so I'm half right, right?
So that's at least correct and let's just do a sanity check.
Hello? Hello.
Alright, so it feels like there's something going on here.
So what might this be?
Right, so there's clearly a lead in today, it somehow relates
to this stuff but like what really is probably going
on underneath the hood that's breaking this program?
Yeah?
[ Inaudible Remark ]
>> Yeah, so I mean that's kind of what it reduces.
To even if you're not quite sure at all on the Y,
feels like the only opportunity
for the bug here really reduces to just one line.
Every other line in this program is pretty straightforward
and pretty uninteresting so the decision point must be
where the flaw is and in fact it is the case
that you cannot compare two strings in this way.
Why can we not compare two strings in this way?
'Cause equals equals has worked for like 4 weeks.
We've used it for chars and ints, the--
it can break with floats and doubles
but that's a different issue.
Remember when you compare floats and doubles
because of imprecision,
you might be comparing something that's ever so slightly off
but a string is a string.
But what is a string really?
What did we say "string" is synonymous?
[ Inaudible Remarks ]
>> Yeah, it's an array of characters, so really remember
if we get rid of the CS50 Library, we lose some
of its synonyms that it's defined and recall that we kind
of peeled back this layer recently
and then quickly hid it again.
What string really is just a synonym for is char star.
So star, we'd just seen a moment ago is apparently the solution
to all of our problems, at least with regard to swapping things.
But char we've seen is just a character,
so char star means pointer to character, or if we boil it
down to its basic definition, char star means the address
of a character, so who cares?
What is this really doing for us?
Well, let me spin this around to a-- a blanks--
okay, so it's coming with us.
Let me spin this around to-- alright.
Okay. So, what really is char star?
Char star is pointer to char but that's just address
of char, so what is a string?
When you allocate S1 like this, and then assign it a value,
what's really going on?
Well, on the left hand side, what you're getting in RAM is--
let's call it a square, a chunk of memory,
that is how many bytes?
How many bits?
In the appliance, at least, this is gonna be 32 bits.
The mere act of having written a star means you're gonna get a
pointer, whatever that is,
and we can represent this pictorially with the square,
and that square represents 32 bits.
Now, we've-- the wrong picture is like this before.
If I ever said int X on the screen with a semicolon,
what that means is give me 32 bits and allow me
to put a number in there.
Well, that's all a pointers, it's just a number.
It just so happens that number has special meaning,
it represents the address of something in memory,
it doesn't represent an integer that I put in memory.
So this is what S1 is, so logically, what is S2?
S2 is just another such chunk of RAM, another 32 bits.
So when I call GetString, we already know
at least conceptually that in a string is an array of characters
and we know this, we've seen this, right in P set 2
with Caesar and Visonaire and the hacker edition with crack,
you've actually, you know, traversed arrays of characters
from bracket 0 all the way up to N minus 1.
So, what really is a string?
What is GetString giving you?
Well, what GetString does, and we'll see this week and next,
is that when you type in the word hello as the human,
GetString is calling a special function,
happens to be called malloc, for memory allocation,
and what it's doing is it's allocating a chunk of memory
for you and it's then putting in whatever letters you type, H, E,
L, L, need a little more, O, need a little more actually.
What else is GetString probably doing based on past promises?
Yeah, it's putting that so-called null character
which we draw as backslash 0.
So, what has GetString doing all of these weeks?
It's been allocating with a new function called malloc,
a chunk of RAM, but what's key about this chunk of memory is
that it's back to back to back to back, it's not a little
over here, little over here, little over here,
it's all contiguous and it's of size N plus 1
so that you can fit the string plus this null
terminating character.
So now, if a pointer I claim is just 32 bits, it's this small,
and it's clearly too small to fit H-E-L-L-O backslash 0,
what's really going in here, do you think?
[ Inaudible Remark ]
>> Yeah, just the address of this.
Right, if this is memory, this is RAM,
and RAM is like 2 gigabytes worth on your MAC or PC,
well we've claimed that you can say this is byte 0,
this is byte 1, this is byte 2 billion, if you withdraw this--
this rectangle as we keep doing.
So these cells in memory, these chunks
of bits all have some address.
This might be address 1, 2, 3, 4.
This might be 1, 2, 3, 5; 1, 2, 3, 6 and so forth, that the--
what the numbers are doesn't matter
but that they have numbers does matter.
So, which of these numbers is probably going inside
of this 32 bits?
Which one do you need to know?
It's really just the first.
What's gonna go in here is the number 1, 2, 3, 4 if 1, 2, 3,
4 is the physical address in memory of the first byte.
Now, this is sufficient to remember S1 because if I know
that the start of the string is at-- address 1, 2, 3, 4,
how do I find the end of the string?
[ Inaudible Remark ]
>> Exactly!
You just very simply, honestly, four loop, Y loop,
whatever your preference is,
you start at that address and you check here.
Is this the null character?
Is this-- aha, it is!
That's the end of the string.
So the function printf does something pretty much like that.
It looks at every character back to back to back,
just like you did with Caesar and Visionaire,
and as soon as printf sees, "wait a minute,
this is not a printable character, this is backslash 0,"
all 0 bits, it stops printing, it returns and voila,
you see some text-- string of text on the screen.
So now, back to the flawed program.
This S1 equals equals S2, what is it really doing then
if we now understand what's going on underneath the hood?
What's it comparing?
S1 and S2, so let's finish this picture.
I typed in goodbye before so what do I need for goodbye?
Well, I need another chunk of memory that's gonna have G-O-O--
bye backslash 0, and now let me just break it
up pictorially with lines.
So now I'm gonna get back--
this is I said before maybe address 4, 5, 6, 7,
so what's going in S2, 4, 5, 6, 7, again numbers don't matter
but that a number is there matters.
So what am I comparing?
You know, I'm kind of comparing two--
I am comparing two distinct addresses.
So even if I typed in "hello here, hello here,"
they're gonna end up at different locations in memory.
The computer is not smart enough to realize, "oh you typed
in hello twice, I'm gonna optimize this
and just reuse that same memory."
No, GetString is gonna use a different chunk of memory,
it's gonna-- thus be at a different place in RAM,
so what are you comparing?
Two addresses, and so, yup, they are wrong.
Those are not correct.
So let's see this actually, so S1 equals equals S2,
let's actually print this out.
So let me just make some temporary space here, printf,
and I'm gonna say, "S1 is percent S comma S1 semicolon,"
and actually I may put a new line in there,
and now I'm gonna also say, "S2 is percent S paste in S2,"
and let me temporary-- I'll leave that in there.
So S1 is something, S2 is something, let's go ahead
and compile this again, so let me go
down to my terminal window.
We go ahead and do make compare 1,
compiled okay, let me run compare.
I'm gonna type in hello, I'm gonna type in hello again just
as I started with, enter, okay.
So at least, they look the same,
but I'm saying I typed different things.
So let's look underneath the hood.
S1 is not percent S, that's actually printed
as what it really is, a pointer,
percent P. So this is gonna show me the address hopefully,
so let's scroll down here, and now let me go ahead
and recompile, let me rerun it, hello, hello, and wow.
So the numbers are not as simplistic as 1, 2, 3, 4,
they're much bigger, they're 32 bits but now you see
that they're so close, right?
But they're actually a few bytes off.
They're 10 bytes off from each other.
>> Notice the 3 for S1 and then the 4 for the next?
So there's a bit of an offset there, and that's just
because GetString has put one of the strings over here,
the other one over here, and they're pretty close
but they're not the same.
So how might we go about solving this?
What do we have to do in order to compare two strings?
Sorry?
[ Inaudible Remark ]
>> A to I?
Okay, so if we used A to I, ASCII to integer, we could com--
we could convert a string to a number.
But the problem here is that H-E-L-L-O is not a number,
so this is a little distinct from Caesar
where you might have typed in 13 and even though
that is a string you wanted as a number,
hello is a string, it's not a number.
So not quite, what could we do?
[ Inaudible Remark ]
>> Well, yes.
So there is in fact a string compare function.
Very, very good-- googling?
Okay, very good.
[ Laughter ]
>> So there's a string compare function.
Alright, so let's actually borrow that,
so I actually don't remember how to use it, so let me go
to cs50.net/resources, let me go to the little [inaudible]
up here, the C reference.
This has something to do with strings, so I'm gonna click
down here on the bottom left corner, standard C-string
in character functions, string compare--
okay, these are all kind
of abbreviated as is the convention.
String CMP, that sounds like string compare.
Alright, so it looks like in string.h,
there's a function called strcmp, S-T-R-C-M-P,
that stands for string comparison.
It apparently takes in two arguments,
string 1 and string 2.
They are indeed strings, because again char star is synonymous
with string.
There is a new keyword here
but you can probably guess what this means,
const-- so it means constant.
So C actually has this mechanism and you might have seen this
in man pages before where you can say just
to be extra paranoid that you don't screw
up the user's inputs, you can say, I'm gonna receive str1
and str2 but I'm specifying they're constant.
I am not gonna take any liberties with these
like a function like swap might and move them around,
I'm gonna promise to whoever's calling me that I will take
in your parameters as constant, even though you're handing them
to me by pointer as suggested by the star.
So this is just a convention that's good practice,
so no need to be too distracted by it.
So here's the summary,
the function strcmp compares string 1
and string 2, and then returns.
So this is interesting, it doesn't return a Boolean,
it actually returns 1 of 3 values.
So string comparison will return 0 if what's the case?
[ Inaudible Remark ]
>> If str1 is equals to str2.
And in this context of the documentation,
it means literally equal like the words are the same
in the-- in a human sense.
But it will also, just to help you out, return less than 0,
it probably returns negative 1
but the programmer didn't even wanna make that commitment.
He or she just said, I will commit to returning a none--
a negative number to you.
So if it returns less than 0, that means str1 is less
than str2 and if the function returns greater than 0,
that means str1 is greater than string 2.
What does it mean for string though do you think
to be less than or greater than?
[ Inaudible Remark ]
>> What's that?
[ Inaudible Remark ]
>> Oh not-- so not about [inaudible], so not correct
but it-- it could be the sum
of the values 'cause these are just ASCII characters,
but that's not it, its even more simplistic than that.
[ Inaudible Remark ]
>> What's that?
[ Inaudible Remark ]
>> Could be the length but even that's not-- not on point here.
[ Inaudible Remark ]
>> Alphabetical.
That's what it's doing.
Right, so this is actually very compelling.
If you want a function
that compares two strings alphabetically,
you actually have it in strcmp already,
it doesn't just tell you equal or not equal, it tells you
which one comes alphabetically first, less than,
or which one comes alphabetically later,
greater than, so you can compare two strings.
So now, already we have a function
that could apparently allow us to implement something
like binary search, which again we've done
on the board here with Shawn.
That doesn't just search for numbers.
Now we could actually search for words, words like Mike Smith
in a phonebook implemented in a computer program.
So let's try this.
Apparently to use this, I have to include string.h
and then I have to know about these return values,
so let's go back here.
Alright, so rather than do equal equals, I'm gonna go ahead
and get rid of my temporary pointer printing
and now I'm gonna say, not this, I wanna compare,
so I wanna call strcmp of S1, S2, if it what?
[ Inaudible Remark ]
>> Equals equals 0, right?
And again, that's just from the documentation.
If it equals 0, that means they're the same.
So you know what, I don't care about alphabetical less than
or greater than here, I'm gonna keep it simple and just say yes
or no, same or different.
So if str compare S1 S2 equals equals 0,
hopefully this will fix my bug.
So let me scroll down here, let me go-- error?
[ Inaudible Remark ]
>> Good! So-- good-- good point.
This is gonna break when I try to compile it,
what error am I about to see?
Yeah, so something undeclared, right?
So let's do a quick-- quick recompile make--
implicit declaration of function strcmp, what does that mean?
Well, that just means that I forgot to declare it.
I don't need to declare it.
I need to include whatever file it's actually declared in,
so let's go ahead and type string.h there,
scroll back down, let me recompile with make,
that seems to be good.
Let's compare.
Let's say hello.
Make sure I didn't break the only part that was working.
Okay, different things, that's good.
Hello, hello-- finally.
It's actually working.
So there is this magical function, str compare,
but you don't need these magical functions, right?
Printf is useful, it's kind of non-obvious
to me how I would actually make stuff appear
on a computer monitor.
But comparing two strings, if you understand what's going
on underneath the hood, should actually be pretty tenable.
So let's actually do this.
I'm gonna say, you are not allowed to use strcmp-- compare.
So for instance, string.h, we accidentally deleted it along
with string.c. So just conceptually, how can we take
in two inputs like string 1 and string 2, and compare them,
and say yes or no, same or different.
Yeah?
[ Inaudible Remark ]
>> Perfect!
So we could just compare each character
and what do we do as we compare?
[ Inaudible Remark ]
>> What's that?
[ Inaudible Remark ]
>> So iterate through and I start comparing the left end
against the left end, and then here, and then here,
and then here, and at what point can I make a decision
or just quit altogether?
[ Inaudible Remark ]
>> So if you see null at the end or if--
if it's a different in any location.
So let's try this.
Let me go ahead and say, okay, 4 int, I gets 0.
I is let's say less than the string length of S1, I++,
let me go in here now and say, okay so if--
how do I express if the leftmost character
of either is different?
Do something, if-- ?
Think back to Caesar, if S1--
[ Inaudible Remark ]
>> I'll say it was good so if-- I could just say is F--
S1 bracket I does not equal S2 bracket I,
so just compare their Ith locations, what can I do?
Well I can say, you typed different things, semicolon,
and then I can quit, right?
So let's say return 1,
'cause something bad happened, that's an error.
But not quite, right?
I just made a bug.
Right, so we need the brackets.
Otherwise only one of those lines will actually get
executed, so let me go back in here, let me do this.
And now, again, I feel like I got some issue still
but I'm gonna claim that if I at least get way down here,
is it pretty safe to assume that-- 1, 2, 3, 4, you--
so this is kind of my catchall.
If I get all the way through the loop
and I don't actually return prematurely and yell at the user
for having typed different things,
I can claim you type the same thing, right?
[ Inaudible Remark ]
>> Alright, why not?
What's flawed here?
[ Inaudible Remark ]
>> I still need what at the top?
[ Inaudible Remark ]
>> So I actually do need string.h, but why this time?
[ Inaudible Remark ]
>> Damn it!
Okay. So let's-- let-- I'll give you that back.
Right, so, I don't really feel
like implementing string length just yet though we could.
Right, how do you implement string length frankly?
[ Inaudible Remark ]
>> Yeah, just start at the beginning and then count, count,
count, count, count, so we'll come back to that
or maybe assign it on the quiz or something,
but it's pretty easy to implement string length
if all you have to do is take in a string, start iterating
over each of its characters, and the moment you hit backslash 0,
stop counting, you're done, you found the end of the string.
Alright, so let's-- we'll give you str length
but not string compare, right?
So I'll take away Google from you.
How about that?
So now, we can't string compare it with the function
but we can do it this way but I actually think this is flawed
for a couple of reasons still.
Yeah?
[ Inaudible Remark ]
>> Yeah.
[ Inaudible Remark ]
>> Exactly.
Let's see what happens, maybe nothing, maybe something.
Let's see what happens if I save it as is, I go back here
and I recompile and I type in S1 that's pretty long,
but an S2 that's pretty short, right?
Because how many times am I gonna iterate according
to my four loop at the moment?
The length of S1, so it feels
like there's a bad opportunity here, so let's run this.
So say something like I am a very long string hello,
okay, S2-- okay, it worked.
Not broken-- correct.
Correctness 5.
Why is it actually flawed?
Can we still break this?
I just need to stall for a moment here.
Okay.
[ Inaudible Remark ]
>> What's that?
[ Inaudible Remark ]
>> Oh okay, so cat and cat-- oh yeah, you know,
I'm kind of an idiot, right?
So what are we doing?
I'm comparing a really long string
against a really short string, but guess where they differ?
>> At the first location, right?
So, not a problem, I'm actually catching that at the beginning.
So let's-- let's control C, let's start this over,
and let's say caterpillar, enter, did I spell that right?
[ Laughter ]
>> Really?
Hang on, I'm giving us-- there we go.
I-- I had to take to go back.
Okay, so-- damn it, I forgot what I copy pasted.
Caterpillar, alright.
Come on, that is not a word I've had
to type very often in life, alright.
So here we go, caterpillar, okay, cat.
Switched them around, cat, caterpillar.
[Laughter] That was only a surprise to make.
So, what's going on here?
Well, now, we have a substring issue, right?
So cat is obviously a substring, a prefix of caterpillar,
and so they do in fact match but if I'm only iterating
from the length of 0 to the length of--
rather, from 0 to the length of S1, I'm only gonna compare
like the first three characters, C-A-T,
and then I'm gonna call it quits.
But in the opposite direction,
it didn't actually happen this time, but if I [inaudible]
around enough it might.
What could happen if the differences
of these strings is long enough?
So I'm gonna start comparing C-A-T,
but what am I gonna hit once I get to the fourth location,
if the one word is caterpillar and it's first,
and then cat is the second word.
So it null, but null is not equal to C-A-T-E, it's not equal
to E, and so it actually still catches that scenario
and we don't overstep the bounds of the array because we
at least stopped there.
But flip them around and we do confuse cat
for caterpillar, or vice versa.
So what's a quick fix here?
What's one way we could fix this?
So we could get the longer length first,
so we could say something like if string length of S1 is less
than string length of S2, then we could go ahead
and say the maximum length is equal to str length of S2,
but I'm kinda pushing it now
with design issues, let me put max here.
Is this correct?
And then I can say, let's change this to max.
So this kind of helps but I'm still kind
of doing something stupid.
What's the quickest way to just check
if two strings are not the same?
[ Inaudible Remark ]
>> Right, if it's not the same length, right?
I could actually have a check like if string length
of S1 does not equal the string length of S2, you don't need
to iterate over anything, you can just immediately yell
at the user and say, obviously not the same, right,
because they are different lengths, and then so long
as I have my curly braces here, I can return one here,
and then if I get to this point here, now does it matter
which string length I use?
So now, I can use either because they're equivalent
so there's a couple optimizations
that are possible here, but now I can do response to the user
in a couple different ways.
I can say they are obviously the different
because they're not even the same length
or same length but different things.
Now, hereto, not perfect design, so correct I think at this point
but where is an opportunity for better design in that loop?
Yeah?
[ Inaudible Remark ]
>> Okay, so what if we did less than or equal to string length
of S1, what would that have us comparing,
in addition to the string itself?
[ Inaudible Remark ]
>> So it would have us comparing the null character, and now just
to push back, is that necessary?
So this is not incorrect but it doesn't really gain as much,
and if anything, we're spending an extra bit of time now
because if we already know these lengths
of the strings are the same, and we already know that in C,
every string ends with backslash 0, it's sort of a waste
of our time to bother comparing the backslash 0,
we can stop one short of that, so not incorrect
but we're just wasting an extra iteration.
Yeah?
[ Inaudible Remark ]
>> Yeah.
[ Inaudible Remark ]
>> Exactly.
So this is subtle and frankly it's--
it's kind of elegant, right?
We've kind of preached the idea of making these succinct lines
of code that are just very straightforward,
but the problem here is that the condition
in a four loop is evaluated not once,
but on every iteration, right?
'Cause you have to check, is it time to break?
Is it time to break?
So, every time you check that condition, you're comparing I
against the current length of S1,
but what is the current length of S1 on every iteration,
what's the same as the very first one.
So a common technique would be, don't call functions
in your conditions, rather move this over here,
introduce something like N and assign it to the string length
and then iterate from I to N. Even here,
there's still an opportunity
for slight improvement 'cause what am I doing that's still
slightly foolish?
[ Inaudible Remark ]
>> I called it earlier as well.
So, you know, not as an expensive of a mistake.
I mean frankly the code is kind of elegant here
and is the strings are pretty short, it doesn't matter
if I'm spending a few extra cycles,
but still I should probably compute string length
of S1 once up top.
Put the result perhaps in a variable
and then actually proceed with the comparisons.
So, all of these though can go away, of course,
if we just use the string compare function.
But what's it doing and what's a lot
of these functions doing in the documentation?
It's just implementing these fundamentals
that years ago people got tired
of every time they wanna compare strings, writing like 10 lines
of code, you collapse it to one line, str compare, and thus,
do you hopefully start to see really the motivation
for writing things as functions
and not just writing everything in main.
So I've got some more craziness in a bit,
let's take a 5-minute break,
and return with the damage we can do with pointers.
[ Pause ]
>> Alright.
So we're back, first, any questions on pointers
and just what they are?
Alright. So let's now start pulling off some
of these training wheels.
So in the CS50 Library, we've been taking these functions
for granted and they've been useful in that they handle all
of the getting of input from the user from the keyboard.
They even do some error checking whereby GetInt if you type
in as we've done monkey, it will say retry, retry, retry,
until the user actually gives you an integer.
But let's focus now on GetString because clearly all this time,
GetString has been doing some interesting stuff with us
with regard to pointers.
This is an excerpt from cs50.h,
the actual file you've been including.
This file lives in a special directory in the appliance
as it would on a typical computer system.
For the curious, it happens to live
in a directory called slash user slash include,
this is where a lot of dot H files are.
In fact, if you recall in a Linux environment,
if you type LS that will list the contents of a directory
and if I do slash users slash include,
notice there's a whole bunch of dot H files in my appliance.
Among them over there on the left is cs50.h. Not all
of them are necessarily in those same directory
but we might see a couple of familiar ones if we go to--
I don't think we've used any of these just yet.
Sorry, oh and crypt, so we've used crypt there
for the Hacker Edition and then also--
[ Inaudible Remark ]
>> -- the CS50, obviously, dot H the header file.
So here it is up at the top, the CS50 header file only contains
that synonym for string, char star.
Remember we saw this a few days ago.
If I scroll all the way to the top,
we introduced this key word, typedef,
which we won't use terribly often.
We will use it for 1 or 2 P sets,
but typedef just defines a type
that char star is henceforth gonna be known as string,
that's where that came from.
But if I scroll now down to the documentation for GetString,
we pretty much been taking for granted how it works
but let's actually read CS50's official documentation.
It says, GetString function reads a line
of text from standard input.
Standard input just generally means the keyboard, the user,
and returns it as a string, otherwise known as char star,
sends trailing new line character.
So even though all this time we humans have been hitting enter
to give the computer a-- a string, we presumptuously, CS50,
we just throw away that backslash N,
because we don't want all of your strings
to have a carriage-- to have a new line in it.
So notice now if the user inputs only backslash N,
it returns this thing, so double quote,
double unquote means the empty string.
It is a string, how many bytes are taken
up to represent quote, unquote?
What do you think?
Zero or one?
Any zero? One?
Okay, so it is actually one.
Why? Well, every string, even if it's of some crazy 0 length,
still has to have the backslash 0.
Why? We have to be able to know how long this string is
so that you're not just handed some garbage value.
But just in case it turns out that there is
and we've seen this word before, NULL, in all caps,
that represents, as of today, a pointer-- a special pointer,
the pointer to memory address zero.
So a very useful thing about computers is that you
as programmers are never ever, ever allowed to store anything
at a location number 0 in a computer's RAM.
This is simply because so that there's at least one place
in memory that is guaranteed not to contain a legitimate value,
so that we can reserve that address, 0,
as a special constant.
So henceforth, if we ever wanna check
if a pointer is actually legitimate or not, that is,
is there a value there or is it maybe some garbage value,
we're gonna start checking for NULL in all caps.
So this function GetString apparently returns NULL
if there's an error
or if there's no user input whatsoever.
>> Now this is hard to induce but it turns out for the curious
if you hit control D whenever asked by a program for input,
sometimes just hitting control D will crash a program
because control D typically means I give you no input
but stop asking me.
And that is different from hitting enter,
which does give you some input,
it gives you backslash N. Now we have
to catch this and we soon will.
So, leading and trailing white space is not ignored.
So this is to say if the user hit space, space,
space H-E-L-L-O, you're gonna get back
to the space bar characters and so forth.
So ultimately we'll see eventually the implementation
of GetString but at least it seems
that sometimes this function might return null.
So we're gonna have to start checking for this.
So let's do the following, I'm gonna go ahead
and create a new file, we'll call it copy1.c,
and let's now try to oops,
let's try to actually copy a string rather than just compare.
So let me zoom in.
I'm gonna go ahead and do int, main,
void and I'm gonna go ahead and let's say first ask the user
as before, say something.
So we have something to play with.
And then I'm gonna do a no more string char star,
S1 gets GetString, alright?
And now I need to start getting into a new habit.
We've not mentioned as much, not expected as much,
but now that we know
that GetString could return a null pointer where null is bad,
we better start checking for this.
So if S1 equals equals the special constant null,
we should probably do something like printf, an error occurred
and then backslash N and then return 1,
or whatever nonzero value.
Alright, so what-- when might a function
like GetString ever return an error?
When might it return null rather
to signify an error, what could go wrong?
I can think of at least two things.
One I already answered.
Control D, so whatever that thing is,
control D apparently can do bad things
and so null might get return.
Now this is not a terribly worrisome case
because most humans are not gonna accidentally hit control
D. But again, there's another more reasonable approach.
How else could GetString fail potentially?
If the string is too long, right?
If I spend half an hour typing letters at the keyboard
such that I type in like 2 billion and 1 characters
or 4 billion and 1 characters, more characters
than I have bytes of RAM, it's possible that GetString,
which happens to use that function called malloc,
memory allocation, which we'll see before long,
what if they just can't give me two gigabytes worth
of memory just to fit some user's crazy long essay?
So how does GetString signify that error condition?
It's got to return a special value.
What's that special value?
It's gonna go ahead and return null.
Now in the past we might have returned false to signify
that something went wrong.
But if GetString is defined as returning a string
but a string we now know is just a pointer, we can't return false
because false is what?
It's a Boolean.
we have to return a pointer so we need to see
that it gives us a special pointer that's reserved
for error conditions, and so it commits to returning null
so now we can check for this.
So this is as simple as this is, this failure to check with an
if condition, something as simple as this
in a program is a huge source of bugs in people's programs,
as well as relatedly a huge source of hacking opportunities
if you are not checking the values of pointers
and are potentially doing things with pointers
that are just garbage values.
And we've already talked about the notion of garbage values,
they apply to pointers as well.
Alright, so now let's go ahead and make a copy of this thing.
I wanna make a copy of S2-- of S1 and call it S2.
So let me say char star S2 gets S1.
Alright, on the left hand side I'm allocating a pointer called
S2, I'm assigning it the value of S1.
And now I'm gonna go ahead and do a printf.
S1 is percent S backslash N and paste in S1.
And let me do the same for S2.
S2 is percent S, S2, okay.
And let's try this.
Let me scroll down, let me go ahead and do make copy 1.
Oh my god, so many errors, what's wrong here?
So, a couple of things, right?
I skipped this part, so include cs50.h, alright,
now I need that for sure for GetString,
let's see if that solved all my problems.
This does not mean I have six
of my problems rather I could just have one
that has a cascading effect.
Make copy 1, no, printf, damn it!
I need that one.
Alright, so it's probably just a good idea to get into the habit
of almost always using these things.
Let's see if I've solved all my problems now.
Make copy 1, whew look out.
So copy 1, enter, say something, hello.
Oh nice, my copy program works.
Okay, but not quite.
Let's try something to prove
that I'm actually not so good at this.
So let me try to capitalize-- capit--
I don't need to Google this.
Capitalize just one of the strings.
And I'm gonna do this as follows.
I'm gonna capitalize just S2, and how do I capitalize it?
Well, I'm gonna capitalize its first letter like this
by 2 upper, can I do this?
S2 bracket 0, you might have used this function before
in Caesar or Visionare or if not 2 upper should.
Just uppercase this one-- a letter.
But let's see if I need to include anything.
Let's try to run this.
Implicit declaration of function 2 upper, so no problem.
So two upper is a string function.
So let's go back to the same documentation.
Two upper, C type, so here's another file.
We actually glimpsed that a moment ago in my directory,
but I need to do C type.
So let's go up here.
Include ctype.h. Now let's zoom in on the bottom,
try recompiling one last time, it looks good.
Now let's run copy 1, hello?
Hmm, now kind of interesting
but hopefully less interesting having just spent all the time
talking about what a pointer is and what a string is.
Why is this program flawed?
I capitalized S2 but apparently the computer decided
to capitalize S1 also, but why is that?
>> They point to the same place.
>> They point to the same place, exactly.
So what's really happened?
Well, I didn't type goodbye,
so let me delete this part of that story.
I did type in H-E-L-L-O.
I did create S1 and S1 is apparently pointing there.
But when I do S1 equal sign S2, or rather S2 equal sign S1,
what's really happening?
I'm not copying all of this.
I'm literally copying S1 putting it into S2.
So what ends up getting written here?
1, 2, 3, 4, 1, 2, 3, 4.
So when I go to S2 bracket 0, bracket 0 is
at what memory address?
1, 2, 3, 4.
Where is that on the board?
Well, it's over here.
So what did I change the H to?
A capital H, but wait a minute that's the exact same chunk
of memory that represents the S1 string, but just so happens
that now I do have copies but have copies of the pointer,
not copies of the whole string.
Now as an aside, I've been making
up 1, 2, 3, 4; 4, 5, 6, 7.
But the reality is these numbers are almost always uninteresting
to us.
So generally what the world does as we'll see
in clay before long is the world just says if it's a pointer,
let's just go with something much more intuitive.
If that's a pointer, just point on the board
to whatever it is you're pointing to in memory.
So we would typically draw pointers as arrows pointing
at something but realize that what's really inside
of here is a number like 1, 2, 3, 4.
But it's kind of uninteresting to keep making up fake numbers.
So we'll typically just draw arrows.
So just conceptually, what's the solution to this copy problem?
How do we actually duplicate the string?
What do we need to do in order
to make a genuine copy of S1 and call it S2?
Sorry? Yeah.
>> Individually copy each character.
>> Okay, we need to individually copy each character,
but into what?
>> Into like another--
>> Yeah, so really what we need to fix this problem
and finish this story is we need the same amount of memory
that has as many locations.
I don't know what's here by default, 'cause again just
as with variables when you allocate memory,
you're gonna get a whole bunch of garbage, it's up to you
to populate it with actual values.
So that begs the question, how do you create an array
of a specific size dynamically?
How do you dynamically allocate memory?
Well, it's actually pretty easy.
Let me go up here and I'm still gonna check null.
But before I do this copy, what I'm gonna do is this.
I'm gonna first say S2 is not S1
but rather char star S2 equals the return value
of this fancy new function malloc.
And just to oversimplify for a moment, I need 1, 2, 3, 4,
5, technically 6 bytes.
So I'm gonna hard code this ever so briefly.
This function, malloc, called as follows,
will hand me back 6 bytes of memory
which pictorially would look like this.
They're at some other memory address, but how do I know
at what memory address malloc allocated me memory?
Via it's return value.
So what malloc does if it can is it allocates memory for you.
It then returns to you the address of which of the bytes
of memory it just allocated, which of the six bytes.
The first, and it's gonna be up to me
to make sure I put a special sentinel value,
special backslash 0 at the very end
so that I don't forget how long this chunk of memory is.
Now I probably shouldn't hard code something like 6.
How can I decide dynamically what the length
of S1 actually is?
Yeah, so a sterling of S1 like this.
Okay, so plus 1.
So here it's okay to hard code
that plus 1 'cause you always need plus 1 byte
for that special backslash 0.
So to be clear, when you call string length as you've done
for a week or so perhaps in your own code,
it returns the actual human length of the string,
it does not include the backslash 0.
>> So when you're allocating memory for this,
you actually do need to do so.
Now as an aside, the official version
of this code that's posted
on the course's website actually has a slight modification,
whereby I have multiplied by the size of a char.
So this is not strictly necessary 'cause
on almost every system a string is composed
of chars and a char is 1 byte.
But just in case my program ends up getting used for 20 years
and is eventually used on a computer
that actually uses 2 bytes for characters.
And this has already started to happen.
There's a system-- there's an alternative
to ASCII called Unicode that actually uses at least 2 bytes.
This is particularly helpful for Asian languages.
We're having only 8 bits.
It's insufficient to represent all possible symbols.
So just in case this program is run on the computer
where characters are more than 1 byte,
there's a special operator called sizeof that if I call it
and pass in the name of the data type I'm trying
to allocate memory for, it will say 1.
Or maybe on fancier systems, it will return 2.
So technically, even though this is getting a little scarier
versus the just malloc 6 that I hard coded,
this is now a bit more rigorous.
So now I have memory, now I have this chunk of memory.
How do I actually populate it with values?
Well, how do I go about copying one string into another?
What about for int I get 0, I is less than--
oh wait, let's not make that same mistake again.
N gets the string length of S1.
I is less than N, I++, and what do I wanna do?
S2 bracket I gets S1 bracket I, and is this quite right?
Slight-- ever so subtle bug.
Okay, besides saving it, thank you.
What else?
I wanna click here, I wanna fix this here, I actually--
I need to fix-- I can fix this in a couple ways.
I probably wanna do something like this, 'cause I also want
to copy that backslash 0, so it's okay in this case
to go one extra because I know it's a backslash 0,
so now I've actually copied the string.
But something could still go wrong.
What happens if what the user is trying
to copy is again a huge essay that they've typed in?
I need to check the value of some-- of some variable here.
If S2 equals equals NULL,
what I should really do here is something like printf,
an error occurred EG out of memory or something like that.
And then I wanna go ahead and return something other than 0.
So these are the habits you now need to get into.
Anytime you're dealing with memory, it's gonna be super easy
to have your code, segmentation fault, core dump,
all because of misuse of these things called pointers.
So now if I capitalize, should this work?
If I leave the rest of my code alone?
Let's go down here, let's go ahead and rerun--
copy, big syntax error, implicit [inaudible] of string length,
so I'm back to making those old mistakes.
Alright, include string.h 'cause I remember where that came from,
and it's telling me I have a syntax error somewhere?
[ Inaudible Remark ]
>> Semicolon, right there.
Perfect. Alright, so now let me try recompiling,
let me rerun copy, hello, enter, nice.
So now, one is lower case, the original;
one is upper case, the new one.
So what's really going on here?
So, here's an example that actually has a bit more syntax
and this time it uses int.
So, here's a function main,
and let's say we allocate a variable X
but it's this time not an int, it's gonna be a pointer
to a value X-- sorry, rather a pointer to an integer,
so let me erase this and draw a picture consistent
with what's going on here, alright.
So, what's going on?
When I declare int star X, that's essentially like saying,
give me a pointer, call it X and I don't know what's there,
so it's some garbage value, question mark.
Then I do the same thing, give me a pointer , call it Y,
it's gonna be the same size but a different chunk of memory,
question mark, 'cause I don't know what it is.
Now, X gets malloc size of int,
so malloc again allocates memory,
how much memory is gonna come back?
How many bytes based on this call?
How big is an int?
So an int is 32 bits, otherwise known as 4 bytes,
that by coincidence is identical to the size of a pointer
in the appliance, so how do I draw this?
Well, I keep saying that 4 bytes or 32 bits is a square,
so this is what malloc just gave me.
And what got stored here in X,
according to the third line of code?
So malloc allocated this one chunk of memory
which is 32 bits-- or 4 bytes.
Why? Because the size of an int is 32 bits.
What does malloc return in general?
The memory address, the first byte of whatever chunk
of memory it just allocated, so maybe it's 1, 2, 3, 4,
so we would draw 1, 2, 3, 4 here.
But again, we're kind of past that point.
We can now just generalize and say, what is an X?
It's a pointer to that chunk of memory.
Alright, and how about Y?
What's happening now with Y?
Well, let's see.
Well, it turns out that this star notation can actually be
used in two different ways.
One, to say that something is a pointer,
and another to say go there.
So before when I had this piece of paper and I said 1, 2, 3, 4,
I handed it to my friend, when my friend went there,
you expressed the idea of going to a pointer
by saying star pointer name.
You don't specify the keyword int again, you just say star X,
means go to the address of X that's on that piece of paper,
so here's X, when I say go there, you can literally think
of it as following the arrow to see where you end up
and what do I put here according to the line of code?
42. So that int goes there.
But here's a bad thing, now I'm saying star Y gets 13.
So here's Y, where do I go?
Question mark, you can now think of as being like, you know,
who knows where this actually is, it's pointing
to some garbage value.
So where am I gonna go?
I'm gonna follow this pointer and then bam!
I'm gonna put 13 here but that is not my memory.
What happens when you touch memory that's not yours?
Segmentation fault, right, core dump,
if you touch memory that's not yours.
Now, this is bad, so if I then do though Y equals X,
Y equals X, how does the picture change?
Y equals X?
So I change its garbage value, I have no idea
where that was even going.
So if I say Y equals X, well, this is literally like saying
if this is 1, 2, 3, 4, put 1, 2, 3, 4 in Y. But pictorially,
it's just saying point to the same value.
So now if I say star Y gets 13, let's bring it home,
what changes on the board?
Star Y gets 13?
42 becomes 13, so what is the value of star Y?
13. What is the value of star X?
Also 13. But this program might not even gotten this far
because of this.
Lets see what Binky has to say on the same subject.
[ Pause ]
[ Music ]
>> Hey Binky, wake up, its time for Pointer Fun.
>> What's that?
Learn about pointers?
Oh goody!
>> Well, to get started, I guess we're gonna need a
couple pointers.
>> Okay, this code allocates two pointers
which can point to integers.
>> Okay, well, I see the two pointers but they don't seem
to be pointing to anything.
>> That's right.
Initially, pointers don't point to anything.
The things they point to are called pointees
and so [inaudible] is a separate step.
>> Oh right, right, I knew that.
The pointees are separate or--
so, how do you allocate a pointee?
>> Okay, well, this code allocates a new integer pointee
and this part sets extra point to it.
>> Hey that looks better, so make it do something.
>> Okay, I'll dereference the pointer X
to store the number 42 into its pointee.
For this trick, I'll need my magic wand of dereferencing.
>> You're magic wand of dereferencing?
That-- that's great.
>> This is what the code looks like.
I'll just set up the number and--
>> Hey look, there it goes.
So doing a dereference on X, follows the own,
access its pointee, in this case to store 42 in there.
Hey, try using it to store the number 13
through the other pointer, Y.
>> Okay, I'll just go over here to Y and get the number 13 set
up and then take the wand of dereferencing and just-- whoa!
>> Oh hey, that didn't work.
Say, Binky, I don't think
that dereferencing Y is a good idea 'cause you know setting
up the pointee is a separate step
and I don't think we ever did it.
>> Good point.
>> Yeah, we-- we allocated the pointer Y, but we never set it
to point to a pointee.
>> Very observant.
>> Hey, you're looking good there, Binky.
Can you fix it so that Y points to the same pointee as X?
>> Sure, I'll use my magic wand of pointer assignment.
>> Is that gonna be a problem like before?
>> No, this doesn't touch the pointees.
It does changes one pointer to point
to the same thing as another.
>> Oh I see, now Y points to the same place as X. So-- so wait!
Now, Y is fixed, it has a pointee, so you can try the wand
of dereferencing again to send the 13 over.
>> Okay, here goes.
>> Hey look at that.
Now, dereferencing works on Y,
and because the pointers are sharing
that one pointee, they both see the 13.
>> Yeah, sharing-- whatever.
So are we gonna switch places now?
>> Oh look, we're out of time.
>> But--
>> Just remember the three pointer rules.
Number 1, the basic structure is that you have a pointer
and it points over to a pointee, but the pointer
and pointee are separate, and the common error is to set
up a pointer but to forget to give it a pointee.
Number 2, pointer dereferencing starts at the pointer
and follows its arrow over to access its pointee.
As we all know, this only works if there is a pointee,
which kind of gets back to rule number 1.
Number 3, pointer assignment takes one pointer and changes it
to point to the same pointee as another pointer,
so after the assignment, the two pointers will point
to the same pointee, sometimes that's called sharing,
and that's all there is to it really.
Bye-bye now.
>> This is Binky.
This is Nick Parlante of Stanford University.
This is CS50.
We will see you next week.
[ Applause ]