Lesson 149 min read

Iterators & Algorithms

One universal remote for any container, with pre-built programs for sorting, searching, and transforming

The Universal Remote

Imagine you have a TV, a Blu-ray player, and a sound system — each from a different brand. Instead of learning three different remotes, you get a universal remote that works with all of them.

That's what iterators are in C++. Whether your data lives in a vector, a map, a set, or a list, iterators give you one consistent interface to walk through elements. And algorithms are the pre-programmed buttons on that remote — sort, search, transform, count — all ready to go.

begin() and end()

Every STL container provides two key iterators:

begin() — points to the first element
end() — points one past the last element (a sentinel, not a real element)

This half-open range [begin, end) is the foundation of every algorithm. It means: "start here, stop before here."

Iterator Categories

Not all iterators are equal. They form a hierarchy:

Input — Read forward once (e.g., reading from a stream)
Output — Write forward once
Forward — Read/write, multiple passes (e.g., forward_list)
Bidirectional — Forward + backward (e.g., list, map, set)
Random Access — Jump anywhere in O(1) (e.g., vector, deque)

Algorithms require a minimum iterator category. std::sort needs random access, so it works on vectors but not lists.

Sorting a Vector

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3};

    // Default sort: ascending
    sort(v.begin(), v.end());
    cout << "Ascending:  ";
    for (int x : v) cout << x << " ";
    cout << endl;

    // Custom sort with lambda: descending
    sort(v.begin(), v.end(), [](int a, int b) {
        return a > b;
    });
    cout << "Descending: ";
    for (int x : v) cout << x << " ";
    cout << endl;

    return 0;
}

Output

Ascending:  1 2 3 5 8 9
Descending: 9 8 5 3 2 1

find and count

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

    // Find first occurrence of 9
    auto it = find(v.begin(), v.end(), 9);
    if (it != v.end()) {
        cout << "Found 9 at index " << distance(v.begin(), it) << endl;
    }

    // Count occurrences of 5
    int c = count(v.begin(), v.end(), 5);
    cout << "5 appears " << c << " times" << endl;

    // Count even numbers with count_if
    int evens = count_if(v.begin(), v.end(), [](int x) {
        return x % 2 == 0;
    });
    cout << "Even numbers: " << evens << endl;

    return 0;
}

Output

Found 9 at index 5
5 appears 3 times
Even numbers: 3

transform — Convert to Uppercase

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string msg = "hello, algorithms!";

    // Transform each character to uppercase
    transform(msg.begin(), msg.end(), msg.begin(),
              [](char c) { return toupper(c); });

    cout << msg << endl;

    // Transform into a new string (doubling each char's ASCII)
    string doubled(msg.size(), ' ');
    transform(msg.begin(), msg.end(), doubled.begin(),
              [](char c) { return c + 1; });
    cout << doubled << endl;

    return 0;
}

Output

HELLO, ALGORITHMS!
IFMMP-!BMHPSJUINT"

accumulate — Sum and Custom Fold

#include <iostream>
#include <vector>
#include <numeric>   // accumulate lives here!
#include <string>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};

    // Sum
    int sum = accumulate(nums.begin(), nums.end(), 0);
    cout << "Sum: " << sum << endl;

    // Product (custom binary operation)
    int product = accumulate(nums.begin(), nums.end(), 1,
                             [](int a, int b) { return a * b; });
    cout << "Product: " << product << endl;

    // Concatenate strings
    vector<string> words = {"C++", " is", " powerful"};
    string sentence = accumulate(words.begin(), words.end(), string(""));
    cout << sentence << endl;

    return 0;
}

Output

Sum: 15
Product: 120
C++ is powerful

The Remove-Erase Idiom

This is one of the most important C++ patterns. std::remove does NOT actually remove elements from a container. It moves the elements you want to keep to the front and returns an iterator to the new "logical end." The container's size doesn't change! You must call erase() to actually shrink it.

Remove-Erase Idiom

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 2, 4, 2, 5};

    // WRONG: remove alone doesn't shrink the vector
    auto newEnd = remove(v.begin(), v.end(), 2);
    cout << "After remove (size still " << v.size() << "): ";
    for (int x : v) cout << x << " ";
    cout << endl;

    // RIGHT: erase from newEnd to actual end
    v.erase(newEnd, v.end());
    cout << "After erase  (size now " << v.size() << "): ";
    for (int x : v) cout << x << " ";
    cout << endl;

    // In one line (the classic idiom):
    vector<int> v2 = {10, 20, 30, 20, 40};
    v2.erase(remove(v2.begin(), v2.end(), 20), v2.end());
    cout << "One-liner: ";
    for (int x : v2) cout << x << " ";
    cout << endl;

    // C++20: much simpler!
    // std::erase(v2, 30);  // removes all 30s, shrinks vector

    return 0;
}

Output

After remove (size still 7): 1 3 4 5 4 2 5
After erase  (size now 4): 1 3 4 5
One-liner: 10 30 40

C++20 Ranges (Preview)

C++20 introduced ranges — a cleaner way to use algorithms. Instead of passing begin() and end() separately, you pass the container directly:

// Old way
std::sort(v.begin(), v.end());

// C++20 ranges
std::ranges::sort(v);

Ranges also support views — lazy, composable transformations that don't copy data. This is the future of C++ algorithms.

Note: The remove-erase idiom: std::remove doesn't actually remove elements — it moves unwanted elements to the end and returns an iterator to the new logical end. You need erase() to actually shrink the container. In C++20, use std::erase_if instead for a one-step solution.

Challenge

Quick check

Why does std::sort work on vector but not on list?

← STL Containers Templates →