Intermediate C++ Game Programming Tutorial 24
From Chilipedia
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
- Main difference between ordered/unordered is performance 0:14
- Implication: if you iterative over an unordered container, keys will appear in (seemingly) random order
- Releasing the ordering requirement makes it possible to use a hash table with performance advantages: O(1) contant time insertion and lookup
- Using an unordered map 1:38
- The interface is pretty much the same as its ordered counterpart
- Include
<unordered_map>
, declare usingstd::unordered_map<KeyType,ValueType>
- You can initialize your map object with an initializer list if you wanted to using
({ {..,..},{..,..},... })
inside your declaration
- The Hash Table data structure 3:20
- A hash table allows you to get the quick access to values, comparable to array access using the index, but with efficient memory usage
- Buckets are used to group keys; this is done by mapping keys to buckets using a hash function (a.k.a. hashing)
- Multiple keys can map to the same bucket in a hash table ("collision"). We use a linked list to store multiple {key,value} pairs in a bucket
- Two ways to minimize hash collisions: i) more buckets, ii) smart hash function that distributes key values uniformly across your bucket space
- Hashing a a two step process 9:26:
- - A hash function takes in the KeyType input (typically a string or int) and outputs a size_t
- - the size_t output is reduced/ditributed to the size of the hash table (number of buckets)
- The Standard Library provides general hashing functions for all the standard types
- For general use of unordered maps, we don't have to worry about the technical details of how the hash table works, the STL provides this
- Requirements for the KeyType of an
unordered_map
/ a hash table 11:56- There needs to be a working hash function defined for the KeyType
- There need to be comparison and equality comparator definitions for the KeyType
- Example: map from
Vec2
class (2D coordinates) to a string 12:46- In order to make this work, you need to define a hash function and the comparators for
Vei2
-
struct CompVec2
{
template<typename T>
- In order to make this work, you need to define a hash function and the comparators for
- [WORK-IN-PROGRESS]
Homework Assignment
The homework for this video is to enable use of a custom datatype in <code>unordered_map
hashing over multiple (4) members of that datatype. The solution video is here.