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.
Topics Covered
Part 1
-
std::map container interface
- Binary tree data structure
-
std::map key requirements (comparison)
-
std::map gotchas (std::remove_if and const keys)
-
std::set
-
std::multimap and std::multiset
Part 2
- 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 over std::unordered_map
Video Timestamp Index
Tutorial 24.1
[Expand]
- The
std::map<KeyType,ValueType> class 0:46
- Maps consist of keys to lookup (associated with) values
-
map.insert( {key,value} ) to insert (key,value) pairs
-
map[key] returns a reference to the ValueType for a KeyType
- The Binary tree data structure 2:46
-
std::map performs lookup in O(log(n)), it uses a Binary tree data structure
- Key properties of a Binary Tree (BT):
- - Nodes can have at most 2 children (hence: binary)
- - Each left child is smaller and each right child is larger than its parent
- - Insertion is done by navigating the tree along a route Left for smaller, Right for larger such that the order property always holds
- The big advantage of the BT properties is that retrieval is very fast
- The beauty of
std::map is that we don't have to implement any of this; it's all there in the STL 7:00
- The STL implementation is further optimized, e.g. it uses a red-black tree for BT rebalancing
- A look at the
std::map cppreference.com documentation 7:35
-
map.insert() takes a pair type std::pair<KeyType,ValueType>, the Map's elements
- C++ can deduce the pair Type, so
map.insert({keyX,valueXYZ}); with curly braces will do the job
- An even better way to insert is through
map.emplace[] operation; iit will construct the pair in-place.
- For lookup, you can use square braces,
map[x] will return a reference to the corresponding value
- Note: a lookup with a new key value will create that element in the map with the default constructed ValueType value
-
insert or emplace with a key that already exists will NOT override the existing value: std::map::emplace returns a std::pair<iterator,bool> where the bool inidicates whether an insertion took place
-
map.find("xyz")<code> returns an iterator to the element if it exitst, and an iterator to <code>map.end() if it doesn't exist (useful to check if a key already exists)
-
std::map comes with iterators and because it is a sorted map, when you iterate over its elements with for (auto& el : map), it will be in order (of the keys)
- Requirements on KeyType 14:30
- The KeyType has to be comparable. The third template parameter is a functor for KeyType Comparison that defaults to
std::less<KeyType>
- So by default keys have to implement the "less than" comparison operator or provide your own comparison functor when defining the map
Tutorial 24.2
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.
Supplementary Link
See also
