Skip to content

Latest commit

 

History

History
215 lines (200 loc) · 6.12 KB

associative_containers.md

File metadata and controls

215 lines (200 loc) · 6.12 KB
Raw
marp math theme paginate
true
katex
custom-theme
true

Associative containers

Today:

  • std::map
  • std::unordered_map
  • std::set
  • std::unordered_set

📺 Watch the related YouTube video!

Special symbols used in slides

  • 🎨 - Style recommendation
  • 🎓 - Software design recommendation
  • 😱 - Not a good practice! Avoid in real life!
  • ✅ - Good practice!
  • ❌ - Whatever is marked with this is wrong
  • 🚨 - Alert! Important information!
  • 💡 - Hint or a useful exercise
  • 🔼1️⃣7️⃣ - Holds for this version of C++ (here, 17) and above
  • 🔽1️⃣1️⃣ - Holds for versions until this one C++ (here, 11)

Style (🎨) and software design (🎓) recommendations mostly come from Google Style Sheet and the CppCoreGuidelines

Use std::map to store ordered data in a tree-like structure

  • #include <map> to use std::map
  • Stores items under unique keys
  • Implemented usually as a Red-Black tree (not guaranteed)
  • Key can be any type with operator < defined
  • By default takes two template parameters: 
    std::map<char, double> map_default{};
  • We can also use > operator by creating the map like this: 
    std::map<int, float, std::greater<int>> map_greater{};
  • Access, add, remove data in $\mathcal{O}(\log{}n)$

Add data to std::map

  • We can create a map from data: 
    const std::map<int, double> map_explicit = {{42, 42.42}};
  • 🔼1️⃣7️⃣ 
    const std::map map_implicit = {std::pair{42, 42.42}};
  • Add item to map: my_map.emplace(key, value);
  • Get (const) reference to an item: my_map.at(key);
  • Modify or add item: my_map[key] = value;
  • 🚨 Operator [] doesn't work on const maps!
  • Check if key is present: my_map.count(key) > 0;
  • Check size: my_map.size();
  • Check if empty: my_map.empty();
  • Clear the map: my_map.clear();
  • Erase key: my_map.erase(key);

Example using std::map

#include <iostream>
#include <map>
using std::cout;
using std::endl;

int main() {
  const std::map<int, double> const_map = {{42, 42.42},
                                           {23, 23.23}};
  // Work with a const map
  cout << "Map is empty: " << const_map.empty() << endl;
  cout << "Map size: " << const_map.size() << endl;
  cout << const_map.at(42) << endl;
  // Work with a mutable map
  std::map mutable_map = {std::pair{42, 42.42},
                          std::pair{23, 23.23}};
  cout << "Map size: " << mutable_map.size() << endl;
  mutable_map[4242] = 23.42;  // Creates a new key-value pair
  cout << "New map size: " << mutable_map.size() << endl;
  cout << mutable_map.at(4242) << endl;
  mutable_map.at(4242) = 42.42;  // Ref to an existing value
  cout << mutable_map.at(4242) << endl;
  mutable_map.erase(4242);
  cout << mutable_map.size() << endl;
}

Use std::unordered_map to store unordered data

  • 🔼1️⃣1️⃣ #include <unordered_map> to use std::unordered_map
  • Serves same purpose as std::map but is implemented as a hash table and not a tree
  • Key type has to be hashable (all fundamental types are)
  • Exactly same interface as std::map
  • Access, add, remove data in $\mathcal{O}(1)$
  • 💡 If you care about performance use std::map when you have small amount of data and std::unordered_map when you have a lot of data (but really, best is to measure)

🔼1️⃣7️⃣ Merge maps

  • Calling map1.merge(map2) allows to merge maps:
    • Elements of map2 not in map1 are added to map1
    • Elements of map2 with keys already in map1 are ignored
  • Works for both: std::map and std::unordered_map: 
    std::map<std::string, int> map1{
    {"A", 1}, {"B", 2}, {"C", 3}};
std::map<std::string, int> map2{
    {"A", 4}, {"B", 2}, {"D", 4}};
map1.merge(map2);
    std::unordered_map<std::string, int> map1{
    {"A", 1}, {"B", 2}, {"C", 3}};
std::unordered_map<std::string, int> map2{
    {"A", 4}, {"B", 2}, {"D", 4}};
map1.merge(map2);
  • ✅ Try it out yourself to see the results!

Use sets to store keys only

  • If you don't have key-value pairs, but just keys that you'd like to be unique, use std::set and std::unordered_set
  • Where maps store pairs, sets store values directly
  • Otherwise, all interfaces are analogous to maps' ones
  • ✅ Try it out yourself to see the results!
  • 💡 Get used to using cppreference.com to figure out interfaces (PS, types are clickable above 😉)

😱 Do not use floating point numbers as keys!

Operations on floating point numbers might result in loss of precision, changing your keys!

#include <iostream>
#include <map>
using std::cout;
using std::endl;
int main() {
  std::map<float, int> blah;  // 😱
  float num = 42.42F;
  blah[num] = 42;
  num += 424242.4242F;
  num -= 424242.4242F;
  std::cout << blah.at(num) << std::endl;
}

We will cover the reason behind this in a later video!

bg