Data Structures (COMP 15), Tufts University, Day 22: April 16, 2014, 10:30-11:45am

okay might as well get started all right Wednesday April sixteenth so do you guys know there’s like three left lectures left right there’s this when there’s today there’s next Wednesday because we have a holiday monday and then there’s the following Monday and that’s it the Monday class will be the review class so we’ll talk about what’s going to be on the final what you have to prepare for etc etc today’s class is going to be kind of on it sits on these things called containers which we’ve already done a little bit about templates which we’ve done and I’m going to talk about vectors I haven’t yet planned out next Wednesday’s class I’ve got a couple of ideas though raise your hand if you’re taking comp 40 next year or at some point in your future okay if you’re not you can laugh yes I see that what what what I might do is on next wednesday have like how to prepare what you need to know to do well in comp 40 something like that which would be basically here’s the C language and some of the differences between C and C++ here’s here’s how you do bit shifting and bit manipulation a couple little things that you’ll need to know in comp 40 now that that that does not mean that those are you who are not taking con 40 like don’t like won’t get anything out of that class either but it’s not really necessarily going to be geared towards you if that’s all right what it what it kind of means is you know you’ll see a little bit of the kind of the pain that you might not have to do it but but that’s one idea i’m also thinking of possibly doing a couple other data structures we haven’t yet talked about but but i’m still think about if you have comments about that if you really like to do if you’d really like to do a you know what’s what’s going to be necessary before you get to comp 40 put something on Piazza or something and maybe we’ll start a little thing there and then otherwise if you say no I’d rather do you know rather do something that’s more data structure itself then we’ll we’ll do that but that’s where I was that’s what I was thinking about their labs next week will be a little different too because Monday doesn’t happen so Tuesday and the following Monday it’ll be our last lab I don’t think we’ll actually do a lab in particular but we’ll be filling out like course evaluations and doing and working on projects so we should be able to to get some of the things done there ok questions before I get going alright so today Oh actually I forgot I didn’t put a UNIX tip of the day but somebody yesterday was asking me something and then and then the conversation ended up going hey you should do a UNIX tip of the dentist yeah question oh how do you provide the plan you do let’s see you do make provide underscore design i believe it is says how to do it in the document in the document i handed out but that’s how you do it and then it should then it should do it the yeah so yesterday somebody came up and she then has anybody anybody ever lost any files on your computer’s computer or or like deleted a file accidentally or whatever right like common stuff i keep everything in dropbox so dropbox saves a lot of my stuff for me but if you’re on the server and you delete something accidentally or if you if you write some right over a file that you didn’t mean to and that happens a lot there is actually a dot snapshot folder some of you guys are going hey i know all about that in your main folder if you look at your main like this is my main folder CH greg in there if you do CD dot snapshot right it actually goes into another folder that says that has a list of hourly backups and then nightly backups and then weekly backups right so your stuff is store now it’s not really every hour your stuff gets backed up but it’s more or less the stuff that says hourly 0 is the latest stuff that got backed up right and if you within a week if you realize that you’re there’s no monthlies on there either know if you realize within a week that you deleted something you can probably get it back right because what you do is if you go into say hourly dot 0 it is all your files those are all the ones that you like and you can go to desktop now right and there’s all your desktop files i don’t have a comp 15 or whatever but if you go in there the files that you deleted the files that were in there yesterday or an hour ago we’ll still be there right and then it gets replaced and everything propagates through and then a week later the last one gets pushed out the other side so it’s a backup system for your stuff and it it’s really nice if you all of a sudden are working on a project and something gets deleted or let’s say you’re going down some path and you realize you know what this is a terrible idea and I didn’t I didn’t figure out how to like save their stuff and I want to go back to what I worked on two hours ago just go back into the end the thing you may be able to find the stuff you worked on two hours ago and get it and then you can just copy it into your main folder or your other

folders wherever you want okay so it’s kind of a cool idea questions on that nice little backup system yeah all right oops oops there we go I’m going to go back here for one sexy there we go all right so let’s talk about here’s we’re going to do today by the way vectors templates and what actually templates are the reason I’m going to talk about this vector thing is because it actually may help many of you in your song search project and by the way when you get done talking the vector you can ask any questions you want about song search and so forth any other thing I the other questions is are fine but the vector container is just like the queue or stack containers we’ve used in lab a couple times and what it but what it is is it’s a what we call a wrapper around a dynamic array so if you have elements you’re trying to put into a dynamic array instead of building your own dynamic array class or object where you have to do the dynamic like expanding and all that this does it for you right here’s kind of the motivation for well well that’s what the vector itself will do okay it does it it being able to store any type of object is the powerful part about it so if you want to store structures of your songs and frequencies if you want to store strings if you want to store characters you can do all of that in these containers okay these containers actually come from what we call the standard template library okay here’s kind of little motivation on this all right you have a container right containers in real life in general aren’t necessarily made for one particular object now that’s not always true right if you get a box and it comes like apples like famous for this right their boxes are like perfectly designed for their exact you know iPhone or whatever it is right and if everything fits perfectly in there right that’s really the only thing that would go in that box in that container that’s that’s an example of a very defined use of a specific container what’s another one I was thinking of sure you ever see you guys know deviled eggs right there’s like little containers that you like put deviled eggs in and each like it’s got a bunch of holes in their egg shaped and they fit eggs and you can put like Downton you give a plate if you go to a fancy party in the hand you one its licking you you know but that’s a very specific container that is not you wouldn’t want to store like ice cubes in it or something right although that’d be kind of cool you have a half egg shaped ice cubes that’d be kind of me anyway in real life we try to store stuff that we try to make containers that will store lots of different things okay so shipping containers can hold toys they can auto apart so they can hold like illegal drugs or whatever right but they can hold lots of lots of different stuff they can actually hold stowaway kittens right that’s when I found at this one that cat got all the way from the Philippines to Los Angeles does not look too happy and I can imagine it wasn’t particularly fun for the cat but first of all it’s like what’s going on for like three weeks right luckily ships are pretty fast but anyway so containers you want them to be able to KITT hold multiple types of things right and that’s what the goal of the standard template library is and some of you guys already know about all this stuff but I’m but I want to just kind of dig in a little bit especially at the end here we’ll go into more details about like how you can build your own template libraries and things okay so the goal of the standard template library is you have these functions or these classes really they’d have the ability to store any kind of object you throw at it you want to store hashes or you want to a strings you want to store a class like class objects or doubles or structure whatever you want they should be able to be handled by that container object and by container i mean the data structure object that we’ve been talking about whether it’s a queue or a stack or in our case of vector that we’re going to talk about in a queue you know something about a queue right you know that you can get the front element you know that you can push and it goes on the back right you can NQ onto the back of a queue and you take the you get the ABS off the front those are generic ideas right and they’re generic in the sense that you don’t care if your push if you’re pushing on an int or a float or a class or a song or a structure of some other sort it doesn’t actually matter and that’s the whole point that you want the container to be able to do this right so if we want a queue of floats we’re just going to use floats yesterday in class we used a queue of integers right when we had the the lab for the lab we used a queue of integers and push that engineers some of you tried to use

a queue of boolean values that actually works perfectly well to write but the but the idea is make a container have it meet the requirements of being able to do its function any kind of object all these guys right so it’s kind of kind of a neat idea and it’s not a particularly like it’s not a really old like old idea there it’s like when when when people were thinking about first programming in writing programming languages they didn’t really think about it this way objects didn’t really exist at types of course existed but if you wanted it if you wanted a queue of floats and you wanted to build it you’d build it for floats if you wanted a queue for integers you’d build it for integers and it’s like what we’ve done in most of our class here you have a very specific type that you’re throwing in and you build it around that type we want to make it more generic okay we’ve seen queues and stacks we’ve been storing integers we can store whatever we want okay that’s the whole point and this this thing called the standard template library is given to you if you have it if you have a C++ compiler you should be able to it should come with this stand template library which has all these great containers and other objects in them light cues and stacks so you don’t have to go build them what’s one good reason for you not to build your own q I can tell you why I wouldn’t want to do it yeah Marcus takes time to build your own q you want to just do that you want the Q function you don’t have to build your own what’s another one yeah you have a small stupid bug ya number one you get a small like the people who create the standard template library they have tested this like as much as they kill like thousands and thousands of people have already tested this so it’s probably works not only that it probably works as efficiently as it can so not to say you guys don’t write a fishing code and that’s the whole point of this class is to write efficient code right but a lot of times you’ll have a little you know you might you might iterate through one extra element when you don’t really need to write sometimes you don’t need to worry about that first like the zeroth element because you’re comparing against the next one but sometimes you you just say ask no big deal well the people who write the standard template library have thought of all of that right so they’ve made it really really efficient okay the other part again of course is that that it’s that’s built for you now part of the reason the main reason you could say that we built a lot of these things ourselves is so that you’d understand them right and you’d understand when to use a queue and Wendy as a stack but point is these are already built for you if you know when to use them great vector you don’t want to use a vector when you’re doing lots of linear searching and so forth that sort of thing so you guys these are the ideas you should know by going through this class right okay so that’s how that’s the types of classes that are included in the standard library okay there’s also a priority queue there are there’s vectors we said their sets there’s maps which are kind of like they can be their hash tables or like binary search trees but there’s lots of different things in the standard library okay and again I’m hammering this part you can store any type in them this is the important part ok questions so far what we’re doing with these okay let’s talk about why this actually works for a second then we’re going to go into more details a little bit later the standard library in standard template library classes have this thing called compile-time polymorphism alright polymorphism is a really interesting idea what it means is that you can take one class and you can say ok I’m going to build it specifically for inch I’m also going to build it specifically for floats I’m also going to build it specifically for strings and it means that you can you can take that same object and apply it Polly all right you can apply it to a whole bunch of different types of objects the compiler actually does that it turns out that the C++ compiler actually has another compiler built into it specifically to do the compiling of these these standard templates that we are these templates ok it’s like kind of like a whole nother compiler it’s actually a whole nother programming language in itself you can kind of think of it like that and it’s been like shoved into C++ so that we can do this stuff ok what the compiler does is it says ok I’m trying to make a dynamic array of integers well then I’d better create a done a dynamic array that is made of integers and when I when I walk through the integers I’d better go one integer at a time instead of say one structure at a time and the compiler has to think about all that and build your code specifically for that what’s nice about this versus say in another language like Java is that it does this it recompile specifically for the type you’re using and doesn’t have to do that

during runtime so it’s really fast that’s what that’s one of the benefits of this is it gets it gets the job done and gets it done fast because it specifically goes and builds these things for your object ok so you tell a queue to use integers and the and the queue functions are then compiled internally to just use integers for that part of the program you can have two queues in your program you can have 100 queues in your program one can be four integers seven can be four strings 6 can be four characters and they’re all going to be built specifically for those types kind of cool stuff okay likewise or any other type you can think of that’s the beauty of it you can make classes and put them in there and struck sand pointers and whatever Rose you’ve got a question ah ok so well here’s here’s what so when you do when you say something like when you say something like uh let’s see my array equals new int 20 right it’s going to do this and it’s going to make an integer array of 20 things wrong right and it would be like int star equals new int 20 right okay so you have to do that now when you come along later and say you know what I actually don’t want to put integers in there i want to put floats in there right you have to go and you have to change all these things to say float now at the beginning of the year we actually the beginning of the class we actually talked about how you can put this part of it like at the beginning of the program then just change it once at the beginning you can do that but what’s nice is the compiler will figure out you don’t even have to do any of this changing at all you have to you once you wait while you do up to say when you’re when you’re defining what you’re trying to do but you don’t actually have to do that and then the compiler goes and says okay I’m going to now base everything in the rest of your program on the fact that i’m using floats instead of integers so it’s really not different from yours except that you can you can make it so that you don’t have to go and redo all this you write one class and then all of a sudden it’s good for floats and in sand characters and strings and all that okay so that’s that that’s the big the big benefit there okay and that’s how and that’s why we can use queues for integers or floats or characters or songs or whatever okay because because they somebody else built the template for it and says now I use this with whatever type you on okay in fact it goes a little bit deeper than that in fact if we if we do the whole prepare for 40 class I was talking about on Wednesday we’ll talk about the fact that for boolean values it actually says oh I’m doing a boolean value I’m going to squeeze the bits down so that I don’t need to use whole like integer numbers to do it it’s actually kind of clever but the idea is you don’t have to think about that somebody’s already done the time ya know oh good question like you have 1q and can you put an integer in one spot and then a float in the next in it you know you can’t do that in C++ other languages you can do that in other languages python is a very good one you can have a list of stuff and in each one it can be anything the problem with that it goes back to it goes back to how do you know when you get it out what type it is like you’ve got to be very careful about that java i believe still allows you to do that to some extent but not as they have these generic types now as well used to be that you could you could get an array in Java and it would put you can put anything any object into any place kind of like Python but they’ve changed that now because they didn’t it doesn’t it makes it harder to debug in the end because you can throw anything in there but now no you can’t for these you can’t you can’t say lets you know going to be any type of object in each particular one good question yeah okay other questions on that so far ok let’s go into the vector class I promised some of you guys I talked about this in class today the reason we’re going to talk about vectors is because I think you will be very happy to use that if you use them for your song search instead of a dynamic array you can do it in √©migr√© we have built dynamic arrays and that’s perfectly fine but you may want to include strings in one dynamic array and then I and then you might want to include song lists in another one and you might want to include and I don’t want you to have to rebuild your dynamic array specifically for each type this is why the vectors done done that for you okay we have to go into a little bit of detail on how to use it right a vector is just as I said just a dynamic array and all of us all the dirty work is done under the covers for you

okay so if you want to add an object to the array well that know it you say push back and i’ll show you how this works you push that up to the back of the rain it says okay i’m going to put at the end of the rake and underneath the covers it says oh am I am I at the end of the array already like in my app the capacity I need to expand it and it does and I need a copy and it does all that under the covers it’s great you can refer to an object in fact in a vector you refer to an object exactly as if it were a regular array so you have some vector it’s like your song vector right song zero is the first one the first song in that vector X I think I have that exact example in a second okay whole point is handle behind the scenes it’s awesome here’s some of the things you can do with it there are lots of things in fact let me let me just bring up a bring up a web page here that shows this let’s see if I do vector c++ it should give me the reference here we go the first link it’s already purple okay and hopefully it’ll come up ok so this ah this tells stop there you go this tells you this tells you all about the class by the way it says it’s a template it’s part of the standard library etc right and it tells you all about it and then it says look here’s the things you can do with it down here right here you’ve got well those are iterators we’ll get to what those mean in a second here you go element access you can use the brackets you can say something at the thing we can get the front of it you get the back of it you can actually get the all the data at once right you can push to the back of an array you can pop from the back you can actually insert in a very in a specific place in the array right in the vector you can insert into a specific place you can erase the whole thing you can swap values you can I don’t know the different clear verses erase not sure the difference between those is and then there are lots of other things you can do with this okay so there’s a ton of different functions we’re only going to talk about a few today but you can feel free to use talk to to look at the rest of them as well push back some value and that value is whatever type you’ve just you’ve you’ve created for that or you decided to use for that vector you say push back the value and it adds the element to the end of the array and by the way we know that’s relatively fast right that’s an order one operation and the way they build these structures they try to model it so that that’s an order one operation unless you have to expand but that’s rare sighs gives you the number of elements so if you do a ray if you have your array song and you do grab be stuck here if you do song period sighs currency front seats a function that will return the number of elements in the song all right it’s easier than keeping some extra count of it yeah it returns the number of the number of songs in there right the capacity you believe it or not you can get the capacity not that you ever need to worry about it like the whole point is you don’t need to worry about it but here it is right here you can get the capacity there’s a function that says capacity return the size of the allocated storage you can also reserve storage if you know this might this might be interesting if you know how about how many types of objects you’re going to store you can reserve space yeah it does not only make it as big as just as big as you need initially anyway go ahead it only gives you the number of elements that are in it right now now if you ask for the capacity it will tell you the total storage amount nope the size just counts how many things by stuck in there so far that’s all it does by the way this is a kind of a cool one they have in the newest version of C++ shrink to fit so let’s say you’re doing in a right let’s say you’re throwing songs into something right and you double the size and then there’s like that one like that and that the last one that you put in double the size of it Alton you’re wasting all this extra space right well if you do shrink to fit it says all right how many are how many elements are in there there’s exactly this many i’m going to reallocate get another set of memory that’s just that long and then give back the extra that I didn’t need so it’s kind of a neat idea and it’s you know they they added this the latest version of c++ c plus plus 11 you do have access to that if you want i put a Piazza post on how to do that you may so

unfortunately it looks like it looks like the clang compiler we use was not quite installed perfectly so so you probably want to go back to g + + instead of clang + + your error messages won’t be as good but it’ll actually work so that’s the trade-offs right but you but you can use if you want I don’t you know what if you wanted to use this for you or you know hash table or something if you had a hash table full of vectors of you could do that you could also do that manually to I mean you can you could also when you get done with all the songs say oh how BIG’s my hash table oh it’s this long I only need to be this long rehash everybody into a smaller one and you’re good yeah yeah you have to read yes you do so you’re probably not going to want a veck you’re probably if you’re building your own hash table you’ll just use a dynamic order like a regular old array because you do have to worry about that it won’t I don’t believe it actually tells you when it’s resizing you could figure this out although I think it’d be just as much work to use a vector to try to cram your hash table into that than otherwise yeah but that’s a good point good point yeah okay other questions before we talk more about the other functions okay so there’s the operator one which I said just works just like this this is an overloaded function we’ve talked about those before it means if the compiler sees your vector and then the bracket and then the number in there it will go to that give you that element okay it’s random access just like all dynamic arrays you can also do an insert okay inserts a little bit different you can’t just insert the value ok you are you can’t just you can insert the value can’t just say here’s the position I want it has to be what we call an iterator I will go over what that is in a minute but it’s a little bit it’s it abstracts away a little bit more of the position for you and it there’s a reason there’s a reason they do that so that you can’t just try to stick it anywhere in memory but it’s but it’s a little bit different we’ll get to what an iterator does ok but these are the big ones you would use push back sighs and operator brackets those are the big ones you would probably use for this here’s another nice thing about the song search one you were we are doing a lot of like putting things into a database we’re not doing much pulling like removing from a database it’s not like I say Oh search for some song and then remove it from the database it’s not like the calendar on where you have to extract elements and change it so that’s well a little bit nicer you probably won’t have to do the erase or the remove or whatever ok all right so those are some of the functions here’s how you declare a vector it’s just like we declared a queue in class you say but by the way you do need forgot about this do you need to say pound include angle bracket vector like that that is necessary when you are when you are doing this and you need to be using the you the using namespace STD which we always do anyway kind of like strings okay so easily do you say i need a vector I want it to be of some type and then the variable name okay creating a vector of strings this sign it seems like one that might be important in the next few days for you guys right a vector of strings called lyrics yeah question Emma your lure you give it a size to start good question you can give it a size but generally you don’t it generally has an initial capacity I want to say the initial capacities like around ten or a dozen or something like that but it’s not that big but it will do the it will double as necessary it’s clever that way yeah good question yep if you know how many you’re going to store yes now for our assignment we’re going to test it on small database and a big database so you’re not going to know up front right and you don’t what you don’t want to do and this is kind of in general you don’t want to say oh I think it’s going to be this big and then all sudden have it small and then you use two gigabytes of memory for the like the nine song rick astley database right you’re just you’re there that’s probably not that that’s probably not the best way to do it now if you if you have some scheme or you read everything in and then count as you go and then all of a sudden you create your database probably not the most efficient way to do it but then you could say oh I know it’s going to be this much now does it take a long time to do this expansion stuff yes and no remember expansion doubles every time so it’s a you you don’t expand that often like you expand at the beginning you expand a lot but then every time you double like you have to get again twice

as many before you double again and then it’s twice as many from that and so you get to the size you need relatively quickly but yeah if you want I mean that would probably help you know to know a little bit about that and trust me when like Google thinks about these things they’re going okay look we know we’re going to get a billion things here so they probably do some of that yeah a class that contains a pointer to a vector of string sure so let’s say you got a class right and it’s going to be I don’t know my strings or something right and then in the in the private lon private variables it’s got a vector another about just a string in there in your class oh yeah point your do a string short string pointer a string yep okay nope using the vector doesn’t change it at all as long as well for your class you do need to consider the you do need to consider the copy constructor and the the equals operator equals overload if you are going to have misdirection like other direction like that you in many cases now you may have a string like strings are actually ok because strings will do the copying for you if you have some pointer to another object that other object had better have a copy constructor or and it equals overload because then when it gets copied into the vector it will not necessarily work now you can put pointers in vectors which is kind of cool too so then you don’t if you ain’t all it’s going to do is copy the pointer it’s going to be very fast and it’s going to to do it I’m going to be nice easier to deal with you don’t have to worry about that much but yeah you do you would have to do it if it was your own class and some other class that you came up with a good question ok anything else on how I’m declaring these ok here’s how you might use a vector this looks familiar to anybody right maybe some of you guys have come up with this idea you have a song structure a struct of songs i forgot the semicolon here and you say string artist that’s artist name string title and then here’s your vector of lyrics ok it’s easier than trying to figure out oh it’s a dynamic array of lyrics it’s going to be handled all for you which is cool and if you wanted to you could take this whole thing and put it in another vector of songs that’s kind of what you’re going to do it if you do a hash table or a try you’re going to have a possibly a pointer to this that’s what I would suggest a pointer to this in some other object and it could be a vector it could be a hash table could be a try whatever you whatever you’ve decided makes sense Marcus look at me like I’m crazy I probably am but that’s this isn’t why all right so anyway here’s the dynamic array it’s just the vector right there of strings okay so this could be your class as you get a new word you pop it into the lyrics for that song makes sense hope so all right so here’s how we’re going to use it here’s our ox is going to do that let’s say you get the word and you say lyrics dot push underscore backward right that’s all it’s all there is to it don’t need to worry about expanding don’t need to worry about the capacity you don’t need to worry about a lot of nice things that you would otherwise have to worry about because we’ve already made you build all those not going to make you rebuild them all all right how do you use it well like I said lyrics 0 is the first word in the lyric okay there’s other ways to get that first one as well in fact a function called begin will give you the first one well it’ll give you an iterator to the first one which we’ll get to in a minute you can do the size as well you could this this will give you how many elements or it contains we’ve talked about that okay and then you may you may want to walk through the list right if you want to iterate through the vector here you can do it the way we’ve kind of always done it right you can say all right by the way vectors hold elements in the size underscore T the amount that remember the size underscore t says basically an integer type that will allow you to store as much as you need for the memory system you’re using you could say integer here it like int you might get a warning if you do that because it’s not an integer it’s actually a long or some other type

that’s not this will this says hey arrays store the size of the pointers are this big okay so you can use that but it’s the same idea once you have that your eye or iterator through or your your index equals zero I is less than lyrics sighs I plus plus and then you can take each one in turn like that so that’s how you’d go through the lyrics okay you’re probably not going to well you may you may count them out like this but you’re probably not going to do that directly like that okay but that’s how you use them yeah Barry yeah don’t you if you use in tier right it will probably work but it won’t necessarily it will give you a warning that says hey it’s not that you’re trying to convert a bigger number into a bigger number type into a smaller number type that’s not it’s it’s a warning it’ll do it for you but it’s a warning now i don’t this would probably not be the case but if you got more than 4 billion things in your in your database and into an even work but a size t might depending on how its defined in the language okay but yeah just i would if you’re going to if you’re going to use vectors this is the size of the values that are kept in there the size of the pointers are the values that are kept in there so don’t use it use size underscore t otherwise you have lots of warnings yeah it actually defined for you in the header files for things like vector and for other other header files yeah it’s already already defined for you yeah so you should be able to use it straight away okay good so this is one way to walk through the walk through a vector the way that we probably understand the easiest up sorry Garden of Eden I think it is an unsigned int actually yeah that would work too so if you want to use an unsigned 8 that’s fine long would probably also work yeah yeah but sighs underscore T will definitely work regardless of the other ones working or not okay so that’s an easy way to walk through it that’s the way we might understand take a look at a different way to walk through a vector okay we can use this thing called an iterator and it’s we talk about iterating through we talk about oh it’s an iterator and it’s iterate through but there is a very specific definition of an iterator for these containers okay an iterator actually allows you to go through the container directly without having a without having a specific number associated with it it looks very similar but it’s not a number and I’ll show you what it what it means but you don’t have to use these iterators for the most part you will for one thing I show you you want to use them for walking through as you get more advanced in C++ you’ll probably want to start using iterators because a they’re everywhere and B it’s really the preferred method for walking through it in a right let me show our walking through a vector and other containers let me show you what I mean okay so we’re dealing with vectors of strings here okay vectors of strings that is your type of the object that we’re dealing with the vector full of strings in it it has another class called iterator that is part of the vector string class so it’s like kind of it’s a class within a class okay and well actually it’s not a class minute class sorry it’s a it’s a it’s a variable within the class that is based on this idea of being able to walk through things okay so it’s a variable in there and what it is is you can say okay here’s this iterator i’m going to call it the word i’m not going to call it the index anymore it’s it’s not an index okay and what it equals is song and then lyrics dot begin that says the first element in your lyrics okay and it’s again not an integer but it’s actually going to be a pointer to a word as you’ll see in a second you start with the B give the first one and you go until the word is not equal to the end and n is not the last one it’s like the one after the last one end means I have finished going through this array there are no more things to deal with okay so it’s like the length of the array it’s like the one after the last one in there that’s what end means okay so here’s what we’re doing we’re saying okay here’s my my iterator it’s going to be called word word starts at begin and goes until end and then we increment the actual iterator that looks very similar to what we did with the the index it our index before right you’ve got it it’s a for

loop you’ve got a begin you’ve got a conditional when you end and then you’ve got an increment in there here’s what you’re actually doing you’re actually printing out in this case these are just just that’s just an extra character and then you are saying give me what word is pointing to word is an iterator that points to some place in the in the vector and it says dereference that and print it out okay and then I’m going to print this other character let me show you what it does this is exactly the same thing except that I didn’t do the I didn’t do that the other angle bracket there but let me show you what it actually looks like see hopefully I have this up here that’s that lon I do not so let me open it up okay here we go let’s look at vector example oops okay let me push push it down for a minute so here’s here’s what we’ve got here we have ok this is a word list let me see if I can’t make it bigger for you lecture hall how’s that there we go a little bigger it’s a lot bigger actually ok so here’s what we’ve got here we’ve got just a word list and by the way you can grab this off the web page ok if you’re having trouble starting on this assignment right you might want to grab this and see how I’ve set it up because this you might be able to work this right into your right into your program for this week so if you’re having trouble starting this might be a good place ok in here we’ve got a thing that says process word current song or the print song here we go so I’ve written it twice here I’ve said the simple counter method and I’ve act that highlighted out or I’ve got that commented out and then I’ve got the iterator method which is exactly what we had in the previous page here ok it’s going to go through the whole lyrics for a song and print out each one word by word with the little little alligator things on each side right the less than I graded on each side ok watch what happens when I run this oops it’s not going to work because I was doing this on a different computer hold on one sec so what happens when you try to work with two different computers luckily leave I know what I’m doing here ok there’s that and there’s that I’m going to put that in here and now it should work ok there we go ok so here’s what it printed out see hang on there we go ok so here’s the Rick Astley first cry for help it printed all the lyrics right lyric so it said there’s the artist there’s a title and then she’s taking my time convinced me blah blah blah right that’s all the lyrics in a row and it’s I put the little angles here just to show you that’s the end of each word and that reads it in and gives you those individual words and put it into a vector that we then print it out ok go look at the code yourself and and and you’ll be able to see how it works but it’ll it’ll show you the idea and this should actually get you started on like reading the database in if you’re having trouble with that and how to maybe structure it into a song class okay I wanted to give you the ability to do that if you’re if you’re still struggling on how to how to begin there ok questions on the iterator for right now yeah that’s a good question is it like a for each loop it is kind of like a for each loop which we want to explain to the class what a for each loop is yep mm-hmm for each option your list you’re then doing what you want to do with it right it is exactly like that really this is saying the object in this case is the word and the word happens to be of a type a pointer to a vector string right way a rather a string which is the type and so that’s the object and that gob could be anything right it could be the song it could be the lyric it could be that whatever and that’s exactly what it’s doing and then instead of saying oh I’m going to reference it by index you’re referencing by the object so yes it’s it’s a for each is a good way of thinking about it yep good question yes hobby absolutely it’s adding one to the pointer value yeah and it knows so so the compiler knows how big is a is a string like how much memory does it take and it has string string string string string right now this keep in mind it’s not the number of characters that

decides that it’s the object itself the characters actually stored somewhere else in memory as I mean and I like it’s a misdirection a little bit but you’ve got a string string string string and it knows it goes the next string is here the next one is here the next one is here like that so exactly what it’s doing it’s walking through the the objects into like it’s going one two one two one next objects good yes Marcus nah yeah why is this the pervert method anyone want to answer that anybody have an idea why this might be better than the other method it’s more generic is what it is right it’s a generic way of doing it in that you can always go through it like this there’s by the way there’s also a ways to go reverse iterators or you can iterate through a hash table if you wanted to that’s a little weird or you could iterate through a set where it’s there’s a function that’s built in on how you get from point A to point B it’s not just an index for a vector it really doesn’t matter vectors we know are in order in memory and we’re going one two one two one but let’s say you at a linked list you could do an iterator through a linked list you can’t do a bracket notation for a linked list you could have to know something about the notes but if you have a linked list with an iterator the iterator under the covers says what’s the next node and it picks it out what’s the next node and picks it up might be over here over here over here so that’s how that’s more generic in that sense okay good yeah ah the good question that’s probably a little beyond the scope right now but really what you do is you say how am I going to you it’s basically a pointer to the type of object that you might be going through that’s really how it is and you can you all you have to do is actually create another another function that’s called iterator that returns some value and this case it’s going to return a pointer to the next word that’s all this one does so it’s actually not that hard it’s just you have to dig in a little bit and see how you do it but you just create another you create another function and it’s called iterator and that knows how to deal with these sorts of iterators and you have to create a begin and you have to create an end and you have to there’s a little bit more to it but not that hard really it’s just it’s just there’s specific rules for it a good question okay yeah Morgan yes yeah good question good question i believe you can i believe this is simply a pointer to the actual location so if its a mix of a type that can be changed then you can change it some of them are not like i don’t you can’t actually change strings directly like this you have to replace it with another string and i’m not sure it allows you to do that but it may if it’s a pointer it should yeah a good question it’s not a it’s not a constant what you don’t necessarily have to have it be constant I don’t believe yeah good question okay anything else on the iterators here you you you really won’t have to worry about it errs unless you do the one of the next things that I talked about but you you probably won’t have to worry about I just wanted to introduce it because you’ll see it a lot if you do more C++ programming okay all right that’s the iterator itself that’s the first element that’s just after the last element okay and that’s how you interpret it and there’s a dereferencing woohoo okay where else could we use vectors well maybe some of you guys are actually thinking of making vectors like an initial dynamic array of songs not sure that’s necessarily the best way to do it but you can okay but you could do it with a vector of song pointers to songs let’s say let’s say you wanted to say i don’t know keep the top 10 hits for a song right if you’re doing a search for it well a vector of song pointers would do that for you right let’s say each word in your dictionary has a vector of songs that it that it knows the that word exists in that would be a good use of this vector of songs so each word as a vector that says okay here’s the word as the vector it says these are the songs where this word appears in and then you can go deal with that as you go along okay and then you’d push back a song right and then the song in this case would be a pointer to a song you could also have it push back the actual song but that’s going to take more time instead of the vector instead of the pointer because it has to copy all the bits from that so it’s it’s we are trying to save some

time here if we can okay question yes ah let’s see maybe it’s in the next slide it’s not quite in the next slide but it’s a couple of slides from now you can sort vectors relatively easily actually in fact there’s a built-in sort function probably I think it’s quicksort actually that will you that you can use on vectors what you have to do though is you have to decide what actually gets what part of the object gets sorted if it strings no problem if it’s songs right remember what songs were right songs were here what’s going to get sorted here you’re going to sort by artist you can sort by title you’re going to sort by lyrics you know now this is probably not the best idea cuz you’re not going to be sorting by song well your pornography sort of misery I’ll give another example where we do do a sort on it in fact there’s good code there’s code on line that I wrote this morning that does exactly that okay good all right so but we’ll get to the answer in a second all right vector vector cyst or pointers to they can store anything that’s the point I’m you might want to have a try for those are you using a try for your data structure right a bunch people are you might want to do it this way I put a note on Piazza on how this might be important to do do a vector of nodes that means you don’t have to create all 36 nodes at once right and especially you’re doing a node pointers it’s going to be a relatively small amount of information it will only create a minimum size for you in fact if you wanted to be really clever about it you could you could have it you could do the node with children and say just give me one to start out capacity of one just in case I happen to have one right you could do it that way because there is a way to declare a vector such that you get a capacity of one might not be a bad idea if you’re trying to save space and your overall try because a lot of word a lot of combinations like ZZ y XL or whatever is not going to be in the word list right so maybe something ac/dc or something arrow but anyway did you hear that ac/dc is like disbanding kind of set yeah no more acadeca all right anyway so you could do this you could you could do this with your children and then every time you get a new child push it back onto the onto the node around to the vector and then just go through and search through the vector to see if the word if the if the letter exists or the child node exists slightly slower but probably saves you lots of space than doing a character per node or 36 i should say characters c’mon by the way this is an important one for those of you haven’t done that who are thinking about a try the tri is going to have letters in it and digits because some things like some there was a lyric that says like something something 1am and the one is part of the word and that’s not getting stripped out okay alpha only actually means alpha and numeric only turns out yeah hash function works perfectly fine for any any string yeah with even with even with the punctuation as well it worked fine yep good question ok so this exactly your comment right let’s say you wanted to store a list of songs by the frequency of the word they contain that seems like it might be likely for our project right if you have a struct a struct that has a song written as a song and also the frequency in there they saw and pointer and also the frequency you can make a vector of song with free structures all right you can do that and that’s what’s nice about being able to do this like like that there is this is the next one I was talking about there is a sort function sorry sorry Bruce you too fast on that that’s all right if I go too fast just question all right so there’s a so there is a sort function that you can use that’s built in that allows you to sort these contain and you don’t you you could use your own sort that you built last week perfectly fine okay if you’re dealing with container classes it’s probably a little easier to do it on it to do the use the one that’s already built for you there are a couple of caveats here caveat number one you have to provide an overloaded less than operator in other words how does your the vector know how to sort based on your structure what would you sort by for this one frequency right so we’re going to create it we’re going to create an overloaded function for frequency it’s actually not that hard to do I’ll show you okay and here’s the other thing the default sort is

ascending in other words it goes from smallest to largest not largest to smallest right so you have to be a little careful with that it’s relatively easy to get around that to you can do two things you can sort ascending and then reverse it because there’s a reverse function in a vector that’s nice or you could soar you could come up with a way to do it by the greater than as well I’ll show you how to do that too and this code is all online on the on the website okay let’s see how you would do that okay so we have our song with frequency struct here okay here’s how we overload the less than sign we say it’s going to return a boolean if you’re saying is this less than this it’s either true or false we’ve overload the boolean operator this is all boilerplate stuff right it’s like you’re going to have a constant going to have song with the frequency it’s a reference to the left hand side and a reference to the right hand side boilerplate you’re going to write that every time for this type of function and if you do have trouble writing these I’m perfectly happy to help you out it’s not not really a hard all you’re saying now is if the left hand side in our case frequency is less than the right hand side frequency return true because the freak because that means that the frequency of the left hand song is less than the frequency of the right hand song and that’s how it’s going to be able to sort it so you see how it’s going to be able to sort it you see how it’s going to be able to sort of using this it knows about less than and it says i’m going to use Stan and figure out if you overload less than it works Tom absolutely yeah you could totally sort using a priority queue a heap sort sort of thing sure yeah absolutely if you want to you want to do it that way that’s perfectly fine yep you would have to build that yourself and that’s you know how to do that now so you could do it right alright here’s how you sort it you say sort and then you give the beginning iterator and the ending iterator and that’s it and then what happens it does it in place or it generally does it in place but it will then when you when you after this line the songs will now be sorted by the frequency tada we win right and it’s quicksort and it’s going to be a good sort hundreds of people have looked at this and like made sure it’s a really good sort they’re going to use all the little tricks that you might not have known for your homework assignment last week right yeah it doesn’t have to say it will as long as whatever object you have in this case songs with frequencies or strings or whatever has a defined less than operator it will sort it just fine based on that less than now for Strings that’s already built in its alphabetical which one comes first in the alphabet is less than the one that comes later right for numbers they’re just numbers you know less than or greater than so for most of the thing things are already done for you for your own struct not done for you you have to come up with your own it’s not it’s two lines long it’s not that hard it’s just you got to know when to do it okay good if you forget to do that it will warn it’ll give you an error and so I can’t I can’t figure this out the error will probably be cryptic but it will give you an error regarding regardless okay yeah this one it is outside the structure kind of floating anywhere else in the file yeah it’s got to be before the sword happens I believe but that’s that’s it yeah you would probably put it in the you this one you would probably put it in whatever whatever you define song with freak you probably put it in that same file yeah or in the associated CPP file yeah good okay that’s how you can do sorts you can sort as I said by the by the greater than as well I show you how to do that in the code that’s online all right okay any other questions on vectors before we kind of go on in the next little bit yeah oh yeah it does delete bite so yeah it will it will when you if your vector is no longer exists it knows to do all the deletions now your own structure should have a a destruct ER as well if it’s going to delete it properly but but otherwise yeah well it will call delete on your it will call your disruptor for your class if you have one yeah good other questions on vectors again the code is online I’m perfectly happy to walk through anybody walk through it with anybody but it it should give you a good starting place for their sorts or for setting up your classes with vectors okay and hopefully it’ll be helpful all right how is it actually possible for classes to do this right this is the kind of this is like going a little bit more into the weeds okay you may never actually worry too much about the next little topic I’m talking about but you should understand it and you should

understand it so that you can read documentation about it that’s kind of the trickiest part right sometimes it’s like how does this work I have no idea because I don’t know how to read the documentation about it hopefully this will help a little bit the standard template library is called a template library because we use templates okay these templates are here’s the structure for building a class that uses any other type okay I’ll i have an example here that will walk us through what that what that actually means okay i’ll walk us through how that actually works let’s say we want to create a little calculator and their calculator does the following it adds two numbers and it multiplies two numbers together this might be our first attempt at this right this is not a temple it’s a regular old function you built this zillion times you have a class at irregular class I’m going to call it calc 1 it’s going to be public methods or multiply and add they’re both going to take integer integer integer integer return integers standard stuff right really simple your multiply function multiplies and returns the value not hard your ad does the exact same thing for addition and it works fine you do see that one plus two and you end up getting three and you do see out two times three and you end up getting six perfectly good right here’s the problem it only works on integers right if you wanted to go do it with floats you would you wouldn’t get this you wouldn’t get a floating-point answer at the end you get an integer and it wouldn’t even might not even work but it would probably try to jam it in there but it wouldn’t do what you think it does why because you’ve hard-coded int int int int int into all those ends right we don’t want to have to do that we want our function to be able to be used with integers and floats so you can do this this next page is your first like your hello world template okay let’s walk through what this says you start with the template you say I’m creating a template okay and then it said and then you say type name sometimes you will see it called class they’ve changed it to be tight name because that got confusing because they used class in other places by the first good decision I’ve seen in a while from like people who make these compilers right type name says what are you what type do you want to put in here it’s not a specific type it’s a generic type we’re going to call it t @ e can be an int it can be a float it could be a string it can be at struct it can be whatever you want as long as its defined type somewhere what have you done now you’ve replaced every where you had int before you’ve said let’s make it my type whatever my type is I’m going to replace there so this says multiply two variables called x and y of type T and return type T that that hard to understand it’s saying genera make it generic whatever your type is do it yeah like I don’t know that’s good question how would you may add or multiply trucks it’s going to work for the types that have add and multiply defined right good very good question keep that in the back of your mind for a minute okay so does this work now when we when we now create a calc 2 is the calc to class we do calc to angle bracket float and we say we’re going to use floats now and then our calculator works on floats woohoo right if we wanted to create a calc 2 with integers we could create a calc 2 with integers woohoo right that’s the whole point now it works or that okay we’ve solved it for other numbers hmm does it work for other things like strings oh good question can you have a calculator that adds two strings together what would a calculator do that has two strings what might be one thing it would do if you have a b c and d e f yeah it concatenates them that’s a that’s actually well defined for strings add a string to another string you get the whole thing scrunched together into one string and you get it back it’s actually defined right how about multiply what does it mean to multiply two strings together if you try compiling this like as it is right it gets through this and goes no problem i can add i can add strings and then it gets to this and goes wait a minute it says i don’t think i can multiply strings there’s no such thing as multiplying strings so then are you done and you say well you can never multiply strings no you define a

multiplication for strings whatever you want that’s the beauty of this right you say I’m going to think string string multiplication means this right and you define it i was i was thinking of an example of this so you know how in you guys haven’t taken linear algebra yet but you’ve you’ve probably taken physics have you done the the dot product and the a cross product for various things right that is a that is a function based on numbers that takes one piece at a time and does something to each piece and comes out with an answer at the end right so it’s kind of like it’s a different function it’s not a multiplication well it’s kind of multiplication but if you multiply if you bring the dot product on three vectors it takes like the piece first piece of the first one the first piece of the second one the first piece of third one it multiplies all those together and then the second piece of the first one on the second piece of the second one second piece of the third one it multiplies all those together that’s how the dot product works so it’s a you’ve defined that function for numbers that are vectors right you can do the same exact thing if you want so so this morning I thought I don’t know what it means to multiply strings but let’s say that I can do this I’m going to mow I’m going to say that multiplying strings is the following string 1 times string 2 is interleaving that’s what I’m going to say I’m going to say if you want but if you multiplied you strange together you’re going to interleave them so ABC times d e f gives you a DB ec f a DB ECF does that sound legitimate for you know we can call it that right we can say multiplication is that define it anyway anyway we’d like awesome right when you define a multiplication what did we see about two slides ago that is a very similar sort of thing to do to an operator overload it right you’re going to overload in fact it doesn’t even exist yet for Strings but you’re going to overload the multiplication operator right okay here’s how we might do this now this is actually looks more detailed than really as all I’m saying is interleave those two strings okay look string operator star that’s my overload here’s my string left hand side string right hands konsa string right hand side it’s exactly the same as that less than thing we just did remember boilerplate stuff very similar it’s going to take a string two strings it’s going to multiply them together it’s going to return a string and here’s how it’s going to do it it’s going to walk through the whole walkthrough both straight whatever the maximum one is you’re going to walk through that many times and you’re going to get to and this may not be the most efficient way I through that together at eight thirty this morning right but if you walk through this you’re going to walk through and then print out each character in turn of the one from the left then the one from the right until you get to the end of one of them in which case you just print the rest of the of the remaining one so you interleave as much as you can and then print the rest of the longest one that makes sense okay you can so I just defined multiplication for a string and then at the end you return the actual string itself not too bad good to find the multiplication when we go back and use this definition this one still works prints out ABCDEF because it’s ABCDEF because it’s concatenated it and this one works right now it works what is this going to say think I did it right hope I did that’s a space by the way and there’s a space before that letter oh what’s it say a secret code right so if you have you break up your strings into two things right you end up you can end up doing something like a little bit of coding right hey here’s here’s what we do okay so Elaine and I want to share something a secret right and we don’t want but and we only want to be able to know the full secret like when we get together like so if one of us gets captured while we’re a spy we can’t like this the message isn’t we both have to reach the place to get the message there and otherwise doesn’t matter so I take this one right and it Lane takes this one and we go both separate ways and we both finally meet up at the secret spy headquarters right and we put our message together and it says a secret code and it tells like the answer to like beating the communists or something right so whatever right so so that’s that’s that but anyway look you can you can do this by all you need to do is

overload that overload that idea okay questions on this yes have you do oh good question how do you know is a multiplying not a dereference it’s all context right one of the things about C++ is it happens to be a context now it’s not a context-free language it needs to know something about the contact it’s probably me it’s actually more explicit than that but it when it compiles it knows hey guess what if I see a multiplication here it can’t are the star symbol here because it came after another variable it can’t be a dereference doesn’t make any sense so it’s got to be a multiplication it goes through a hierarchy of kind of a heuristic of how to figure it out yeah good question yeah good question other questions on this when we starting our spy company anytime soon all right okay so hopefully that gave you a little bit of information about vectors a little bit about the possibly seeing type like templates right if you see something like this type name T that means that’s the type that you’re going to be sticking in there okay and you kind of get a feel for how C++ does this and then you can see you can do fun stuff like come up with secrets by codes other questions on this No ok let’s see anything else on this templates really important are really powerful you probably won’t use them much I mean like you probably won’t build many templates it’s not that often that you need to do something for many different types but you should be able to understand them and use them and you should use iterators definitely ok a bunch of vector a bunch of references here the vector reference is a good one a bunch of wikipedia articles good template tutorial idiots guide to templates you know all right all right if there are no other questions I’ll see you guys Monday to know next wednesday next y or tuesday in lab yeah the Monday labs will be the following Monday