Hope you all enjoyed the latest addition to the C++ series! Let me know if you have any questions about maps below 👇 Also definitely check out Hostinger for all your web hosting needs, and use coupon code CHERNO for a discount: hostinger.com/cherno
Please could you talk about dealing with hash collisions? In your vector video and others you did a great job explaining how they're implemented in memory. Something similar for maps and unordered_maps would be really helpful. Thanks for all the great videos!
Can you do a vid on template metaprogramming? And as code review it would actually be nice to go over a library container such as vector and explain what is going on. Especially as a beginner /intermediate this feels like it's a whole other language
thanks Cherno, as always great content. Would be great if you could also talk about std::equal_to in the context of unordered maps and hash collision resolution etc. Especially what happens if hash collisions occur. Keep up the good work.
21:01 - When using find(), you can avoid the second lookup required by at() by saving the iterator returned by find(). For example: if (const auto it = cities.find("Berlin"); it != cities.end()) { const CityRecord& berlinData = it->second; // ... } I recommend always doing this whenever you use find() to do a lookup. If you only need to know whether the element exists or not, you can use ".count(key) != 0" (or ".contains(key)" in C++20) instead.
Also, if you want to check wether or not a map contains a key but don't need to access its value, you can use std::unordered_map::contains(key), available in C++20
@@DrShwynx That works with vectors but not a map. "find" in a vector is a linear search. You could use for(auto& val : vector ) to iterate over the vector too for searching and just "break;" out of it. Find is useful if you want to use the iterator later on and not just finish up in the loop.
15:20 A hash function is not required to return a unique hash. Two things with the same hash will be stored in the same bucket, which is inefficient for lookups, but it will function fine. The hash provides fast access to the appropriate bucket. The equality operator is what determines if a key actually matches. You should strive to make unique hashes for performance reasons, but hash collisions will not compromise the map. 26:50 -If two cities have the same population and that is all you are using for comparison, then they will appear in an arbitrary order but still appear next to each other in the map. Nothing is broken in this case. You just will not be able to rely on their order remaining consistent as the map changes.- This is incorrect. Not sure what I was thinking when I wrote it.
You can come up with a great hash function that minimizes the amount of collisions, but at the end of the day you can compromise a bit of speed when creating the hash map through linear probing or other methods (O(N)) to get perfect collision-less hash maps by sampling the next index until you are sure that you don't have collisions.
As for now, it seems like youtube should give a platform for contributing into videos' drafts with deep fakes :3 Im pretty sure that we could bring all the educational stuff to a brand new level
"26:50 If two cities have the same population and that is all you are using for comparison, then they will appear in an arbitrary order but still appear next to each other in the map. Nothing is broken in this case. You just will not be able to rely on their order remaining consistent as the map changes." you are wrong. in c++20 the population is used for the key, if it's equal between two objects the compiler will assume that you are referring to the same object.
Hey Cherno, I started watching you 5 years ago, while I was in my first year of college. I saw every video you made. I patiently rewrote line by line your sparky engine, but then I had so many school duties and I had to start working to pay for the college, so that I had to stop following you. Now 5 years later I'm back and ready to continue. I don't know what is so magical about working with OpenGL and graphics, but it's still my dream job to work with OpenGL. I tried many specialization like neural nets, hardware design in VHDL, motor control, image processing but nothing got me interested as OpenGL. Best part of college was C++ course, where I applied everything you taught me. Thank you so much for your content and god bless your family.
Hey Cherno, would love a “productivity in c++” kind of video maybe going over keyboard shortcuts or ways to code more efficiently in visual studio or just in general
@Ralph Reilly there is nothing personal about how to use vs's editor functionality. you would be surprised how much time you could save if someone showed you how to use it properly.
One important thing to mention is that the std:: (unordered-)map/set containers are very slow, because they need to guarantee pointer stability and abi breaks hinder compiler vendors from improving them. You can get speedups of sometimes up to 5x by just using a different hash map, e.g. absl::flat_hash_map or tsl::robin_map.
I will counter this by saying. This does not matter unless it is showing up in performance captures as a problem. Use the standard library liberally and as much as you can. It is fantastic and should be the first tool that you reach for. And if you happen to notice slow downs and find that something in the standard library is actually the issue, then start to look elsewhere for replacements. As a software engineer, it is the API and guarantees that that API gives that matter most. Software has to be correct before it can be fast. And if you can just swap something out later for something that has a faster implementation, but the same API then it's probably easier to just use the standard library before reaching beyond it when it might be a non-issue anyway.
Define slow here, what is slow are you talking about? Insertion? Appending? Search? deletion? Be specific since all data structures has their pro's and cons.
15:51 What you're trying to do is called aggregate initialization. It requires you to also use curly brackets. Unfortunately you'll need to use push_back instead of emplace_back because the parameters aren't passed through, but the object is first created and then passed through. Thanks for the great content. Keep them coming!!
I love the honesty of how you handled the odditites in the industry, I love that you explain multiple ways of doing something even if there is a less conventional way as a just in case, I love that you actually explain how to read the error messages and output errors and most of all I love your accent. Thank you so much for being clear and connecting dots.
Thanks for your videos Cherno. I only just stumbled across your channel and your videos have been a really useful recap for my rusty C++ skills from over a decade ago!
15:48 Hey TheCherno, it can be solved by passing the arguments as "initializer list-looking" syntax, as emplace_back is requiring a single Object. So, the arguments have to be a single object. They can be: .emplace_back(CityRecord{ "CityName", 50000, 70, 70}); Or just, .emplace_back({ "CityName", 50000, 70, 70}); By the way, I'm a long-term TheCherno follower, and it's the first time I suggested something to my mentor :)
This was big for me. I am still at 12 minutes into video, and tried to compile. Compiler said nope. Something about no overloaded function had that many parameters. ChatGPT showed me how to build constructors for my struct (messy). This cleaned that right up!
at 21:18 you're searching for element twice, at "find" call and at "at" call The better way would be to get an iterator of "find" and then use iterator instead of "at" call For unordered_map it might be not that important but it is for a map
This is so cool! I was just doing a Clash of Code on CodingGame yesterday and asking a guy about these! Now, you're posting a video on them: A nice coincidence!
Guy, i'm from Brazil, english not is my native language, but i need to say that this channel is my favorite font to learn and apply your content; Thank you for this video, i very like to be here. 🎯🚀
wow, i learned about at() throwing in the morning getting to work, and the same day I actually used this knowledge in my work process! so cool, never payed attention to that before
Like your videos a lot, hope to see more of these! I will be nice if you could have videos about C++20 features. P.S You could have mention that c++20 has contains() for maps.
STL error/warning messages are so much fun to try and comprehend. At least C# custom hashing is wickedly easy to implement, albeit a bit challenging to implement "correctly" (with uniformly-distributed hash codes). All of this discussion about std::map, and you just lit the light bulb for a problem that I was dealing with. Thanks Cherno!
Nice video, however, at 15:31, when 2 keys give the same hash they don't necessarily map to the same element, they only do it when they compare equal, so, just returning 0 in the hash function will not break the unordered_map, it will only make it really slow. Also, your setup seems to implicityly define some constructors and operators as, with `g++ -std=c++17`, in the std::vector example you needed to define the constructor and for using a custom type for the key in a std::unordered_map it also needed defining operator==. I think you should mention that you also need to define something that would tell if 2 keys are equal
I’m confused on the second quarter, after around 9:30. My brain just doesn’t want to comprehend all that new stuff rn. I’ll be coming back to this video later!
Holy shit at 25 minutes I was literally putting my plate down to ask you to cover the case that you literally IMMEDIATELY introduced as I touched my keyboard near the end of the video. Incredible, best CPP channel on the platform. Casual pace but advanced topics ♥️
I'm glad you're still doing these!! These video's help a lot. I''m not doing maps yet but I know I'll be back here in no time. I can't wait until I know enough to follow your code review videos!
15:30 Would it really override data if your hashes come out to the same? I thought it would do a memcmp or something under the hood as a way of handling collisions.
It stores the colliding elements in the same bucket and handles lookup by doing a linear search using the equals operator, so yeah there is no overriding of data. The worst that can happen is poor performance.
Thank you very much for all the explanations and examples, Cherno! Would definitely love to see a benchmark comparison for various kinds of maps! On a separate note, you once mentioned thinking about a video on variadic templates - would be excited to see that one too!
i would love a video going over a bunch of beginner, intermediate, advanced projects in c++ since yk the best way to learn to code is to...actually code lol
I was already familiar with std::map, but i was not aware of the constness of the operator[] and how it always insert an element regardless, good stuff, keep it up ! Definitly interested to see a benchmark video !
Note that using std::pmr memory resources can significantly improve your containers performance, provided you set your memory resource objects appropriately.
Why the sintaxis to define the hash function is so complex? Why is not possible to define a hash method in the struct? Just the same as it is possible to define the less than operator to use std::map
I wonder if having a vector and then a map/unordered_map is too much for situations where you have too many elements (+1M) and you are iterating (i.e. every frame) but also need that fast lookup. Then we could iterate over the vector but lookup through the map. Maybe is not the best types but some kinda of searchable index that would retrieve the vector index of the object.
This is a common space vs. time trade off. You are taking up more memory for an increase in speed. Depending on how you use the data, yes something like this can be worthwhile. Just remember that simply consuming more memory can hurt performance because it can affect caching performance. You might hear people call this kind of stuff a “hybrid” data structure as well. This is referring to some combination of two other data structures to get the benefits of both. This is never without downsides, but those downsides might not matter for your use case.
This video reminded me of why I put off learning C++ for so long! I've been using C# for years and even learned C last year, but C++ still scared me lol. I was going through your playlist and following along pretty well and then I started skipping around... and well... That hash setup is gross XD. I'll stick with it tho!
You can have best of both worlds with an index map; store values in a Vec and a map of hashes to indexes. Although the tradeoff is that more memory is used.
Another great video! I'd love to see a video where you write your own memory allocator, maybe talking about different ways to implement them, and what scenarios each way might provide a boost in performance for. I've been working on my own physics engine and took a lot of inspiration from Box2D which uses a couple of different custom allocators for different situations, and I'd love to learn more.
Great video as always. I'd be keen to see the performance benchmarking of standard and unordered maps. I've heard that there's a couple of dimensions to the problem, in particular if the keys, (when strings) often start with identical substrings (common issue naming keys, eg 'address_line_1', 'address_line_2' etc) as this affects how long the string comparisons take to find the location in the tree. So apparently ordered maps can be faster for small collections, where a very small tree search can outstip the hash function, and the transition point depends on how distinct (or overlapping) the start of the strings in the keys are on average. I haven't done any benchmarking myself, but would be great to see.
If two hashes would return the same value, and there is a collision, would c++ still know that there are two different values for the same key? I naively made a map once and whenever there was a collision of my key, i checked if stored them in a vector and retrieved linearly. Took the workload off overall but felt hacky. So i am wondering how to solve it ‚,correctly“
Thanks for reminding me of binary search. Haven't used that algo in years, mainly because the containers I work with tend to be unordered. But good to know, that you *could* use it.
Is there any way to use a map where you know the component but dont know the key, could you look that up, so like a map but you reverse the look up. EX. if the original is map[int, string], coud you look up map[string] returns int or something. obviously this onyl works if the data is all unique.
![Noob To Max With DRAGON REWORK In Blox Fruits [FULL MOVIE]](http://i.ytimg.com/vi/LnBMOinoOvA/mqdefault.jpg)
Hope you all enjoyed the latest addition to the C++ series! Let me know if you have any questions about maps below 👇
Also definitely check out Hostinger for all your web hosting needs, and use coupon code CHERNO for a discount: hostinger.com/cherno
Please please make a video about named pipes
Please could you talk about dealing with hash collisions? In your vector video and others you did a great job explaining how they're implemented in memory. Something similar for maps and unordered_maps would be really helpful.
Thanks for all the great videos!
Can you do a vid on template metaprogramming? And as code review it would actually be nice to go over a library container such as vector and explain what is going on. Especially as a beginner /intermediate this feels like it's a whole other language
@@brandonmint007216
Yoiuu.
€1€98£8
98IIIYU78
thanks Cherno, as always great content. Would be great if you could also talk about std::equal_to in the context of unordered maps and hash collision resolution etc. Especially what happens if hash collisions occur. Keep up the good work.
21:01 - When using find(), you can avoid the second lookup required by at() by saving the iterator returned by find(). For example:
if (const auto it = cities.find("Berlin"); it != cities.end()) {
const CityRecord& berlinData = it->second;
// ...
}
I recommend always doing this whenever you use find() to do a lookup. If you only need to know whether the element exists or not, you can use ".count(key) != 0" (or ".contains(key)" in C++20) instead.
I actually had this little mistake a couple times in my current project. Very cool tip.
100% agree. Worth noting also that your "it" is taking advantage of C++17 if-initializer syntax, so this isn't available before that language version
I’ve personally always used .count() and then accessed with either [] operator or .at(). I didn’t know about .find()
Also, if you want to check wether or not a map contains a key but don't need to access its value, you can use std::unordered_map::contains(key), available in C++20
@@DrShwynx That works with vectors but not a map. "find" in a vector is a linear search. You could use for(auto& val : vector ) to iterate over the vector too for searching and just "break;" out of it. Find is useful if you want to use the iterator later on and not just finish up in the loop.
15:20 A hash function is not required to return a unique hash. Two things with the same hash will be stored in the same bucket, which is inefficient for lookups, but it will function fine. The hash provides fast access to the appropriate bucket. The equality operator is what determines if a key actually matches. You should strive to make unique hashes for performance reasons, but hash collisions will not compromise the map.
26:50 -If two cities have the same population and that is all you are using for comparison, then they will appear in an arbitrary order but still appear next to each other in the map. Nothing is broken in this case. You just will not be able to rely on their order remaining consistent as the map changes.- This is incorrect. Not sure what I was thinking when I wrote it.
Yup and in addition it's possible that different hashes end up in same bucket
You can come up with a great hash function that minimizes the amount of collisions, but at the end of the day you can compromise a bit of speed when creating the hash map through linear probing or other methods (O(N)) to get perfect collision-less hash maps by sampling the next index until you are sure that you don't have collisions.
As for now, it seems like youtube should give a platform for contributing into videos' drafts with deep fakes :3
Im pretty sure that we could bring all the educational stuff to a brand new level
"26:50 If two cities have the same population and that is all you are using for comparison, then they will appear in an arbitrary order but still appear next to each other in the map. Nothing is broken in this case. You just will not be able to rely on their order remaining consistent as the map changes."
you are wrong. in c++20 the population is used for the key, if it's equal between two objects the compiler will assume that you are referring to the same object.
@@rhoynarr You are correct. I am not sure what I was thinking when I wrote that 6 months ago.
Yes! This C++ series is truly a gold mine :D
The find + at pattern at 20:50 does twice the amount of necessary work, because find already returns a pointer to the data.
Hey Cherno, I started watching you 5 years ago, while I was in my first year of college. I saw every video you made. I patiently rewrote line by line your sparky engine, but then I had so many school duties and I had to start working to pay for the college, so that I had to stop following you. Now 5 years later I'm back and ready to continue. I don't know what is so magical about working with OpenGL and graphics, but it's still my dream job to work with OpenGL. I tried many specialization like neural nets, hardware design in VHDL, motor control, image processing but nothing got me interested as OpenGL. Best part of college was C++ course, where I applied everything you taught me. Thank you so much for your content and god bless your family.
100/100 c++ videos from this playlist watched!
Been very informative so thanks for this series!
Hey Cherno, would love a “productivity in c++” kind of video maybe going over keyboard shortcuts or ways to code more efficiently in visual studio or just in general
Screw you doctor your pills made me feel worse.
@Ralph Reilly there is nothing personal about how to use vs's editor functionality. you would be surprised how much time you could save if someone showed you how to use it properly.
Look out for CUA, it's awesome what you can do in basicaly ANY text editor.
Vim. Keybindings. Full. Stop.
It's called vim homeboy
Expecting more content in this C++ series. This series is a gem. 🔥
Indeed it is
Am totally cured off herpes (hsv1) and am so so happy right now thanks Dretiko on RUclips for your good work,,
One important thing to mention is that the std:: (unordered-)map/set containers are very slow, because they need to guarantee pointer stability and abi breaks hinder compiler vendors from improving them. You can get speedups of sometimes up to 5x by just using a different hash map, e.g. absl::flat_hash_map or tsl::robin_map.
can you link to some reliable anaysis/commentary on this?
I will counter this by saying. This does not matter unless it is showing up in performance captures as a problem.
Use the standard library liberally and as much as you can. It is fantastic and should be the first tool that you reach for.
And if you happen to notice slow downs and find that something in the standard library is actually the issue, then start to look elsewhere for replacements.
As a software engineer, it is the API and guarantees that that API gives that matter most. Software has to be correct before it can be fast. And if you can just swap something out later for something that has a faster implementation, but the same API then it's probably easier to just use the standard library before reaching beyond it when it might be a non-issue anyway.
@@theKStocky true
Define slow here, what is slow are you talking about? Insertion? Appending? Search? deletion? Be specific since all data structures has their pro's and cons.
@@marcspecter Search for Martin Ankerl's Hashmaps Benchmarks for a recent (2019) thorough hash table benchmark
Oh nice. Finally a video for the C++ series. I got so excited when I saw the notification.
Finally a C++ series tutorial with an old style thumbnail!
Never would've thought I'd learn basic c++ in two weeks knowing just js but here we are. This series is wild.
Great video! A follow up video about std::set in which you compare the different sets to the different maps would be awesome! Keep it up!
Or perhaps about the container adaptors like stack, queue and priority_queue
15:51 What you're trying to do is called aggregate initialization. It requires you to also use curly brackets. Unfortunately you'll need to use push_back instead of emplace_back because the parameters aren't passed through, but the object is first created and then passed through.
Thanks for the great content. Keep them coming!!
100th video of the c++ series. Well done Yan!!
I love the honesty of how you handled the odditites in the industry, I love that you explain multiple ways of doing something even if there is a less conventional way as a just in case, I love that you actually explain how to read the error messages and output errors and most of all I love your accent. Thank you so much for being clear and connecting dots.
Thanks for your videos Cherno. I only just stumbled across your channel and your videos have been a really useful recap for my rusty C++ skills from over a decade ago!
15:48 Hey TheCherno, it can be solved by passing the arguments as "initializer list-looking" syntax, as emplace_back is requiring a single Object. So, the arguments have to be a single object.
They can be: .emplace_back(CityRecord{ "CityName", 50000, 70, 70});
Or just, .emplace_back({ "CityName", 50000, 70, 70});
By the way, I'm a long-term TheCherno follower, and it's the first time I suggested something to my mentor :)
This was big for me. I am still at 12 minutes into video, and tried to compile. Compiler said nope. Something about no overloaded function had that many parameters. ChatGPT showed me how to build constructors for my struct (messy). This cleaned that right up!
@@vtgordo It's a pleasure to know :)
at 21:18 you're searching for element twice, at "find" call and at "at" call
The better way would be to get an iterator of "find" and then use iterator instead of "at" call
For unordered_map it might be not that important but it is for a map
100th video in the playlist!🔥
This is so cool! I was just doing a Clash of Code on CodingGame yesterday and asking a guy about these! Now, you're posting a video on them: A nice coincidence!
💯 completed. Thank You. Its a historic moment.
Thank you so much to put more content in this series. Waiting for more videos on data structures
That was actually perfect for a beginner. Thank you!
20:50 now you can use std::unordered_map::contains in c++20 instead of checking if find() equals the past-the-end
Guy, i'm from Brazil, english not is my native language, but i need to say that this channel is my favorite font to learn and apply your content; Thank you for this video, i very like to be here. 🎯🚀
wow, i learned about at() throwing in the morning getting to work, and the same day I actually used this knowledge in my work process! so cool, never payed attention to that before
Gold, I'd expect nothing less. Thanks Cherno
Yes !!!, Thanks so much for these. Please more on c++ data structures
damn, in 10 seconds you've solved my c++20 problem. twas a hardly laugh to see that i've been rockin' C++14 the whole time
Like your videos a lot, hope to see more of these!
I will be nice if you could have videos about C++20 features.
P.S
You could have mention that c++20 has contains() for maps.
STL error/warning messages are so much fun to try and comprehend. At least C# custom hashing is wickedly easy to implement, albeit a bit challenging to implement "correctly" (with uniformly-distributed hash codes).
All of this discussion about std::map, and you just lit the light bulb for a problem that I was dealing with. Thanks Cherno!
For the next episode, don't forget to compare a std::map to a constexpr std::vector, because compilers don't already do enough work on our behalf.
I love this little focus videos man. Keep it up!
Yes!! Continue this series I love it!!!
since when Mr. Beast is teaching programming???
This didn't age well LOL
LOL mrbeast is teaching programming
I was almost two weeks behind on my assigment. this helped me to finally get the courage and finish it. thanks!
Thanks for c++ tutorial/series. You're amazing keep on
16:07 I think you don't need the constructor now if you're using C++20. C++20 permits aggregate initialization with parentheses now.
Also you can specialize the std::hash struct without opening the std namespace, just use template struct std::hash { things } and you're good to go.
Very well explained , appreciate for your hard work and honest effort !!
Once again you summarize a key data structure better than my college professor.
19:46 that`s why i love c++, sometimes it`s so tricky and unpredictible
Wow bro… you gat me dripping …
I was just thinking of it about an hour ago…
Keep streaming Yan, it makes my day.
Looking forward to the video of the performance between these maps!!!🤩
"Why are there two different types of maps? Because there are different types of maps." - Cherno 2022
you are basically screwed. absolutely loved that word "screwed".🤣🤣
Nice video, however, at 15:31, when 2 keys give the same hash they don't necessarily map to the same element, they only do it when they compare equal, so, just returning 0 in the hash function will not break the unordered_map, it will only make it really slow.
Also, your setup seems to implicityly define some constructors and operators as, with `g++ -std=c++17`, in the std::vector example you needed to define the constructor and for using a custom type for the key in a std::unordered_map it also needed defining operator==. I think you should mention that you also need to define something that would tell if 2 keys are equal
Appreciate this series so much!
Fantastic video for C++ learner！
I’m confused on the second quarter, after around 9:30. My brain just doesn’t want to comprehend all that new stuff rn. I’ll be coming back to this video later!
Update: im back bitches
Holy shit at 25 minutes I was literally putting my plate down to ask you to cover the case that you literally IMMEDIATELY introduced as I touched my keyboard near the end of the video. Incredible, best CPP channel on the platform. Casual pace but advanced topics ♥️
Python developers when Cherno says "Expensive"
*cricket noises*
Sure, performance video about maps would be awesome!
I missed this series so much buddy =]
This video helped a ton. Thanks as always.
I actually learned this today, would have liked to have this video a couple hours ago hahaha
I'm glad you're still doing these!! These video's help a lot. I''m not doing maps yet but I know I'll be back here in no time. I can't wait until I know enough to follow your code review videos!
the equals sign is because of microsoft's new font having ligatures, you can disable it
15:30 Would it really override data if your hashes come out to the same? I thought it would do a memcmp or something under the hood as a way of handling collisions.
It stores the colliding elements in the same bucket and handles lookup by doing a linear search using the equals operator, so yeah there is no overriding of data. The worst that can happen is poor performance.
I was about to comment about this
When using string as a key for map it’s generally good to pass a string comparator func as well
Thank you very much for all the explanations and examples, Cherno!
Would definitely love to see a benchmark comparison for various kinds of maps!
On a separate note, you once mentioned thinking about a video on variadic templates - would be excited to see that one too!
Fantastic channel! really nice to have as support when I'm studying. I think a video about concepts and constraints in C++20 would be interesting
You are to C++ as Shakespeare is to the rhyming couplet - that was just great stuff....
!the best c++ channel
Glad this series is back!! It helped me a ton when learning c++
In C++20 you could do map.contains() to check if an element exists.
i would love a video going over a bunch of beginner, intermediate, advanced projects in c++ since yk the best way to learn to code is to...actually code lol
Thank you, for saving my course project.
@The Cherno Please make a video for all the shortcut you use for coding, like at 06:55 and 21:00. I am highly anticipating it.
Still going strong ? Happy to see you back :)
Of course we want performance comparisons and/or performance measuring tips in general. :)
Your videos are so funny and teach me a lots
Please continue this series
Wow i love that visual studio theme! Sir can you please tell what theme is it?
It has been a year, and i still want to see the performance comparison and more c++ series!!!
I came for Cherno video. I stayed for the monologue.
I was already familiar with std::map, but i was not aware of the constness of the operator[] and how it always insert an element regardless, good stuff, keep it up !
Definitly interested to see a benchmark video !
Note that using std::pmr memory resources can significantly improve your containers performance, provided you set your memory resource objects appropriately.
Why the sintaxis to define the hash function is so complex? Why is not possible to define a hash method in the struct? Just the same as it is possible to define the less than operator to use std::map
I wonder if having a vector and then a map/unordered_map is too much for situations where you have too many elements (+1M) and you are iterating (i.e. every frame) but also need that fast lookup. Then we could iterate over the vector but lookup through the map. Maybe is not the best types but some kinda of searchable index that would retrieve the vector index of the object.
I was wondering the same
This is a common space vs. time trade off. You are taking up more memory for an increase in speed. Depending on how you use the data, yes something like this can be worthwhile. Just remember that simply consuming more memory can hurt performance because it can affect caching performance.
You might hear people call this kind of stuff a “hybrid” data structure as well. This is referring to some combination of two other data structures to get the benefits of both. This is never without downsides, but those downsides might not matter for your use case.
@@deanjohnson8233 so, "profile it" it is I guess : p
This video reminded me of why I put off learning C++ for so long! I've been using C# for years and even learned C last year, but C++ still scared me lol. I was going through your playlist and following along pretty well and then I started skipping around... and well...
That hash setup is gross XD. I'll stick with it tho!
Do we need to write a customised hash function for using std::vector as the key?
Bro, perfect timing.
Thanks for the great videos. Yes, a video map benchmark please :)
you've aged mate... i'm looking at your awesome stuff from five years ago
great video as always, you should give a talk at cppcon about teaching cpp next year
20:54 - I think using cities.contains("Berlin") is much simpler and cleaner than the whole cities.find("Berlin" ) != cities.end()
IMO it's a bit about C++ standards. Sure, it was just worth mentioning
13:13 What happens if you don't do template specialization here and make the template take in an argument in the angle bracket?
"finally, no more paris"
good
You can have best of both worlds with an index map; store values in a Vec and a map of hashes to indexes. Although the tradeoff is that more memory is used.
Another great video! I'd love to see a video where you write your own memory allocator, maybe talking about different ways to implement them, and what scenarios each way might provide a boost in performance for.
I've been working on my own physics engine and took a lot of inspiration from Box2D which uses a couple of different custom allocators for different situations, and I'd love to learn more.
Great video as always. I'd be keen to see the performance benchmarking of standard and unordered maps. I've heard that there's a couple of dimensions to the problem, in particular if the keys, (when strings) often start with identical substrings (common issue naming keys, eg 'address_line_1', 'address_line_2' etc) as this affects how long the string comparisons take to find the location in the tree. So apparently ordered maps can be faster for small collections, where a very small tree search can outstip the hash function, and the transition point depends on how distinct (or overlapping) the start of the strings in the keys are on average. I haven't done any benchmarking myself, but would be great to see.
Finally! A new video!!!!!!!
If two hashes would return the same value, and there is a collision, would c++ still know that there are two different values for the same key? I naively made a map once and whenever there was a collision of my key, i checked if stored them in a vector and retrieved linearly. Took the workload off overall but felt hacky. So i am wondering how to solve it ‚,correctly“
where did you put your hair?
Thanks for reminding me of binary search. Haven't used that algo in years, mainly because the containers I work with tend to be unordered. But good to know, that you *could* use it.
Hair???
BTW, I've been programming cpp for about 2 years. Your videos really got me going at the start. I owe it all to you...
I just can't get used to his short hair
@@nielsdaemen NEITHER CAN I 🤣🤣🤣
We can also use the operator= to get the specific element in the vector :
Is there any way to use a map where you know the component but dont know the key, could you look that up, so like a map but you reverse the look up. EX. if the original is map[int, string], coud you look up map[string] returns int or something. obviously this onyl works if the data is all unique.