Iterators & Algorithms

The standard library contains more than a hundred ready-made algorithms: functions that sort, search, count, copy and transform the contents of containers. They are tested, fast and clear to read, so a professional C++ programmer reaches for an algorithm before writing a loop by hand.

Algorithms work with any container through iterators, a common way to step through elements. In this lesson you will learn what iterators are, use the classic algorithms from <algorithm> and <numeric>, and then switch to the shorter C++20 ranges versions with projections.

What is an iterator?

An iterator is an object that marks a position in a container. It behaves like a pointer:

• *it gives the element at that position, and it->member reaches a member of it.
• ++it moves to the next element.
• begin() is the position of the first element; end() is the position one past the last element, a stopping marker that must never be dereferenced.

#include <print>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> cities = {"Agra", "Bhopal", "Chennai"};

    for (auto it = cities.begin(); it != cities.end(); ++it) {
        std::println("City: {}", *it);
    }

    auto it = cities.begin();
    ++it;
    std::println("Second city: {} ({} letters)", *it, it->size());

    for (auto r = cities.rbegin(); r != cities.rend(); ++r) {   // reverse
        std::print("{} ", *r);
    }
    std::println("");
}

City: Agra
City: Bhopal
City: Chennai
Second city: Bhopal (6 letters)
Chennai Bhopal Agra

A range-based for loop uses begin() and end() behind the scenes. You write iterators by hand mainly when you need positions, for example to insert or erase. Every container provides iterators, so one algorithm can work with a vector, a deque or a set alike.

Classic algorithms with iterator pairs

Classic algorithms take a pair of iterators describing the part of the container to work on, usually v.begin(), v.end() for "all of it".

#include <algorithm>
#include <numeric>
#include <print>
#include <vector>

int main() {
    std::vector<int> sales = {1200, 450, 3100, 800, 450, 2600};

    int total = std::accumulate(sales.begin(), sales.end(), 0);
    auto big_days = std::count_if(sales.begin(), sales.end(),
                                  [](int s) { return s >= 1000; });
    int lowest = *std::min_element(sales.begin(), sales.end());

    std::sort(sales.begin(), sales.end());
    auto found = std::find(sales.begin(), sales.end(), 800);

    std::println("Total: {}, days over 1000: {}, lowest: {}", total, big_days, lowest);
    std::println("After sorting, 800 is at index {}", found - sales.begin());
    for (int s : sales) {
        std::print("{} ", s);
    }
    std::println("");
}

Total: 8600, days over 1000: 3, lowest: 450
After sorting, 800 is at index 2
450 450 800 1200 2600 3100

std::accumulate (from <numeric>) adds everything up, starting from the value you give it, here 0. std::min_element returns an iterator to the smallest item, and the * in front copies that value out before the vector is sorted. std::find returns an iterator to the first match, or end() if there is none; subtracting begin() turns a vector iterator into an index.

Ranges: algorithms without begin and end

C++20 added versions of the algorithms in the std::ranges namespace that take the whole container directly. They also accept a projection: a member or function applied to each element before comparing. This makes sorting objects by a field a one-liner.

#include <algorithm>
#include <functional>
#include <print>
#include <string>
#include <vector>

struct Student {
    std::string name;
    int marks;
};

int main() {
    std::vector<Student> students = {{"Rohan", 78}, {"Isha", 92}, {"Kabir", 65}, {"Meera", 88}};

    std::ranges::sort(students, std::ranges::greater{}, &Student::marks);
    for (const auto& s : students) {
        std::println("{:<6}{}", s.name, s.marks);
    }

    auto top = std::ranges::max(students, {}, &Student::marks);
    std::println("Topper: {}", top.name);

    auto it = std::ranges::find(students, std::string("Kabir"), &Student::name);
    if (it != students.end()) {
        std::println("Kabir is at position {}", it - students.begin() + 1);
    }
}

Isha  92
Meera 88
Rohan 78
Kabir 65
Topper: Isha
Kabir is at position 4

std::ranges::sort(students, std::ranges::greater{}, &Student::marks) reads as "sort students, largest first, comparing their marks". The {} in max means "use the default comparison". Prefer the ranges versions in new code; they are shorter and harder to misuse, because you cannot accidentally pass iterators from two different containers.

Transforming, copying and removing

#include <algorithm>
#include <iterator>
#include <print>
#include <vector>

int main() {
    std::vector<int> prices = {100, 250, 80, 400};

    std::vector<int> with_gst;
    std::ranges::transform(prices, std::back_inserter(with_gst),
                           [](int p) { return p * 118 / 100; });

    std::vector<int> costly;
    std::ranges::copy_if(prices, std::back_inserter(costly),
                         [](int p) { return p > 150; });

    std::erase_if(prices, [](int p) { return p < 100; });     // C++20

    for (int p : with_gst) { std::print("{} ", p); }
    std::println("");
    for (int p : costly) { std::print("{} ", p); }
    std::println("");
    for (int p : prices) { std::print("{} ", p); }
    std::println("");
}

118 295 94 472
250 400
100 250 400

transform writes the result of the lambda for each item. std::back_inserter is a special output iterator that calls push_back, so the destination vector grows as needed. std::erase_if removes every item that matches, directly from the container.

Searching sorted data

On sorted data, binary search finds items much faster than checking one by one: it halves the search area at each step.

#include <algorithm>
#include <print>
#include <vector>

int main() {
    std::vector<int> rolls = {3, 8, 15, 21, 34, 42};      // must be sorted

    std::println("Is 21 present? {}", std::ranges::binary_search(rolls, 21));
    auto pos = std::ranges::lower_bound(rolls, 20);         // first item >= 20
    std::println("First roll from 20 up: {} at index {}", *pos, pos - rolls.begin());
}

Is 21 present? true
First roll from 20 up: 21 at index 3

Common mistakes

• Dereferencing end(). It points past the last element. Always compare a search result with end() first.
• Using iterators after changing the container. push_back on a vector can move all elements, making every existing iterator invalid (iterator invalidation). Get fresh iterators after modifying.
• Binary search on unsorted data. The answer is meaningless; sort first.
• Writing loops for everything. A hand-written loop that counts or finds hides its purpose; count_if and find say what you mean.

Key points

• Iterators mark positions: *it reads, ++it advances, and end() is one past the last element.
• Classic algorithms take iterator pairs: std::sort(v.begin(), v.end()).
• C++20 std::ranges algorithms take whole containers and support projections such as &Student::marks.
• std::back_inserter grows a destination container; std::erase_if removes matching items.
• binary_search and lower_bound are fast on sorted data.
• Modifying a container can invalidate its iterators.

#include <algorithm>
#include <functional>
#include <numeric>
#include <print>
#include <vector>

int main() {
    std::vector<int> runs = {34, 102, 8, 56, 77, 0, 45};

    int total = std::accumulate(runs.begin(), runs.end(), 0);
    auto fifties = std::ranges::count_if(runs, [](int r) { return r >= 50; });
    int best = std::ranges::max(runs);
    std::ranges::sort(runs, std::ranges::greater{});

    std::println("Total: {}, 50+ scores: {}, best: {}", total, fifties, best);
    for (int r : runs) {
        std::print("{} ", r);
    }
    std::println("");
}

Total: 322, 50+ scores: 3, best: 102
102 77 56 45 34 8 0