Standard Template Library (STL)
Iterators
Generalized pointers for traversing STL containers — the glue between containers and algorithms
Interview: Fundamental STL concept — iterator invalidation rules are a common interview trap
Iterators
Iterators are the abstraction that allows STL algorithms to work with any container. An iterator behaves like a pointer — it can be dereferenced (*it), incremented (++it), and compared (it != end()). The five iterator categories define what operations are available, allowing algorithms to be optimized based on capabilities.
Iterator Categories
| Category | Operations | Containers |
|---|---|---|
| Input | Read, ++, single-pass | istream_iterator |
| Output | Write, ++, single-pass | ostream_iterator |
| Forward | Read/write, ++, multi-pass | forward_list |
| Bidirectional | Read/write, ++, --, multi-pass | list, set, map |
| Random Access | +n, -n, [], compare | vector, deque, array |
Iterator Invalidation
Modifying a container while iterating can invalidate iterators — leading to undefined behavior. Rules: vector insertion/deletion at end doesn't invalidate other iterators (unless reallocation occurs); any vector middle insertion invalidates all iterators. list, set, map: erase invalidates only the erased element's iterator; insert doesn't invalidate any.
Interview Corner
Q: What happens if you erase an element from a vector while iterating?
A: vector::erase(it) returns the iterator to the next valid element. Don't increment the iterator after erasing: it = v.erase(it); instead of v.erase(it); ++it; (which skips the element that moved into the erased position). The erase-remove idiom is the canonical approach: v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());
Common Pitfalls
- Using invalidated iterators: Modifying a container can invalidate iterators — always use the return value of erase/insert which gives a valid next iterator.
- Using std::sort on non-random-access iterators: std::sort requires random access — doesn't compile for list. Use the container's own sort() member.
Best Practices
- Use
autofor iterator types — saves verbose typing and adapts to const-correctness automatically. - Use the erase-remove idiom for efficiently removing elements matching a condition from vectors.