Difference between revisions of "Intermediate C++ Game Programming Tutorial 24"
From Chilipedia
(→Video Timestamp Index) |
(→Video Timestamp Index) |
||
Line 27: | Line 27: | ||
** <code>map[key]</code> returns a reference to the ValueType for a KeyType | ** <code>map[key]</code> returns a reference to the ValueType for a KeyType | ||
</div> | </div> | ||
− | * A Binary Tree data structure is used to manage the order of | + | * A Binary Tree data structure is used to manage the order of map elements [https://youtu.be/JlPsCoCO99o?t=2m46s 2:46] |
<div class="mw-collapsible-content"> | <div class="mw-collapsible-content"> | ||
** <code>std::map</code> performs lookup in O(log(n)), it uses a Binary tree data structure | ** <code>std::map</code> performs lookup in O(log(n)), it uses a Binary tree data structure |
Revision as of 04:54, 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: ordered associative containers
-
std::map
container interface - Binary tree data structure
-
std::map
key requirements (comparison) -
std::map
gotchas (std::remove_if
andconst
keys) -
std::set
-
std::multimap
andstd::multiset
Part 2: unordered associative containers
- Hash table performance vs. binary tree performance
- Hash table data structure
-
std::unordered_map
key requirements - Hash combining
-
std::unordered_map
bucket interface and hashing policy - When to choose
std::map
overstd::unordered_map
Video Timestamp Index
Tutorial 24.1: The ordered associative containers
[Expand]
- The
std::map<KeyType,ValueType>
class 0:46
- A Binary Tree data structure is used to manage the order of map elements 2:46
- A look at the
std::map
cppreference.com documentation: insert, lookup & find 7:35
- Requirements on KeyType 14:30
-
std::map
cppreference.com documentation continued: erase 15:28
- Two <<important>> things to know when working with associative containers 16:04
- The
std::set<KeyType>
class 20:00
- The
std::multimap
andstd::multiset
classes 21:28
- Practical example of a multimap use case 22:30
- Lookup in multimaps 25:21
Tutorial 24.2: The unordered associative containers
- [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.