Topic 8 of 27 · Advanced
Iterators & STL Algorithms
sort, binary search, accumulate, transform and iterator invalidation.
Concept
Iterators are generalised pointers that connect containers to algorithms. begin() points to the first element, end() one past the last.
<algorithm> and <numeric> provide sort, stable_sort, lower_bound, upper_bound, accumulate, transform, unique, reverse, next_permutation and more.
Modifying a container can invalidate iterators — e.g. push_back on a vector may reallocate. Use the erase-remove idiom (or std::erase_if in C++20).
Code (C++20)
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v{4, 1, 4, 9, 2, 4};
sort(v.begin(), v.end()); // 1 2 4 4 4 9
auto lo = lower_bound(v.begin(), v.end(), 4);
auto hi = upper_bound(v.begin(), v.end(), 4);
cout << "count of 4 = " << (hi - lo) << '\n'; // 3
v.erase(unique(v.begin(), v.end()), v.end()); // 1 2 4 9
int sum = accumulate(v.begin(), v.end(), 0);
erase_if(v, [](int x) { return x % 2 == 0; }); // C++20
string s = "abc";
do cout << s << ' '; while (next_permutation(s.begin(), s.end()));
}Remember
- lower_bound needs sorted data.
- unique only removes adjacent duplicates.
- Beware iterator invalidation.
Interview questions
lower_bound vs upper_bound?
lower_bound returns the first element ≥ value; upper_bound returns the first element > value.
What algorithm does std::sort use?
Introsort: quicksort switching to heapsort on deep recursion and insertion sort for small ranges — O(n log n) worst case.
Lesson test
Take an 8-question test on “Iterators & STL Algorithms” — concepts, output prediction, bug spotting and interview questions.