Maps in C++ (std::map and std::unordered_map)

Key Takeaways

hey what's up guys my name is vicherno welcome back to my c plus plus series today we're going to be talking all about maps if you have been programming for any amount of time really you probably have heard of a map or a hash map or a hash table or an associative array basically these refer to a data structure that allows you to associate some kind of key with a value so for example you have some sort of id such as like an id number and you'd like to use that to look up the rest of the data at its core a map is kind of similar to an array like a vector or a static array even if you think back to a vector i've made a video on that by the way i'll have it linked up there a vector uses an integer indexing system every element that we push into that vector gets an id which is its index inside that data structure that works fine if you just need like ascending indices 0 1 2 3 4 5. if that means something to you then again that works great or if you just need to store like an array of elements and you might care about the order of those elements but you don't necessarily care about accessing them randomly based on some other value you just need to have them like in a bucket so that they're stored somewhere and you can iterate through them that's where a vector is really useful however if you need to constantly retrieve specific elements from that vector that's where it can become a little bit of a problem because to find a particular element if you just have one piece of data and you'd like to retrieve the entire element means that you have to search the entire vector sorting can help here because if you sort it in some way then maybe you can minimize how much of the vector it has to search but you still have to search the vector to find what you're looking for that's basically a problem that maps solve with a map you can define a key which is like the thing that you use to look up your value and then of course a value which is the data that you're looking for if you have that key which could be like an id it could be a name you can just retrieve the value really easily because that key can be used as an index like instead of an integer in a vector it can be used as an index to retrieve that data i know we're only scratching the surface it's going to be a long video buckle down but let's dive in and take a look at a simple example to begin with now when we're talking about using maps in c plus plus there are actually two different types of maps and we are going to talk about what they are today we have map and we have unordered maps why are there two different types of maps well because they're different types of maps one of them is a sorted map meaning that all of the elements are actually ordered and the other map on ordered map is unordered so the ordered map which is just called map is a self-balancing binary search tree typically a red black tree you don't really need to know the details of that although we might get into it in a future video but basically all you need to know is it is a tree and you typically find elements by comparing them to other elements and seeing like where a key falls as you go through the branches and because it's a tree like a binary tree the elements end up being sorted because they're kind of compared to each other using a less than operator and stored in the appropriate place that's why when you iterate through an scd map you have all of the elements in order in some order now on the other hand unordered map is a hash table it uses a hash function to hash your key and it can use that kind of generated index to figure out which bucket your value lies in and then that's how you retrieve your value this is completely unordered and usually can actually be quite a bit faster than map but we will get into performance later in this video because it's a bit of a complicated topic as a basic rule of thumb i would probably recommend that you use unordered map wherever possible unless you need an actual sorted data structure because unordered map usually ends up being faster than map or at the very least the same speed okay let's create our fictional scenario example here let's say i have some kind of city record that i want to maintain now cities typically have like a name maybe they have a population which can apparently be above 4 billion they might have some kind of like latitude and longitude anyway you get the point we have a city we have data belonging to a city now what i want to do is store every single city that we have in the entire world so i'm going to create a vector to demonstrate this to begin with we're going to have a vector of city record these are going to be our cities and then whenever i want to add a new city here i can just like you know in place back a city provide a name so i live in melbourne so let's use melbourne as an example population like five million latitude longitude i don't actually i'm regretting even writing that but let's just write this i'm gonna add a few more cities we're gonna have lol town and let's add berlin let's add harris and london and i'm just going to keep all the rest of the data as is so now that we have all of this data organized nicely into a data structure what would i need to do to retrieve information about a specific city so let's say i want to know the population of berlin how would i find that out well with the way that we've currently written this we basically have to iterate through like the entire cities vector and then basically check to see if city dot name equals whatever our like the name that we're searching for is such as berlin if it is then fantastic we have our city and we can easily look up the population this will be the population of berlin done right and of course we could break from this for loop once we found it do whatever we want with it that data is there can you see the problem here there's a few problems let's discuss them first of all searching every single city that we have is a bit of a pain now it is true that we could maybe order these alphabetically and then use some kind of binary search algorithm to kind of narrow down the city that we're looking for we know it starts with letter b so if we have an ordered vector then of course you know we could optimize that in some way however if it is in fact completely random and we have like a thousand or ten thousand cities or something in here then worst case scenario we have just done ten thousand string comparisons looking for berlin string comparisons aren't exactly cheap either so basically what i'm saying is using a vector for this is not really ideal what i would do instead is use a map so let's take a look at how we would use just a normal city map when we created it takes in two template arguments well actually it can take a lot more than two but for the simple case you have to provide two it takes in a key and it takes in a value now the key is what you use to index into your data so again since we are indexing these by name we would use an scd string as the key so let's type in std string now the value is the data that we're actually storing for that key which of course will be a city record so i'll call this city map how do we go ahead and put all of these into the map well we basically can use something similar but i'm going to change it up a little bit into something that's a bit more common and i'm just going to write citymap equals city record like that and we'll just replace these parentheses with curly brackets and in here i specify my key so let's go ahead and put in melbourne lol town i don't know how we ended up with lol town considering all the other cities are real but whatever and that's it so now we've again we're associating a particular key with that value in a vector this would just end up being like zero one two three blah blah but of course here you can see we have an actual meaningful key that is in fact a string which is the name of the city so now that we have this data structure how do i retrieve information about berlin well the good news is i just do it like that so let's grab our city record out of here berlin data and that's it and again if i want my population then i can just do billion data.population there's my population how easy was that and again it's not just easy it's really fast for a small data set like this it probably is about the same speed but the larger your data set is the faster this will essentially be this has the added bonus of being ordered so if i was to iterate through all of these then these cities would actually be in alphabetical order but no you said an unordered map is faster maybe how do you use an unordered map well you'll be delighted to know that it's the same but you just change the type to unordered map the api is identical all right that's pretty much the video but you know me i'm gonna keep talking for like another 20 minutes probably so let's just get this over and done with first actually before i commence my monologue do you need web hosting you probably do in some capacity and for that i recommend that you use hostinger the sponsor of today's video hosinger is an amazing web hosting platform that i personally use for all of my websites and have for quite a while the best thing about hostinger is that it's extremely affordable but it doesn't sacrifice quality their servers are really reliable their user interfaces are fantastic and they also have a bunch of well-written documentation and tutorials to help you get started the process of setting up a brand new server is you're watching it right now it's really simple i probably can't even finish this sentence in time yeah there's like nothing more to say if you need a web host then just go to hosting that's hosting.com just make sure that you use my channel coupon code at checkout to get an even bigger discount huge thank you to hosting as always for sponsoring this video alright so maps let's dive in and take a look at maps in much more detail most of what i'm going to explain here applies to both unordered map and map obviously the specific stuff i will mention but as i mentioned the api is very similar so first of all let's discuss this in a bit more detail so again we have a key obviously an std string now it's really important first and foremost that whatever you use as the key is actually hashable if you're using an arnold map or it has less than operator if you're using an scd map if we decided that we actually wanted for example to be like well let's create a map of city record to i don't know some additional data that we wanted maybe that wasn't part of this original struct such as like i don't know the year that it was like founded in or something like that if we tried to create something like that so that we could pass in a city record and then get information about when the city was founded as an example founded map then if we try to compile this with control f7 we're gonna get a crazy like error message and i'm telling you this is one of the worst things about both c plus plus and maps if you don't understand what the problem is you are basically screwed like come on like are we going to read this we could we could show you guys how to read this this is also why by the way i always recommend that instead of looking at the error list which just says hey man this scd compare thing is attempting to uh reference a deleted function whatever that means you look at the output because if you look at the output then you don't just get that error message that this error list has passed you actually get all of it which look how much more detail it has this is all the one error by the way so if you actually follow this through you'll see that eventually you get to message c reference to class template instantiation and if we double click on this it will take us first of all to where we are which as you can see is that founded map that i tried to create really important that you look at the output now it's telling you here by the way all of the template arguments so we know that for example it's trying to use scd-hash city record that doesn't exist basically the reason that we're getting this error is because we're trying to use the hash function to hash cityrecord we have to hash that key so that we can you know store the value and then retrieve the key again everything goes through the hash function as i mentioned but cityrecord is a custom type so how is super supposed to know how to hash this now as a side note if this was for example a city record pointer which again a lot of people like to use and if you're coming from a managed language then basically everything is usually appointed there that is a different story why because a pointer is just an integer it's a 64-bit integer on a 64-bit you know compiled binary so it's obviously going to be able to hash that because you may as well have written a uint64t right easily hashable the language comes or the standard template library i should say comes with that ability out of the box now cityrecord on the other hand without the pointer is no longer an integer that actually is this data so it doesn't know how to hash it so what do we do well we have to provide a hash function for city record now i'm going to be honest with you guys this is one of the things that i pretty much google anytime i have to implement because i don't remember how to do this off the top of my head but i have already worked out how to do this for the purpose of this video so i'll show you how to do it but yeah program is google stuff all the time and that's i mean that's pretty obvious right now theoretically if we wanted to we could kind of reverse engineer this because we know that it's it's basically going to come up to here and try and use hash but it's like again going through the senate template libraries a bit of a nightmare so what we basically have to do is create a template specialization for the std hash class that is specialized with the type that is our key so normally we would implement it like this namespace std because this has to be in the city namespace and then we're going to create a template specialization for the hash struct now this hash struct again because it's a template specialization we're going to type in template with an empty template argument and then we're going to specify the template argument here so of course hash of city record is what we'll be creating and then that comes with an operator a parentheses operator which is like the call operator that returns a size t which is that hash value a 64-bit uint and then we specify a city record a const reference to a city record as our like key that will be hashing basically and then it's up to us to return any kind of hash value that we want now we could just return zero and then obviously all city records are now equal because whenever you hash a city record you always get zero so we don't want to do that instead we want to maybe take a look at the data and be like what uniquely identifies this now cities don't really have unique names i mean there are many cities in the world especially if you don't just look at like capital cities obviously but you go further down so you could like you know hash the name with the population and combine that and latitude and longitude latitude longitude actually probably is a much better way to go but as an example let's take a look at name so how would we hash name well name is a string so this is obviously something that c plus already has the ability to hash because s cd string is part of the center template library and the standard template library includes hash functions for like most of the types there so for this we can just call hash with key dot name now unfortunately it's not as straightforward as that because hash is a templated class here so we actually have to put an sd string and additionally we're actually calling this operator so with that so we actually have to basically kind of like construct this and then call it anyway syntax looks a bit weird but this is what we can do so yeah looks a bit weird but does the job so that is something that you should like copy and paste install i mean whenever i need this honestly when i'm working on a project like hazel i just look elsewhere in the code base and copy it from there because again i don't retain this information but this is basically how it works hopefully it makes sense how it works you just put in your custom type here the call operator with that template specialization is what kind of gives you an opportunity to specify how that type should be hashed and then whatever code you put into this function is what generates a hopefully unique hash for this specific object again your goal here is to be unique because you need to obviously if it's not unique then you could type in another city name and it could amount to the same value which means that it will overwrite data that's stored there hopefully that makes sense anyway now if we hit control f7 then this still doesn't compile because if you read this no overloaded function takes four arguments so the reason this didn't compile here is because i i'm not sure why it just decided to break now or maybe it never worked but basically i used in place back with four arguments here for the vector but we don't technically speaking have a constructor that matches that i was hoping that it wouldn't matter but anyway since we're past vectors if you wanted to make this work obviously within place back you would just write a constructor that took in all those arguments instead of kind of leaving up to the struct initializer list but we are going to just get rid of our vector control f7 and there we go compiles and everything is wonderful now so yeah our founded map obviously works we can basically grab like a city record such as this and push into that like the year that it was founded which i have no idea when melon was founded but let's just say 1850. the interesting thing about this is again the only thing that identifies this is the fact that it's a city record of melbourne like this data could be whatever like if i wanted to retrieve you know the year a bit later like so then i could specify whatever i want here it doesn't matter because it's just going to use this to look up my value because that is obviously what the hash function is using now this is a fantastic time to mention what this index operator actually does because it works a little bit differently than in other languages because this index operator that you use to insert things in we'll always insert things in there is no const version of this operator what am i talking about well let's get rid of this founded map because it's a little bit annoying if i wanted to look up berlin like so if berlin didn't actually exist then this code here actually will insert berlin into the unordered map and then give me a reference to that newly inserted city record right and of course in this case we're not specifying like parameters for it i mean we're not specifying any values for these variables so it will just be the default value which will be like you know an empty string and uninitialized memory whatever this can be annoying if you are new to c plus plus now i personally use this all the time because if there's a lot of data that needs to be filled out here and i just want to have access to that city record already in the right place this is great because i can then go through and do things like billion name you know equals billion right i can go through and set up everything and because it's a reference to that already in place memory i don't need to then later set it so like an alternative way to do this might be let's create a brand new city record by writing some code like this right let's set up like the name and the population and like whatever else you need to set up and then we can just basically get our map and assign that back in like so now the downside here is that you're creating it first here on this kind of stack and then you're copying that into the map whereas over here apart from not having that final line of code because it's not necessary you're also avoiding the copy because you're kind of creating it in place and then referencing that memory so i actually tend to use this quite a lot to just avoid copies and to make the code a little bit cleaner but if i really truly want to retrieve the data without actually inserting it then what i should be using is dot at now as a quick little note before i show you dot at since this index operator inserts elements if they're not there if you happen to have like a const map so if i wrote something like const auto cities equals city map so now i have a const map right this map is now const if i try to write code like this of course it won't work because there is no const version of this operator so if you pass like a const map into a function you have to use dot app like i remember back in the day i was so confused as to why i couldn't use index operators if the map was const i'm like but i'm just trying to access because like in java and c sharp whatever this is normal right but in c plus plus that operator is kind of like it has the ability to mutate the actual data of course the map because it can insert elements so of course there can't be a constant they could have made a const version that would not insert elements but i guess to keep it less confusing they made dot at instead so dot add is in fact const because it will never insert new elements it will only return those elements to you now of course it will return them to you in a const state which is why that wasn't working and well for this example it's not gonna work because we can't assign to that obviously it's const so yeah my rule of thumb is i use dot at everywhere unless i am okay with it inserting data which again sometimes like on the fly you don't mind if the element's not there insert it sure that works for me but a lot of the times you don't want that to happen now what happens if the data isn't there so we don't have build in here so what's going to happen here well you're going to crash it's going to like throw an exception or something or a set if you use dot at the data has to be there so how does one check to see if the data is there that's where we can use dot find and again it's pretty simple you can just write cities dot find berlin which is my key doesn't equal cities dot end i don't know why my new visual studio is decides to convert that into that i guess that's just trendy these days but anyway we'll ignore that and then inside this if block you can actually use dot app because you've checked to make sure that it actually is inside that map that pretty much covers like a good deal of how to use map but there is one other crucial part that you might want to do and that is iterate through the entire data structure so i want to go through and print every single city now lots of people will tell you not to do this it's a bad idea it's a map you don't integrate three maps blah blah blah blah all that is false ideally yes you wouldn't iterate through maps because a vector keeps all of your elements in contiguous memory very cache friendly it's just it's the best thing to do if you want to iterate through elements that is why vectors in general are by far like the most popular data structure most of the time you use a vector because it just stores all your memory in a row and you probably don't need fancy indexing systems like this most of the time not saying maps are unpopular they're extremely popular but vectors are more popular however iterating through maps is not the slowest thing in the world it is slower than a vector for sure if you iterate through a vector it will always be faster however it's also very useful to be able to iterate through a map and it's also very easy so all we have to do if we want to iterate through our map here is just write a for loop now i will basically always write a for loop like this for auto then reference if you don't want to copy and then using structured bindings in c 17 i can actually just write like the name of my key such as like the name of the city and then whatever value i want so city right because we have a name to city record then i just specify my city map so it's kind of like a range based for loop here however we can use structured bindings which by the way as i compile i realize that we haven't enabled simple 17. let's just go over here we're on c plus 14 apparently for some reason sure 17 is good enough you know what before we do that let me just show you what you would do like in c plus 14 again with range based for lips and everything what you can do is instead of iterating through it and retrieving those the key value immediately you can just uh make a variable called like kv for key value and then you have key value dot first which is like your you know so let's just do auto name is that and then the city would be your second so this is your city record probably shouldn't use auto to be more clear and then that is your name now you can see that in this case the key is returned as a const value so we'll have to do that as well because we can't really edit it so this is like the stone age of how you would iterate through a map you don't really do that these days instead with civil 17 and above we can use structured bindings so you can immediately just have your name and your city over here and then well yeah you're done like this is this is my name string and this is my city and i can access like you know whatever data i want so let's go ahead and actually just print all the cities we'll actually run a program for once today i'll go through print the name of the city and then maybe let's print the population city.population and that shall be the end of that scdc get f5 and you can see that i am printing all of my data let's kind of you know change some of these so that it's not silly bring back berlin and there you go you can see that we're able to access obviously all the entries inside our map now you will notice that of course they are not in alphabetical order because we are using an unordered map now if you look at this it does happen to be in the order that they were inserted in but again that's definitely not guaranteed so just be careful with that an unordered map is unordered so this would be a perfect time to show you how we would have an ordered map so of course if we would just use an scd map instead of that sc unordered map and that's really all we have to do so now if i hit f5 then you can see that we now have all of these in alphabetical order how do we remove one of these from the map you ask why we can simply do citymap.erase and then whatever key we want to erase so for example we don't want paris in here we just citymap.erase paris and that's it no more paris now finally the last thing that i have to show you is if we go back to using the founded cities that we had so founded city founded or whatever it was so we basically have the city record be the key and then we have some kind of value we had to specify a hash function obviously for the hashmap for the unordered map but for the map for the audit map we actually have to specify something as well now one complain when you actually just create a new map here but when you try and use it so if i try to actually like you know insert a value into here such as like let's just copy this pop that in like that ctrl f7 once we compile it it will tell us that there is no binary less than operator right so again it will it's a it's a self balancing binary tree it will try and compare the two nodes to each other to see which one is less than the other one so that it can sort it into the appropriate branch that's not going to happen because there is no less than operator so how do we define a less than operator well you can actually define one within your custom class itself so obviously it's going to return bull and we literally just need to have a lesson operator so const city record other we'll mark it as const and then we can return true or false for if it's less than something else so let's sort these by population and this is cool as well because you can sort it by whatever you want because it has name you know we don't have to sort it by name although we could we could sort it by population so we'll return population less than other population as a quick side note this lesson operator is responsible for more than just sorting of course this is what defines the unique key inside your actual map so if one city's population is the same as another city's population they'll actually clash so it's important that you you know do this properly not just for sorting let's compile it with ctrl f7 again you can see it compiles now before we add all of these into this city founded map another interesting note is because this index operator inserts elements we can actually write a bunch of statements like this without even setting it equal to like you know the year that it was founded in right because this code itself will actually insert the element in and that might be all we're trying to do so that's also something that people do from time to time okay so we're iterating through our city map over here let's go ahead and insert all these cities into city founded so we'll just do city founded and then city and then i mean it doesn't really matter when it was founded for this example we'll just set it to that and then what i want to do is iterate through city founded and we should see of course that it's sorted by population so this will be city this will be founded the name we can print here we won't set this let's run this program i'll just comment out this as well so that's not confusing so now where and again this is another great example of like i just want to insert something not necessarily set a value but just insert the key and finally if we iterate through all of these we should see them in ascending order from the lowest population to the highest population as you can see here all right that's pretty much it now what i would like to talk about next is performance between these maps because performance is very important i'm a game engine developer i care about performance the short answer as i mentioned you want to basically use scd on ordered map whenever you can if you do not care about the order unless you've actually benchmarked profiled all of that stuff and you can see that std map is actually faster in some compilers i have seen that a cd map is faster than an ordered map and you also have to realize that this very much depends on how much data you have if you have 200 elements 500 elements a thousand elements inside a map you're probably not going to see a big performance difference if you have a million elements in your map and you're doing lookups then the hashmap will be much faster if you don't need that data to be ordered now when iterating through maps which of course isn't the most ideal thing in the world map generally performs better than unordered map however it will be an order of magnitude faster to iterate through a vector so if you're going to be iterating a lot and not really doing lookups very often you should still use a vector but if you're mostly doing lookups iterating maybe for debugging or every now and then then of course you should use a map preferably an unordered map if you don't need it to be ordered the long answer is i will probably make a video talking about the performance between these maps and show some actual benchmarks if you want to see that leave a comment below i hope you guys enjoyed this video if you did please don't forget to hit the like button let me know what you want to see next in the seat below series in the comment section below and also if you need web hosting check out hosting up using my link in description below thank you guys for watching i'll see you next time goodbye [Music] you