I did a C++ University Assignment

so i have this series on my channel called code review pretty simple concept people send me code and i review it it's more of like a fun kind of let's take a look at some code and i'll give my opinion kind of thing now last time i did this someone sent him their university assignment i'll have that video linked up there and this was like such a interesting university assignment to say the least that i mentioned that maybe i should just rewrite it and just do it my way and of course everyone wanted that so here i am sitting down to do a university assignment in i think it's been at least five years since i've done any university assignments so the plan is pretty simple i have the assignment here in front of me i've kind of taken it and rewritten it basically paraphrased it because i don't want to give away the identity of the university or anything like that and we are going to give ourselves like i don't know this shouldn't really shouldn't take longer than like an hour but i'm going to basically go through this talk about the requirements and then implement this as best as i can now a fair warning what i'm looking at is a real second year university assignment i think the unit subject is called something like like data algorithms and patterns or something like that this is the exact same assignment that we looked at last time we did a code review like this is this is it we're going to be doing that exact one the reason why i'm being so specific about this is because this is a in my opinion quite an odd university assignment but hey it's a real university assignment that someone actually did and sent in the code for so that's i'm just i'm gonna do that what i haven't done is like hand-picked the best university assignment i could find the one that would maybe demonstrate the most value to you or would be easiest for me to do i'm just doing the one that we looked at and i i never planned to do this assignment when i did that code review so just a fair warning this is this is going this is about to get interesting so before we take a look at all of these requirements i want to mention that this video is sponsored by skillshare so for those of you who don't know skillshare is an amazing online learning community where millions of creative and curious people from all around the world come together to learn new skills it's honestly in my opinion one of the best skill sharing platforms on the internet i mean it's literally called skillshare they've got so many classes on pretty much any topic you could think of anything from creative topics such as like videography photography editing illustration all the way over to like business and marketing and productivity they've also got excellent courses on how to make youtube videos i really like this one by mkbhd as a c plus plus programmer i am pretty much all about efficiency and i think skillshare does an excellent job at that skillshare's videos are really well made and they're really kind of well timed they're like these bite-sized chunks that you can just watch when you have a spare five minutes you don't have to wait till the end of the day and allocate like an hour or two to just spend on this thing you can just consume it kind of on the go coming in at just under ten dollars a month for an annual subscription i think skillshare is fantastic value but also the first 1 000 people who click the link in the description below will receive a one month free trial a one month free trial of skillshare premium is plenty of time to explore the platform see what they've got and see what courses you like so go ahead and click that link in the description below check out skillshare premium see what they have to offer thank you again to skillshare for sponsoring this video now this university assignment let's take a look at the requirements and then we'll kind of talk about our strategy for implementing this okay so i just spent a little bit of time going through the actual assignment requirements that whole kind of sheet and then rearranging them into this kind of dot point format that we can take a look at together so the first thing is this time is gonna be marked automatically so it's gonna be put through like a bunch of test cases as we'll see in a minute failure to follow this guideline will result in zero so they're pretty serious about these requirements exactly one file main.cpp no design documents need to be submitted and the task is basically to implement a very specific hash table so this hash table as i mentioned in the code review video that we did last time it's not exactly a hash table even i mean you can't just put in a certain key and then expect to get a value out the key that you put in it's more of a hash set really and i mean the hash set is kind of pushing it but basically all it is is a storage of 26 english words as we'll see in a minute and the the word can either be in there in this data structure or it cannot so there is no kind of associative array i can't you know put in a word and get another word out that's what a hash table would be so i mean it does say it's a very specific hash table but i think that one thing we can take away from this assignment and assignments like this assignment is that it is in fact very specific it's unlike anything that i've actually seen in the real world which first of all does kind of uh you know kind of brings up the point of is this even useful but i think in a way it is because this assignment is a good example of getting getting you to actually follow requirements because it needs to be done exactly in this way so this very specific hash table what is it keys are lowercase english words so like apple for example length of a key is at most 10 so like words under 10 characters the hash function is and this is a quote simply using the last character example the hash of apple is e so if we put in a word like apple the hash is in fact e which means that obviously if there's i don't know apple and orange those are two words that end in e there will be a collision but of course we can deal with collisions as we'll find out in a minute the hash table contains exactly 26 slots a2z by the way if you're following along with this at home try and write down these requirements and implement this for yourself i think it'll be a good exercise and then we can compare our solutions in the end you won't need more because of course this is designed to just go through the test cases it's marked automatically if it goes through the test cases you win that's not to say we should maybe hack this and just produce something that isn't even a hash table but you know that is that is possible table slots have three different statuses never used tombstone or occupied so the fact that these are here and in quotes to me basically says that okay so we have 26 slots they have to be strings they have to be either never used tombstone or occupied because i mean i guess fundamentally they don't need to be strings but it seems to imply that they should be strings table starts with never used um so basically i guess in the beginning we initialized 26 slots all we've never used searching works as follows so given a key take its last character as the hash value so if we enter a key like apple then e is in fact the uh the last character first try the corresponding table slot so each letter in the english alphabet a through z has a table slot so we could basically have an array where it's like from 0 to 25 and then we just need some kind of conversion function to convert from the letter into the table slot i mean it's just really just we could use it as an index if the key is there you found it if it's never used it doesn't exist so if we put an apple and we get back never used it never existed if the key is occupied or tombstone then move to the next slot so if we're trying to look for apple and we get occupied and it's not apple or we get tombstone then we try and move to the next slot and we may need to like wrap the table so if we're at slot 25 we'll go back to zero keep trying until key is found or we're certain it doesn't exist so so at worst this is just going to search the entire table basically i mean it's kind of unlikely because if we run into never used then it doesn't exist so unless the table is literally full and we don't have that key we're not going to search everything keep trying until key is found always certain it doesn't exist yet insertion works as follows so first perform search to see if the key exists if it does then do nothing take the take the last character of key as hash value so we get if we're trying to insert apple we take e if that slot is not occupied put the key there and occupy the slot if it's occupied try the next slot until you find a free slot so this is the collision kind of management so what happens is if we already have apple in the list i mean i'm even accidentally calling it a list instead of a hash table because that's basically what it is but if we have apple in there already and we're trying to insert orange they both end in e we end up in that same kind of index but what we do is we just go forward in index so we effectively put it into the slot of the letter f instead of e now according to these requirements if it's occupied try the next slot until you find a free slot until you find a free slot so if there is no free slot um this will just go infinitely and i'm pretty sure that's what the assignment that we looked at did it's just it just happens to be that none of the test cases happen to use more than 26 and i mean the assignment does say that we have exactly 26 slots and we won't you won't need more so if you won't need more then i guess this is fine because it will it should never run into a problem where it just can't insert the value because there's no free slots since at most we have 26 slots and 26 possible inputs deletion works as follows given a key search for it to locate its slot if it doesn't exist do nothing and if found change to tombstone so if it if i it doesn't really say what to do if so i guess if you run into it never used then clearly it doesn't exist tombstone would mean you go to the next slot because there could have been another key there but then also if you get occupied and it's not the key you're looking for then you also move to the next slot so i wonder what would happen if you try to delete a key and then you try to delete that same key again it would probably go through the whole table and not find it but then the search function keep trying until he's found always certain it doesn't exist so the search function needs a way then to basically terminate if it has in fact searched everything and it couldn't find it again very unlikely because we will we will run into a never used unless the hash table is full so i guess we can ignore that when program starts init empty hash table so 26 never use slots okay command line input is 1 through 26 modification moves separated by spaces so moves are a word which is the character a followed by a lower case english word of up to 10 characters so a apple means insert key apple into hash table same with d except d is for delete so delete apple from hash table is d apple once input is processed output is all the slots in the hash table that have occupied values separated by spaces ignore invalid inputs so if the input is malformed we just ignore it okay so sample input is this a apple a orange so we've added apple and orange and then we've deleted apple and then we've added strawberry and we get orange strawberry which is what you would expect submit via svn and then marking done automatically total markers 10 one for compiling and then nine marks for nine test cases and it's also compiled using g plus plus um with c plus plus 11 optimization two warnings all main.cpp so obviously we have to provide a main.cpp as it mentioned above and then we also have to uh make sure that we are in fact only using simple house 11 and that it compiles with g plus plus so that's obviously the compiler we're going to use for this assignment the uh the sun is really creeping up on me you know i didn't really plan for this to be this in depth let me know what you think of this kind of uh this this kind of video i was going to just skim through it in like 10 minutes but there's just so much here to unpack so i'm probably gonna skip the whole designing this stage i mean the assignment mentioned we don't need to submit any kind of design document and also i think this video is dragging on long enough so i'm probably just going to jump into the code and start programming this at its core i think it's quite simple it shouldn't really give us too much trouble there's just a few particular cases and um you know i mean i i don't really want to change this too much like you know it it says table slots have those kind of never used tombstone or occupied statuses i could make that some kind of enum or an integer or just like something like that i don't think i will i'm not really going to be focusing on performance here i'm just going to try and implement this as best i can based on these requirements and obviously so that it actually gives us our output correctly okay so as we dive into this let's take a little bit of a look at my setup for this assignment so i basically have just made a folder i've opened up sigwin and then the reason for this is because i just found this on my computer and it happened to have g plus plus kind of in the path i didn't really have this in command prompt so that's why i'm using this just so that i don't have to like add it to my path or do anything crazy like that you can use anything you want because the only reason to use this terminal at all is for the actual compilation now if we take a look at the university requirements they're pretty specific meaning that we need to use basically this exact command to compile our code if we don't do that then there's a possibility that of course it won't compile like if our files are not named correctly or something like that it just won't compile obviously on the automated testing and when you're dealing with automated testing you need to make sure that everything works exactly the same way that it's going to be automatically tested i don't want to get zero for this assignment so we have to use this now instead of typing this all the time uh it makes sense to kind of put this into like a little bit of a batch file now i don't think that like we're not going to be the ones running the command we don't need to write a file like a script for the server to execute or whatever they're going to be running the command so this is just for us and we're on windows so i'm just going to touch a file here called like build.bat and then inside that build.bat file that we've just made let's go ahead and drag it here and then we can paste in that command that's all we're doing it's just so that instead of actually having to run that command every time i can just call uh build.bat like this please help me um now if it's giving you a permission denied it's because this is like a kind of linux e terminal i guess and so we have to actually do a chmod plus x to make it executable so let's go ahead and do that not technically required on windows we can of course just run it normally but to run it through this it wants that to be happy anyway there we go so we don't have a main.cpp file so let's quickly just touch that in here and now we can just drag it in to our um vs code over here and we can just edit that let's just try compiling it i mean obviously it's not going to really do anything oops i touched it again let's go back and run build.bat and then i mean we don't have a main function or anything like that so it's not going to do anything but obviously it's sending the right file to the compiler so the first thing i always do in these cases i mean always is just make sure that my tool chain is set up correctly especially when compiling from the command line so all you have to do for that is include like i o stream and just try and print something so i'm going to go ahead and print hello like this and then if we go back to our sequin over here and try to build up that you can see that it compiles and it gives us a main dot out if i run this main dot out then we get hello printing and everything as well now to make this a little bit easier what i can do is actually call build bat and and so double ampersand and then main dot out and that way it will compile it and then run it immediately so this is kind of nice when we're testing if you don't want to set up like a whole thing through vs code because i don't really care about that to be honest okay so moving on to the actual code i'm going to be referring to the assignment requirements pretty heavily for this i have them on my other monitor so i'm not going to show them all time if you want to look at them you can go back in the video but i will highlight certain things so the first thing that i actually feel like starting with is the input processing so we know that based on what they've told us the input can either be um like a word or d word basically so if i copy and paste stuff from the assignment sheet that i made earlier then you can see we have a apple a orange and in fact let's go ahead and copy the sample output so if we start to take a look at this input i basically just want to make this command parsing work why because it's going to be the foundation for testing the rest of the application and i like to iterate frequently and test pretty much all the time so how are we going to be able to pass this input so we know that we have one character here a or d that's going to be basically one of two commands so we clearly need to determine uh whether or not the command is to add or delete but before we do that we also need to be able to take in a string like this and separate it by each space lots of different ways to do this i think the most straightforward way that is also obviously supported in uh c plus 11 is just to use string stream honestly so what this means is that if we wanted to take a line in which it seems like if we look at the requirements they're not actually command line arguments the sample input is literally this it's not like you know running the application and then passing in everything as command line arguments so we're not going to be using those we need to actually be able to take an input from scdc in that's how i interpret it and that's also how the assignment we looked at during the code review did it so because of that let's go ahead and just basically write our input here we'll use the getline function to just get that input line from c in this obviously gets our entire line and then what i want to do is actually feed this into string stream so if i go std string stream ss with that input string what i can do now is just keep pulling out tokens from this so if i write a while loop that continues basically as long as that string stream still has tokens for us to process we can simply pull out the token uh by using this kind of bit shift right operator here so now we should just have a list of tokens basically so let's go ahead and try and print them just to make sure everything is working successfully and you can see we basically have most of our input parsing sorted already very easy so i'll save that by the way we do not need a return zero that's not really required although now that i'm thinking about it maybe it is in c 11 maybe that's a newer feature but um no actually we would have gotten a warning especially with warning all so the main function is special in the fact that even though it returns int you don't have to return anything and it will assume you're returning zero so let's go ahead and run our little command once again and we'll see what we get so okay so it's waiting for input now so let's go ahead and copy this input that we'll be using as a little sample input for now i'll paste it in and run it and you can see we get every token here on a separate string so that that's immediately done i mean you can see how quick that is really really easy to use um and no need to like go through every character look for spaces anything like that we can just take advantage of this t plus plus standard library that was available to us back in back in the day back in sleepless 11. okay so moving on now let's go with the kind of second part of the input parsing which is what do we want like to add an element in to insert an element or to remove an element so to do that we just simply need to of the like for each token so our token obviously is going to be like this for example for every token we just check the first character so in other words uh if that first character of the token so token 0 is equal to a right and remember it has to be in this format has to be uppercase this has to be lowercase everything's very much set in stone so it's really easy for us to do our jobs here if token equals a then that's kind of it else if so there's no reason for us to check it again so we can just use an else if we can go over here and uh check to see if it's d and so basically this means that we have an add command and we have a delete command but then we have the next kind of stage of this which is kind of okay so i've got my add and delete commands but what string do i send to that command right because um we obviously don't want to just take the token and send it because the token is a apple we are interested in this so what is the easiest way for us to actually uh take this i guess take this token and just trim off that first character so a few ways come to mind um the simplest one probably using the standard library is just to use substring so if we go ahead and say like sd string and i guess this is like entry name um we can just set that to like token dot sub string so substitute one and then that will automatically go to the end of the string and starting from the first character so that's definitely going to work i think so if we go ahead and well let's kind of set this up so we'll do scdc out and then we'll say add and then i'll print the actual entry name that we're trying to add here notice that i've written this um in uh let's quickly add that end line in notice that i've written this up here i'm not doing it in each if statement because it applies to both and if that if if we give an invalid input then it doesn't really matter anyway um so let's go ahead and go back here and see what we get so i'm going to go ahead and paste in my input and then you can see we have add apple add orange delete apple and add strawberry let's for fun put in like some inputs that um are just a bit weird so i'll put these in but maybe the first uh i know i've ruined something let's try that again so if i paste in like this input for example but let's just archer which is a bit weird oh thanks for overriding everything but whatever then you can see it just simply ignores cherno it just goes with well actually add apple still and then cherno's here ah this is just i think this is just sigma being weird so let's go ahead and run that again um so let's just type in hello a apple d orange which doesn't exist and then some random stuff you can see out of that it only took an add and delete because those are invalid commands okay so it ignores all the other ones which looks like it works fine the other way that comes to mind that isn't really required is we could just use the constructor of our city string that takes in like a cons chart pointer so in other words if we were to get like this character from it basically right um except set this to be the memory address of the first character of this which is this the memory address of this since it is just a string buffer we can also do that um i assume i'm not going to lie that actually came to mind first because i'm usually thinking about memory and stuff like that but you can see that we get the same kind of result i would probably leave it as substring just because it probably makes more sense to most people okay brilliant so we've got the entry names we've got all of the input parsing done it ignores everything it's very clean at least in my opinion so let's go ahead and talk about the actual hash table now so the way that i want to write this um because we have some fair initialization code that we need to do remember we have to fit we have to fill in 26 slots with the status i've never used so i'm actually going to write a class for this um it's not really required to do this of course you can write this however you like but i'm i'm kind of thinking of it as a class and i want to keep it organized under a class so what we're going to do is write a hash table to be honest the constructor i think is probably just going to be a default constructor and then this is going to contain a bunch of entries and this entry structure i'm going to create in a minute but each entry is going to contain the actual data that we're storing as well as the status because those need to be stored separately so we're going to go ahead and i guess i'll just call this entries and we know we need 26 of them rather than writing 26 i'm probably going to let's make a little uh so i can't use constant expression const expert because that's not a 6 11 thing so let's go ahead and just make a static constant i'll call this size so this is inside the hash table namespace so clearly we're referring to the hash table size and i can just pass in size as long as it's const g plus plus probably accepts non-constant uh like stack allocated array things as well but whatever we'll leave it as this so um let's go ahead and create that entry struct again i'm going to create this right within the hash table like this in the public section because i we don't need to pollute the namespace or anything and i don't want to call it hashtable entry it fits perfectly inside this class again i'm just using this as a bit of an organizational thing so we have the data which we're storing and then the status as a string which feels a little bit uh a little bit wrong to me to store status as a string but again we're following the assignment directly and it's not really going to make any difference if we really think about it if you spell everything right and you're not going to have like thousands of string comparisons which isn't going to happen okay so anyway we've got this we've got our 26 entries now let's go ahead and actually fill out these commands so the first step that it actually says by the way is to initialize everything with never use which i've actually already done right so entry creates 26 of these they get initialized with never used so technically speaking we should already have 26 never used entries just by doing this we don't need to manually iterate through everything and to kind of uh you know demonstrate this i'm going to write a print function which we need anyway because the output needs to be that and that's basically going to go through and just output um all of the entries that we actually have but for now what i'm going to do is actually go through every entry and just print everything mostly for debugging so i'll go through all of the size here and then basically what i'm going to do is just do scdc out and then we'll do m entries m entries i and let's do let's just print the status of the entries for now um and i mean i guess it makes sense to also do the data when we're debugging and stuff like that so let's do data and then um maybe like some kind of uh bracket over here parentheses to actually print the status and uh obviously the data here as well so let's go ahead and just run print basically so i'm going to go ahead and actually create the hash table it doesn't really matter where we do this um let's just do it like maybe over here so we'll go ahead and say hash table hash table and then um after we pass all the input i'm just going to go and do hash table dot print which will eventually become the print function of printing it in this format which is what we uh require so let's go ahead and run that um i will paste in my um my test kind of case and then you can see that we already end up with no data in any of them and just 26 never use slots so everything looks like it's working pretty well okay so the next stage is to add these functions that are going to add or delete our entries so we don't actually need these because i'm just going to call hashtable dot add and then i want to pass in the entry name so we have add and delete could call this insert but we'll call it add for a um and uh let's write these functions so up over here void add now we're using okay so i probably would take this in as some kind of string view but since we are using c plus 11 which doesn't have that i'm just going to take it as a const reference so const scd string entry name we'll call it maybe entry string because it's not necessarily a name i might go over here and rename it as well for consistency not that any human is going to read this assignment apparently it's just going to be all done through uh an automated testing little program so great anyway um so we have uh add and delete so what is ad going to do so let's take a look at the requirements so to add we first need to perform a search to see if the key exists so what that means is that we need to look at this first so given a key take its last character is the hash value let's focus on that first so what i'm going to do is actually write a find function which i guess will return like a boolean whether or not it actually finds what we're looking for now if i'm being really like pedantic about the organization i guess i would mark this as private i like to make a separate private section for functions versus members by the way so we'll have a find function that takes in some kind of entry string and looks for it but obviously in order to actually find it we need to first be able to hash it so i'll call the hash function get index because that makes a little bit more sense to me and i guess what we'll do is we'll just accept in a string and we'll get back the index into this array that it should belong to so how do we calculate the index well the hash function remember is just the last character of the string so entry string dot back gets us the very last character no need to do something like entry string entry string dot size -1 you can just use the dot back function and it will get you the last character of that entry string but now how do we map that into an index here i mean we know that if the character is a and it is in fact through um from a to z a should probably map to like zero inside here and then z should map to 25 which i mean it won't at this case so how do we write a conversion function well the way that ascii works obviously is that every character actually has like a numeric value and if we look if we take a look at like ascii table dot com for example we know that the lowercase letter a has a decimal value of 97. so if we were to take the last character like a which is actually just an integer with the value 97 and subtract 97 from it we get 0 which is exactly the spot for it similarly if we get the second character b and we subtract 97 from it is 98 we get 1 which is slot 1 all the way down to z if we subtract 97 from 122 we will in fact get 25 which is the correct value so all we have to do is subtract the numeric value now that's really really easy to do there's no need to like create some weird switch statement that goes through and like you know tries to map you know a to 97 it already is that value so all we need to do is take entry string dot back which is a char and subtract another chart from it like a and that will subtract 97 from whatever the character value here is now of course if we abuse this and put in uppercase characters or symbols we will probably get a crash because it will not be in the bounds of the array but that's not what the assignment requirements state so that's all we'll do we just have to return entry string dot back minus a that is our entire hash function pretty easy so now that we've done this uh hash value key thing find first try the corresponding table slot if the key is there we found it if it's never used it doesn't exist so we can return false from our find function if the key is occupied or tombstone then move to the next slot and keep trying until the key is found always certain it doesn't exist pretty simple so all we have to really do is go through basically every slot check to see if it's actually is equal to the string that we're trying to search for and then if it is returned true if it's not and it's and it's never used return false otherwise we can obviously return uh otherwise we just keep going basically so let's go ahead and start by probably declaring some kind of index which is going to be the ideal index of entry string so we can do that by just running our get index function with the entry string and then we can just write a little while true loop to make this kind of easy now it didn't say anything about terminating after a certain uh you know after a certain kind of amount of iterations or if we can't find the string because remember we'll never have more than 26 so it's a little bit you know i probably wouldn't write this in real code but for the assignment it's totally fine so what we'll do is uh check every entry so now we're at this index so we just need to check entries at that index to see whether or not the status here is well let's just go with never used first so if it's never used um and uh it's not equal to what we're actually looking for then we know we can just return false but obviously before we do that we actually need to see if this index contains what we are looking for and we can do that by just doing m entries dot index dot data equals that entry string and if it does then we found the string and we can return true even though i'm writing false for some reason so there we go return true if it's never used we return false and then obviously the last thing to do is actually increment the index now we can't just increment it because if it's some because it needs to be able to wrap around so instead we can just set index equal to index plus one mod the size of our table basically and that will wrap around if it's 25 it'll go back to zero when we try and add one to it and then mod it so that's pretty simple if we somehow get to the end of this i mean this will never this is unreachable code but we'll write it anyway return false again i would really make this terminate after like 26 iterations but um whatever so let's go ahead and try that out i guess we'll try and find something that has been oh well i mean we can't do this yet because we haven't added anything so the first step is try is to try and see if the key exists if we're inserting uh if it does do nothing okay otherwise take the last character of the key as the hash value obviously we have our get index function if that slot is not occupied put the key there and occupy the slot if it is occupied try the next slot so immediately let's implement the first stage of that um let's go ahead and just write a boolean called exists we'll call find on entry string so if it if it does already find it so we're trying to insert something that exists we can just return basically from the function um otherwise let's take a look at uh where to add it so now i'm thinking like okay i mean we've searched this this already goes through the loop we could write another function that basically tries to find the next available spot for insertion and i think i will do that the other idea that came to mind that we might use for something else a little bit later is actually taking in a parameter that is our kind of out insertion index and that way when we do stumble upon a never use or a tomb slot just since we're since we are actually iterating through this we could just immediately set out index to that first index but i think it will probably make more sense to just write another function which um is something like find or something like get insert index or something like that so get insert index will find the first available place where we can in fact insert entry string and so what it will do is again it needs to see what the ideal index is and now it's just about seeing what is currently at that index because if there's nothing at that index so if it is in fact never used then um we will in fact just return this index since we can put it in there and in fact it's not if it's just never used it's also if it's uh tombstone because it's that you know an object has been deleted and the requirements state that if it's tombstone or never used then obviously that's a valid insertion index otherwise we basically keep going so in other words if the status is in fact uh occupied then we keep going until we find a suitable index um so this will return an int instead um we're obviously returning index otherwise i don't know we can return negative one it doesn't matter this is a wild true loop and anyway we won't get into that also this is another really good case for why string comparisons are just a really weird idea for this um you know we have to type this perfectly otherwise it's not going to work and also we are literally just comparing comparing character by character to see if these are equal i don't know why we're doing that comparing an integer like viral enum would be obviously a lot better but we're doing this this way because i like pain okay so now we obviously can scroll back up here um and just see what our kind of insertion insert index i'll call it is so we'll run get insert index with entry string that should give us back a valid index and then all we have to do is do m entries insert index we need to set the data to be our entry string and then we need to set the status to be occupied uh and i think that's probably it for the add function let's go ahead and test this i'm a little nervous because we've written a lot of code there is no like you know intellisense or any kind of error checking inside this uh text editor so let's go ahead and just run that and see if it even compiles okay it did somehow um and let's oh well actually i'm not adding anything am i i know i am so let's see because it will in fact print it so let's copy our example case and see what happens obviously delete doesn't really work yet okay so um what do we have we have apple occupied at slot what is a zero one two three four so a b c d e and it does in fact end with e that's occupied orange is occupied at the next available slot because it also ends with e remember i mentioned it would take the f slot and then strawberry is occupied at the y slot because this is obviously z so looks pretty good obviously deleting doesn't work but i think we were able to validly kind of validly i don't know if that's a word um we were able to insert properly all of our kind of elements that we try to let's make delete work so what does delete do um so delete basically does uh something similar to this right i mean it tries to find whether or not this entry string exists if it doesn't exist then we return because there's nothing to delete but otherwise we need to actually like find the index of that actual entry right so this is where i am actually going to modify the find function so the find function returns true or false i could get it to return an index and then we could check to see if the index is negative one which means it didn't find it something like that but what i'll do is instead i'll take in an integer by reference which is going to be out index right i'm just i'm labeling it as out so we know it's an output parameter but um basically what this is going to be is in the case of the fact that it does in fact find what we're looking for it's going to set the out index to be whatever index that happened to be at so now it gives us a little bit more information it doesn't just tell us whether or not the entry string exists it tells us where it exists and that's perfect for a function labeled find so now what we can do and that's really i think all we need to do because this returns false we don't care about that so if we go back up here we'll have to add it into here even though it's unused so i could um you know just label this as index or even unused if i wanted to by the way i could make this a pointer and that way it's null by default and if it's not by default you don't have to use it that way you know what i've already shown you guys how to do it this way i might as well show you the other way so the other way would be if we make this a pointer instead set it to null pointer as a default parameter and then what we could do is uh set uh out index to index if it's actually valid so if it's not null we'll set out index to index like so dereferencing and copying the value into that output parameter and then um over here that means we can still uh for the for this case we can call it with no parameter but then for this case we can in fact make an integer called index um and then pass that in like so so let's go ahead and compile that and make sure that works um okay it does i'm not gonna lie i was slightly scared that default parameters weren't supported in cpus 11 for some reason i think i'm thinking of like c plus plus 98 or something uh way older than c plus 11 or c plus zero three um anyway so delete um so if it doesn't exist for return otherwise we've already got the index of deleting it so what do we do well really all we need to do is mark for that particular index the status as tombstone now we could clear the data it doesn't really tell us that we have to and obviously if it's tombstone when we write our print function properly it's not going to print it it's only going to print occupied slots so we don't really need to worry about wasting time changing the data that's kind of it the one thing i will do to these two functions is i'm going to change the if statements because at the moment i mean we have a return here and we also return obviously when we get to the end of the function multiple function returns can be a little bit confusing if this was a huge function i would definitely leave this here because i don't like to put massive uh you know bodies of like if statements and stuff like that but for this because it's only three lines of code and here it's even it's even shorter it's just one line of code what i'll do is i'll say if not exists right then we can add it by just basically uh putting this inside the if statement like so and then here if it does exist let's just delete it like that so this makes it a little bit more clear and that way we know where we exit the function it's going to be in the same place i think that is possibly it so let's take a look at this again um i can't believe we're getting no compile errors i mean i'm just writing this and no errors look at that so where's our example cases uh here they are um paste okay so we didn't crash which is nice um okay so apple has been set to tombstone right because we added apple we added orange we deleted apple and then we added strawberry so apple has in fact been changed to tombstone now here's another test actually tombstone should be a valid parameter to use so what happens if i do apple orange and then let's add something else grape is also a fruit that ends in an e so let's go back and uh try and add that in because it should occupy that slot actually so that that'll be a nice little test um i know i'm compiling it every time i run it but it's okay it's fast um all right so there we go so apple okay apple tombstone and then grape actually goes to this occupied slot so i'm not sure why it didn't actually use this let's go back to the code and see maybe why so get insert index is in fact supposed to check to see if tombstone is a thing so that is uh very interesting oh never mind it's because i'm adding the grape before i delete the apple so that's that's fantastic so let's go ahead and make sure we add this after we delete the apple and we'll try that out paste this in and there you go so now grape is in apple's slot basically so i think that's kind of it now the last thing is obviously to make sure that this is um formatted in the right way because that's our our expected output i'll get rid of this and then so to do that we'll basically just go through and iterate over all of our outputs wherever that happens here we go in the print function except instead of printing uh you know the status which we kind of use only for debugging i'm going to go ahead and let's add a body to this if statement i'm going to go ahead and just check to see if the status is occupied because if it is occupied uh then we uh actually what am i doing status equals occupied then um then we're going to go ahead and print the data otherwise we're not so we don't want to print it on a separate line we actually want to print it along with like a space so i will add that in and then i guess we'll print a separate line at the end so it's a little neater okay that i believe is it so let's go ahead and run this i'll paste in my data which is gone let's go ahead and find it again paste it in and we get a whole bunch of nothing and that of course is because this should be out here not after every iteration just because the for loop didn't have a body before this let's go ahead try that again paste that in orange strawberry that is in fact our expected output so i believe we have finished this assignment about 100 lines of code uh pretty pretty quick to do i think this code is a lot cleaner than the code that we obviously reviewed last time and hopefully you learned a thing or two by watching me do this assignment now before we actually claim that we've done it let's take a look at the test cases because i also have access to those so these over here are the actual test cases that were uh given to everyone doing the assignment first of all i mean you can i don't want to like roll the ball we'll say on on anyone here but like the effort that has gone into this assignment is so little i mean there's just random characters like one of these has actual words anyway so let's go ahead and uh i mean i'm not gonna do all of these let's go ahead and maybe do this one and see if we get the expected output so let's go ahead and um actually these might have been the actual test cases because it says your output so this is this is cool so let's go ahead and grab this test case over here we'll go ahead and run this and we'll paste in the uh input and the output is banana orange tomato which is in fact correct let's try this like crazy long one here um we'll go ahead and clear this and run main dot out paste enter now i'm not going to compare this manually so i'll just go ahead and copy this and see if we can find it within here and in fact it does show up in defined results so we know that it is in fact the correct string and uh let's go this has a bunch of deletions let's go ahead and try this one and we'll call it a day so main dot out right click paste enter then we get a uh yeah like five a's or six a's and then this okay cool so that is in fact a wrap so actually one thing i forgot to mention was that students were given three weeks to complete this assignment i just uh wanted to throw that in there let's go ahead and clean this up a little bit i will leave a link to this in the description below in case you guys want to take a look at this if you have any questions about this implementation or you want to or you have some suggestions as to how to make it better please let me know of course share all of that in the comment section below but otherwise i think we managed to do a pretty good job so a couple things that i noticed while editing this actually is um i mean for a lot of these functions i could have definitely made them const it's a little thing but it's usually something that i like to do i just forgot to do it um so obviously these don't actually modify the state so it's fine to kind of make them um const and then the other thing was if we're really being kind of pedantic and we should be to be honest because it is automated testing this print function uh prints our values but it adds a space after every single value that it prints meaning that if we did have something like this um this does have a space after it so the expected output doesn't have a space after it but it looks like um the person who did this uh code review actually did have a space after it like we did and i guess um i mean they got i think 10 out of 10 or something like that for it so clearly that's fine the automated testing ignores spaces i guess but if we were really being like super uh you know serious about these requirements we wouldn't want that space to be printed now unfortunately this isn't quite as straightforward as it seems because we can't just do something like if i less than like size -1 then print a space because we're not iterating through all of the elements necessarily isn't we're not printing all of the elements necessarily i you know i less than that might not have an occupied slot which means that well you know we'll always print that space so to be honest the simplest kind of logical thing that i can think of is to actually do the space first that way we'll never have a trailing space but then the question obviously is whether or not we do it for the first iteration right and so what we can easily do is just have a little first thing where basically if it is not the first element then we will do a then we will do a c out with a space uh and then i guess we can we can just set first to true here all the time except let's like set this to false because that'll be correct so then basically what we have here is uh a little boolean called true that we basically uh we we won't actually mark it as false until we run through this for the first time then we'll just keep setting it to false which is fine but the idea is that we only do this we don't do this for the first time that we print this um so obviously we get rid of it here right so we add a leading space if it's not our first element that we're printing and that way we'll never have a trailing space to deal with so if we go back over here let's uh compile this and run it and let's try this input because i don't think we tried this one so if i paste this in i mean i guess it'll be hard to see if we actually have a trailing space but you can i guess you can see over here that um it doesn't look like there's a trailing space and this of course should be the correct output and you can see that it is okay so i hope you guys enjoyed this video if you did please don't forget to hit the like button below let me know what you thought of this kind of uh video i mean it's not something i've really ever done before so i'm definitely interested in your feedback hopefully this was helpful to you guys if you have any criticisms for my code feel free to point them out in the comment section below and have like a discussion with everyone if you have any particular university assignments or other kind of tasks that you may have done that you found interesting and you'd like me to either review them or maybe even take a crack at implementing them then send an email to chinareview gmail.com the email address will be in the description below and i will take a look at hopefully some interesting content like this in the future but anyway thank you guys for watching don't forget that you can check out the link in the description below to get your free trial of skillshare premium and i will see you guys next time [Music] goodbye [Music] you

Channel: The Cherno

Views: 157,796

Rating: 4.9304752 out of 5

Keywords: thecherno, thechernoproject, cherno, c++, programming, learn c++, c++ tutorial, I did a C++ University Assignment, c++ assignment, university, assignment, c++ university assignment, programming help

Id: kQsHF7C-FUY

Length: 50min 22sec (3022 seconds)

Published: Fri Jul 02 2021