Iterators
An iterator is a generalized pointer. Every container exposes begin() (first element) and end() (one past the last). The range is half-open: [begin, end) includes begin, excludes end. end() is a sentinel you never dereference.
std::vector<int> v = {10,20,30};
for (auto it = v.begin(); it != v.end(); ++it)
std::cout << *it; // dereference like a pointer
// find returns an iterator; compare to end() to test "not found"
auto it = std::find(v.begin(), v.end(), 20);
if (it != v.end()) { /* found at *it */ }Lambdas
A lambda is an anonymous function you can pass to algorithms. The [ ] is the capture list — how it grabs variables from the surrounding scope.
auto square = [](int x) { return x * x; }; // no capture
int threshold = 10;
auto big = [threshold](int x) { return x > threshold; }; // capture by value
auto add = [&threshold](int x) { threshold += x; }; // capture by referenceA lambda that captures by reference and outlives the captured variable holds a dangling reference — the same lifetime bug from Module 03, now hidden inside a callable. Capture by value when the lambda may outlive the scope (e.g. stored for later, or run on another thread).
The algorithm workhorses
#include <algorithm>
#include <numeric>
std::sort(v.begin(), v.end()); // ascending, O(n log n)
std::sort(v.begin(), v.end(), [](int a,int b){ return a>b; }); // custom order
auto it = std::find(v.begin(), v.end(), 42); // linear search
// lower_bound: first element NOT LESS than value, in a SORTED range, O(log n)
auto lb = std::lower_bound(v.begin(), v.end(), 20);
int total = std::accumulate(v.begin(), v.end(), 0); // sum, seed 0
std::transform(v.begin(), v.end(), v.begin(), // map each element
[](int x){ return x * 2; });
int n = std::count_if(v.begin(), v.end(), // count matches
[](int x){ return x > 0; });They express intent (std::sort says "sort" — a raw loop makes the reader decode it), they're battle-tested and optimized, and they eliminate off-by-one and iterator-invalidation bugs. Interviewers notice when you reach for the standard algorithm instead of reinventing it. lower_bound especially — binary search on a sorted range is exactly the kind of O(log n) thinking they want to see.
lower_bound and the order book
When an order arrives at a price not yet in the book, you insert a new price level in sorted position. A std::map does this for you, but understanding lower_bound — find the insertion point in O(log n) — is the same idea and a common interview question. It returns the first element not less than your value, which is exactly where the new one belongs.
Exercise 08.1 — Replace your loops
- Given a
vector<int>, compute the sum, the count of even numbers, and the max — each with a single standard algorithm, no raw loops. - Sort a
vector<Order>by price using a lambda comparator. - Use
lower_boundon a sorted vector to find where a new value should be inserted, then insert it and confirm the vector stays sorted. - Write a lambda that captures a local threshold by value and use it with
count_if. Then rewrite capturing by reference and reason about which is safe if the lambda were stored for later.
You've now covered memory, RAII, move semantics, and the STL. Milestone Exam II is next — closed-book across Modules 05–08. Pass it before Block III (templates, concurrency, debugging).
Takeaways
- Iterators generalize pointers; ranges are half-open
[begin, end); never dereferenceend(). - Algorithms found "not found" by returning
end(); always compare against it. - Prefer
sort,find,lower_bound,accumulate,transform,count_ifover hand loops. - Lambdas capture by value (safe to outlive scope) or by reference (fast, but watch lifetimes).
lower_boundis O(log n) binary search on a sorted range — the insertion-point idea behind the order book.
Loading starter code…
Checkpoint · Iterators & Algorithms
6 questions · pass at 70%
end() refer to?std::find signal that the value was not found?std::lower_bound return, and what does it require?std::sort?Finished Module 08?
Pass the quiz, then take Milestone Exam II.