← C++ roadmap

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.

Practise C++ with the AI mentor

Lesson test

Take an 8-question test on “Iterators & STL Algorithms” — concepts, output prediction, bug spotting and interview questions.

Can't find a C++ topic you need for exams or placements? Request it and we'll add it.