Learn C++ STL

Lesson 5 of 9 · array and deque: Fixed Size, and Growing at Both Ends

Module 4 · array and deque: Fixed Size, and Growing at Both Ends

Under the Hood: deque's Blocks and Map, and What a Push Breaks

ProReading

Kenji rewrote his step tracker with a deque, "because a deque does everything a vector does". It reads a million step counts by index, a hundred times over, and it is slower than his old vector. Same code, same O(1) on paper. "So where did the time go?" Amara says the two are different machines, and this lesson opens both.

Checking what this lesson needs for you…

What is inside Under the Hood: deque's Blocks and Map, and What a Push Breaks

  1. std::array: a C array with its size in the type
  2. deque: a map of pointers to fixed blocks
  3. Where d[i] lives: the arithmetic
  4. When a block arrives and when it leaves
  5. What a push breaks: iterators, not references
  6. The performance lab
Under the Hood: deque's Blocks and Map, and What a Push Breaks | Learn C++ STL | Progsity