all right so I know you guys are
thinking about the mnsure stuck on a
midterm a practice problem and you want
to ask about it you feel free to do that
it's a good way to get your question
answered we also have office hours today
and tomorrow and so on and there's a
layer now in terms of what we're doing
this week I would expect that you guys
would focus on midterm study and most of
this week our midterm is on Thursday
because we hate you you know I mean
people want to work on it but I would
generally not expect you to start on it
until after you've done your exam it's
due in the middle of next week
so you could totally focus on the exam
right now finish the exam then you've
got all the finish and hey if that's not
enough you can take a late day so I you
know I think you'll have time to focus
on each individual cash posted on the
exam section of the webpage you can look
at that when you're ready to look at
that in terms of lectures I basically
think of the midterm as covering up
through last Friday and then starting
today I'm not going to explicitly test
you on this stuff from these lectures
here on the midterm exam so I guess that
might cause you to tune out or leave or
whatever but you still need to learn it
so that's the plan okay that's the plan
bless you okay so anyway what we're
gonna do today is we've been learning a
lot about linked lists we also learned
last Monday about how to implement a
collection using an array we made a
collection called array stack and I want
to revisit all of that stuff again today
the theme of today is going to be
talking about how to implement
collections as classes both with arrays
and with linked lists and that's also
going to be the theme of your fifth
homework assignment
we'll be due next week okay so let's go
to our slides
remember this last Monday we wrote a
class named array
an internal structure of an array events
but then externally the class was
presenting itself as a stack and if you
push elements in the stack it would add
them to the end of their way so we
maintain an array in the size and the
capacity which is the overall length of
the array so yeah I want to go back to
that class and add a couple of features
to it today that's not really how linked
lists are usually used by a client on it
and so that's a slightly different style
than what we have been doing so I'm
going to talk about how you would change
our code to be in that stuff so that's
the plan for for now so let's go back to
that array stack let me just open that
code with you guys I have a cute creator
project the main code could say things
like this you know make an array stack
and you know add some elements by
calling push so push some mints and then
print the two string of the stack and so
the code we wrote will that's kind of a
small font you can push things onto the
stack and then you'll see the stack get
bigger okay so that's not too shocking
the bottom is on the left and the top is
on the right and then when you pop
things off the stack or peek at them
it'll give you the last element or the
top element from from the stack that's
what we wrote last week okay yeah so
let's learn about a few other things you
can do I want to talk about the word
Const you may have seen this pop up
occasionally in assignments or starter
codes or lecture codes or whatever we
haven't really talked about it
Const just means constant something that
cannot be changed in Java there's a
keyword called final that has the same
meaning JavaScript I think has a Const
keyword Python if you learned Python
does not have any constants concept but
anyway most languages have a concept of
this where you can say this value
doesn't change so there's a couple
different ways you can use cons
you can use it when you're declaring a
variable or a parameter like your first
example there if you pass something
that's constant means the call cannot
change it now you don't need to use
constant you're passing something simple
like an int because it doesn't really if
you change it or something like this
now some of those methods are supposed
to modify the vector modify the grid but
some of them aren't and if the method
isn't going to modify the thing it's
good practice to declare it as being
constant the reason it's good to do that
is because it kind of tells anybody
looking at the code like this method is
not gonna change this thing and if you
declare something confident function
food tries to change the state of the
object it will not compile so if the
bank account class has like a deposit
method that changes the balance of the
account it won't allow you to call the
deposit method inside of the foo
function so that's cool it helps catch
potential errors where you might be
modifying an object unintentionally
that's cool there's another context in
which you can use the word const that is
if you are writing a class you can
declare that one of your methods is a
const method and what that means is
you're saying this method i promise if
you call this method on me i won't
change the state of myself if i'm a bank
account you call get balance on me that
won't change anything about the accounts
internal state it will stay constant
okay to use of the word const are
related because the first one only let
you call methods from the second one so
like if you have a parameter this time
it will only allow you to call methods
that are declared as being cost on it
so it's good practice when you're
writing a class to look at all your
methods and figure out which ones don't
change the object state and write the
word constat the end of them so if you
look at our array stack that we wrote we
have a file called array stack H here we
have a push method we have a pop method
a peek method we have is empty and to
string which of these methods are
contour should be Const
what's why peak right you can't put
Const on push or pop because the whole
point of it is to modify the state of
the stack right any others I think is
empty and two-string are also ones that
you know you can call two straight a
hundred times it doesn't modify what's
in the stack right now small detail if
you declare your methods this is in the
dot H file array stack dot each if you
declare your method as being Const then
you also have to go to the dot CPP file
and you have to go down to the same
method here and you have to put Const
there as well if you forget in one place
or the other you'll get that lovely
error about a symbol not defined for
architecture x86 underscore six four and
then you'll get stuck and confused on
that so anyway if you add constitute
your methods it doesn't really do
anything visible to the client but it's
good practice to do it it also you know
it helps avoid like if the client of the
stack like here's the stack client if I
say void foo array stack reference stack
if I try to say stack push 42 you know
law it's not constant after all then it
should give me an error oops it didn't I
think it's because I need to rebuild the
project I need to clean it and rebuild
it because if you change your method to
be in concept doesn't always notice
right away oh no wait wait sorry I'm
stupid
the reason it's supposed to object to
that is if you were to say Const here
then it wouldn't want to let you modify
the stack so that's why it didn't
complain I was expecting a compiler if
it finishes by that anyway you can't
call push because the parameter is
declared as Const oh I think I saw it
there the error is a little bit Spalla
fires whatever it just means that you
can't call that method on a Const stack
if I were to remove Const then the code
would compile but now it doesn't okay
but by contrast I could call stack
dot peek I could call stack dot is empty
and that compiles just fine okay
so if I asked you to write a class I
might say I want you to make methods
Const as appropriate that means if they
don't modify the state of the object put
the word Const at the end of the method
head okay so that's Const be questions
about Const
so yeah what what modifications D need
to make so remember when we're writing a
class there's kind of two sides to that
there's like you write the class and
then there's also client code that uses
the class sometimes you write both of
those pieces of code sometimes different
people write them for example the
Stanford library we wrote vector H you
are using vector H as a client so you're
asking me what modifications need to be
made it depends if you're the client or
the author of the class or both if
you're the author of the class you do
that if you're the client of the class
you might be choosing to do that but
that's more dependent on your client
program and what your program is doing
if I'm using the stack in a way that
isn't modifying it I might want to say
Const on my heading there okay well I'm
just kind of surveying showing you some
other features of classes that are
relevant
also if this had not said Const on is
empty and then also here not and then
here if I try to call it it shouldn't
compile even though we could look at the
coda we could see that is empty doesn't
modify the state of the object the fact
that the method doesn't say Const the
compiler doesn't trust us it won't
compile the code so I'm gonna put it
back but yeah it's not so much whether
you modify it's whether you say that
you've modified and then of course if we
said Const what we'd lying like in here
we tried to do like size plus plus or
something that shouldn't work either it
won't let us so you can't say Const and
then lie about it okay let's just cover
some other stuff here's an interesting
C++ feature it's called operator
overloading this is the coolest or the
worst feature ever depending on the kind
of person that you are operator
overloading is redefining or adding
meanings to the built-in operators of
the language so like you can define what
the plus operator means when used on
your class like I don't know if you've
ever noticed this before but if you have
a vector you can use operators like +
equals on it have you ever seen that I
haven't talked about it very much but
like over here if I include vector dot H
vector dot H if I make a vector and I go
like you know vector of strings V and
you normally would say like VI pad you
know Marty you do like that right but
you can also write V plus equals Marty
that's weird it lets you do that it
compiles it runs it behaves the same way
as ad and so the reason that works like
I'm taking a vector plus a string in a
language like Java that wouldn't make
any sense that would be a compiler error
in C++ you can do this thing called
operator overloading you can basically
tell the compiler hey if you're using
this operator with these data types
here's what you should do here's what
that should turn into and that's that's
operator overloading and
so that is you basically write a
function describing the operator but the
name of the function is land operator
plus or operator times or operator
equals or whatever it's the word
operator followed by the actual
characters of the operator and then you
have parameters and you fill in the body
of what you do so look you can do all
kinds of weird stuff with this feature I
personally think it's a bad feature
because it makes it so that like any
given statement with any given operator
could just do some random thing that
they overloaded it to do I think it's
kind of dangerous but the guidelines of
the language they say that you should
only overload operators if the meaning
is obvious so like if you're taking you
know two bank accounts and you do a
minus operator between them it doesn't
really make sense what would that do you
know so don't do that but a really
common use of the operator is to make an
object printable so there's a there's an
operator you can overload to do this now
look at our array stack I'm gonna delete
this vector for a minute if you have an
array stack and you want to see what's
in it we have this method called to
string right okay well what if I just
wrote C out stack that's what you can do
with a vector that's what you can do
with a map right you could just say C
out my vector you know printed it
actually doesn't let you do that because
C++ doesn't know how to print an array
staff and you might say well but it's
obvious you print it by calling to
string on it well C++ doesn't understand
that that's how you to print a stack you
have to tell it so the way you tell C++
how to print something is you actually
overload this less than less than
operator and so that looks like this you
write an operator called operator less
than less then the parameters are a
little bit confusing it takes an output
stream reference oh stream that output
stream is like C out or a file out those
are all post stream objects and it also
takes your value that you want to print
those are the two
it takes so basically you just print the
thing out to that Street and then you
have to also return the output stream
the reason you have to return the output
stream is so that you can chain together
multiple less than less than Zhan one
line it's kind of a subtlety but look
this is this style that you have to use
to write this operator this is the exact
setting that it has to have so if you
want to make your array stack printable
well a lot of people coughing and
sneezing today I hope everybody's
feeling well don't know hugs after class
I'm calling no hug with me policy you
know each other not mean so if you want
your object printable what you do is you
come down here this is this is in the
array stack dot H you go down to the
bottom of your class underneath the
class it's actually not inside the class
and you say oh stream reference operator
less and less then which takes an oath
stream reference which I'll call out and
it takes an array stack reference called
stack so you're saying you're declaring
I'm going to implement this overload for
this operator you always declare things
in an H file with a semicolon
then in the array stack cpp somewhere
you write that same operator but with
curly braces and you actually write the
body of how to do it so how do you do it
well just pretend that you're printing
the stack how would you print the stack
well I mean over here in the client we
said you know see out stack talk to
strain right so you just do that so you
could just come over here and say see
out stack dot to string
indle there's a couple things wrong this
is pretty much the idea you just include
the code of how to print the thing but
there's two things that are wrong with
this one is you're not supposed to
include the endl because the person
printing the snack might not want and
endl you should let them decide if they
should print an endles so i'm going to
delete that part the other part you
should change is this operator can be
used to print a C out and it can be used
to print two files and any other kind of
output stream so really this parameter
called out is the thing that you're
printing the thing to so you just say
out that means this parameter here
whatever the output stream is that
you're printing me to send my to string
to that stream so you compile this now
remember
the original thing didn't support
calling just print with stack here but
now I compile and oh wait I have an
error that says I didn't return anything
so back here after you print the out
stack to string you have to say return
out return that you returned the same
output stream that was passed to you
that's always what you do so basically
every operator less and less then looks
about like this it's usually just a
minor to a code I compile this and I go
back to the main program and now it
compiled it allowed me to print the
stack like that and I print it and I get
the same output where it it prints the
stack like this now if you don't believe
it because the output didn't change I'll
try to convince you so first of all I'm
going to remove all the things that say
to string so it's supposedly calling our
operator in the main client here but I'm
also going to go to the array stack and
I'm gonna change it to say Booya
something like that what's up so I'm
just gonna put some silly stuff on the
sides of the string and then when I run
it it is going to print those messages
on the sides so basically this was
printed to the output stream whatever so
it's calling the operator that we wrote
so that's how to make an object
printable I'm not gonna spend a lot of
time on it but I mean in a lot of
languages like how do you make something
printable in Java you know what method
do you have to write
bless you yeah
well system.out.print lien is how you
print things but if you say print lien
and you pass an object of type of bank
account it usually just print some kind
of gibberish how do you make it so that
print lien on a bank account print
something meaningful what do you have to
write in the bank account class yeah
yeah to stream ends out you're gonna say
to sir yeah sorry about that um yeah to
string method so actually this to string
that we wrote if you had just written
that Java would automatically know how
to print objects of your type C++ if you
want to make things principal you have
to write this in fact you don't even
have to write a to string method to
string it's not a special method in C++
so the fact that we had it was just
because I thought that might be more
familiar to you guys cuz a lot of you
come from Java but this method is not
special okay so I'm gonna ask you to
write one of these operators on the on
homework 5 so does this general syntax
seem okay to you I mean it's a little
weird looking but basically copy and
paste it change a race back to your type
and then do the equivalent of this or
whatever and then you're good any other
questions
okay that's how to make objects
printable let's see what's next I'm
gonna jump ahead a little bit here here
okay I want to talk about something
called a destructor or a destructor is
the opposite of a constructor you know
what a constructor does constructor is
code that runs when an object is being
created it's being born destructor is
code that runs when the object dies when
the object falls out of scope and it's
being cleaned up thrown out if you write
this special method whose name is a
tilde followed by the name of your class
then it will run that method on your
object as your object is being deleted
right before it gets delete why would
you want to write something like this
well the main reason that you would ever
want to do this is if your class
allocates memory using new allocates
pointer memory using the word new then
remember how that kind of memory does
not get cleaned up automatically in C++
if you want that memory to be cleaned up
you have to clean it up yourself by
saying the word delete and so this is a
place where you would do that deleting
so let me show you example this array
stack that we have written if I go to
erase DAC dot CPP up here when we create
the array stack we make a new array of
10 it's the way the current new program
is written the erase DAC has a memory
leak if you create a stack and then get
rid of it those tenants are just sitting
in the memory and can never be used
again until the program quiz so that's
bad it's hard for me to demonstrate that
to you guys what I would have to do is
run a loop that we're because 10s aren't
that much memory so I'd have to run a
loop that made a million stacks and
you'd have to see the memory usage go up
and I'm not gonna spend the time to do
that I want you to just take me at my
word on that antennas isn't the worst
thing in the world to lose track of but
if you had a program that ran for days
and days this would be a problem so we
need to clean this memory up so the way
you do it is in your H file your array
stack dot H you come up here and then
you write a method called same name as
the constructor but with a tilde so this
is a destructor
okay and now in the dot CPP file the way
you implement it is you have to say the
class name with colon colon in the front
just like every other member when you're
implementing the body now here you just
write what code you want to run as the
stack is being destroyed as and so for a
minute I won't put anything yet but
here's what I'll do I'll just do C out
and D structur was called okay
indle but let's just see if it works
would see that print out so if I run the
program we will see it prints all the
normal output as usual but then it calls
it says destructor was called so I don't
think that's super helpful I mean it did
I guess it showed you that this thing
got run but it's not totally clear I
don't think this totally illustrates
what's going on here so let me try to
make it a little more clear if I go to
the client program stack client all the
code that plays with the stack is in
main right so let's change the coaches
slightly let me grab this code and let
me make a new method called void example
and I'm gonna put this code here okay
just paste it everything from main into
this other function and I'm gonna have
main I'm gonna put some print statements
here C out main begins okay and then I'm
gonna say main ends I'm also gonna do
the same thing for this other method I'm
gonna say example begins an example ends
okay just want to see the flow of what
happens in this program example begins
example and so I guess my point is this
stack gets created in the example
function it should get cleaned up and
destructed at the end of the example
function so if I run the program now
main begins main ends what did I not
call it
they should make me take my own midterm
and if I can't get at least a 50 they
should just boot me the heck out of here
shouldn't they oh well yeah thank you I
appreciate your help I didn't remember
to call my function okay what do we got
up at the top we got Maine begins then
main calls example example begins it
prints a bunch of output about stacks
then it says example ends destructor was
called because we're exiting example
we're cleaning up the stack now after
that main hence so as we're exiting the
example function it d-structs that stack
that's going out of scope okay so look
we haven't finished yet because the
destructor isn't just supposed to print
something it's supposed to clean up this
memory it's supposed to clean up this
memory that we allocated up here so you
just basically need to say delete
elements that's the only piece of memory
that we need to clean up we also have a
size and a capacity some students ask
but don't I need to delete those as well
no you only need to delete memory that
means new if you don't use new the
compiler will automatically manage the
memory for you that's the whole point
that's why we didn't use new until now
but the array we did use new we have to
use delete um a small thing if you're
deleting an array you have to say delete
bracket wreckage yeah it needs to know
that you're deleting an array any other
thing isn't an array you just say delete
sorry that's a little subtlety of the of
the syntax that's it that's a complete
implementation of the destructor there
were any other pointers that were new
memory we definitely delete those as
well okay so what do you think you have
questions about destructor what it does
what should be put in a destructor any
questions about this
yeah
sorry because the irregular yeah because
the array is the only thing that you
said new that means it's the only thing
we need to explicitly clean up new and
delete are trying pairs you should
almost always have one new for every
delete you don't I mean like if you knew
that you need to delete if you didn't do
it you don't need to delete it
new means I want to manage this I want
to take care of this memory and its
lifespan
that also means when that life spins
over I will clean up after myself I will
delete it any other questions
okay
let's move on so I want to talk about a
class for a linked list we've been
playing with the class for a stack I
just want to that was talking talking
about two things right the class for the
class concept and I'm talking about a
great implementing license using the RIC
so now I want to implement a collection
using functionality no it's an pointers
and next of data and looping current
nixed all that we did a bunch of good
stuff
but the way that we wrote it was what I
would call a procedural style all of it
was just a bunch of functions that took
a linked list front pointer as a
parameter so if you don't remember those
functions I'll just open the file that
we worked on before it's a code from
last week last Friday so we made a
client of code actually wait let me set
up cuz I'm gonna run this one so I'm
gonna change this to be like main stack
so I doesn't run that one I'm gonna go
back to this linked list file this is
the code we wrote before so we wrote all
these methods remember this all these
functions and they all take the front of
the list as a parameter and then in main
I'm gonna change this to be just named
main now you say like well let's make a
list that's a front and you add things
to it and you could print it and you can
add first at last you can you know we we
called these functions from main like
this okay now I don't like this code
this is not the way you would normally
do this I did it this way with you guys
cuz we're just learning this is the
simplest way I can show this to you
trying to clear out any unwanted concept
so we could focus on that pointer and
linked list stuff because that stuff is
hard but really if you want to use a
linked list you don't want to be dealing
with all these pointers and star and new
and null and all that stuff you just
want to talk to some friendly object
that kind of wraps all that up for you
and look what is an object really it's
data combined with behavior its
variables combined with functions its
data and behavior together that's what
an object is that's what objects are
useful for so when it comes to a
collection when it comes to a linked
list you can look at the data we're
storing in these nodes and the function
we're using to process the notes let's
just put the chocolate and the peanut
butter together dip it one another we
got something even better right we got
to have a linked list class and we don't
have to pass front front front front
front front front as a parameter to all
these functions instead where's the
front on a beat how do you if I delete
the parameter or front from all these
functions how will my code know where
the front of the linked list is a
private variable inside of the linked
lists class it will keep track of the
front and it will have all these
functions you can call that will start
at that front so that's what we're gonna
do so instead of this style I'm gonna
make a file called linked int list dot
CPP I'm not going to start from scratch
because it's a lot of typing but we'll
walk through some parts of it okay so
you'll make a class called oops where am
i I want to H file how do I do that
there okay
I'm with H file there so you'll make a
class called linked in to list that has
all these these are basically the same
functions we had in the other file but
they don't take the front front front
front front as a parameter they
otherwise take the same parameters right
but no front
where's front front is here the front is
the private man that's what you just
said the front front as the private
member variable so like if you're gonna
write a constructor for a list the
constructor initializes the private data
of the class what is the initial state
of a list when you first made it
I guess I'm asking what should I set the
front to be when he link to give lists
that's being created
you really feel that I'm reaching you
today we're really clicking we're
connecting it's like a big group hug but
without all the legal implications
what's the different be when you first
make a linked list object what do you
think it should be known because there
are no elements yet there's no data so
the front should be known so in this
constructor
I will initialize the front to be known
but then when you add things look at the
code for add this is the same code that
we wrote for adding to the back of the
list if the front via new no we wrote
this code that's why I'm not writing it
now with you we already wrote it the
only difference is I changed the heading
to say linked list add instead of just
void add and I deleted the parameter a
front because front is known to the
whole file it's the private member
variables and all of these functions
have that same style to them one
interesting difference is that in the
code we wrote before we had to think
about this like reference to a pointer
business you know remember that if we're
modifying the list we have to pass a
reference to a pointer the interesting
thing about this new style is we don't
have to worry about that issue if we're
doing it this way because you always
have sort of the direct access to that
pointer and if you need to change it you
just can so I don't have to worry about
references to pointers in this
particular style of coding so like if I
were gonna take a method like add front
and I wanted to move that over I would
just come over to the code we already
wrote I guess we called it add first
over here but I would just take this
exact code and I would just copy and
paste it over and it would just work
because this thing's called front and
this the same name that the parameter
front used to be called so I wouldn't
have to modify the code at all basically
so I'm not gonna sit here and copy and
paste and copy and paste and copy and
paste but that would be all we would
need to do the bulk of the work would
just be like writing out this this
header this dot H file to have all the
functions we need and then coming over
and filling in the bodies by pasting
them from the code we wrote last week
one thing I don't have in here oh I
guess I do is um which methods should be
Const so like asking if the list is
empty that's Const
asking for the size of the list that's
cost but adding removing etc those
things are not cons okay so look the the
whole point of that the the reason you
would want to convert over to this style
you might say what's the benefit of
doing this seems like a bunch of stuff I
don't like all put together you said it
was chocolate and peanut butter Marty
but this is like broccoli and pickles I
don't like either whatever I don't know
pick your favorite two bad foods like
why are you combining me I don't like
classes they're weird syntax sucks and I
don't like this pointer link list stuff
either why are you taking all this stuff
I hate it I'm putting it all together
well you're thinking of things from one
side like this version where the linked
list is a class is much easier to use by
a client so I'm bundling up all the
linked list stuff we had to think hard
about adding front and pointers and
references to pointers and all that
loops over linked lists and null and all
this I'm bundling all that up in here in
this class and then the client doesn't
have to think about any of that what
does the client code look like if you
have this it looks more like the
following you say linked in list my list
add 42 at negative 3 add to the front
this print the dot size remove the front
room if this is much cleaner much better
the person who uses this doesn't have to
know anything about pointers there's no
stars on the whole screen do you see
this the person implementing the class
has to understand pointers but not the
client so that's the benefit I once
heard an analogy from my mentor Stewart
Regis he said the linked list nodes are
like little paint cans and you know
you're painting a house or building or
whatever and the linked list object the
class is like sort of the painting
company your contractors or whatever
it's like if you're trying to get your
house painted you don't want to be
picking up all the pumpkins and moving
the paint cans yourself you just want to
talk to the painting company he can you
keep my house blue and they just take
care of it they deal with all the pink
hands and
finkles where how many paint cans do we
need they're dealing with all the
nitty-gritty details and we don't have
to as a client and I know you guys
appreciate this because that's what
you're doing every time that you use a
vector every time you use a map or a set
or a stack or a cube a lot of those
collections have pointers and nodes and
going on inside of there and you'd
have to think about that at all so
that's sort of a whole point of classes
is to shield the client of the class
from the details of how the behavior of
the class is implemented so today we
have a linked list class after all this
and the front is its private data one
thing I haven't done here is I haven't
talked about if you were to write a
destructor for a linked list you're
supposed to free up all the memory so
what memory do you think I need to free
up do I need to free up any memory if so
what memory is that and how do i free it
up
do you think
all the pointers all the nodes I got
this chain of nodes I got three of them
here I got to free up all three of those
nodes so let me tell you some things
that would not be adequate one thing
that would not be adequate would be to
say oh I got to empty out the list okay
front equals molar that will sort of
empty the list its equivalent but that
does not do the whole purpose of the
destructor which is to free of all those
nodes
another thing that would not be adequate
would be to say ooo okay that's not what
he wants he wants delete from the lead
is how you free up memory what's wrong
with this this is better but what's
wrong with this same delete front yes it
goes to the object pointed at by the
pointer and it frees up that object's
memory what's wrong
it doesn't delete all the rest of the
dough there's no like cascade
automatically here that's because it's a
week right in front points the other
things doesn't mean it goes in there you
know Domino's all the other ones you
delete them - I didn't need to write a
loop that loops across the list deleting
each node to really clean this up and
I'm not going to write that code right
now because I want you to write that
code but that's what you need to do okay
so I guess I guess this is not
hypothetical stuff I'm gonna make you
guys on homework 5 implement collections
as classes some of which have a raise
for the data and some of which have
nodes for the data so you will have to
do essentially this kind of stuff so I
want to answer any question you may have
about doing so yeah
oh how do you implement a for each loop
yeah so for starters I can't use that in
here right now it won't work if you want
to implement it for each loop you have
to learn about something called an
iterator if you're curious I would
Google for C++ STL iterator it's a
little too complicated for me to want to
show it to you today there's a couple of
extra methods you have to add and if you
have those methods C++ will notice and
it'll allow for each loops on your on
your code you basically have to explain
to C++ how to iterate across the
contents of the collection it's not
super hard but it takes more time than I
have today to talk about yeah can you
have a destructor in a struct yeah you
can
if the struct has pointer fields inside
of it but in general we don't do that as
often structs are usually very small
even a struct like a list node it
doesn't like you could imagine the
destructor for a list node automatically
going to next and deleting them too
the reason we don't do that is because
sometimes you pull out a node and you
want to just get rid of them and then
oops they boo-boo-boo-boo-boo and they
kill a bunch of other nodes on the way
and you don't you don't want to blow
them all up so we mostly handle this at
this level in the class rather than in
the list node struct because any other
questions about that I just kind of
shrapnel the whole bunch of random
at you today I just trying to fill up
all the loose ends of what you need to
know to implement these collection
classes any other question about that
yes
oh the friend keyword yeah I I didn't
mention that yet um there's a keyword
called friend I very briefly mentioned
this once if you declare this overloaded
this is that same operator to print out
a list you know if you declare that
operator using the word friend it means
that the operator is allowed to see the
private variables of the list so if I go
to the implementation of that operator
you'll see that it refers to the front
of the list lists up front it's allowed
to do that because it's friends with the
class even we're not it wouldn't be
allowed to see it
now you might say wait a minute Marty
you didn't talk about friend when you
did the array stack and that's because
in the array stack the operator didn't
need to look at anything private it just
called the public to string method to
get the output if I had individually
wanted to look at the array of elements
I would have wanted to make this one a
friend as well on the assignment that
I'll give you I'll declare all the dotty
headings for you and I'll put friend in
there for you so it'll let you look at
private stuff we talked about it sort of
a friends-with-benefits kind of a
keyword right look at each other's
private things yeah it's kind of a FM
otq version of friendship you might say
I don't know what do you do isn't it
wasn't that some kind of makeout session
one time I was walking home from work
and I accidentally kind of walked right
past where that was happening when I
like to narrowly avoided the
gravitational pull of FM otq and I was
like oh man that would have been a
scandal though I'd accidentally walk
through hey what's everybody doing
I got a little more stuff I want to show
you before we're done I want to talk
about something now how I talk about a
particular collection type called a
priority queue and you might say what
the heck how can you possibly be
introducing this to me in 10 minutes and
I think the idea is I'm not going to try
to help you master this in 10 minutes
yes I want you're going to go and think
about this for your assignment and so
I'm gonna sort of seed and introduce
this concept to you and you need to take
it from there
so it's intentional that this is brief
there are certain tasks that you might
work on where you want prioritization
you have a printer and normally the
print jobs are printed in the order that
they come in except certain people are
more important if a professor prints a
job cuts in line in front of all
students or something like that might
have an emergency room that has a queue
of patients that needed to process very
very pain they're sick they're hurting
they need help but you know so in
general you process people first come
first serve but if somebody more
important shows up they're bleeding
they're urgently in critical condition
you cut them in line in front of people
who just have the sniffles or whatever
so prioritization is important if you're
going to model these things in code you
would want some concept of
prioritization it's basically a cue with
urgency priority so the operations this
magical cue would be nice to have would
be the ability to add a new person to
the line and the ability to pluck out
the most urgent person from the line so
that you could process them you sort of
always handling the most urgent person
in the list in the line if you want to
do this there is an ADT there's a data
type as a collection type that's for you
it's called a priority queue priority
queue has the following operations you
can in queue think of it start out like
a normal queue you can in queue you can
DQ you can peak except what do you hate
you you pass in a priority level
somewhat unintuitive maybe lower
priority levels are more purchased the
intuition areas like
super-important kind of a parity to my
lessons workers so you add elementary
priorities then the cute story
somehow I just wrote it through it as a
cue out the most urgent one with the
lowest priority so in this example the
number 2 as the lowest settlement exit
out the word if for you okay so that is
the thing that exists you this
collection exists it's in our libraries
you can even use it
it's called pqh what was your question
yeah so here's the priority queue class
number as its priority will come out so
Eric would come out before Marty if I
added another one with priority of three
that one would come out second after
Eric and so on it's not super
complicated to understand the structure
I don't think if you've already used
other ATP's like queues and maps and
these kinds of things so I'm not
expecting that this would be super hard
for you to understand and I hope I've
explained some context where you would
want something like this the real
question is if you had to implement this
thing if you had to make a classic this
thing didn't exist already and you had
to write it from scratch how would you
implement it internally how would you
store the data for this thing
that's literally what your homework
assignment is I want you to implement
something like this two different ways
so let's quickly talk about some ways
that you could implement this thing you
could store it in an array or a vector
like we do with our stack
whenever sorted if they were unsorted
what you could do is you could it you by
just adding to the end regardless of
priorities put it at the end you could
DQ by looping across the thing looking
for the one with the lowest priority
number 30 now we're moving and returning
that one so if that's your structure
adding is fast and removing is slow
right what if instead a store is sorted
by priority when new patients come in
you stick in the narrow spot to be in
sorted order when patients come out who
comes out which element
if the PQ is sorted the lowest - thank
you the Spartan okay ray is the one that
would come out it's always them - I need
to start see that so those are two ways
you could implement this is an unsorted
or sorted array / victor you could also
use a linked list unsorted or sorted if
it's unsorted you just add into the
frame or and or wherever if it's sorted
you have to loop over and find a right
spot and insert them at the right spot
to maintain sorted order right which one
of these is better well I mean it kind
of depends what you're optimizing for
but I hope you'll see that all for
unsorted sorted array linked lists all
four of those combinations they all have
certain operations that are really slow
they all have some operations where you
have to loop across the whole list
looking for stuff loop across elements
to shift them right we talk about that
as being Big O of n because you only
have to look at all n of the contents of
the vector right so these structures all
have their drawbacks well look there's
an answer that's better than any of
these and it's a special structure
called a heap a heap is simply an array
that you use in a particular way if
you're using a heap you think of each
element is having parents and children
parents are at Packer index children are
at double your index and double your
index plus y this is just a concept just
an idea why do you think of this this
way because if you keep the array sorted
quote-unquote such that parents are more
urgent than their children this
structure will be very efficient for
building a priority queue how do you do
that when you add something to the PQ
you put it at the end but now it's out
of order
because it's got priority one it should
be closer to the start right it's out of
order so what do you do use swap swap
swap it up with its parent until it is
in order send its parent is three it's
got the more urgent priority than three
so you swap it frees pair in this one
it's got
more urgent priority than one so you
swap it you swap spots left with index
over to index over to index over to
until it gets to the right place in
sorted order with respect to those
parents similarly if you're removing you
take the first element out you swap the
last element up now it's out of order
so you bubble it down with child child
child times two times two times two
until it's in the right order this all
sounds like a bunch of complicated
mumbo-jumbo but if you implement this
behavior what you will find is that
adding and removing from this structure
all have a Big O of log and run time
because if you're jumping by times two
times two if you're jumping by / two / -
those are log base two of the input size
in so this is a very nice balanced run
time for the core operations of this
thing and it also has the nice property
that the most urgent element the one
that needs to come out first the one
that you would want to peek at or remove
is where where is it located watching
this at the start the lowest index in
this case that's index one so this is a
really clever little trick to implement
this
it's not it's not the same as DCs 107
assignment of doom called Heep allocator
that's a different thing you don't we're
able to make you implement that what
you're gonna have to do for this
homework is I want you to implement a
priority queue using 2004 a griefer
while using an unsorted array so that's
this first thing unsorted array the
second style is a sorted linked list the
bottom one here and the third is using
this weird parent-child vertical ordered
heap structure I know I blitz through
that really fast that's because it's all
in the spec in lots of detail and I want
you to think about it and read about it
and work on it after your exam that's
all for today I'll see you Wednesday