Module 5 · list and forward_list: When Elements Move and Positions Must Not
Under the Hood: list's Nodes, the Sentinel, and What a Walk Really Costs
ProReading
Kenji moved his exam marks from a vector into a list, because a list "inserts in O(1)". Now the program that adds up a million marks is slower, and he never inserts anything in the middle. "A walk is O(n) in both. So where did the time go?" Amara says the O tells you how the cost grows, not what one step costs. This lesson opens a list node by node and measures each step.
Checking what this lesson needs for you…
What is inside Under the Hood: list's Nodes, the Sentinel, and What a Walk Really Costs
- A node: two links and a value
- The list object and its sentinel
- forward_list: one pointer and a head slot
- Why size() is O(1), and the splice that pays for it
- list::sort relinks nodes, it never copies values
- What an insert or an erase breaks: only the erased node
- The performance lab