C++ STL Performance And Interview Idioms

What's being tested

Interviewers probe practical mastery of the C++ Standard Library: picking the right container/algorithm, understanding performance costs (time, memory, cache behavior), and exposing tradeoffs under real constraints. Optiver cares because low-latency, high-throughput systems require predictable resource use and micro-optimizations that change real P&L risk. Expect questions that validate you can measure, reason about, and communicate those tradeoffs clearly.

Core knowledge

• std::vector: amortized O(1) push_back, contiguous storage, cheap random access O(1), reallocation invalidates pointers/iterators; use reserve() to eliminate reallocations and control growth costs.

• std::deque: segmented contiguous blocks; constant-time push_front/push_back, non-contiguous memory so pointers may be stable across some ops but not guaranteed; index access is O(1) with slightly worse locality than vector.

• std::list / std::forward_list: node-based linked lists; constant-time splice/erase given iterator, poor cache locality; avoid for large-scale numeric data or frequent random access.

• std::map vs std::unordered_map: ordered tree O(log n) vs hash O(1) average; unordered_map pays hashing cost and cache-randomness; use reserve()/max_load_factor() to avoid rehash thrash on hot paths.

• Iterator invalidation rules: each container has precise rules — vector and string invalidate on reallocation, deque invalidates on insert/erase at ends for iterators to affected blocks, associative containers keep iterators stable except for erased elements.

• Erase-remove idiom: use v.erase(std::remove_if(...), v.end()) for predicate removals in vector; erase in the middle is O(n) because elements shift — account for that cost.

• emplace vs insert/push_back: prefer emplace_back() for in-place construction to avoid copies/moves, especially for heavy types; but measure: modern compilers optimize many cases.

• std::sort complexity: typically introsort O(n log n) average and worst-case, stable sort is std::stable_sort (O(n log n) with extra memory); avoid repeatedly sorting when incremental updates suffice.

• Move semantics and swap: std::move enables cheap transfers of resources; swapping containers is O(1) for most standard containers — use swap instead of element-wise moves when you can.

• Cache locality and profiling: contiguous containers (vector) have superior cache behavior; hash tables and linked structures scatter memory; profile with realistic workloads (perf, callgrind) rather than microbenchmarks.

Worked example — "Optimize in-place removal of duplicates from a large unsorted std::vector<T>"

Start by clarifying constraints: must preserve relative order? Is extra memory allowed? Is T hashable or only comparable? A strong candidate states assumptions and two main approaches: (1) preserve order using a hash-set scan and in-place compaction, (2) drop order and sort+unique. Skeleton: choose algorithm based on memory/time tradeoff; implement carefully to avoid unnecessary allocations. For preserve-order: create a std::unordered_set<T> with reserve(v.size()*1.3) to avoid rehashes, iterate vector writing unseen elements to write-index (index overwrite pattern), then resize(write_index). For unordered approach: sorting uses O(n log n) time, less extra memory, but destroys order. Tradeoff to flag: unordered_set uses more memory and random-memory accesses hurting cache; sort is CPU-bound but benefits from contiguous memory. Close by saying: if more time, I'd benchmark realistic input distributions, consider a robin-hood hash or parallelize with partitioned hashing, and measure allocator behavior.

A second angle — "Choose between std::vector and std::deque for a high-throughput queue"

Frame the need: do you need frequent push_front and push_back, stable pointers to elements, or contiguous memory for memcpy/SIMD? If the priority is raw throughput with mostly tail operations, std::vector with a circular-index ring buffer (manual head/tail indices and reserve) often outperforms std::deque because of better locality. If you need guaranteed cheap front insertions with unpredictable size and don't need contiguous blocks, std::deque fits. Mention iterator invalidation: vector reallocation invalidates pointers; deque can keep element references valid across some operations. Close by recommending microbenchmarks for your typical element size and access patterns.

Common pitfalls

Pitfall: assuming erase from the middle of a std::vector is cheap — it’s O(n) due to element shifting; for repeated deletions prefer compaction or a different data structure.

Pitfall: using std::unordered_map without reserve() and expecting stable performance — growing and rehashing will spike latency; pre-reserve based on expected cardinality.

Pitfall: optimizing micro-level operations without profiling — changing from vector to deque or swapping algorithms can worsen overall throughput because of cache effects; always validate with representative workloads.

Connections

Interviewers may pivot to concurrency (thread-safety of containers, lock-free structures) or custom allocators (pooling to reduce allocation overhead). They might also connect to profiling/benchmarking practices and memory-leak/UB diagnostics.

Further reading

• [Effective Modern C++ — Scott Meyers] — guidance on move semantics, emplace, and modern idioms.

• [C++ Standard Library: A Tutorial and Reference — Nicolai Josuttis] — deep reference for container guarantees and complexity.

• cppreference.com — authoritative, up-to-date reference for iterator invalidation and function semantics.