UNIVERSITY ASSIGNMENT! // Code Review

hey what's up guys my name is the channel welcome back to another code review for those of you not familiar with this series this is where i basically take a look at your code and try and give suggestions and or thoughts depending on what the project is if you would like the opportunity to appear on the next episode of the code review series then read the description there'll be some information as well as an email address where you can send your code to so today i thought we would do something a little bit different for this series in the past we've been looking at like graphical projects mostly stuff that we can look at on the screen whether that be like a 2d game engine or a game or some kind of like particle demo that's what we looked at last time i'll have that video linked up there but i know a lot of you watching my videos are just students and maybe it's even your first or second year of university you're going through and learning about all these different data structures so what i have today is an actual real world university assignment where the task was to write a hashmap this particular person who sent in this code wishes to remain anonymous probably because this actually was a university assignment and maybe there are certain rules against sharing them but for the purposes of this we'll call him tim that may or may not be his real name so tim has sent in a single file implementation of this as about 200 lines of code here as well as the actual university assignment sheet which is really cool because i'll actually see what the requirements are i think that it's worth noting that with these university assignments i mean i remember the ones that i kind of got some of them had weird requirements and the marking criteria was also not really what i expected if you contrast that with real world code like if i was actually writing a hashmap for my own purposes it would probably be vastly different than code that's specifically written for a university assignment so it's going to be really interesting to actually take a look at a university assignment but before we jump in i just want to mention that this video is sponsored by skillshare 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 basically it's a platform with concise informative high quality classes that will teach you almost anything you want to learn whether you are interested in photography videography more business side topics like business management productivity marketing or one of my personal favorites illustration skillshare has you covered i've mentioned this before but i think that their illustration classes some of the illustration classes that they have there are absolutely phenomenal and it's just so relaxing to chill out after a long work day and just draw something that's one of my favorite things to do right now coming in at just under 10 a month for an annual subscription skillshare is also fantastic value i honestly don't think there is any other platform out there that has so much information condensed into such a consumable format a lot of their classes have videos that are like 5 to 10 minutes long which is perfect if you only have a spare moment but for a limited time skillshare is giving the first 1000 people who click the link in the description below a free trial of skillshare premium so that you can access their whole library for free and see what they have i highly recommend you do that you will not be disappointed huge thank you to skillshare as always for sponsoring this video let's take a look at some of this code i think it's amazing that you have to submit this via svn so before we jump into the code that is in front of us and take a look i've been reading this assignment sheet i don't really want to show it because it gives like the name of the university there's a bunch of stuff here you know we'll just ignore this you guys will just have to take my word for it but this is like what an assignment this is i mean i don't know who wrote this it's just very strange like it's it's odd to me because i feel like the assignment could have been you know just write a hash map that works maybe like four strings hashes strings you know generates like a little index as to where to store your data and then like let us be able to retrieve this and maybe basically avoid some you know collisions in most cases with the test data like that would be a reasonable assignment this is very interesting and i think it's almost more fun that you guys don't know what i'm seeing because as we look through this code i think it's going to be quite amazing anyway so first of all there's a disclaimer here which i think is great assignment requirements set by the hash table size uh set the hash table size of 26. i have verified that is in fact the case which is also the maximum amount of entries i know this is bad for two reasons once it's not prime preferred size of the table is 26 times 1.3 to minimize the chance of collisions sure however this is assignment requirements yes some of these assignment requirements are a bit weird let's um so this is all the code that we have here let's maybe start with the main function because that's a good place to start reading code from i think so the first thing we do is create a string called str now this is already a you know i'm going to start the critique here um don't do this like name the variables so what is str i mean you know i can maybe deduce the str is going into you know get line c in so this is us taking input from the console so like maybe something like you know at least input or like um you know input string or like you know whatever something a little bit more destructive descriptive than str because that's a little bit annoying like this is called user input but this you know i'm not the biggest fan of this okay good so we get the line from cn sure then we send it into the input formatter function which is all the way up here um this takes the string this copies the string um and then i guess has an output of user input now one thing i personally like doing you don't really need to do this if you don't want to but i like well first of all i like writing the um you know the uh the asterisk or the uh reference the ampersand reference operator on this side i know some people prefer it on this and there are reasons for both but um that's besides the point my point is that user input is clearly meant to be an output right this is where this data is being pushed to so what i would do is just name it something like out user input that just makes a little bit more sense as to like what's going on with user input especially if the variable is called input because that almost implies that maybe this returns something but it doesn't that's also an option you know return uh you know in this case we're creating a um are we using this function a lot actually no we've nev we never use it again so this would be a good example of maybe having that vector be a return value because then these two lines and all of this kind of code would just be simplified to hey you know let's take in the string and then let's format it into this vector of strings so that might be a little bit easier to understand which is always good um by the way with these like code reviews i mean even right now i'm just looking at this code and i'm going to give some uh advice as to how maybe to write the code better like the thing is the the the requirements for this assignment are set in stone and they are pretty not flexible um and i think my favorite part of the requirements was also how it says that this will marking will be done automatically the total mark is 10 one for compiling so i guess if it compiles you get one mark and nine for nine test cases i don't know if it it doesn't outline the actual test case but it gives you some sample input inputs and kind of expected outputs but in general the requirements are very specific i think that if anything this is maybe teaching how to follow requirements because uh again they're just very non like real world use case kind of requirements anyway so what do we do here so we go through the size of the string which again is the input now the first thing i would do here by the way is definitely not take this string in as a copy like this like that definitely doesn't need to be done now this is an existing string you basically have two options you can take it in as a const reference that's probably what i would do because i tend to do that a lot the other thing you could do is just use a string view that's just basically a view into that string that just it doesn't copy it it just it's almost like passing a pointer to the string data with like an end point as well so that will just make it a little bit better because you won't have to actually copy that string which of course is a little bit of a waste of time not that this is a performance issue it's absolutely not we run this once at the start of our program no one's even going to notice that but for future use that that's i think that's helpful advice going through every character in the string is our next case and if the string character does not equal 32 okay please don't do this just write code like this right so 32 is the ascii uh value 32 in decimal is the ascii value for a space um this code is already a lot more readable i mean who on earth understands that 32 is a thing um so yeah write code like that it's going to be better one thing i noticed with a lot of this code that actually people send me is just the formatting is just bad like for example you know we have a new line for this and for this for these braces but then this one just is is on the same line for some reason this one's on a new line but that's on the same line it's a little bit inconsistent so if you're not using like visual studio or like an ide with an auto formatter just because i know visual studio will try and clean this stuff up for you whereas other tools will actually um have you like run i guess a command or something to make it happen just you know maybe just just clean it up and make sure it looks good again this does not affect the apparently this is does not affect the result of the assignment because it's marked automatically by a computer i would imagine and um if it can if it compiles and succeeds with the nine test cases that's a hundred percent so why bother i guess but i would still do that and removing like all these comments which again does not affect the assignment grade so it's i'm not digging this assignment um so yeah i would basically format things like this okay so if it's not a space we basically have a temp string that we append to okay this is bad for a number of reasons um what i would do though is rewrite this whole algorithm with basically instead of actually iterating through every character as if this is like the stone age just use some more modern kind of stl functions and particularly string has something called like find which will actually try and look for something like a space within the string don't remember the exact um like signature of this function but what you can do is actually recursively do that until it's like until you've searched the whole string and then just take each because that will that will return the position of the space you can use that to basically uh substring you know all of the other string functions and create new strings out of them which seems to be the intended output of this function uh sub string so i would i would basically do that um that would just be a little bit of a better way to pass this uh you know unless you want to like full and create like a tokenizer which i probably wouldn't um there's also a c api that you can use i remember using this back in the day string string i guess i think that also returns a pointer to a constituent array that is at what you're looking for something like that but basically using the library a little bit more than writing this by hand would just be easier and again the point of this assignment is clearly not to do this all you're all you're trying to do here is sort out your input basically split string by space and simple doesn't have like a little you know string.split thing where you can just split it by space and get an array back like a lot of other languages do so using something like find and substring is probably your best bet otherwise that's that function sorted um by the way let me know what you guys think about the level of detail i'm going into with all these like should i just you know this isn't very big that's why i'm doing this if it was like 100 files obviously i couldn't do that but uh anyway if this is um yeah just let me know all right so number number of inputs user input.size okay so this is an example of variables that i think are useless num input if this was called something like completely different then i would i would probably see some worth as to creating like a variable out of it so like number of like apples or something right from user input does size that adds so much meaning to what that actually is what this is num input you don't need that variable because the variable is here right instead of using num input you could just use this um another reason to have num input is if you changed it which you don't right so if maybe if you were like going to decrement it or something like that then of course you'd have to bring it on to a variable but i would just skip that have as little as have have less variables unless you know the the weight that you get like the data you need is like a huge string then maybe you would want to simplify that into like an alias using a reference or bring it onto a variable like this but otherwise i would just rewrite that code like that basically um okay and then we have uh our hash table okay cool so um hash map hash table by the way same thing obviously unordered map is also what um c plus plus calls it so let's look at the hash table class which is like three lines of code okay cool so hash table um it's a class that's good public status object okay and then the constructor sets the status to never used now i probably would have thought that this was just a debugging thing but actually it's like it's in the assignment like you have to set a table slot has three different statuses never used tombstone and occupied the table starts with 26 never used slots so this is all legit um just so you guys know i just want to make that clear um anyway so we create 26 of these all right all right so first of all um we don't need to set this up like this at all um the first thing i want to say actually if we go back to this hash table class here right is that you don't need a constructor you can just set the status to never used up here right and then just not have a constructor the reason being that when it gets initialized like this isn't like prior to c plus 11 when you couldn't have assignments like this in like header file well in header files and like class declarations like this um so we can definitely do that and that will probably be better and it would just reduce the amount the need for this code this is also useless because it's the same as just calling the default constructor um so i i would basically rewrite this class to look something like this and again because it's a public bunch of members i would also remove this and just make it a structs no difference between a structure or class apart from the fact that structs are public by default if you don't specify something whereas classes are essentially private by default they're members i mean so that's how i would rewrite this class however at the very least what you could have done is just basically ran status with never used like this in kind of the constructor i guess initializer list the reason being that um that prevents the string from being created twice once up here again it's an empty string this point is not about like performance it's just more about like code style and what actually is happening so that you're more aware um you know in this case it creates a string up here um and then also it would have it would have created it down here again reassigned it to something else and constructed a string out of this kind of char const chart pointer essentially using an implicit constructor again so you've kind of made two strings whereas if you if you write one of these bad boys it basically replaces whatever you wrote here so this is now meaningless it will instead use this um so that's kind of important but again you know in this case i would not do anything like this by the way i don't know what version of c plus plus this needs to compile with um i think it it actually did mention okay yeah c plus 11 with optimization level two using g plus plus that is what's going on here okay cool interesting um so yeah sables 11 definitely supports everything that i'm doing so this is how i would rewrite this basically um and just get rid of that because you don't need it uh okay so okay we create 26 of these now this is the other thing um you could create like this you could just use an array as well so we could have an array of like hash table objects like this 26 of them this is what i would do again the reason being that we now have site the biggest reason honestly for this is that apart from having some nice functions uh to help us out with certain things we have a size right a size that isn't really stored as a variable um but that we can retrieve using an api like this that's a lot better than having to use the value 26 you know here for example you would just write something like array array of object.size and that would be that speaking of which you actually don't need this for loop whatsoever there are a few ways to actually fill an array you could use something like std fill but i would instead use this so if you just do that or assign it to essentially an empty set of parentheses or curly brackets rather like this then it's actually going to initialize all of the objects with um you know whatever value you set there which is nothing meaning that the default constructor will be called for all 26 of these objects meaning that you don't need this for loop like whatsoever so you could just completely remove that i'm gonna by the way keep the original code if you guys want to see like a video of me completely rewriting this entire assignment the way i would write it let me know in the comments below but obviously i'm trying to do a code review here and not rewrite everything so i'm gonna probably stop doing this in the future for this video i mean but basically yeah do something like this and it means that you don't need any of this in this case this is used for just initializing all the elements but if you had something a little bit more simple like maybe you know five integers you could also use this to essentially give a value for each of the integers so initialize the lists are great okay anyway moving on so we've chosen to go with this which is fine and then that means that yeah essentially we do need to initialize it using an algorithm like this or an algorithm a for loop like this okay and then we go through the user input dot size so this is now the kind of um separated by spaces uh tokenized kind of commands i guess that we've given in the user input so what are the commands that we can handle so we have this function called command get now again you know this is a very interesting uh code style right like literally every single every single style has been used here in terms of like in terms of function names like i mean literally like we have this i don't even know what this one's called this kind of snake case but then with the capital second word letter like get we have this kind of i think pascal case is what it's called um it's very like microsoft style uh we've got this one which again could be i guess snake case um then we've got this one which is uh camel case um we've got we've got them all we've we've got them all input formatter is another example of pascal case so um i don't know why just stick to one and just use it um very important uh because see the thing is i can't even give this advice because you still get a hundred percent if you get this anyway whatever okay it doesn't matter we'll move on we'll move on from that so command get user input i okay so we give it a character a single character no no sorry user input is a vector so we give it a string essentially so this is probably also by oh no no this is by reference okay that's better i guess it's going to actually write out to that string yeah it resizes the string so what does this do so we get the first character um we then uh resize this string oh so you are using substring so you're aware of that which is good we get the first character we we basically use this temp string thing here to just resize this to be one um or not resize it but to basically um select uh you know ever the entire string minus the first character basically so we drop the first character from the string and assign it to temp string then we resize the string and then we reassign it which is defeats the purpose of resizing it here for no reason okay this is all very messy um this is what you need this is what you're trying to do i think i think you're just trying to do this without any of this you're just trying to take the string and reassign it to basically a substring of that original string that doesn't include the first character so we can just leave it at that and not and not get too crazy and then we return the very first character so we've saved out the first character into a variable because that we're changing it we're changing what the string is we're dropping that first character and that's what we return seems weird right well actually it's because the assignment says that the way that we give commands to this program is we basically have to have the first character specified as either a or d in which case a means that we add to the hashmap and then d means we delete so in other words an example command might be like i want to add cherno to the hashmap and then i want to delete cherno from the hashmap that's literally what this literally what you do you just do this um so that's why we're looking at that first character and then kind of separating it because obviously this is the actual value we want to add but then this is what says what to do so again a very creative assignment um so what do we do okay so basically what this is the switch case is now operating on that very first character whereas the user input has now been modified to contain not the first character so we've kind of trimmed that off we just have the key i guess that we're actually trying to add to the map um which begs the question is it really a map if all we're doing is adding keys without values um this is more of like a hash set to be honest uh at this point in time so um but i guess maybe we are storing some kind of associated anyway let's not jump the gun let's see what's let's see what's happening so the first thing we do if we want to add something is we search so remember array of objects is that that hash table array which hash table really is just two strings um object which i guess stores the actual value and then status which is a string that is initialized with never used so then we go through this um we search we okay so let's let's let's go through this first of all so we take the actual string so like churner let's just we'll leave this up here so that it's clear what the command was a cherno so now we know that this user input contains just cherno we put it into the hash function so the hash function sees cherno what's our hash function i think this is a bad function because words ending in the same letter will end up being placed in the same slot in the hash table why yes that does sound bad but i also don't know how to write a better function using only the one character so i will keep going only the one character yes because i think i remember something in the assignment talking about how you're only allowed to use a single character to generate a unique hash what is happening anyway whatever um so what do we do here we we do char get string what what does that function do it returns the last character in the string and and of course it has time to copy the string okay so first things first don't do this you can just you know do something like string i don't know string size minus one here right doesn't need to be a function and instead of calling this chi which is almost you know the beginning of a good word you could instead actually call this something like last character that immediately makes this algorithm or this hash function way more readable right so then we do in constant and then we do oh look you know how to use these things in like mathematical operations so definitely then you should have done the space where was it um this is also not very well organized but we won't get into that too much um in the uh in here right you should have have done that okay back to the hash function so in constant equals so the last character then we subtract uh the ascii value of zero which i i i would say i know what that is but i'd be lying um so let me just get back my ascii table so 0 is in fact 48 so that's kind of like the start of i guess the usable characters because um anything below that is a symbol like divided by or comma or plus and then anything above that we basically well i mean we have our numbers then we have like colon semicolon stuff like that and then we have capital uh letters and then log case letters so um that's kind of like i guess the this is almost like our zero um and then we subtract so basically any character any character really is guaranteed to be above zero most likely unless we we're giving it like a character that we shouldn't be maybe like as far as this assignment goes um we add three to it which is a bit weird so we get kind of the value from that start we get three get three and then we mod it by 26 and that that is that is what our our index i guess is or like at least our hash function very interesting um and again it's just taking that last character so this obviously only really functions on the last character now the fact that this is already mod 26 and 26 happens to be the size means that this probably actually you know this isn't just the hash function that generates a hash for us it actually specifies what bucket that we should be storing our value in or retrieving our value from so this actually gives us back that index so hash maps um hash maps obviously uh store all of their values in various buckets and you the hash function the point of the hash function is to generate a value that can then be used to actually get an index and then you can see where your data should be or is so that's what this is doing so it's kind of doing two in one here okay cool so that's our hash function so now we basically get back an index as to where to store our data that's the point that's our data and that's my array so search is doing that um so i guess the thing is we're already specifying something so it's not like we're searching by string so what exactly does this search function does do what exactly does this search function does okay so we're taking an array um sure i'll probably write this a little bit differently i think this is kind of old school not that it's a huge uh you know difference in this case and we have a place here so we actually okay so we basically check to see if this is almost like a little collision check um we check to see if the array contains an object that has the same name as the one we're trying to insert i guess um and if sober return negative one uh otherwise if the status is never used so obviously this it doesn't equal now so it's either never used or it's occupied never used of course being this uh you know status here very important that you spell that right and don't use capital or lowercase um you know letters accidentally or something like that or write it as one word because otherwise the whole algorithm breaks so yeah extremely important to uh you know when you're dealing with strings as statuses for some reason but again assignment requirements value cannot be used in the hash table this object doesn't exist so i think i think it means can be used in the hash table maybe because this obviously means that it's free um otherwise if it's occupied we try and basically resolve that collision i guess by just like doing something like this um again what you could do is uh you know not do this but use that beautiful modulus operator you you were using earlier to just basically make it so that you do something like you know place plus one mod 26 maybe like that and then that's kind of just a little bit of a better way to write that a little bit of code so you don't need the if statement um and then we basically recursively try and see like okay well let's increment the the index and then see if that's free so a little bit of collision kind of avoidance i guess but uh this is also slightly dangerous because if they are all occupied this will just crash with the stack overflow exception because you you never stop searching and if you've exhausted all 26 slots that's the end of the day that that's the end so um let's not do it that way but anyway if this doesn't return negative one then obviously we're good we have an index for it so now we do search for free so there's a lot of stuff going on here that seemingly shouldn't be happening like why what we've searched already we know that it's free why are we searching again um not sure but anyway this basically does the same thing this this actually looks almost the same as the other function but um i i mean i don't know again recursively looks for recursively tries to like increment the index search for a new kind of place if there's a collision um otherwise if it's never used or as a tombstone meaning i guess the object has been deleted it used to be there but has been deleted then we get that index back so yeah not sure i mean ideally again into an empty hash table into an empty hash table in this program you would just immediately get your place so i don't i don't know why this is happening and in fact it doesn't search return it does return an integer so um i mean this has nothing to do with the whole tombstone situation so what you can do is basically do either never used or tombstone right and in that case if it's never used or tombstone then obviously you can use that slot and then basically just do something like in play sql search up here and then well that's it you don't need that other function you can just go ahead and add it so i would um do something like that okay anyway um so now we have the index yet again i wouldn't call it place either i'd call it index sounds a bit more professional i guess and a bit more descriptive but i guess i guess they mean the same thing right at the end at the end of the day don't they um and then add so what does add do it changes the status and just copies the object copies the string into there again no reason to do something like this you know just do that or at the very least if you're going to move this in then maybe you could you know move it in um yeah this is beyond the assignment and i don't really care so let's move on huh move on so we break which is good um and then that's how we add objects basically pretty straightforward how do we delete objects so we have again the search function which um now this is interesting right so okay all right okay yeah so we need to make sure that we find whether or not that object exists and then we find the place of it actually hang on am i misunderstanding something so what does this do so search looks for something and then if it is occupied it all right well negative one just means it can't it can't find no no negative one means it's founded so in that case it doesn't give us a place yeah okay no so it's fine my thing still works because if it's negative one means it means like it it i guess it already exists then it does nothing because this wouldn't be true so actually like to be fair when i wrote my thing um you know i should have surrounded it with more parentheses so that we actually check the that variable then with um negative one otherwise that wouldn't really work but anyway um so yeah so we do the same thing here we basically this is just us checking to make sure that it exists in the in the hash table if it doesn't we can't delete it right it's not there so if it does exist we again search for it um because search returns negative one if it exists um which means that we don't get the index of of where it exists it'd be nice to have that as an output variable if you had done something like that you know how like a little out index or whatever if it does in fact find it if the function itself doesn't return the index um which also wouldn't have been a bad idea we're trying to search for something and we get an index but anyway um so now we do search for kill a nicely named function and this basically um i guess if it finds the string and the status is not tombstone then we found it and it's not dead so we can kill it i guess um otherwise if it's occupied i don't understand why this happens like surely this is just us trying to find the objects that we now need to delete so and then we're trying to find the index of it so why would we recursively try and oh no hang on i see okay yeah this this has to exist because if we previously had a collision then we shifted it so it's possible that even though the hash function says that you're at index 5 you may have actually been at like index 7 because when you were inserted into the hashmap it incremented your index twice because there were collisions so that's us doing the same thing here um yeah what you need to do is cut this three different search functions to just a single search function that just tells you the status potentially whether or not the object if the object exists and you're trying to find that the index of the found object and then maybe like you know an empty place or something like that again maybe two functions one for like add and one for actual search because search again search to me um you know it's kind of like a find function in which case you'd expect it to return an existing object right or nothing maybe negative one if it couldn't find it at all but this actually returns negative one if it does find it so it's a little bit a little bit weird anyway and then finally we delete it so how do we do that we pass in that array we pass in the string by value again and then we uh we have the index so we basically do another check to see if they're equal um okay and then we set the status to tombstone so we leave the data there but we've just set it to tombstone meaning it can be reused cool um and that's kind of it so the output is the the good thing so basically we just go through all 26 values here and we just see if the status is occupied so if it's been deleted it will be tombstone if it's never used it'll be never used but if it's occupied that's good that means we basically print it along with a space which the assignment says is the expected output and then we're then we return zero so that is the um hash table assignment yeah wow that's um this is uh i i have to say i this is not at all what i expected okay so i hope you guys enjoyed this video if you did please don't forget to hit the like button as i mentioned earlier you can submit your code to me for review by emailing cherno review gmail.com there will be that email address in the description below as well as some instructions i hope that you guys have a great rest of your day and don't forget that you can check out skillshare for free by using the link in the description below i'll see you guys next time goodbye [Music] you

Channel: The Cherno

Views: 45,133

Rating: 4.9537573 out of 5

Keywords: thecherno, thechernoproject, cherno, c++, programming, learn c++, c++ tutorial, code review, hash map, hash table, university assignment, assignment

Id: 5aZCJ_Soq4w

Length: 35min 19sec (2119 seconds)

Published: Fri Jun 04 2021