Learn C++ STL

Lesson 5 of 9 · set and multiset: Sorted, Unique, Found in log n

Module 8 · set and multiset: Sorted, Unique, Found in log n

Under the Hood: The Tree's Nodes, Its Height, and Iterators That Stay

ProReading

Kenji keeps a million sensor readings in a set, inserted in the order they arrived. Then he adds them up in a loop. A loop over a vector of the same values took 0.23 ms. Over the set, the same loop took 164 ms in one run. Both walks are O(n). Maria asks the question this lesson answers: "But why is one O(n) walk hundreds of times slower than another?"

Checking what this lesson needs for you…

What is inside Under the Hood: The Tree's Nodes, Its Height, and Iterators That Stay

  1. A node: a colour, three links and the value
  2. The set object: a header node and a count
  3. The red-black rules, and the height they buy
  4. How ++it finds the next value
  5. Iterators that stay: an erase relinks, it never copies
  6. The performance lab: where Kenji's time went
Under the Hood: The Tree's Nodes, Its Height, and Iterators That Stay | Learn C++ STL | Progsity