latency.lab
Module 07

STL Containers

Level: coreTime: ~2.5 hrsPrereq: Module 06

By the end you can

The STL containers are the backbone of practical C++. Interviewers expect you to pick the right one instantly and justify it by complexity. This module is dense on purpose — it's a reference you'll come back to.

The complexity cheat sheet

containers — Big-O
vector          push_back O(1) amortized · index O(1) · insert/erase middle O(n)
deque           push front/back O(1) · index O(1) · insert middle O(n)
list            insert/erase anywhere O(1) (with iterator) · NO random access
map             ordered · insert/find/erase O(log n) · sorted iteration
unordered_map   hashed · insert/find/erase O(1) average, O(n) worst
set / multiset          ordered unique/duplicate keys, O(log n)
unordered_set           hashed unique keys, O(1) average
priority_queue          push/pop O(log n) · top O(1) · a binary heap

std::vector — your default

A dynamic array: contiguous memory, cache-friendly, O(1) random access, O(1) amortized append. Reach for it 90% of the time.

vector.cpp
std::vector<int> v;
v.reserve(100);        // pre-allocate to avoid reallocations
v.push_back(10);
v.emplace_back(20);     // constructs in place, avoids a temporary
int x = v[0];         // no bounds check
int y = v.at(0);       // bounds-checked, throws std::out_of_range
The reallocation trap

When a vector grows past its capacity, it allocates a bigger buffer and moves everything — invalidating all pointers, references, and iterators into it. If you hold a pointer to v[0] and then push_back, that pointer may dangle. This is precisely why the order book stores orders in a std::list (stable addresses) rather than a vector.

std::map vs std::unordered_map

Both associate keys with values. The difference decides your data structure:

  • map — a balanced tree. Keys stay sorted; iteration is in key order. O(log n) operations. Use when you need ordering.
  • unordered_map — a hash table. No ordering; O(1) average lookup. Use when you only need fast key lookup.
maps.cpp
std::map<int64_t, int> ordered;      // price -> qty, iterated low to high
ordered[15025] = 100;                   // insert or update
auto it = ordered.find(15025);          // end() if not present

std::unordered_map<uint64_t, Order*> by_id;  // order id -> location, O(1) lookup
This is your order book, exactly

The bid and ask sides are std::maps keyed by price — because you constantly need the best price, which is begin() of a sorted map (O(1) to read). Bids use std::greater so the highest price is first; asks use the default so the lowest is first. Meanwhile an unordered_map<order_id, ...> gives O(1) cancel-by-id. Two containers, two jobs.

std::priority_queue

A binary heap. top() is the largest element in O(1); push/pop are O(log n). Great when you only ever need the extreme element and don't need to cancel arbitrary entries — which is why it's not ideal for an order book (you must cancel by id), but perfect for things like event scheduling.

Iterator invalidation — the silent killer

invalidation.cpp
// vector: insert/erase/realloc invalidates iterators at or after the point
// (reallocation invalidates ALL of them)

// map / set: erasing an element invalidates ONLY iterators to that element;
// all others stay valid

// list: erasing invalidates only the erased element's iterator

// BUG: erasing while iterating a vector the naive way
for (auto it = v.begin(); it != v.end(); ++it)
    if (*it == target) v.erase(it);   // it is now invalid — UB on ++it

// FIX: erase returns the next valid iterator
for (auto it = v.begin(); it != v.end(); )
    it = (*it == target) ? v.erase(it) : it + 1;
Build

Exercise 07.1 — Container selection drills

  • Build a word-frequency counter with unordered_map<std::string,int>, then print the results sorted by count.
  • Store the same data in a std::map and observe it iterates in sorted key order for free.
  • Reproduce the reallocation trap: hold a pointer to v[0], push_back enough to force a regrow, and observe the pointer now dangles (use a sanitizer from Module 11 to catch it).
  • Write the safe erase-while-iterating loop for a vector and for a map. Note how they differ.

Takeaways

  • vector is the default: contiguous, cache-friendly, O(1) index and amortized append.
  • map = sorted tree, O(log n); unordered_map = hash table, O(1) average.
  • Vector reallocation invalidates all iterators/pointers; map/list erase invalidates only the erased element.
  • Best price = begin() of a sorted map; that's why the order book uses maps per side.
  • Use reserve to avoid reallocations; use emplace_back to construct in place.
Live

Loading starter code…

Live

Loading starter code…

Checkpoint · STL Containers

6 questions · pass at 70%

Q01
You need fast lookup by key and do NOT care about ordering. Which container?
Whyunordered_map is a hash table with O(1) average lookup. map is O(log n) but keeps keys sorted, which you said you don't need.
Q02
What invalidates ALL iterators/pointers into a std::vector?
WhyWhen a vector exceeds capacity it allocates a new buffer and moves elements, invalidating every existing iterator, pointer, and reference into it.
Q03
Why does the order book keep bid/ask sides in std::map rather than unordered_map?
WhyMatching always needs the best price. A sorted map gives it in O(1) at begin(). unordered_map has no ordering, so finding the best price would be O(n).
Q04
Erasing one element from a std::map invalidates:
Whymap/set are node-based; erasing invalidates only the iterator/reference to the erased node. All others remain valid — unlike vector.
Q05
What is the time complexity of top() on a std::priority_queue?
WhyA priority_queue is a binary heap: top() is O(1), while push and pop are O(log n).
Q06
Why does the order book store resting orders at a price level in a std::list?
WhyA list never relocates its nodes, so a pointer/iterator to an order stays valid as others are added or removed — essential for O(1) cancel-by-id. A vector would invalidate on reallocation.

Finished Module 07?

Pass the quiz to complete it automatically.

+ Note