Intermediate C++ Game Programming Tutorial 24 - Revision history

R vdw: /* Tutorial 24.2: The unordered associative containers */

2020-02-02T14:47:54Z

‎Tutorial 24.2: The unordered associative containers

R vdw: /* Tutorial 24.2: The unordered associative containers */

2020-02-02T14:46:52Z

‎Tutorial 24.2: The unordered associative containers

R vdw: /* Tutorial 24.2: The unordered associative containers */

2020-02-02T14:13:46Z

‎Tutorial 24.2: The unordered associative containers

R vdw: /* Tutorial 24.2: The unordered associative containers */

2020-02-02T13:36:05Z

‎Tutorial 24.2: The unordered associative containers

R vdw: /* Tutorial 24.2: The unordered associative containers */

2020-02-02T13:35:20Z

‎Tutorial 24.2: The unordered associative containers

R vdw: /* Tutorial 24.2: The unordered associative containers */

2020-02-02T13:34:11Z

‎Tutorial 24.2: The unordered associative containers

R vdw: /* Tutorial 24.2: The unordered associative containers */

2020-02-02T13:31:38Z

‎Tutorial 24.2: The unordered associative containers

R vdw: /* Tutorial 24.2: The unordered associative containers */

2020-02-02T13:30:50Z

‎Tutorial 24.2: The unordered associative containers

R vdw: /* Tutorial 24.2: The unordered associative containers */

2020-02-02T13:08:04Z

‎Tutorial 24.2: The unordered associative containers

R vdw: /* Tutorial 24.2: The unordered associative containers */

2020-02-02T13:07:26Z

‎Tutorial 24.2: The unordered associative containers

@@ Line 161: / Line 161: @@
 };
 </syntaxhighlight>
-:* 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].
+:* You pass this 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
 </div>

@@ Line 145: / Line 145: @@
 <div class="mw-collapsible-content">
 :* 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
+:* A simple google search will give you good examples of how to combine hash values in C++
 :* You can implement a hashing functor as a <code>struct</code> that defines a member function, templated on <code>T</code>, the basic type of the <code>Vec2</code> coordinates:
 ::<syntaxhighlight lang="cpp" line>
-size_t operator()( const _Vec2<T>& vec ) const
+struct HashVec2
+{
-     std::hash<T> hasher;
+     template <typename T>
-    auto hashx = hasher ( vec.x );
+    size_t operator()( const _Vec2<T>& vec ) const
-    auto hashy = hasher ( vec.y );
-    hashx ^= hashy + 0x9e3779b9 + (hashx << 6) + (hashx >> 2);
+        std::hash<T> hasher;
-    return hashx;
+        auto hashx = hasher ( vec.x );
+        auto hashy = hasher ( vec.y );
 </syntaxhighlight>
 :* 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].

@@ Line 128: / Line 128: @@
 <div class="mw-collapsible-content">
 :* In order to make this work, you need to define a hash function and the comparators for <code>Vei2</code>
-:* You can implement a comparison/equality functor as a <code>struct</code> that defines a <code>bool operator()( const T& lhs,const T& rhs ) const</code> member function, templated on <code>T</code>
+:* You can implement a comparison/equality functor as a <code>struct</code> that defines a <code>operator()</code> member function, templated on <code>T</code>
 :* 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

@@ Line 140: / Line 140: @@
 size_t operator()( const _Vec2<T>& vec ) const
+{
-	std::hash<T> hasher;
+    std::hash<T> hasher;
-	auto hashx = hasher ( vec.x );
+    auto hashx = hasher ( vec.x );
-	auto hashy = hasher ( vec.y );
+    auto hashy = hasher ( vec.y );
-	hashx ^= hashy + 0x9e3779b9 + (hashx << 6) + (hashx >> 2);
+    hashx ^= hashy + 0x9e3779b9 + (hashx << 6) + (hashx >> 2);
-	return hashx;
+    return hashx;
+}
 </syntaxhighlight>

@@ Line 153: / Line 153: @@
 <div class="mw-collapsible-content">
 :* 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 for your own custom types only
+::<syntaxhighlight lang="cpp" line>
 namespace std
-*: <code>namespace std</code>
-*: <code>{</code>
+    template <> struct hash<Vei2>
-*:: <code>template <> struct hash<Vei2></code>
-*:: <code>{</code>
+        size_t operator()( cont Vei2& vec ) const
-*::: <code>size_t operator()( cont Vei2& vec ) const</code>
+        {...}
-*::: <code>{...}</code>
+    };
-*:: <code>};</code>
-*: <code>}</code>
+</syntaxhighlight>
-−
-−
 :* Now you don't need to pass <code>HashVec2</code> in the map definition
 </div>

@@ Line 147: / Line 147: @@
+}
 </syntaxhighlight>
-** 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].
+:* 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
+:* 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
 </div>
 * Template Specialization [https://youtu.be/LsjFAx-dG5I?t=18m43s 18:43]
 <div class="mw-collapsible-content">
-** 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 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 for your own custom types only
 *: <code>namespace std</code>
 *: <code>{</code>
@@ Line 161: / Line 163: @@
 *:: <code>};</code>
 *: <code>}</code>
-** Now you don't need to pass <code>HashVec2</code> in the map definition
 </div>
 * The <code>std::unordered_map<></code> Bucket interface [https://youtu.be/LsjFAx-dG5I?t=20m00s 20:00]
 <div class="mw-collapsible-content">
-** Allows you to get information about the buckets in the hash table and access nodes
+:* Allows you to get information about the buckets in the hash table and access nodes
-** The bucket iterator takes an index of the bucket and allows you to iterate over all the elements in that specific bucket
+:* The bucket iterator takes an index of the bucket and allows you to iterate over all the elements in that specific bucket
 </div>
 * The <code>std::unordered_map<></code> Hash policy interface [https://youtu.be/LsjFAx-dG5I?t=21m47s 21:47]
 <div class="mw-collapsible-content">
-** Allows you to tune your hash table (and thus the growth behavior & performance of the map)
+:* Allows you to tune your hash table (and thus the growth behavior & performance of the map)
-** Load Factor = average number of elements per bucket. For performance, you typically want to keep this below 1
+:* Load Factor = average number of elements per bucket. For performance, you typically want to keep this below 1
-** You can set the maximum load factor above which the table gets rehashed
+:* You can set the maximum load factor above which the table gets rehashed
-** When the load factor becomes too high, it will automaticall rehash the table and increase the number of buckets
+:* When the load factor becomes too high, it will automaticall rehash the table and increase the number of buckets
-** You can manually rehash to a number of buckets you define
+:* You can manually rehash to a number of buckets you define
-** You can reserve space for max number of elements, is then derives (and manages) the required number of buckets
+:* You can reserve space for max number of elements, is then derives (and manages) the required number of buckets
 </div>
 * When to choose <code>std::map</code> over <code>std::unordered_map</code>? [https://youtu.be/LsjFAx-dG5I?t=24m15s 25:15]
 <div class="mw-collapsible-content">
-** For simplicity and when performance is not a critical issue, no need to define a hash function;
+:* For simplicity and when performance is not a critical issue, no need to define a hash function;
-** If you want to iterate in order;
+:* If you want to iterate in order;
-** When you want to be able to find keys that are close to a certain key (with <code>lower_bound</code> and <code>upper_bount</code>
+:* When you want to be able to find keys that are close to a certain key (with <code>lower_bound</code> and <code>upper_bount</code>
 </div>
 * Homework assignment [https://youtu.be/LsjFAx-dG5I?t=26m04s 26:04]

@@ Line 122: / Line 122: @@
 * Requirements for the KeyType of an <code>unordered_map</code> / a hash table [https://youtu.be/LsjFAx-dG5I?t=11m56s 11:56]
 <div class="mw-collapsible-content">
-** There needs to be a working hash function defined for the KeyType
+:* There needs to be a working hash function defined for the KeyType
-** There need to be comparison and equality functor definitions for the KeyType
+:* There need to be comparison and equality functor definitions for the KeyType
 </div>
 * Example: map from <code>Vec2</code> class (2D coordinates) to a string [https://youtu.be/LsjFAx-dG5I?t=12m46s 12:46]
 <div class="mw-collapsible-content">
-** In order to make this work, you need to define a hash function and the comparators for <code>Vei2</code>
+:* In order to make this work, you need to define a hash function and the comparators for <code>Vei2</code>
-** You can implement a comparison/equality functor as a <code>struct</code> that defines a <code>bool operator()( const T& lhs,const T& rhs ) const</code> member function, templated on <code>T</code>
+:* You can implement a comparison/equality functor as a <code>struct</code> that defines a <code>bool operator()( const T& lhs,const T& rhs ) const</code> member function, templated on <code>T</code>
-** Defining a custom hashing function is an art, it requires knowledge of cryptography, abstract algebra, discrete math, etc.
+:* 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
+:* Luckily, we don't need this; you can revert to the standard hashing functions for the basic types that make up any custom type
 </div>
 * Hash combining [https://youtu.be/LsjFAx-dG5I?t=14m25s 14:25]
 <div class="mw-collapsible-content">
-** Combining hashes from basic types to create a hash over your custom object
+:* 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
+:* 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 <code>struct</code> that defines a member function, templated on <code>T</code>, the basic type of the <code>Vec2</code> coordinates:
+::<syntaxhighlight lang="cpp" line>
 *: <code>size_t operator()( const _Vec2<T>& vec ) const</code>
 *: <code>{</code>

@@ Line 115: / Line 115: @@
 :* 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 [https://youtu.be/LsjFAx-dG5I?t=9m26s 9:26]:
-*:- A hash function takes in the KeyType input (typically a string or int) and outputs a size_t
+::- 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 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

@@ Line 110: / Line 110: @@
 * The Hash Table data structure [https://youtu.be/LsjFAx-dG5I?t=3m20s 3:20]
 <div class="mw-collapsible-content">
-** A hash table allows you to get the quick access to values, comparable to array access using the index, but with efficient memory usage
+:* 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)
+:* 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
+:* 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
+:* 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 [https://youtu.be/LsjFAx-dG5I?t=9m26s 9:26]:
+:* Hashing a a two step process [https://youtu.be/LsjFAx-dG5I?t=9m26s 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
+:* 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
+:* 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
 </div>
 * Requirements for the KeyType of an <code>unordered_map</code> / a hash table [https://youtu.be/LsjFAx-dG5I?t=11m56s 11:56]