Container Costs and Iterator Invalidation
The complexity table for the standard containers is the part every candidate has memorised. The language-semantics questions at the C++-first firms go one level down: which operations invalidate an iterator, a pointer or a reference, and why a structure with the better big-O loses on real hardware. Both answers come from the same place, which is where each container keeps its elements.
Where the elements live
std::vector holds its elements in one contiguous block. Iteration touches memory in order, the prefetcher predicts it, and a scan over a million doubles runs faster than any node-based structure of the same size. When the block is full, push_back allocates a larger one, moves every element across and frees the old block. The growth factor is 2 in libstdc++ and libc++ and 1.5 in MSVC, which is what makes push_back amortised .
The rest of this lesson is for subscribers
Unlock every lesson in Systems Programming for Trading, and every other premium course.
Subscribe to continueTest your knowledge
Keep reading Systems Programming for Trading
27 lessons in this course, and every other premium course, on one subscription.
- Every lesson in every course, with the worked examples and interactive simulators
- Graded questions on every lesson, with explanations for the wrong answers as well as the right one
- The trainers, timed assessments and brainteaser library that go with them