Difference between revisions of "Intermediate C++ Game Programming Tutorial 24"
From Chilipedia
(→Video Timestamp Index) |
(→Video Timestamp Index) |
||
Line 134: | Line 134: | ||
*: <code>}</code> | *: <code>}</code> | ||
− | ** You pass these functors when defining the map: <code>std::unordered_map<Vei2,std::string,HashVec2> map;</code> [https://youtu.be/LsjFAx-dG5I?t=17m15s 17:15]. Note that the comparison functor is not needed: we can revert back to the equality operator already defined in the <code>Vec2</code> class definition | + | ** You pass these functors when defining the map: <code>std::unordered_map<Vei2,std::string,HashVec2> map;</code> [https://youtu.be/LsjFAx-dG5I?t=17m15s 17:15]. |
+ | ** Note that the comparison functor is not needed: we can revert back to the equality operator already defined in the <code>Vec2</code> class definition | ||
** Unordered map uses <code>std::hash</code> by default. You can inject Template Specialization for <code>std::hash</code> into the <code>std</code> Namespace [https://youtu.be/LsjFAx-dG5I?t=18m43s 18:43] for your own custom types only | ** Unordered map uses <code>std::hash</code> by default. You can inject Template Specialization for <code>std::hash</code> into the <code>std</code> Namespace [https://youtu.be/LsjFAx-dG5I?t=18m43s 18:43] for your own custom types only | ||
*: <code>namespace std</code> | *: <code>namespace std</code> |
Revision as of 20:51, 2 February 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
- 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 functor 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
- You can implement a comparison/equality functor as a
struct
that defines abool operator()( const T& lhs,const T& rhs ) const
member function, templated onT
- Defining a custom hashing function is an art, it requires knowledge of cryptography, abstract algebra, discrete math, etc.
- Luckily, we don't need this; you can revert to the standard hashing functions for the basic types that make up any custom type
- In order to make this work, you need to define a hash function and the comparators for
- Hash combining 14:25
- Combining hashes from basic types to create a hash over your custom object
- Stack Overflow question "How do I combine hash values in C++" give the example as used in the boost library
- You can implement a hashing functor as a
struct
that defines a member function, templated onT
, the basic type of theVec2
coordinates:
-
size_t operator()( const _Vec2<T>& vec ) const
-
{
-
std::hash<T> hasher;
-
auto hashx = hasher ( vec.x );
-
auto hashy = hasher ( vec.y );
-
hashx ^= hashy + 0x9e3779b9 + (hashx << 6) + (hashx >> 2);
-
return hashx;
-
-
}
- You pass these functors when defining the map:
std::unordered_map<Vei2,std::string,HashVec2> map;
17:15. - Note that the comparison functor is not needed: we can revert back to the equality operator already defined in the
Vec2
class definition - Unordered map uses
std::hash
by default. You can inject Template Specialization forstd::hash
into thestd
Namespace 18:43 for your own custom types only
-
namespace std
-
{
-
template <> struct hash<Vei2>
-
{
-
size_t operator()( cont Vei2& vec ) const
-
{...}
-
-
};
-
-
}
- Now you don't need to pass
HashVec2
in the map definition
- You pass these functors when defining the map:
- [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.