Difference between revisions of "Intermediate C++ Game Programming Tutorial 24"
From Chilipedia
(→Video Timestamp Index) |
(→Video Timestamp Index) |
||
| Line 60: | Line 60: | ||
*:- By key through <code>map.erase(const KeyType& key)</code>; this operation returns the number of elements erased (in <code>size_type</code>) | *:- By key through <code>map.erase(const KeyType& key)</code>; this operation returns the number of elements erased (in <code>size_type</code>) | ||
</div> | </div> | ||
| − | * | + | * Two <<important>> things to know when working with associative containers [https://youtu.be/JlPsCoCO99o?t=16m04s 16:04] |
<div class="mw-collapsible-content"> | <div class="mw-collapsible-content"> | ||
** <code>std::remove_if</code> does not work with associative containers (will come with C++20). | ** <code>std::remove_if</code> does not work with associative containers (will come with C++20). | ||
*:- You have to iterate over the elements with <code>for( auto i = map.begin(); i != map.end();)</code> | *:- You have to iterate over the elements with <code>for( auto i = map.begin(); i != map.end();)</code> | ||
*:- And apply <code>i = map.erase(i);</code> in the body of your <code>if</code> logic, and <code>++i</code> in the <code>else</code> block. | *:- And apply <code>i = map.erase(i);</code> in the body of your <code>if</code> logic, and <code>++i</code> in the <code>else</code> block. | ||
| − | ** | + | ** You're not allowed to modify the keys [https://youtu.be/JlPsCoCO99o?t=18m38s 18:38] |
| + | *:- Makes sense: the keys define the structure of the binary tree. If you modify the key you invalidate this structure (it would require a deletion and insertion to do it properly) | ||
</div> | </div> | ||
</div> | </div> | ||
Revision as of 04:02, 20 January 2020
Associative containers are super useful, both as a convenient fast way to create dictionary or mapping for real-world problems like managing game resources, and as a data structure to help solve more abstract algorithmic computer science problems. And hash tables are fast as balls.
Contents
[hide]Topics Covered
Part 1
-
std::mapcontainer interface - Binary tree data structure
-
std::mapkey requirements (comparison) -
std::mapgotchas (std::remove_ifandconstkeys) -
std::set -
std::multimapandstd::multiset
Part 2
- Hash table performance vs. binary tree performance
- Hash table data structure
-
std::unordered_mapkey requirements - Hash combining
-
std::unordered_mapbucket interface and hashing policy - When to choose
std::mapoverstd::unordered_map
Video Timestamp Index
[Expand]
- The
std::map<KeyType,ValueType>class 0:46
- The Binary tree data structure 2:46
- A look at the
std::mapcppreference.com documentation: Insert, Lookup, Find 7:35
- Requirements on KeyType 14:30
-
std::mapcppreference.com documentation continued: Erase 15:28
- Two <<important>> things to know when working with associative containers 16:04
- [WORK-IN-PROGRESS]
Homework Assignment
The homework for this video is to enable use of a custom datatype in unordered_map hashing over multiple (4) members of that datatype. The solution video is here.
